稀疏矩阵的直接求解器

稀疏矩阵的直接求解器涉及比稠密矩阵更为复杂的算法。主要复杂性在于需要高效处理L和U因子中的填入。一个典型的稀疏求解器包含四个不同的步骤，而稠密情况下只有两个步骤：

1. 排序步骤，重新排序行和列，以减少因子中的填入，或者使矩阵具有特殊结构，如块三角形式。
2. 分析步骤或符号分解，确定因子中的非零结构，并为因子创建合适的数据结构。
3. 数值分解步骤，计算L和U因子。
4. 求解步骤，使用因子进行前向和后向代入。

每个步骤都有多种算法。Duff的综述论文[137]（另见[135, 第6章]）和Heath、Ng及Peyton的论文[219]可以作为各种算法的优秀参考。通常，步骤1和2仅涉及矩阵的图，因此仅涉及整数运算。步骤3和4涉及浮点运算。步骤3通常是最耗时的部分，而步骤4大约快一个数量级。步骤1中使用的算法与步骤3中使用的算法相当独立。但步骤2中的算法通常与步骤3中的算法密切相关。在最简单的系统，即对称正定系统中，这四个步骤可以很好地分离。对于最一般的非对称系统，求解器可能会合并步骤2和3（例如SuperLU），甚至合并步骤1、2和3（例如UMFPACK），以便数值也参与确定消去顺序。

在过去十年中，出现了许多利用新架构特性（如内存层次结构和并行性）的新算法和新软件。在表10.1中，我们列出了相当全面的稀疏直接求解器清单。最方便的是将软件分为三类：串行机软件、共享内存并行机软件和分布式内存并行机软件。

表10.1: 使用直接方法求解稀疏线性系统的软件。

代码	技术	范围	联系
串行平台
MA27	多前端	对称	HSL	[140]
MA41	多前端	对称-模式	HSL	[6]
MA42	前端	非对称	HSL	[144]
MA47	多前端	对称	HSL	[141]
MA48	右看	非对称	HSL	[142]
SPARSE	右看	非对称	Kundert	[281]
SPARSPAK	左看	对称正定	George	[191]
SPOOLES	左看	对称和对称-模式	Ashcraft	[21]
SuperLLT	左看	对称正定	Ng	[339]
SuperLU	左看	非对称	Li	[126]
UMFPACK	多前端	非对称	Davis	[103]
共享内存并行机
Cholesky	左看	对称正定	Rothberg	[405]
DMF	多前端	对称	Lucas	[308]
MA41	多前端	对称-模式	HSL	[7]
PanelLLT	左看	对称正定	Ng	[211]
PARASPAR	右看	非对称	Zlatev	[471]
PARDISO	左右看	对称-模式	Schenk	[395]
SPOOLES	左看	对称和对称-模式	Ashcraft	[21]
SuperLU_MT	左看	非对称	Li	[127]
分布式内存并行机
CAPSS	多前端	对称正定	Raghavan	[220]
DMF	多前端	对称	Lucas	[308]
MUMPS	多前端	对称和对称-模式	Amestoy	[8]
PaStiX	左右看{}^*	对称正定	CEA	[224]
PSPASES	多前端	对称正定	Gupta	[210]
SPOOLES	左看	对称和对称-模式	Ashcraft	[21]
SuperLU_DIST	右看	非对称	Li	[306]
S+	右看\dag	非对称	Yang	[182]

{}^* 尽管论文标题如此
\dag 使用QR存储静态容纳任何LU填入
表中使用的缩写： SPD = 对称正定； Sym = 对称且可能不定； Sym-pat = 对称非零模式但非对称值； Unsym = 非对称； HSL = 哈威尔子程序库：http://www.cse.clrc.ac.uk/Activity/HSL

没有单一的算法或软件适用于所有类型的线性系统。有些软件针对特殊矩阵，如对称正定矩阵，有些则针对最一般的情况。这在表的第三列“范围”中有所体现。即使是相同的范围，软件也可能决定使用特定的算法或实现技术，这对某些应用更好，而对其他应用则不然。在第二列“技术”中，我们给出了高级的算法描述。关于左看、右看和多前端之间的区别及其对性能的影响，请参阅Heath、Ng和Peyton的论文[219]以及Rothberg的论文[370]。有时，最好的（或唯一的）软件不是公开的，而是商业的或研究原型。这在第四列“联系”中有所体现，可能是公司名称或研究代码的作者姓名。

另一个复杂性是由于多样化的应用...像SPARSE这样的旧代码，独特的优势...

在特征系统分析的移位-反演谱变换（SI）上下文中，我们需要对A-\sigma I进行因子分解，其中A是固定的。因此，A-\sigma I的非零结构是固定的。此外，对于相同的移位\sigma，通常需要用相同的矩阵和不同的右端解多个系统（在这种情况下，求解成本可以与分解成本相当）。在步骤1和2中花费更多时间以加速步骤3和4是合理的。也就是说，可以尝试不同的排序方案，并根据符号分解估计数值分解和求解的成本，使用最佳排序。例如，在计算SVD时，可以选择AA^*、A^* A和[{0 \atop A^*} \; {A \atop 0}]之间的移位-反演，所有这些都可能具有相当不同的分解成本，如第6章所述。

一些求解器内置了排序方案，但其他求解器没有。内置的排序方案也可能不是目标应用的最佳选择。有时，用外部排序方案替换内置的排序方案更好。许多求解器提供了定义良好的接口，使用户可以轻松进行这种替换。应该阅读求解器文档，了解如何进行这种替换，以及推荐的排序方法。