赖智超　罗晓群　张其林

摘要：采用列压缩稀疏（Compressed Sparse Column， CSC）矩阵存储策略对矩阵LDL分解前进行填充元优化排序；基于消去树进行LDL符号分解，使之独立于数值分解，避免多余的内存消耗，减少不必要的数值运算.利用矩阵非零元的分布特性分析并实现超节点LDL分解算法，将稀疏矩阵的分解运算变为一系列稠密矩阵运算，并使用优化的BLAS函数库加速分解.测试表明：算法在成倍地提高计算速度的同时进一步降低内存消耗，适用于大规模的结构计算.

关键词：稀疏矩阵； LDL分解； 消去树； 符号分解； 超节点

中图分类号： TP301

文献标志码：B

现代结构工程的计算经有限元法处理后往往归结为一个规模庞大的线性代数方程组的求解.大规模的矩阵存储和快速的求解是制约大型结构计算的关键.

稀疏矩阵是指矩阵中大多数数值为零的矩阵.对于较大规模的稀疏矩阵，非零元占总元素个数比例非常小.结构分析中得到的矩阵就是一个具有很好特性的对称正定（Symmetric Positive Definite，SPD）稀疏矩阵.本文的关注点是结构工程中的SPD稀疏矩阵的直接法求解计算.目前，已经有不少稳定高效的求解库，如csparse，taucs，cholmod和superLU等，它们主要是使用cholesky分解和LU分解将稀疏矩阵A分解为LLT或

LU的形式.由于分解后的L中非零元相对于A会增多，所以称之为“填充元”.[1]因此，一般将稀疏矩阵的分解分为2部分：计算填充元的位置，称之为“符号分解”；进行实际的数值分解计算，称之为“数值分解”.

第一个通用快速SPD稀疏矩阵求解器实现库是……