吴建平 银福康 彭 军 杨锦辉

(国防科学技术大学海洋科学与工程研究院 湖南 长沙 410073)

0 引 言

稀疏线性方程组是混凝土细观数值模拟[1]、数值天气预报格点模式[2]、线性弹性问题[3]、油藏模拟[4]等许多科学与工程计算领域的核心计算模块之一，求解时间在整个应用问题中占很大比重，其求解效率是影响整个应用问题数值模拟效率的关键环节之一。正因为具有极端重要性，因此，直到最近，还广受关注并有大量研究[5-6]。Krylov子空间迭代[7-8]是求解这种稀疏线性方程组最有效而健壮的一般性方法之一，当系数矩阵对称正定时，其中共轭斜量(CG)法以计算经济、理论上较快的收敛速度应用最为广泛。但这种迭代法的实际收敛速度与系数矩阵的特征值分布有关，分布越集中，收敛速度越快。

多重网格算法[9-10]是求解稀疏线性方程组的另一类有效方法，其显著特点是通过将光滑与校正有机结合，具有潜在的快速收敛性。但这类方法健壮性一般不理想，因此，将其用作预条件，来加速Krylov子空间迭代法，是将两者优势有机结合的最佳选择。在针对一般稀疏线性方程组的代数多重网格算法中，聚集型代数多重网格算法以其计算与存储上的经济性、可控性广受关注。对这种多重网格算法，其核心是网格层次结构的选取与确定方法[11]，经典的聚集算法中，最有效的是基于强连接的算法及其变种[12-13]，但这些算法主要基于系数矩阵邻接图的局部特性，因而具有容易陷入局部最优的潜在缺陷，且不易于进行并行实现。……