图论分析

科学计算中的各种问题都可以被表述为图问题（关于图论的介绍见附录18）；例如，我们已经遇到了负载平衡（第2.10.4节）和寻找独立集（第6.8.2节）的问题。

许多传统的图算法不能立即适用，或者至少不能有效地适用，因为图往往是分布式的，而传统的图理论假设了对整个图的全局知识。此外，图论通常关注的是寻找最佳算法，而这通常不是一种并行的算法。因此，并行图算法本身就是一个研究领域。

最近，在科学计算中出现了新的图计算类型。这里的图不再是工具，而是研究对象本身。例如，万维网或Facebook的社交图，或一个生物体内所有可能的蛋白质相互作用的图。

由于这个原因，组合计算科学正在成为一门独立的学科。在这一节中，我们看一下图分析：大型图的计算。我们首先讨论一些经典的算法，但我们在代数框架中给出这些算法，这将使并行实现更加容易。

传统图算法

我们首先看一下几个 “经典 “的图算法，并讨论如何以并行方式实现它们。图和稀疏矩阵之间的联系（见附录18）在这里至关重要：许多图算法具有稀疏矩阵-向量乘法的结构。

最短路径算法

有几种类型的最短路径算法。例如，在单源最短路径算法中，人们想知道从一个给定节点到任何其他节点的最短路径。在全对最短路径算法中，人们想知道任何两个节点之间的距离。计算实际路径不是这些算法的一部分；但是，通常很容易包括一些信息，通过这些信息可以在以后重建路径。

我们从一个简单的算法开始：寻找非加权图中的单源最短路径。用广度优先搜索（BFS）来做这件事很简单。

  1. Input : A graph, and a starting node 𝑠
  2. Output: A function 𝑑(𝑣) that measures the distance from 𝑠 to 𝑣 
  3. Let 𝑠 be given, and set 𝑑(𝑠) = 0
  4. Initialize the finished set as 𝑈 = {𝑠}
  5. Set 𝑐 = 1
  6. while not finished do
  7.   Let 𝑉 the neighbours of 𝑈 that are not themselves in 𝑈 
  8.   if 𝑉 =∅ then
  9.     We’re done
  10.    else
  11.      Set 𝑑(𝑣)=𝑐+1 for all 𝑣 ∈𝑉. 𝑈←𝑈∪𝑉
  12.      Increase 𝑐 ← 𝑐 + 1

这种制定算法的方式在理论上是很有用的：通常可以制定一个谓词，在while循环的每一次迭代中都是真的。这样，你就可以证明该算法终止了，并且它计算了你想要计算的东西。在传统的处理器上，这的确是你对图算法的编程方式。然而，现在的图，如来自Facebook的图，可能是巨大的，而你想对你的图算法进行并行编程。

在这种情况下，传统的表述方式就显得不够了。

  • 它们通常基于队列，节点被添加或减去；这意味着存在某种形式的共享内存。

  • 关于节点和邻居的声明是在不知道这些是否满足任何形式的空间定位的情况下做出的；如果一个节点被触及一次以上，就不能保证时间上的定位。

Floyd-Warshall最短路径

Floyd-Warshall算法是一个全对最短路径算法的例子。它是一种动态编程算法，是基于逐步增加路径的中间节点集。具体来说，在步骤𝑘中，所有的路径$u\rightarrow v$都被考虑，它们的中间节点在集合 $k={0, …. \Delta k(u,v)}$被定义为从$u$到$v$的路径长度，其中所有中间节点都在$k$。最初，这意味着只考虑图边，当$k \equiv |V|$时，我们已经考虑了所有可能的路径，算法完成。

计算的步骤是 $$ \Delta{k+1}(u, v)=\min \left{\Delta{k}(u, v), \Delta{k}(u, k)+\Delta{k}(k, v)\right} $$ 也就是说，对距离$\Delta (u, v)$的第 $k$个估计值是旧的估计值和一条新的路径的最小值，现在我们正在考虑节点$k$的可行性。这条路径是由$u \rightarrow k$和$k \rightarrow v$两条路径连接而成的。

用算法来写:

  1. for 𝑘 from zero to |𝑉| do 
  2.   for all nodes 𝑢, 𝑣 do
  3.     Δ𝑢𝑣 ← 𝑓(Δ𝑢𝑣,Δ𝑢𝑘,Δ𝑘𝑣)

