多项式预处理CMRH方法
摘要
本文研究求解大型稀疏非对称线性方程组的CMRH算法,主要的创新工作是提出了多项式预处理的CMRH算法,在本文中,我们把它称之为PCMRH算法。
求解大型稀疏非对称的线性方程组有很多方法。Krylov子空间算法如GMRES,QMR,CMRH等,是求解此类问题其中的一类非常有效的方法。CMRH方法利用Hessenberg过程构造Krylov子空间的一组基,相对于GMRES方法而言,具有所需的存储量较少等优点。但和GMRES方法一样,CMRH方法在解方程组时,可能发生停滞。为了克服CMRH方法解线性系统Ax=b过程中可能出现的收敛缓慢或不收敛,本文利用CMRH本身构造出一种有效的多项式预处理因子p_k(z)。数值实验表明:该多项式预处理因子非常简单且易于实现,PCMRH算法可取得比CMRH算法更有效的收敛。
本文分为以下四章:第一章主要介绍相关的问题背景,并概述本文的主要内容。第二章简要地描述了GMRES算法和CMRH算法。在第三章,我们具体给出多项式预处理CMRH算法的主要思想,并给出具体的实现过程。最后一章是数值试验,我们对许多不同类型的问题进行测试,来体现本文所给出的PCMRH算法对原来CMRH算法的改进。
In this paper the CMRH method for solving large and sparse, nonsymmetric linear systems is studied, a polynomial preconditioner for the CMRH algorithm is given, and the new method is called the PCMRH method in this paper.
There exist a lot of methods for solving the nonsymmetric linear systems, the Krylov type method such as GMRES, QMR, CMRH is one of the most popular algorithms. CMRH uses the Hessenberg process to construct a Krylov basis. Compare to the GMRES methods, CMRH is less expensive and requires slightly less storage. But like GMRES, the restart CMRH method may not converge or be stationary. In order to remedy this difficulty, this paper gives a polynomial preconditioner for CMRH based algorithm. The results of numerical experiments show that the polynomial preconditioner is quite simple and easy to be implemented and PCMRH can achieve convergence more efficiently than the CMRH.
This paper includes four parts. In the first part, related problems and background is introduced and the main contents of this paper are also described. In the second part, we briefly describe the GMRES and CMRH method. In the third part, the main idea of PCMRH is introduced. The last part is the numerical experiment. We test a wide range of problems to show that the new algorithm has better performance than the original algorithm.
求解大型稀疏非对称的线性方程组有很多方法。Krylov子空间算法如GMRES,QMR,CMRH等,是求解此类问题其中的一类非常有效的方法。CMRH方法利用Hessenberg过程构造Krylov子空间的一组基,相对于GMRES方法而言,具有所需的存储量较少等优点。但和GMRES方法一样,CMRH方法在解方程组时,可能发生停滞。为了克服CMRH方法解线性系统Ax=b过程中可能出现的收敛缓慢或不收敛,本文利用CMRH本身构造出一种有效的多项式预处理因子p_k(z)。数值实验表明:该多项式预处理因子非常简单且易于实现,PCMRH算法可取得比CMRH算法更有效的收敛。
本文分为以下四章:第一章主要介绍相关的问题背景,并概述本文的主要内容。第二章简要地描述了GMRES算法和CMRH算法。在第三章,我们具体给出多项式预处理CMRH算法的主要思想,并给出具体的实现过程。最后一章是数值试验,我们对许多不同类型的问题进行测试,来体现本文所给出的PCMRH算法对原来CMRH算法的改进。
In this paper the CMRH method for solving large and sparse, nonsymmetric linear systems is studied, a polynomial preconditioner for the CMRH algorithm is given, and the new method is called the PCMRH method in this paper.
There exist a lot of methods for solving the nonsymmetric linear systems, the Krylov type method such as GMRES, QMR, CMRH is one of the most popular algorithms. CMRH uses the Hessenberg process to construct a Krylov basis. Compare to the GMRES methods, CMRH is less expensive and requires slightly less storage. But like GMRES, the restart CMRH method may not converge or be stationary. In order to remedy this difficulty, this paper gives a polynomial preconditioner for CMRH based algorithm. The results of numerical experiments show that the polynomial preconditioner is quite simple and easy to be implemented and PCMRH can achieve convergence more efficiently than the CMRH.
This paper includes four parts. In the first part, related problems and background is introduced and the main contents of this paper are also described. In the second part, we briefly describe the GMRES and CMRH method. In the third part, the main idea of PCMRH is introduced. The last part is the numerical experiment. We test a wide range of problems to show that the new algorithm has better performance than the original algorithm.
引文
[1] H.Sadok,CMRH:A new method for solving nonsymmetric linear systems based on the Hessenberg reduction algorithm,Numer.Algorithms .20 (1999)303-321.
[2] Y.Saad,M.H.Schultz,GMRES:a generalized minimal residual algorithm for solving nonsymmetric linear systems,SIAMJ.Sci.Statist.Comput.7 (1986) 856-869.
[3] Freund R W, Nachtigal N M. QMR: A quasi-minimal residual method for non-Hermitian linear systems. Numer Math, 1991, 60: 315 339.
[4] M.B. van Gijzen,A polynomial preconditioner for the GMRES algorithm,J.comput.Appl.Math.59 (1995),91-107
[5] W.Joubert,A robust GMRES-based adaptive polynomial preconditioning algorithm for nonsymmetric linear systems,SIAM J.Sci Comput,15 (1994),427-439.
[6] P.E.Saylor and D.C.Smolarski,Implementation of an adaptive algorithm for Richardson's method,Linear Algebra and Its Applications,154-156 (1991),615-646.
[7] P.N.Brown,A theoretical comparison of the Arnoldi and the GMRES algorithms, SIAMJ.Sci.Statist.Comput.12 (1991)58-78.
[8] R.T.GregoryandD.L.Karney, A Collection of Matrices for Testing Computational Algorithms (Wiley,NewYork,1969).
[9] N.M.Nachtigal,L.Reichel and L.N.Trefethenk,A hybrid GMRES algorithm for nonsymmetric linear systems,SIAM J.Matrix and Appl.,13 (1992),796-825.
[10]L.Reichel,The application of Leja points to Richardson iteration and polynomial preconditioning,Linear Algebra and its Applications,154-156(1991).389-414.
[11]O.G.Johnson,C.A.Micchelli and G.Paul,Polynomial preconditioners for conjugate gradient calculations,SIAM J.Numer.Anal.,22(1983),362-376.
[12]S.F.Ashby,Minimax polynomial preconditioning for Hermitian linear systems,SIAM J.Matrix and Appl.,12(1996),766-789.
[13]G.Starke and R.S.Varga,A hybrid Arnoldi.Faber iterative method for nonsymmetric systems of linear equations,Numer.Math.,64(1993),213-240.
[14]T.A.Manteuffel and G.Starke,On hybrid iterative methods for nonsymmetric systems of linear equation,Numer.Math.,73(1996),489-506.
[15]Baojiang Zhong,Implementation of the hybrid GMRES algorithm using Householder transformations,Transactions of Nanjing University of Aeronautics & Astronautics,14(1997),146-152.
[16]全忠,向淑晃,基于GMRES的多项式预处理广义极小残差法,计算数学,2006,28(4):365-376.
[17]卢琳璋等,《线性代数》,科学出版社,2002
[18]李红伟,卢琳璋.添加近似误差的重新启动的simpler GMRES方法(英文)[J].数学研究,2006,(03).
[19]牛强,卢琳璋,王瑞瑞.A modified GMRES method for solving large nonsymmetric linear systems[J].高等学校计算数学学报,2005,(S1).
[2] Y.Saad,M.H.Schultz,GMRES:a generalized minimal residual algorithm for solving nonsymmetric linear systems,SIAMJ.Sci.Statist.Comput.7 (1986) 856-869.
[3] Freund R W, Nachtigal N M. QMR: A quasi-minimal residual method for non-Hermitian linear systems. Numer Math, 1991, 60: 315 339.
[4] M.B. van Gijzen,A polynomial preconditioner for the GMRES algorithm,J.comput.Appl.Math.59 (1995),91-107
[5] W.Joubert,A robust GMRES-based adaptive polynomial preconditioning algorithm for nonsymmetric linear systems,SIAM J.Sci Comput,15 (1994),427-439.
[6] P.E.Saylor and D.C.Smolarski,Implementation of an adaptive algorithm for Richardson's method,Linear Algebra and Its Applications,154-156 (1991),615-646.
[7] P.N.Brown,A theoretical comparison of the Arnoldi and the GMRES algorithms, SIAMJ.Sci.Statist.Comput.12 (1991)58-78.
[8] R.T.GregoryandD.L.Karney, A Collection of Matrices for Testing Computational Algorithms (Wiley,NewYork,1969).
[9] N.M.Nachtigal,L.Reichel and L.N.Trefethenk,A hybrid GMRES algorithm for nonsymmetric linear systems,SIAM J.Matrix and Appl.,13 (1992),796-825.
[10]L.Reichel,The application of Leja points to Richardson iteration and polynomial preconditioning,Linear Algebra and its Applications,154-156(1991).389-414.
[11]O.G.Johnson,C.A.Micchelli and G.Paul,Polynomial preconditioners for conjugate gradient calculations,SIAM J.Numer.Anal.,22(1983),362-376.
[12]S.F.Ashby,Minimax polynomial preconditioning for Hermitian linear systems,SIAM J.Matrix and Appl.,12(1996),766-789.
[13]G.Starke and R.S.Varga,A hybrid Arnoldi.Faber iterative method for nonsymmetric systems of linear equations,Numer.Math.,64(1993),213-240.
[14]T.A.Manteuffel and G.Starke,On hybrid iterative methods for nonsymmetric systems of linear equation,Numer.Math.,73(1996),489-506.
[15]Baojiang Zhong,Implementation of the hybrid GMRES algorithm using Householder transformations,Transactions of Nanjing University of Aeronautics & Astronautics,14(1997),146-152.
[16]全忠,向淑晃,基于GMRES的多项式预处理广义极小残差法,计算数学,2006,28(4):365-376.
[17]卢琳璋等,《线性代数》,科学出版社,2002
[18]李红伟,卢琳璋.添加近似误差的重新启动的simpler GMRES方法(英文)[J].数学研究,2006,(03).
[19]牛强,卢琳璋,王瑞瑞.A modified GMRES method for solving large nonsymmetric linear systems[J].高等学校计算数学学报,2005,(S1).