摘要
大型稀疏线性方程组的求解是对自然科学和社会科学中许多问题进行数值模拟的关键技术之一。而GMRES算法是目前求解大型稀疏非对称线性方程组最为有效的迭代算法之一。在执行整体的GMRES算法时,所需的计算量和存储量会随着迭代步数的增加而变得不可接受。为了克服这一困难,可以使用重新开始策略或混合迭代策略。最近,重新开始GMRES算法在迭代过程中表现出的补足收敛性质引起了人们的兴趣。特别地,基于这一性质所提出的积混合GMRES算法能够显著改善混合迭代策略求解方程组的效率。
积混合GMRES算法在执行过程中,需要首先计算出多次迭代GMRES迭代循环的残量多项式,然后重复使用这些多项式的乘积进行Richardson迭代。然而,当迭代循环的步长较大时,计算出的残量多项式可能是不稳定的,从而导致Richardson迭代的发散。为了提高积混合GMRES算法的稳定性以及收敛速率,本文提出了多项式预处理积混合广义极小剩余算法。
首先,本文介绍了求解大型稀疏矩阵的预处理Krylov子空间方法的原理以及在此基础上发展起来的各种迭代法,包括共轭梯度法,广义极小剩余法。
其次,本文重点介绍了在重新开始GMRES循环的残量多项式在矩阵的谱上收敛的互补性以及在此基础了得到的积混合广义极小剩余算法,构造出了多项式预处理矩阵,并将该矩阵作为积混合广义极小剩余算法的预处理矩阵,改善其系数矩阵谱的性质,提高了该算法的收敛速率和稳定性。
最后,本文对预处理后的新算法做了数值实验模拟与分析,将新算法与经典的成熟算法进行了对比,结果均表明,新算法更适合大型稀疏矩阵问题的求解,在计算量和存储量方面都有相应的改进。求解大型稀疏矩阵的积混合广义极小剩余算法得到了进一步的改善。
The solving of large sparse linear systems is one of the most important technologies for carrying out numerical simulation to many of the problems in natural and social sciences,and GMRES is one of the most popular algorithms for solving large nonsymmetrical linear systems. Unfortunately, the computational cost of full GMRES usually becomes unacceptable as the iteration number increases. To overcome the difficulty, restarting scheme or hybrid scheme of GMRES can be employed. Recently, the complementary behavior of restarted GMRES has attracted a wide interest. In particular, based on the study of complementary behavior,a product hybrid GMRES algorithm has been proposed, which improves the efficiency of hybrid scheme significantly.
To implement the product hybrid GMRES algorithm ,a couple of GMRES polynomials are constructed, and then the product of the polynomials are used repeatedly via a Richardson iteration.However, if the restarting frequency is not small,the GMRES polynomials may undergo a great instability. In consequence, the Richardson iteration may diverge. Polynomial preconditioned hybrid generalized minimal residual algorithm is proposed to accelerate its convergence rate and improve its stability.
Firstly, the principle of Krylov methods for solving large sparse linear systems is introduced. Then, GMRES algorithm and CG algorithm are introduced, which are based on the principle of Krylov methods.
Secondly, we discuss the complementary behavior of restarted GMRES and the product hybrid GMRES algorithm which is based on the study of complementary behavior.Then, calculating the polynomial preconditioned matrix, and using it as preconditioned matrix for the product hybrid GMRES algorithm to improving spectral nature of the coefficient, accelerating its convergence rate and improving its stability.
This paper gives some numerical experiments simulation and analysis for new preconditioned methods with classical algorithm of mature. The results show that the new algorithms is more suitable for large sparse matrix linear systems,computing and storage has a corresponding improvement. The product hybrid GMRES algorithm for solving large sparse matrix have been further improved.
引文
[1] Lanczos C. An iteration method for the solution of the eigenvalue problem of linear differential and integral operators[J]. J Res Nat Bur Sstand, 1950, 45:255-282
[2] Lanczos C. Solution of systems of linear equations by minimized iterations[J]. J Res Nar Bur Stand, 1952, 49:33-53
[3] Amoldi W E. The principle of minimized iteration in the solution of the matrix eigenvalue problem[J]. Quart Appl Math, 1951, 9:17-29
[4] Hestense M and Stiefel E. Methods of conjugate gradients for solving linear systems[J] . JRes Nat Bur Standards, 1952, 49: 409-436
[5] Paige C C. The computation of eigenvalues and eigenvectors of very large sparse matrices [D]:[dissertation]. London:University of London. 1971
[6]蔡大用,白峰杉.高等数值分析[M].北京:清华大学出版社,1997:71-93
[7] M.B van Gijzen. A polynomial preconditioner for the GMRES algorithm[J] . J. Comput. Appl. Math, 1995, 59: 91-107
[8] W. Joubert. A robust GMRES-based adaptive polynomial preconditioning algorithm fornonsymmetric linear systems[J] . SIAM J. Sci. Comput, 1994, 15: 427-439
[9] L.Reichel. The application of Leja points to Richardson iteration and polynomial preconditioning[J] . Linear Algebra and its Applications, 1991,56: 615-646
[10] S.F. Ashby. Minimax polynomial preconditioning for Hermitian Linear systems[J] . SIAM J.Matrix and Appl.,1996: 766-789
[11] Weiss R. Error-minimizing Krylov subspace methods[J] . SIAM J Sci Comput, 1994, 15(3): 511-527
[12] Miroslanvnik, Rudiger Weiss. On the stable implimetation of the generalized minimal eror method[J]. Jounal of Computational and Applied Mathematics, 1998:49-62
[13] Y. Saad AND M. H.Schultz. GMRES:A generalized minimal residual algorithm for solving nonsymmetric linear systems[J] . SIAM J.Sci.Statist.Comput, 1986,7: 856-869
[14] Nachtigal, N.M, Reichel, L and Trefethen., et al. L. N. A hybrid GRMES algorithm for nonsym-metric linear systems[J] . SIAM J. Matrix Anal. Appl. , 1992, 3(3):796-825
[15] Brown P N, Hindmarsh A C. Reduced storage methods in stiff ODE systems[J]. Appl MathComput , 1989, 31:40-91
[16] Brown P N, Saad Y. Hybird Krylov methods for nonlinear systems of equations[J]. SIAM J SciStatist Conput , 1990, 11:450-481
[17] Zhong B J. A product hybrid GMRES algorithm for nonsymmetric systems[J]. J Comput Math,2005, 23:83~92
[18]李庆扬,关治,白峰杉.数值计算原理[M].北京:清华大学出版社,2001:45-53
[19] Meijerink J A and Van Der Vorst H A. An iterative solution method for linear system of which the coefficient matrix is a symmetric M-Matrix[J]. Math Comp, 1977, 31: 148-162
[20]张永杰,孙秦.大型稀疏线性方程组新的ICCG方法[J].数值计算与计算机应用,2007,28(2),133-137
[21]吴小平,徐国明.不完全Cholesky共轭梯度法及其在地电场计算中的应用[J].石油地球物理勘探,1998,33(1),89-94
[22] Kershaw D S. The Incomplete Cholesky-conjugate gradient method for the iterative solution of systems of linear equations[J]. J Comp Phys, 1978, 26: 43-65
[23]张光澄,黄世莹,侯泽华.最优化计算方法[M].成都:成都科技大学出版社,1989:43-58
[24]张永杰.大型稀疏方程组预处理迭代快速求解技术研究[D].西安:西北工业大学,2006
[25]全忠.基于GMRES的多项式预处理广义极小残差法[J].计算数学,2006,11:365-376
[26]钟宝江.一种灵活的混合GMRES算法[J].高等学校计算数学学报,2001, 3: 261-272
[27] Reid J K. On the Method of Conjugate Gradients for the Solution of Large Sparse Systems of Linear Equations.Proc Conference on“Large Sets of Linear Equations”, Academic Press Inc, New York, 1971
[28] Y. Saad. Iterative methods for sparse linear systems[M]. New York: PWS Publishing , 1996:65-89
[29] G. H.戈卢布,C. F.范洛恩.矩阵计算[M].北京:科学出版社,2001:547-641
[30] Strakos Z. and Petr Tichy. On Error Estimation in the Conjugate Gradient Methodand why it Works in Finite Precision Conputations[J]. Electronic Transaction on Numerical Analysis on Numerical Analysis, 2002, 13: 56-80
[31] Q. W. Freund and N. M. Nachnical. QMR: a quasi-minimal residual residual algorithm for non-Hermitian linear systems, Numer. Math. 1991, 60: 315-339
[32]郑志镇,李尚健,李志刚.稀疏矩阵带宽减小的一种算法[J].华中理工大学学报,1998,12:43-45
[33] P.E.Saylor and D.C.Smolarski. Implementation of an adaptive algorithm for Richardson’s method[J]. Linear Algebra and Its Applications, 1991,154-156, 615-646
[34] Beaumens Robert. Iterative Solution Methods[J]. Applied Numerical Mathemetics, 2004, 51: 437-450
[35] Manteuffel T A. An incomplete factorization technique for positive definite linear systems[J]. Math Comp, 1980, 34: 473-497
[36]徐树方,高立,张文平.数值线性代数[M].北京:北京大学出版社,2000: 11-27
[37]徐士良.数值方法与计算机实现[M].北京:清华大学出版社,2006:13-48
[38]安学庆.求解大型稀疏线性方程组算法研究[D].郑州:郑州大学,2006
[39] Arany.I. Numerical Experiences of Solving Elasticity Systems by PCG Methods[J]. Computers and Mathematics with Applications, 2001, 42: 1025-1033
[40] Wayne D.Joubert and Graham F.Carey.Parallelizable restarted iterative methods for nonsymmetric linear systems[J].Part I, II, International Journal of Computer Mathematics, 1992, 44: 243-290
[41] Jocelyne Erhel.A parallel GMRES version for general sparse matrices[J].Electronic Transactions on Numerical Analysis,1995, 3: 160-176
[42] Z.Bai,D. Huand and L. Reichel. A Newton basis GMRES implementation[J]. IMA Journal of Numerical Analysis, 1994, 14: 563-581
[43] Gallivan, K, Plemmons, R and Sameh, A. SIAM Rev[J].1990, 32: 54-135
[44] FAHRINGER,T. Estimating and Optimizing Performance for Parallel Programs[J]. computer, 1995, 28(11):47-56
[45]管勇.右端积多项式预处理GMRES算法[D].南京:南京航空航天大学, 2006
[46]张建华.求解大型稀疏线性系统Krylov子空间方法[D].南京:南京航空航天大学,2007
[47] Gallopoulos, E . , Lee, D. Proc 1988 Int.Conf.Supercomputing[C].America:ACM Press, 1988: 488-499
[48] Azeddine Essai .Weighted FOM and GMRES for solving nonsymmetric linear systems [J]. Numerical Algorithms , 1998,18:277–292
[49] Mickal Robbé, Miloud Sadkane. A convergence analysis of GMRES and FOM methods for Sylvester equations[J]. Numerical Algorithms ,2002,30:71–89
[50]程治胜.大型稀疏矩阵的预条件混合GMRES算法研究[D].广州:华南理工大学, 2009
[51] DONGARRN,J.,S. W. OTTO,M. SNIR, D. WALKER.A Message-Passing Standard for MMP and Workstations[J].Comm.ACM,1996.39(7):84-90
[52] Kershaw D S. The Incomplete Cholesky-conjugate gradient method for iterative solution of systems of linear equations. J Comp Phys, 1978,26:43-65
[53]吴建平,王正华,李晓梅.稀疏线性方程组的高效求解与并行计算[M].长沙:湖南科学技术出版社,2004:69-73
[54]熊新平.并行预条件GMRES方法[J].计算机工程与设计,1994,4:25-32
[55]杨耀忠,韩子臣.一种黑油模型并行快速新解法—改进GMRES算法[J].计算机应用与软件,2003,1: 48-51
[56]吴牡兰. Richardson迭代算法的研究[D].北京:北京交通大学, 2008
[57]孙春晓.重新开始块GMRES算法的补足收敛性质[J].新课程(教研版),2009,8:116-117
[58]刘凯,陈红坤.以对称反对称分裂预条件处理GMRES(m)的不精确牛顿法潮流计算[J].电网技术,2009,19(33):123-126
[59]张瑜,袁书娟,杨爱民.Krylov子空间上并行预校GMRES(m)算法的研究[J].微电子学与计算机,2009,9(26):143-145
[60]张立翔,郭亚昆,张洪明.基于GMRES算法的弹性结构强耦合小变形流激振动分析[J].应用数学和力学,2010,1(31):81-89