计算复杂性

稀疏操作的计算复杂度成正比NNZ在矩阵的非零元素的数目。计算复杂度也线性依赖于行大小米和列的大小n基质的，但独立于产品的m * n个，即零元素和非零元素的总数。

相当复杂的操作(如稀疏线性方程的解)的复杂性涉及排序和填充等因素，这些因素在前一节中已经讨论过。然而，一般来说，稀疏矩阵运算所需的计算机时间与非零数量上的算术运算的数量成正比。

算法细节

稀疏矩阵通过计算根据这些规则传播：

重新排序为稀疏

重新排序矩阵的列往往能使其LU或QR因素稀疏。重新排序行和列往往使其乔莱斯基因素稀疏。最简单的这种重新排序是非零计数的列进行排序。有时，这是一个很好的重新排序非常不规则的结构矩阵，尤其是如果有行或列中的非零计数差异很大。

的colperm计算的置换，通过非零元素的每列中的数订单矩阵的列从最小到最大。

重新排列，以减少带宽

反向Cuthill-麦基排序旨在减少基体的轮廓或带宽。它不能保证找到尽可能小的带宽，但它通常不会。的symrcm函数实际上作用于对称矩阵的非零结构+“，但结果也是非对称矩阵是有用的。这个排序是针对来自一维的问题或问题，在某种意义上矩阵有用瘦长。

近似最小次数排序

在图中的节点的度是该节点的连接数。这是相同的邻接矩阵的对应的行中的非对角的非零元素的数目。近似最小度算法生成基于这些学位是如何高斯消元法或Cholesky分解过程中改变的顺序。这是一个复杂而强大的算法通常导致稀疏的因素比其他大多数排序，包括列数和反向Cuthill - 麦基。因为保持每个节点的度的轨道是非常耗时的，近似最小度算法使用的近似的程度，而不是精确度。

这些MATLAB^®函数实现近似最小度算法:

看到重新排序和分解以下是示例symamd。

您可以更改与使用的算法细节有关的各种参数spparms函数。

有关所使用的算法细节colamd和symamd,请参阅[5]。近似度算法使用基于[1]。

嵌套的解剖点

像近似最小度排序，嵌套解剖排序算法实现由解剖函数将矩阵考虑为图的邻接矩阵，从而对矩阵的行和列进行重新排序。该算法通过将图中的顶点对折叠在一起，将问题减少到一个小得多的规模。在对小图重新排序后，该算法应用投影和细化步骤将图扩展回原始大小。

相对于其他重排序技术的嵌套解剖算法产生高质量重排序和执行特别好地利用有限元矩阵。有关嵌套解剖排序算法的详细信息，请参阅[7]。

LU分解

如果年代是稀疏矩阵，下面的命令返回三个稀疏矩阵l,U和P这样P * S = L * U。

陆(L U P) = (S)

鲁获得由高斯消去具有部分枢转的因素。置换矩阵P只有n非零元素。和密集矩阵一样，这个表述[L，U] = LU（S）返回一个置换单元下三角矩阵和上三角矩阵，其产物是年代。就其本身而言,陆(S)返回l和U在不枢转信息的单个矩阵。

三输出语法

陆(L U P) = (S)

选择P通过数值偏枢转，但不枢转，以改善在稀疏鲁因素。在另一方面，四输出语法

[L，U，P，Q] = LU（S）

选择P通过阈值部分旋转，并进行选择P和问以改善稀疏鲁因素。

您可以使用控制稀疏矩阵旋转

鲁（S，THRESH）

哪里打在[0,1]的枢轴阈值。旋转时，在一列对角线条目幅度小于发生打乘以这一列中任意亚对角分量的大小。打= 0强制对角线旋转。打= 1是默认的。（默认为打是0.1对于四输出语法)。

当你打电话鲁有三个或更少的输出，MATLAB自动分配存储稀疏所需的内存l和U因子分解过程中的因子。除了四输出语法外，MATLAB不使用任何符号LU预分解来预先确定内存需求和建立数据结构。

重新排序和分解。这个例子显示了重排序和分解在稀疏矩阵的效果。

如果你得到一个好的列置换p从降低填空题，也许symrcm要么colamd,然后计算鲁（S（：，P））比计算节省时间和存储空间陆(S)。

创建使用巴基球例的稀疏矩阵。

B =巴基;

B具有每行和列中恰好三个非零元素。

创建两个排列，r和米运用symrcm和symamd分别。

R = symrcm（B）;M = symamd（B）;

两个排列是对称的反向Cuthill-麦基排序和对称近似最小的有序度。

创建间谍阴谋显示巴克球图的三个邻接矩阵与这三个不同的numberings。原编号的地方，基于五边形结构是不是在别人明显。