我们看到这个算法的结构与高斯消除法相似，只是在那里，内循环是 “对于所有的$u，v>k$”。

在第5.4.3节中，你看到稀疏矩阵的因式分解会导致填充，所以这里也会出现同样的问题。这需要灵活的数据结构，而且这个问题在并行时变得更加严重，见第9.5节。

代数上。

  1. for 𝑘 from zero to |𝑉| do
  2.   𝐷 ← 𝐷.min[𝐷(∶, 𝑘) min ⋅+ 𝐷(𝑘, ∶)]

Floyd-Warshall算法并不告诉你实际的路径。在上面的距离计算过程中，存储这些路径的成本很高，无论是时间还是内存。一个更简单的解决方案是可能的：我们存储第二个矩阵𝑛(𝑖, 𝑗)，它有𝑖和𝑗之间路径的最高节点号。

练习 9.1 将$n(i, j)$的计算包含在 Floyd-Warshall 算法中，并描述在已知$d(⋅, ⋅)$和$n(⋅, ⋅)$的情况下，如何利用它来寻找$i$ 和$j$之间的最短路径。

生成树

在一个无向图$G=⟨V,E⟩$中，如果$T\subset E$是连接和无环的，我们称之为 “树”。如果它的边包含所有的顶点，则被称为生成树。如果图的边权重为$wi ∶i\in E$，则树的权重为$\sum{e\in T}w_e$，如果树的权重最小，我们称它是最小生成树。一个最小生成树不需要是唯一的。

Prim算法是Dijkstra最短路径算法的一个小变种，它从一个根开始计算生成树。根的路径长度为零，而所有其他节点的路径长度为无穷大。在每一步中，所有与已知树节点相连的节点都会被考虑，并更新它们的最佳已知路径长度。

  1. for all vertices 𝑣 do l(𝑣) ← ∞
  2. l(𝑠) ← 0
  3. 𝑄 ← 𝑉 − {𝑠} and 𝑇 ← {𝑠} while𝑄 ≠∅do
  4. let 𝑢 be the element in 𝑄 with minimal l(𝑢) value remove 𝑢 from 𝑄, and add it to 𝑇
  5. for𝑣 ∈𝑄with(𝑢,𝑣)∈𝐸do
  6. if l(𝑢) + 𝑤𝑢𝑣 < l(𝑣) then Set l(𝑣) ← l(𝑢) + 𝑤𝑢𝑣

定理3 上述算法计算出每个节点到根节点的最短距离。

dijkstra-proof

证明：本算法正确性的关键在于我们选择$u$为最小$l(u)$值。把到顶点的真正最短路径长度称为$L（v）$。由于我们从一个无限大的$l$值开始，并且只减少它，我们总是有$L(v)\leqslant l(v)$。

我们的归纳假设是，在算法的任何阶段，对于当前租用的$T$中的节点，路径长度的确定是正确的。 $$ u\in T \Rightarrow L(u)=\ell(u) $$ 当树只由根$s$组成时，这显然成立。现在我们需要证明归纳步骤：如果对于当前树中的所有节点，路径长度都是正确的，那么我们也将得到$L(u)=l(u)$。假设这不是真的，有另一条路径更短。这条路径需要经过目前不在$T$中的某个节点$y$；这在图9.1中得到说明。假设$x$是$T$中的节点，位于$y$之前的据称最短路径。现在我们有$l(u)>L(u)$，因为我们还没有正确的路径长度，并且$L(u)>L(x)+w$，因为在$y$和$u$之间至少有一条边（有正权）。 但$x\in T$，所以$L(x)=l(x)$，$L(x)+y=l(x)+y$。现在我们注意到，当$x$被添加到$T$时，它的邻居被更新，所以$l(y)$是$lx+y$或更少。将这些不等式，我们发现 $$ \ell(y)<\ell(x)+w{xy}=L(x)+w{xy}<L(u)<\ell(u) $$ 这与我们选择$u$为最小$l$值的事实相矛盾。

为了并行化这个算法，我们观察到内循环是独立的，因此可以并行化。然而，外循环有一个选择，即最小化一个函数值。计算这个选择是一个减法运算，随后它需要被广播。这种策略使得顺序时间等于$d \log P$，其中$d$是生成树的深度。

