高效装配算法：整体刚度矩阵

在采用变带宽算法进行刚度矩阵的装配与分解时，矩阵各行的存储需求相对还是比较大。在采用预条件CG法来求解对应的稀疏线性方程组时，线性方程组的求解时间可以大幅缩短。但如果依然采用变带宽算法中的分块技术来进行刚度矩阵的组装，之后再转化为CSR（Compressed Sparse Row），即按行格式存储法存储（吴建平等，2004），则时间复杂性必然与矩阵的外形成正比。当稀疏线性方程组的求解时间大幅下降之后，刚度矩阵装配所耗费的时间在总模拟时间中所占的比重就十分可观了。为减少刚度矩阵装配所需要的时间，提出了一个直接利用稀疏向量技术来进行高效装配的算法，下面对该算法进行具体描述。

首先对第k个未知量，利用VNE（k）统计包含该变量的单元数量，每装配一个单元，判断该单元是否包括第k个变量，如果包含，则将VNE（k）减1。同时用ncur记录下一次待转存为CSR格式的首行行号。

之后，利用eval，enod，cbpos，cpos，cptr来记录每个变量对应的各个单元中其他变量所对应的值与变量号，即eval中当前位置的值等于该值，而enod当前位置的值等于该变量号。并对第k个变量，以cbpos（k）指向eval与enod中记录第k个变量对应数据的第一个位置，cpos（k）指向当前位置，cptr指向下一个位置。

如果所存数据已达到eval与enod的存储容量，或所有单元已装配完毕，则进行按CSR格式转存的工作。具体措施为：检测从ncur开始后的所有行，直到某个ncur2使得对k＝ncur～ncur2，都有VNE（k）＝0，而VNE（ncur2+1）不为0为止。这时，对k＝ncur～ncur2，将第k行中所有val值与nod值进行提取并组合，转存为CSR格式。同时置相应的cbpos为－1，置相应的cptr值为－1，之后对eval、enod与cptr数组进行重整。

为对第k行中的数据进行提取与组合，采用稀疏向量技术（Saad，1996；吴建平等，2004），用w（1：nnz）记录该行中的非零元数值，用iw（1：nnz）记录这些数值对应的列号，如果第（k，j）号元素不为0，则用iw（n+j）指向w（1：nnz）、iw（1：nnz）中存储该元素的位置，否则iw（n+j）为0。(www.xing528.com)

在重整时，从第n+1号位置开始，每当某个cptr（j）等于－1，就将位置j记录到数组free中。进行后续装配时，利用free中的指针来分配新eval与新enod值的存储位置。

在经过以上操作之后，实际上已经形成了全局矩阵，但矩阵每行中所存储的元素是无序的，即同一行中的元素虽然都存储在相邻的存储空间中，但这些元素没有按任何顺序进行存储。由于ICT预条件要求各行中的元素按列号从小到大的顺序进行存储，所以还需要对得到的矩阵进行处理。排序时，当然可以对各个行分别进行，对每个行中的元素采用各种各样的排序技术进行排序，但这样排序所花费的时间比较长。

考虑到问题的特殊性，这里采用另一种排序技术，其时间复杂性为O（nnz），即与矩阵中的非零元个数成正比。其基本思想是，先将CSR格式的矩阵转存为CSC（Compressed Sparse Column）格式，即列格式存储法格式（Saad，1996），这样矩阵就逐列进行存储，列号从小到大，同时，在同一列内，各行上的元素也按行号从小到大的顺序进行存储。由于这里的矩阵是对称矩阵，所以得到的矩阵就已是满足要求的存储形式。