基于秩结构矩阵的快速并行算法

Rank-structured matrices are a very important class of structured matrices, which include semi-separable, quasi-separable, HSS, SSS matrices and so on, and have been widely used in many applications such as solving integral equations, elliptic PDEs, eigenvalue problems and linear equations. Some matrices appeared in some classical algorithms often have ‘off-diagonal low-rank’ property, e.g., the divide-and-conquer algorithm for eigenvalue and singular value problems, the LU factorization of some sparse matrices and some root-finders for nonlinear equations. In this project, we will exploit this off-diagonal low-rank property by using rank-structured matrix techniques especially the HSS matrices, and develop some fast parallel algorithms for these three kinds of problems above. The developed algorithms should have the following good properties such as low computation and storage complexity, low communication cost and good speedup in multi-core shared-memory parallel computing environment. The communication costs of these algorithms on multi-core shared-memory platform will be analyzed in detail, and the algorithms will be modified accordingly. Finally, the algorithms will be implemented efficiently and the codes will be collected together as a useful package.

秩结构矩阵是一类非常重要的结构矩阵，包括半可分、拟可分、HSS、SSS矩阵等，可被应用于求解积分方程，椭圆偏微分方程，特征值问题、大规模线性方程组等。在经典的数值算法中出现的某些矩阵往往具有“非对角块低秩性”，例如求解特征值和奇异值分解的分而治之算法、某稀疏线性方程组的LU分解和非线性方程的求根算法等。本课题将重点研究如何用秩结构矩阵(尤其是HSS矩阵)来刻画这些矩阵的低秩性，进而设计计算复杂度低的、存储和通信开销低的、多核共享存储计算环境下的高效并行算法。进一步分析算法的通信开销，并做相应的改进。最后在统一的框架下对各算法进行编程实现，形成具有实用价值的算法库。

本项目面向多核共享式存储处理器，以秩结构矩阵(HSS矩阵)为工具，研究新型的快速并行算法，主要成果包括：提出一种HSS改进的三对角DC(分而治之)算法，可用于求解对称三对角矩阵的特征分解，基于随机低秩逼近算法来实现并行的HSS构造算法，在intel平台可比MKL中的相应算法快5倍以上；提出一种HSS矩阵改进的带状DC算法，可用于求解带状矩阵的特征分解和SVD，当带宽较小时，该算法可比Intel MKL库中的相应算法快100倍以上；结合STRUMPACK，将三对角DC算法扩展到分布式并行情形，在天河2超级计算机上，在进程数不超过256时，可比Scalapack中的相应算法快2倍以上；将HSS矩阵用于加速快速的球谐变换，性能获得了明显提升；撰写了基于HSS矩阵的并行算法库HSSPACK，可用于求解特征值问题，线性方程组(Cholesky和LU分解)，Updating和Downdating SVD等问题，可在Github上自由下载。项目资助发表SCI期刊论文4篇，国际会议论文1篇，开源算法库1项，国家发明专利1项，培养与本课题相关的硕士生3名，博士生1名。