三、稀疏技及稀疏向量法.ppt

三稀疏技术及稀疏向量法 主要内容 因子表应用 因子表元素 因子表求解 稀疏因子表 回顾几个结论： 以高斯消元法逐列消元，对应于以消去节点法逐个消去节点 消元过程中的注入元，在物理意义上对应于由于消去某节点而出现新的互联支路导纳。 就形成因子表而言，三角分解法与高斯消元法完全等效，而以高斯消元法逐列消元又对应于以消去节点法逐个消去节点，因此可通过考察消去节点以考察因子表的形成 基于如上关系，高斯消元后如出现注入元，该注入元也将出现在三角分解后所得的上、下三角矩阵中，并将出现在所形成的因子表中。 因子表中是否会出现注入元等价于网络消去节点后是否会出现新的互联支路。 一、 因子表应用 网络方程需要求解多次，每次只是改变方程右端的常数向量，因此，考虑采用因子表 因子矩阵的元素以适当的形式贮存起来以备反复应用。 因子表的形成有多种方式，一般有 按行消元，逐行规格化的高斯消去 与上面高斯消去法对应的CROUT分解 LDU分解 因子矩阵的元素表达式如下 利用因子表(LDU分解)求解分两步： 前代（消元）： 例3－1 用因子表求解方程组AX=B。 先做消元运算 做规格化及消元运算 做回代运算 稀疏因子表的利用 求解： 从例子中看出 当线性方程组的稀疏性得到充分应用时 形成因子表过程中减少了计算量 更重要的是减少了求解方程组时前代和回代的计算量 二、稀疏技术1、概述 稀疏技术 针对稀疏矩阵及稀疏矢量，进行排零存储及排零计算 W. F. Tinney 2. 稀疏技术 IU（3）为4，表明A矩阵上三角部分第3行的第1个非零元如果有的话应在U的第4个位置，而U表中第4个位置没有非零元素，为了检索方便，IU(3)仍应赋值4。 有了IU表即可知道A的上三角部分第i行的非零元的数目 如果要查找A的上三角第i行所有非零元素，只要扫描A从IU(i)到IU(i+1)－1即可，JU(k)指出了该元素的列号，U(k)是该非零元素的值。 对于按列存储的格式进行查找的情况类同。 三角检索存储格式在矩阵A的稀疏结构已确定的情况下使用是十分方便的。 但在计算过程中，如果A的稀疏结构发生了变化，即其中的非零元素的分布位置发生变化，相应的检索信息也要随着变化，很不方便。 有两种办法处理 事先估计注入，符号分解。 链表格式 当新增加一个非零元素时，可把它排在最后，并根据该非零元素在该行中的位置的不同来修改其相邻元素的LINK值。 例如，新增a13，把a13排在第11个位置，把a12的LINK值由3改为11， a13本身的LINK值置为3，NA(1)增加1，变为4。 2.2 稀疏矩阵因子分解 对n×n阶矩阵A，分解成下三角矩阵L和单位上三角矩阵U两者的乘积，即A＝LU。 常规计算流程如下： 对稀疏存储格式应按所采用的存储格式的要求进行计算。 例如，当假定对矩阵A进行了符号分解，当用三角检索存储格式时可用下面计算流程。 对不同的分解方法有不同的计算流程。但主要是避免无效运算。 2.3 利用稀疏矩阵因子表求解稀疏线性方程组 对Ax=b ，假定分解成A＝LDU。则有： Lz=b 前代过程 Dy=z Ux=y 回代过程 结构如下： 即z中的第i个元素zi ，只会对z中下标大于i的元素有影响。换句话说， z中某元素只会受z中比该元素下标小的元素影响。因此，前代运算应从小号到大号依次进行。计算流程如下： 考虑了矩阵和矢量的稀疏性，重写前代的计算流程： 首先将独立b矢量送入z 可见： (1) 矢量z中下标小的元素只会影响下标大的元素，而不会影响比该元素下标小的元素。例如z2不会影响z1，z3不会影响z1和z2，等等。 (2) 前代中只取 每列中非零元素并用它和z矢量中相应元素进行前代运算。例如i＝1时，l3l和l4l是零元素，不必考虑z1和这两个零元素的运算。在稀疏矩阵计算中，实际上只扫描该列中的非零元素，而不必扫描零元素。 (3) 如果前代之前b中只有少数非零元素，例如b中只有b2是非零元素，由上面计算过程可知，i＝1的计算步可省去(因为z1 =0)。i＝2的计算步结束后， z4和z5变成非零元素， z3仍是零。i= 3的计算步也可省去。经过i＝4计算步后，最终的解z中也只有三个非零元素，即z2，z4，z5。这说明如果原来独立矢量是稀疏的，前代结束后，解矢量仍可能是稀疏的。到底哪些元素将由零元素变成非零元素，取决于 的稀疏结构，也取决于独立矢量b中非零元素的分布。 求解(3—7)式，只需做以下除法运算； yi＝zi／dii i＝1，…，n (3—10) dii是D的第i个对角元素。很明显，对于zi ＝0的除法运算可以省