Global Communication Strategy Of Krylov Subspace Method Parallel Algorithm

The numerical solution of most partial differential equations can be attributed to the problem of solving large sparse linear equations.Therefore,it is an important task to design efficient algorithms for solving large sparse linear equations.The method of solving linear systems is divided into direct method and iterative method,and when the coefficient matrix is a large-scale sparse matrix,iterative methods are often used.The Krylov subspace method is one of the major iterative methods to solve the large sparse linear equations.With the increase of the scale of the problem and the development of the parallel computer,it is imperative to adopt the parallel algorithm to solve the linear system.In the distributed parallel computing environment,the global communication caused by the inner product calculation becomes the bottleneck of the efficient parallel computation of the Krylov subspace method.In this paper,the smooth conjugate residual squared method(SCRS)and the preconditioned conjugate residual squared method(PCRS2)are studied for the glob-al communication problem caused by the inner product calculation.The SCRS algo-rithm is obtained by adding a smoothing operator to the conjugate residual squared method(CRS).The PCRS2 algorithm is obtained by adding a Preconditioner to the CRS algorithm.On the basis of SCRS and PCRS2,an improved LCSCRS and LCPCRS2 algorithm suitable for distributed parallel computing environment is proposed by changing the computational order and reconstruction algorithm.In LCSCRS,we reduce the three global communication points to one;in LCPCRS2,the number of global communication is reduced from twice to one,and the inner product required for each iteration is independent,The required communication time can be effectively overlapped with the calculation.To increase the cost of a small amount of calculation to improve the efficiency of the calculation.The performance of LCSCRS and SCRS algorithm,LCPCRS2 and PCRS2 algorithm are analyzed theoretically,including parallel time,acceleration ratio,s-calability and parallel performance improvement ratio.The results show that the LCSCRS algorithm and the LCPCRS2 algorithm have less parallel time and bet-ter scalability than the SCRS algorithm and the PCRS2 algorithm,respectively.The acceleration ratio of LCSCRS algorithm is 3 times higher than that of SCRS algorithm,and the improvement ratio of parallel performance is 66.7%.The accel-eration ratio of LCPCRS2 algorithm can reach 2 times of PCRS2 algorithm,and the improvement ratio of parallel performance is 50%.The calculated time and convergence behavior of PCRS2 algorithm and CRS,conjugate gradient method(CGS)and biorthogonal conjugate gradient stability(BiCG-STAB)were compared by numerical experiments.The experimental results showed that PCRS2 had better ratio than CRS,CGS and BiCGSTAB Algorithms with less computational time and smoother convergence behavior.The results of parallel numerical experiments show that LCSCRS and LCPCRS2 have better acceleration ratio and scalability than SCRS method and PCRS2 algorithm respectively,and verify the result of theoretical analysis.