图副区（1,3,1）间谍（B）标题（'原版的'）副区（1,3,2）间谍（B（R，R））标题（“反向Cuthill  - 麦基)(1、3、3)间谍(B(m,m))最小程度的)

反向Cuthill - 麦基订购，r，减少了带宽并集中所有的对角附近的非零元素。近似最小度排序，米，生成具有大量零块的分形结构。

若要查看在巴基球的LU因数分解中生成的填充，请使用speye的稀疏单位矩阵，在的对角上插入-3B。

B = B - 3*speye(size(B));

因为每个行和现在都是零，这个新的B实际上是单数，但它仍然是有益的计算它的LU分解。当只有一个输出参数调用，鲁返回两个三角形的因素，l和U在单个稀疏矩阵。在该矩阵的非零元素的数目是的时间和存储的量度所需的求解线性系统涉及B。

这里有三个排列的非零计数正在考虑中。

尽管这是一个小示例，但其结果是典型的。原始的编号方案导致最多的填充。填补反向cuthil - mckee命令是集中在乐队，但它几乎是广泛的作为前两个命令。对于近似最小度排序，在消去过程中保留了较大的零块，填充量明显小于其他排序产生的填充量。

的间谍下面曲线反映每个重排序的特性。

图副图(1,3,1)特务(lu(B))'原版的')次要情节(1,3,2)间谍(陆(B(r,r))))“反向Cuthill  - 麦基(1、3、3)间谍(陆(B(m,m)))最小程度的)

Cholesky分解

如果年代是对称（或厄米），正定，稀疏矩阵，下面返回语句稀疏，上三角矩阵R以便R'* R = S。

R =胆固醇(S)

CHOL不会自动旋转为稀疏，但你可以计算近似的最小度和轮廓限制排列与使用胆固醇(S (p, p))。

由于乔列斯基算法不使用用于稀疏枢转，并且不需要用于枢转数值稳定性，CHOL确实需要的内存量的快速计算和分配所有存储在分解的开始。您可以使用symbfact，它使用算法相同CHOL，以计算分配了多少内存。

QR分解

MATLAB计算稀疏矩阵的完整QR分解年代同

(Q, R) = qr (S)

[Q, R E] = qr (S)

但这往往是不切实际的。酉矩阵问经常不能有高比例的零元素。还有一种更实用的方法，有时被称为“Q-less QR分解法”。

有一个稀疏输入参数和一个输出参数

R = QR（S）

返回刚刚QR分解的上三角部分。矩阵R提供了与正规方程相关的矩阵的Cholesky分解:

‘* R = S *

然而，数字信息的损失的计算固有S'* S是可以避免的。

与具有相同的行数的两个输入参数和两个输出参数，语句

[C R] = qr(年代,B)

应用正交变换来B、生产C = Q'* B没有计算问。

Q-less QR分解允许解决稀疏最小二乘问题

有两个步骤

并[c，R] = QR（A，B）X = R \ C

如果一个稀疏，但不是正方形，MATLAB使用这些步骤，线性方程组求解反斜线操作：

X = A \ B

或者，你们可以自己做因数分解并检验一下R为等级不足。

另外，也可以解决最小二乘线性序列具有不同右手侧系统，b，但不一定是在什么时候R = QR（A）计算。该方法解决了“半正规方程”

R '* R * X = A' * B

同

x = R \ (R \(“* b))

然后采用迭代细化的一步来减少舍入误差:

[R = B  -  A * X E = r \（R '\（A' * R））X = X + E

不完全因子分解

的ilu和ichol函数提供近似,残缺因式分解，这是因为预条件稀疏迭代方法是有用的。

的ilu功能生成三个不完整的下 - 上（ILU）因式分解：所述填零ILU(ILU (0))、ILU (管器（头）)，以及阈值下降和旋转的ILU (ILUTP（TAU））。的ILU (0)从未枢转并且将得到的因子只有在位置在输入矩阵有非零元素的非零元素。都管器（头）和ILUTP（TAU）然而，还有基于阈值的下落与用户定义落忍τ。

例如：

A = gallery('neumann'， 1600) + speye(1600);nnz(lu(A)) ans = 126478

显示，一个有7840个非零，它的LU分解有126478个非零。另一方面，下面的代码显示了不同的ILU输出:

[L U] = ilu(一个);nnz (L) + nnz (U)造(,1);ans = 7840规范(A - (L * U)。* spones (A),“来回”)。/规范(A,“来回”)ans = 4.8874 e - 017选择。类型=“ilutp”;opts.droptol = 1E-4;[L,U,P] = ilu(A, opts);nnz (L) + nnz (U)造(A, 1) ans = 31147常模(P * A - L * U,“来回”)。/规范(A,“来回”)ans = 9.9224 e - 005选择。类型=“克劳特”;nnz (L) + nnz (U)造(A, 1) ans = 31083常模(P * L * U,“来回”)。/规范(A,“来回”)ans = 9.7344 e - 005

这些计算表明零填充因子有7840个非零ILUTP（1E-4）因素31147个非零和ILUC（1E-4）因子有31083个非零。此外，零填充因子的乘积的相对误差在的模式上基本上是零一个。最后，在与阈值滴产生的因式分解的相对误差是下降的公差相同的顺序上，虽然这不能保证发生。查看ilu参考页查看更多选项和详细信息。

的ichol功能提供零填充不完全Cholesky因子分解(IC（0）），以及基于阈值的不完整的滴下Cholesky分解（ICT（TAU））对称，正定稀疏矩阵。这些因子分解是不完全LU因式分解以上的类似物，并有许多相同的特点。例如：

一个= delsq (numgrid (S, 200));nnz(chol(A，'lower')) ans = 7762589

L = ichol（A）;NNZ（L）ANS = 117216标准（A-（L * L '）。* spones（A），' 来回 '）./范数（A，' 来回 '）ANS = 3.5805e-017 opts.type =' ICT“;opts.droptol = 1E-4;L = ichol（A，OPTS）;NNZ（L）ANS = 1166754范数（A-L * L”， '来回'）./范数（A， '来回'）ANS = 2.3997e-004

IC（0）具有非零元素仅在下部三角形的图案一个的图案一个，的因子的乘积相匹配。此外，ICT（1E-4）因素是相当稀疏比完整的Cholesky因数，和之间的相对误差一个和L * L '是在相同的顺序的下降公差。重要的是要注意，不同的因素提供CHOL，提供的默认因素ichol是下三角。查看ichol引用页面了解更多信息。

直接的方法

直接方法通常比间接方法更快和更普遍适用，如果有足够的存储可用来执行它们。迭代方法通常适用于方程组的限制情况，并依赖于诸如对角优势或潜在微分算子的存在等性质。直接方法是在MATLAB软件的核心中实现的，并且对于一般的矩阵类是尽可能有效的。迭代方法通常在matlab语言文件中实现，可以使用子问题的直接解决方案或预处理。

使用不同的Preordering。如果一个不是对角的，带状的，三角形的，或者三角形矩阵的一个排列，反斜杠(\)重新排序的索引一个为了减少填充的数量——即添加到稀疏分解矩阵的非零项的数量。新的顺序叫做a预订被的因式分解之前执行一个。在某些情况下，你可能能够提供更好的比反斜杠算法使用的一个preordering。

要使用不同的preordering，首先请关闭自动亚序的反斜杠可能在默认情况下，执行使用功能spparms如下:

currentParms = spparms;spparms (autoamd, 0);spparms (autommd, 0);

现在，假设你已经创建了一个排列矢量p它指定的索引的预先排序一个，对矩阵应用反斜杠A（：，p）的，它的列是的列一个，根据向量置换p。

X = A（：，P）\ B;X（P）= X;spparms（currentParms）;

命令spparms（defaultParms）将控件恢复到它们以前的状态，以备使用一个\ b以后没有指定适当preordering。

迭代的方法

有11个函数实现了线性方程组的稀疏方程组的迭代方法。

这些方法的设计是为了解决一个x=b或最小化的规范b- - - - - -一个x。预条件共轭梯度方法，PCG,一个必须是对称的，正定矩阵。MINRES法和symmlq可以在对称不定矩阵被使用。对于LSQR，矩阵不一定是正方形。其它七个可以处理非对称，方阵和每个方法具有明显的好处。

这11种方法都可以使用预调节器。线性系统

由等效系统取代

的预调节器米被选择以加速迭代方法的收敛。在许多情况下，在数学模型中自然发生的预调。具有可变系数A偏微分方程可以由一个常系数来近似，例如。不完整的矩阵分解可以在不存在自然预条件来使用。

五点有限差分近似拉普拉斯方程在方形，二维域提供了一个例子。以下语句使用预条件共轭梯度方法的预处理器米=l*l”，其中l的零填充不完全Cholesky因子是一个。

A = delsq（numgrid（ 'S'，50））;B =酮（尺寸（A，1），1）;TOL = 1E-3;麦克斯特= 100;L = ichol（A）;[X，旗，ERR，ITER，RES] = PCG（A，B，TOL，麦克斯特，L，L'）;

为了达到规定的精度，需要21次迭代。另一方面，使用不同的预处理剂可能会产生更好的效果。例如,使用ichol构建修饰不完全Cholesky分解，在规定的精度仅15次迭代之后满足：

L = ichol（A，结构（ '上' '类型'， 'NOFILL'， 'michol'，））;[X，旗，ERR，ITER，RES] = PCG（A，B，TOL，麦克斯特，L，L'）;

这些迭代法和不完全因式分解的背景资料可在[2]和[6]。