中国科学院软件研究所机构知识库

本论文意图为大规模非对称的线性方程组Ax=b并行求解器提供一个兼顾高可扩展性和高逼近精度的新型预条件子核心部件，称之为“LST 类预条件子”，其基于系数矩阵的对称部分而形成，算法构造依托于权重连通图及相关联的Laplacian矩阵和广义逆矩阵。LST类预条件子的算法构造基于两个理论系统，其一为分解理论，主要解决新型预条件子的高可扩展性；其二为近似理论，主要解决新型预条件子的高逼近精度。

 

LST类预条件子的并行程序实现尽力地保持了权重连通图的局部特性，该特性一方面由聚类形的局地表达方式体现，以Cheeger值和Cheeger常数作为度量函数；另一方面由骨架形的主干路表达方式体现，以均值Stretch值和均值Stretch常数作为度量函数。

 

LST类预条件子高逼近精度的程序实现尽力地近似了原系数矩阵对应的权重连通图的广义条件数和谱分布，其逼近精度的度量和控制主要采用了两种模式： 其一是矩阵A 和B之间的谱范数逼近，通过引入广义条件数来实现；其二是矩阵A和B之间的Frobenius范数逼近，通过特征值的和(迹算子)之间的逼近进行实现。新型预条件子对应于权重连通图的谱稀疏化子图，稀疏化子图与原图之间的逼近由迹算子的逼近进行度量，它又归结为以均值Stretch值/均值Stretch常数为测度的逼近度量。

 

LST类预条件子的程序实现有三个核心算法模块，其一是权重连通图的局部特性保持的算法模块，据此得到系统矩阵的大尺度聚类剖分和中小尺度区域分解；其二是权重连通图的谱稀疏化子图算法与(过)抽样算法模块，其有效利用了大规模集成电路网格的等效电路原理与有效电阻概念，将预条件子与系数矩阵之间的逼近问题转化为广义逆矩阵之间的逼近问题，利用(过)抽样算法的不等式约束手段，得到了近似线性时间开销的高逼近精度的稀疏广义逆，从而得到了高逼近精度的谱稀疏化子图的快速构造算法；其三是Low stretch生成树(LST)模块，它利用分层递进式的Petal-分解策略、分级逐层地渐进式地构造了权重连通图的LST生成树，从而将连通图的全局特性与局地特性有效地融合起来，并为谱稀疏化子图的形成提供了骨架式的主干路，该模块因此而成为新型预处理算法的基础算法模块。

 

本论文基于通讯极小化的图剖分算法、具有$\epsilon$-approx逼近精度的谱稀疏化子图算法、基于Petal-分解的LST生成树算法等构造理论与算法实现，对新型的LST类预条件子进行了系统地理论分析与算法研究，由此给出了求解非对称线性方程组的高可扩展高计算精度的预条件子的核心算法组件；在程序设计和算法实现的基础上，本文利用理论算例、数值算例和应用算例，对LST类预条件子的剖分效果、逼近效果、聚类质量、谱分布效果、求解器加速效果等进行了定性和定量的数值试验与数值分析。

 

本论文在LST类预条件子的算法构造过程中，系统性的研究了将分解理论与近似理论有机融合的预处理算法构造理论，有效地构建了将聚类形的局地表达方式与骨架形的全局表达方式融合在一起的谱稀疏化子图算法及其程序，充分地使用了分层递进式Petal-分解和Low stretch 生成树在大尺度聚类剖分中的通讯极小化特性，从而得到了兼顾高可扩展性和高逼近精度的新型预条件子。上述的理论研究和算法实现构成了本论文的创新性工作。