第4章稀疏矩阵求解技术

稀疏矩阵指的是非零元非常少的矩阵；而稀疏系统指的是其数学描述最终生成稀疏矩阵的系统。任何可以用耦合节点描述的大系统，如果该系统中的大多数节点只有很少的连接就可能生成稀疏矩阵。很多工程和科学中的系统可以用稀疏矩阵来描述。每个节点只与其他几个节点相连的大系统包括有限元分析中的网格点、电子电路中的节点以及电力网络中的母线。例如，电力网络可能包含数千个节点（母线），但每个节点的平均连通度为3，即每个节点平均与3个其他节点相连。这意味着具有1000个节点的系统，其描述矩阵中的非零元的比例为。这样，如果只将非零元保存在内存中，那么对内存的需求仅仅为1000×1000满矩阵存储的0.4%。如果按满矩阵存储的话，n×n阶系统矩阵的存储空间将按照n²增长；而如果按稀疏矩阵存储的话，同样的系统矩阵其存储空间只大致随n线性增长。因此，通过采用稀疏存储和求解技术，可以大大减少存储空间。另一个采用稀疏矩阵求解技术的激励因素是可以大大减少求解含大比例零元素矩阵时所需的计算量。考虑求解如下的线性问题

Ax=b

式中，A为稀疏矩阵。将A进行LU分解时需要大量的乘法运算，而这些乘法运算中可能一个元素甚至两个元素都为零。如果事先知道零元素在矩阵中的位置，这些乘法运算是可以避免的（因为它们的乘积为零），从而可以大大减少计算量。这里的突出优势是这些运算可以全部跳过。手工进行LU分解时人们会注意到哪些元素为零，从而跳过这些特定的运算。但是，计算机没有“看到”零元素的能力。因此，稀疏求解技术必须按照如下方式来组织，避免所有的零元素运算，只对非零元素进行运算。(www.xing528.com)

本章中，我们将讨论稀疏矩阵求解技术的存储问题和计算问题。将给出数种存储技术，同时导出使计算量最小化的几种排序技术。