在单个处理器上，寻找数组中的最小值是一个$O(N)$的操作，但通过使用优先级队列，这可以减少到$O(\log N)$。对于生成树算法的并行版本，相应的项是$O(\log(N/P))$，还不包括减少的$O(\log P)$成本。

Graph cut

有时，你可能想对一个图进行分区，例如出于并行处理的目的。如果这是通过划分顶点来实现的，那么你就是在切割边，这就是为什么这被称为顶点切割分区。对于什么是好的顶点切割，有各种标准。例如，你希望切割的部分大小大致相等，以平衡平行工作。由于顶点通常对应于通信，你希望顶点的数量（或在加权图中它们的权重之和）要小。图Laplacian（第18.6.1节）是这方面的一个流行算法。

图的切割的另一个例子是二方图的情况：一个有两类节点的图，而且只有从一类到另一类的边。例如，这样的图可以模拟一个人口和一组属性：边表示一个人有某种兴趣。现在你可以做一个边的切割，将边的集合进行分割。这可以给你一些具有类似兴趣的人的集合。这个问题很有意思，比如说，用于定位在线广告。

并行化

许多图的算法，如第9.1节中的算法，并不容易并行化。这里有一些考虑。

首先，与许多其他算法不同，很难针对最外层的循环层，因为这通常是一个 “while “循环，使得并行停止测试成为必要。另一方面，通常有一些宏观步骤是连续的，但其中的一些变量是独立考虑的。因此，确实存在着可以利用的并行性。

图算法中的独立工作是一种有趣的结构。虽然我们可以确定 “for all “循环，它是并行化的候选者，但这些循环与我们以前看到的不同。

  • 传统的公式往往具有逐步建立和删除的变量集的特征。这可以通过使用共享数据结构和任务队列来实现，但这限制了某种形式的共享内存的实现。
  • 接下来，虽然每个迭代操作都是独立的，但其运行的动力学原理意味着将数据元素分配给处理器是很棘手的。固定分配可能会导致很多空闲时间，但动态分配会带来很大的开销。
  • 在动态任务分配的情况下，算法将几乎没有空间或时间上的定位。

由于这些原因，线性代数的表述可能是比较好的。一旦考虑到分布式内存，我们肯定需要这种方法，但即使在多核架构上，它也能为鼓励局部性而付出代价。

在第6.5节中，我们讨论了稀疏矩阵-向量乘积的并行评估问题。由于稀疏性，只有按块行或块列进行划分才有意义。实际上，我们让分区由问题变量之一来决定。这也是唯一对单源最短路径算法有意义的策略。

练习 9.2 你能为将并行化建立在向量的分布上做一个先验的论证吗？这个操作涉及多少数据，多少工作，多少个顺序步骤？

策略

