大规模矩阵的MPI并行求逆算法设计与分析

DESIGN AND ANALYSIS OF MPI PARALLEL ALGORITHM FOR LARGE-SCALE MATRIX INVERSION

针对最小二乘解算中的大规模矩阵求逆问题,基于MPI实现了高阶稠密对称正定矩阵的Gauss-Jordan并行求逆算法,减少了计算耗时;通过优化矩阵读写、存储等方式降低了单个计算节点的内存耗用量,拓展了算法的可移植性。通过并行读写效率、单节点进程数、加速比和相对效率等因素评价算法的计算效率,计算结果表明:通过引入并行读写、减小单个计算节点的负荷等方式,并行求逆的相对效率峰值可达60%。以卫星重力场反演为例,采用曙光集群上的8个计算节点分别恢复截断阶次为120、240的地球重力场模型,求逆耗时为229 s、7 395 s,单个节点的内存耗用峰值为205 MB、1.57 GB,反演精度可达10-18量级,表明该算法能够快速稳定地获取最小二乘问题的最优估值。

In order to solve the problem in large scale matrix inversion with least square solving, gorithm to inverse the high-order dense symmetrical positive define matrix with Gauss-Jordan method the parallel al- on the basis of MPI was proposed. Considering the high memoI7 demand on single processor for this algorithm,the MPI I/O inter- face was introduced, which can reduce communicational time between each node simultaneously. Introducing the parallel I/O efficiency,memory demand on single processor, acceleration ratio and relative efficiency,the efficiency of the parallel algorithm can be estimated comprehensively. The simulation result indicates that this parallel algo- rithm can improve the efficiency significantly, ant its relative efficiency can reach to 60%. Eventually, the earth gravity field complete to degree and order 120 and 240 are recovered on the Sugon Cluster,and the relative inver- sion time is only 229 s and 7 395 s respectively. In addition,the memory demand on the single node is only 205 MB and 1.57 GB,while its inversion accuracy can reach to 10 -18,which indicates that the parallel algorithm in ｜his study can be used to obtain optimal value in least square efficiently and stably.