求解大规模线性方程组的并行多层低秩分解方法研究

One of the main tasks in scientific and engineering computing is solving large systems of linear equations derived from discretized partial differential equations or integral equations. So it's particularly important to study fast and efficient parellel solvers for large-scale dense systems or ill-conditioned sparse systems. Based on the theory of low-rank factorizations for the hierarchical semiseparatable structured (HSS) matrix, this project will study numerical methods and related parallel algorithms on the fast solution of linear equations. Hierarchically recursive low-rank factorization method has a linear or near linear complexity, and can reach any given accuracy, so it can not only be used as a fast and stable direct solver, but also be used to construct a high-efficient preconditioner to accelerate the convergence of iterative solvers. . Based on the parallel hierarchical recursive low-rank factorization method, this project will develop a parallel program for the fast solution of electromagnetic scattering problems with hundreds of millions of unknows on distributed computing platform, and use the formed algorithm and program to simulate hundred-million scale problems about photonic crystals and electromagnetic metamaterials with complex nano-structures under high performance computing environment, which will promote the application of fast parallel algorithms in computational electromagnetics.

在科学与工程计算中，主要任务之一是求解由偏微分方程或积分方程离散得到的大规模线性方程组。因此对于大规模稠密问题或病态的稀疏问题，研究快速、高效的并行求解算法尤为重要。本项目基于多层半可分（HSS）结构矩阵的低秩分解理论,研究快速求解线性方程组的数值方法及相关并行算法。多层递归低秩分解方法具有线性或近似线性的复杂度，而且能达到任意给定的精度，因此既可以作为快速、稳定的直接法求解器，也可以用来构造高效的预条件子，加快迭代求解器的收敛速度。. 基于并行多层递归低秩分解方法，本项目拟开发能够在分布式计算平台上快速求解上亿未知量规模的电磁散射问题的并行程序，并运用所形成的算法和程序在高性能计算环境下完成具有复杂纳米结构的光子晶体和电磁超材料的上亿规模的数值模拟，推进快速并行算法在计算电磁学中的应用。

利用系数矩阵非对角块的数值低秩属性，构造基于 HSS 结构矩阵的快速直接求解器及其并行算法。求解过程包括对矩阵的分块压缩并行构造、并行ULV 分解、并行三角求解。采用二维循环分布方式存储矩阵，将HSS 树和处理机网格进行映射，然后快速求解二维电磁散射问题得到的方程组，数值结果表明该算法具有良好的扩展性，不仅比ScaLAPACK的直接LU 分解求解快一个数量级，而且数值误差很小。HSS求解器可用于快速求解非对角块具有数值低秩结构的稠密线性方程组，并应用于Toeplitz、Hankel结构矩阵分解，位势场、电磁场的模拟，图像压缩等领域。另外，基于HSS压缩的快速ULV分解，HSS求解器的多波前方法快于基于MUMPS的标准多波前方法，尤其适合规则网格上的有限差分应用。