下面是三种图算法的并行化方法，按明显程度递减，按可扩展性递增。(另见[118]）。

动态规划

许多图算法建立了一个要处理的顶点的数据结构$V$；他们执行一个包含循环的超步序列

  1. for all v in V:
  2.      // do something with v

如果对一个顶点$v$的处理不影响$V$本身，那么这个循环是并行的，可以通过动态调度来执行。

这实际上是将数据动态分配给处理元素。在这个意义上，它是高效的，没有任何处理元素会与不需要处理的数据元素发生冲突，因此计算机的所有处理能力都得到了充分的利用。另一方面，动态分配带有操作系统的开销，而且会导致大量的数据传输，因为顶点不可能在处理元素的本地内存（如缓存）中。

另一个问题是，这个循环可能看起来像。

  1.  for all v in V:
  2.      for all neighbours u of v:
  3.        // update something on u

现在可能发生的情况是，两个节点$v_1$和$v_2$都在更新一个共享的邻居$u$，这个冲突需要通过缓存一致性来解决。这带来了延迟上的损失，甚至可能需要使用锁，这带来了操作系统上的损失。

线性代数解释

现在我们将表明，图算法通常可以被视为稀疏矩阵算法，这意味着我们可以应用我们为这些算法开发的所有概念和分析。

如果$G$是图的邻接矩阵，我们也可以将最短路径算法类似于一系列矩阵-向量乘法（见附录18.5.4节）。让$x$是列出与源的距离的向量，也就是说，$xi$是节点$i$与源的距离。对于$i$的任何邻居$j$，到源的距离是$x_i + G{ij}$，除非已经知道更短的距离。换句话说，我们可以定义 $$ y^t = x^tG\equiv \foralli: y_j\min{x_j,\min{i:G_{ij\neq 0}}{x_i+1}} $$ 而上述while循环的迭代对应于此定义下的后续矩阵-向量积。

这种算法之所以有效，是因为我们可以在第一次访问时将$d(v)$设置为其最终值：这恰恰发生在等于路径长度的外循环次数之后。内循环执行的总次数等于图中边的数量。加权图就比较麻烦了，因为一个有更多阶段的路径实际上可以用阶段的权重之和来衡量更短。下面是贝尔曼-福特算法。

  1. Let 𝑠 be given, and set 𝑑(𝑠) = 0 Set 𝑑(𝑣) = ∞ for all other nodes 𝑣 for |𝐸| − 1 times do
  2. for all edges 𝑒 = (𝑢,𝑣) do
  3. Relax: if 𝑑(𝑢) + 𝑤𝑢𝑣 < 𝑑(𝑣) then
  4. Set 𝑑(𝑣) ← 𝑑(𝑢) + 𝑤𝑢𝑣

这个算法是正确的，因为对于一个给定的节点$u$，在外迭代的$k$步之后，它已经考虑了所有路径$s\rightarrow u$的$k$阶段。

练习 9.3 这个算法的复杂度是多少？如果你对图形有一定的了解，外循环的长度是否可以减少？

我们可以再次将其写成一系列的矩阵-向量积，如果我们将积定义为 $$ y^t = x^tG\equiv \foralli: y_j\min{x_j,\min{i:G{ij\neq 0}}{x_i+g{ij}}} $$ 这与上述基础基本相同：到𝑗的最小距离是已经确定的距离的最小值，或者到任何节点𝑖的最小距离加上过渡$g_{ij}$。

全对算法的并行化

在上面的单源最短路径算法中，我们没有太多选择，只能通过分布向量而不是矩阵来实现并行化。这种类型的分布在这里也是可能的，它对应于$𝐷(⋅, ⋅)$量的一维分布。

练习 9.4 画出该算法变体的并行实现。证明每个$k$次迭代都涉及到以处理器$k$为根的广播。

然而，这种方法遇到了与使用一维矩阵分布的矩阵-向量乘积相同的缩放问题；见6.2.2节。因此，我们需要使用二维分布。

练习 9.5 做缩放分析。在内存不变的弱缩放情况下，渐近效率是多少？

练习 9.6 使用二维分布的$𝐷(⋅, ⋅)$量勾画Floyd-Warshall算法。

练习 9.7 并行的Floyd-Warshall算法对零点进行了相当多的操作，当然是在早期阶段。你能设计一种算法来避免这些操作吗？

分割

传统的图划分算法[146]并不是简单的可并行化。相反，有两种可能的方法。

  • 使用图Laplacian；第18.6.1节。
    • 使用多层次的方法。 1 分割图的粗化版本。 2 逐步解除图的粗化，调整分区。

现实世界 “图

在诸如第4.2.3节的讨论中，你已经看到了PDEs的离散化是如何导致具有图的方面的计算问题的。这种图的特性使它们适合于某些类型的问题。例如，使用FDMs或FEMs对二维或三维物体进行建模，会导致每个节点只与几个邻居相连的图形。这使得它很容易找到分离器，这反过来又允许像嵌套剖分这样的解决方法；见6.8.1节。

然而，有一些应用的计算密集型图问题看起来并不像FEM图。我们将简要地看一下全球网络的例子，以及像谷歌的PageRank这样试图寻找权威节点的算法。

现在，我们将称这种图为随机图，尽管这个术语也有技术含义[61]。

随机图的性质

我们在本课程的大部分内容中看到的图形，其属性源于它们是我们三维世界中物体的模型。因此，两个节点之间的典型距离通常是$O(N^{1/3})$，其中$N$是节点的数量。随机图的表现并非如此：它们通常具有小世界的特性，典型的距离是$O(\log N )$。一个著名的例子是电影演员和他们在同一电影中出现的联系图：根据 “六度分隔”，在这个图中没有两个演员的距离超过六。在图形方面，这意味着图形的直径是六。

小世界图还具有其他特性，例如存在小团体（尽管这些特性在高阶有限元问题中也有）和枢纽：高度的节点。这导致了如下的影响：在这样的图中删除一个随机的节点不会对最短路径产生很大的影响。

练习 9.8 考虑机场图和它们之间存在的航线。如果只有枢纽和非枢纽，论证删除一个非枢纽对其他机场之间的最短路径没有影响。另一方面，考虑到节点在二维网格中的排序，并删除一个任意的节点。有多少条最短路径会受到影响？

超文本算法

有几种基于线性代数的算法用于衡量网站的重要性[139]。我们将简要地定义几个算法并讨论其计算意义。

HITS

在HITS（Hypertext-Induced Text Search）算法中，网站有一个衡量它指向多少其他网站的枢纽得分，以及一个衡量有多少网站指向它的权威得分。为了计算这些分数，我们定义了一个发生率矩阵$L$，其中 $$ L_{i j}=\left{\begin{array}{ll} 1 & \text { document } i \text { points to document } j \ 0 & \text { otherwise } \end{array}\right. $$ 权威分数$x$被定义为所有指向$i$的中心分数$y_j$的总和，反之亦然。因此 $$ x=L^ty\ y=Lx $$ 或$x=LL^tx$，$y=L^tLy$，表明这是一个特征值问题。我们需要的特征向量只有非负项；这被称为非负矩阵的Perron向量，见附录13.4。佩伦向量是通过幂方法计算的；见13.3节。

一个实用的搜索策略是。

  • 找到所有包含搜索词的文档。
  • 建立这些文档的子图，以及可能的与之相关的一到两层的文档。
  • 计算这些文档的权威性和枢纽得分，并将其作为一个有序的列表呈现给用户。

PageRank

PageRank[166]的基本思想与HITS相似：它的模型是 “如果用户不断点击页面上某种程度上最理想的链接，那么总体上最理想的链接集合是什么”。这是通过定义一个网页的排名是所有连接到它的网页的排名之和来建模的。该算法 它通常是以迭代的方式表述。

  1. while Not converged do for all pages 𝑖 do
  2. rank𝑖 ← 𝜖 + (1 − 𝜖) ∑𝑗 ∶ connected𝑗→𝑖 rank𝑗

其中的排名是这个算法的固定点。$\varepsilon$项解决了这样一个问题：如果一个页面没有出站链接，那么一个会在那里停留的用户就不会离开。

练习 9.9 论证这个算法可以用两种不同的方式来解释，大体上响应雅可比和高斯-赛德尔迭代法；5.5.3节。

练习 9.10 在PageRank算法中，每个页面都给它所连接的页面 “提供排名”。给出这个变体的伪代码。说明它对应于一个列的矩阵向量乘积，而不是上述表述的行。在共享内存并行中实现这个方法会有什么问题？

对于这个方法的分析，包括它是否收敛的问题，最好是完全用线性代数的术语来表述。我们再次定义一个连接矩阵 $$ M_{i j}=\left{\begin{array}{ll} 1 & \text { if page } j \text { links to } i \ 0 & \text { otherwise } \end{array}\right. $$ $e=(1,…,1)$，向量$d^t=e^tM$计算一个页面上有多少个链接。$d_i$是页面$i$上的链接数量。我们构建一个对角矩阵$D = diag(d_1, …)$ 我们将$M$归一为$T= MD^{-1}$。

现在$T$的列和（即任何一列的元素之和）都是1，我们可以表示为$e^t T = e^t$ 其中$e^t =（1，…，1）$。这样的矩阵被称为随机矩阵。它有如下解释。

如果$p$是一个概率向量，即$p_i$是用户正在查看页面$i$的概率，那么$T_p$是用户点击了一个随机链接后的概率向量。

练习 9.11 从数学上讲，概率向量的特点是其元素之和为1。说明随机矩阵与概率向量的乘积确实又是一个概率向量。

上面制定的PageRank算法对应于取一个任意的随机向量$p$，计算权力法$T_p，T^2_p，T^3_p，…，$并看这个序列是否收敛到什么。

这个基本算法有一些问题，例如没有外向链接的网页。一般来说，在数学上我们是在处理 “不变子空间”。例如，考虑一个只有2个页面的网络，并有以下邻接矩阵。 $$ A=\left(\begin{array}{ll} 1 / 2 & 0 \ 1 / 2 & 1 \end{array}\right) $$ 自己检查一下，这对应于第二页没有外链的情况。现在让$p$成为起始向量$p_t = (1, 1)$，并计算几个迭代的功率法。你是否看到，用户在第二页的概率上升到了1？这里的问题是，我们正在处理一个可还原矩阵。

为了防止这个问题，PageRank引入了另一个元素：有时候，用户会因为点击而感到无聊，会去一个任意的页面（对于没有出站链接的页面也有规定）。如果我们把𝑠称为用户点击一个链接的机会，那么进入一个任意页面的机会就是1-𝑠。一起来看，我们现在有这样一个过程 $$ p^{\prime} \leftarrow s T p+(1-s) e $$ 也就是说，如果$p$是一个概率向量，那么$p’$就是一个概率向量，它描述了用户在进行了一次页面转换（无论是通过点击一个链接还是通过 “传送”）之后的位置。

PageRank向量是这个过程的静止点；你可以把它看作是用户进行了无限次转换之后的概率分布。PageRank向量满足以下条件 $$ p=s T p+(1-s) e \Leftrightarrow(I-s T) p=(1-s) e $$ 因此，我们现在不得不想，$I-sT$是否有一个逆。如果逆的存在，它满足 $$ (I-sT)^{-1}= I + sT +s^2T^2+… $$ 不难看出逆的存在：利用格什哥林定理（附录13.5），你可以看到$T$的特征值满足$|\lambda| \leqslant 1$。现在利用$𝑠<1$，所以部分和的序列收敛。

上述逆的公式也指出了一种通过使用一系列矩阵-向量乘法来计算PageRank向量$p$的方法。

练习 9.12 写出计算PageRank向量的伪代码，给定矩阵$T$。证明你从来不需要明确计算$T$的幂。(这是霍纳规则的一个实例）。

在$𝑠=1$的情况下，也就是说，我们排除了远程传输，PageRank向量满足$p=Tp$，这又是寻找Perron向量的问题；见附录13.4。

我们通过幂级迭代找到佩伦向量（第13.3节）。 $$ p^{(i+1)}=Tp^{(i)} $$ 这是一个稀疏的矩阵向量乘积，但与BVP的情况不同，稀疏性不太可能有带状结构。在计算上，人们可能必须使用与密集矩阵相同的并行论据：矩阵必须是二维分布的[162]。

大型计算图论

在前面的章节中，你已经看到许多图算法有一个计算结构，使矩阵-向量积成为它们最重要的内核。由于大多数图相对于节点数来说是低度的，所以该乘积是一个稀疏的矩阵-向量乘积。

然后在很多情况下，我们可以像第6.5节那样，对矩阵进行一维分布，由图节点的分布诱导：如果一个处理器拥有一个图节点$i$，它就拥有所有的边$i$，$j$。

然而，往往计算是非常不平衡的。例如，在单源最短路径算法中，只有沿着前面的顶点是活跃的。由于这个原因，有时边的分布而不是顶点的分布是有意义的。为了平衡负载，甚至可以使用随机分布。

Floyd-Warshall算法的并行化（第9.1.2节）沿着不同的路线进行。在这里，我们不计算每个节点的数量，而是计算作为节点对的函数的数量，也就是一个类似矩阵的数量。因此，我们不是分配节点，而是分配节点对的距离。

节点与边的分布

有时我们在处理稀疏图矩阵时需要超越一维分解。我们假设我们要处理的图的结构或多或少是随机的，比如说，对于任何一对顶点来说，有一条边的机会是相同的。另外，假设我们有大量的顶点和边缘，那么每个处理器都会存储一定数量的顶点。那么结论是，任何一对处理器需要交换信息的机会都是一样的，所以信息的数量是$O(P)$。(另一种可视化的方法是看到非零点随机地分布在矩阵中)。这并不能提供一个可扩展的算法。

出路是把这个稀疏矩阵当作密集矩阵，并援引第6.2.2节的论据来决定矩阵的二维分布。(参见[207]中对BFS问题的应用；他们以图的形式制定了他们的算法，但是二维矩阵-向量乘积的结构是清晰可辨的）。二维乘积算法只需要处理器行和列的集合体，所以涉及的处理器数量为$O(\sqrt{P})$。

超稀疏数据结构

在稀疏矩阵的二维分布下，可以想象一些过程会出现行数为空的矩阵。从形式上看，如果非零的数量（渐进地）小于维度，那么一个矩阵被称为超稀疏。

在这种情况下，CRS格式可能是低效的，可以使用称为双压缩存储的东西[24]。