解大型稀疏非线性特征值问题的一类迭代投影法
|
摘要
本文研究了解大型稀疏非线性特征值问题的一类迭代投影法。非线性有理Krvlov法和非线性Arnoldi法适用于求解非线性问题在一个区域内的多个特征值。二者都属于迭代投影法,在本质上是等价的。在实现方式上却有所不同。非线性Arnoldi方法可以采用高效的算法来求解投影小问题,在实现上更为灵活。一般说来其实现性能要好于非线性有理Krylov方法。但非线性有理Krylov法在计算过程中不必明确给出投影小问题,可能比较适用于某些应用问题。
非线性有理Krylov法将非线性问题线性化,只能近似求解投影特征值问题。本文考虑在算法中引入精化策略,用精化向量来取代Ritz向量,形成了精化非线性有理Krvlov方法。
鉴于对大型问题,矩阵分解有可能无法实现或占用了过多的资源而影响算法的效率,本文采用一个内层迭代来求解非线性Arnoldi方法中的预条件系统,得到不精确的非线性Arnoldi方法。
文中给出了这些方法的实用算法,最后列出的数值算例说明了精化非线性有理Krvlov方法和不精确的非线性Arnoldi方法比原方法高效。
A class of numerical methods for nonlinear large sparse eigenvalue problems are studied in this thesis.Rational Krylov method and nonlinear Arnoldi method arc effective methods to find all eigenvalues of a nonlinear eigenvalue problem in some region.Both algorithms are belong to iterative projection inethods and do indeed resemble each other.The difference between them lies only in the way of implementation.Nonlinear Arnoldi method has the advantage over nonlinear Krylov method that it can take a flexible and more effieient way to solve the projected eigenvalue problem.But nonlinear rational Krylov method does not require the explicit form of the projected eigenvalue problem and may be more suitable for some particular applications.
Nonliner Krylov method use a linearization to approximate the nonlinear problem and solve the projected eigenvalue problem approximately.By making use of the idea of refined projection and adopting refined vector instead of Ritz vector,we present the refined nonlinear rational Krylov method.
In view of the considerable expense of LU factorization for large system,we nse a inner iteration to solve the precondition system and propose the inexact nonlinear Arnotdi method.
Practical algorithms are given for these methods and numerical examples with them indicate the improved two methods presented in this thesis are superior in speed of convergence.
非线性有理Krylov法将非线性问题线性化,只能近似求解投影特征值问题。本文考虑在算法中引入精化策略,用精化向量来取代Ritz向量,形成了精化非线性有理Krvlov方法。
鉴于对大型问题,矩阵分解有可能无法实现或占用了过多的资源而影响算法的效率,本文采用一个内层迭代来求解非线性Arnoldi方法中的预条件系统,得到不精确的非线性Arnoldi方法。
文中给出了这些方法的实用算法,最后列出的数值算例说明了精化非线性有理Krvlov方法和不精确的非线性Arnoldi方法比原方法高效。
A class of numerical methods for nonlinear large sparse eigenvalue problems are studied in this thesis.Rational Krylov method and nonlinear Arnoldi method arc effective methods to find all eigenvalues of a nonlinear eigenvalue problem in some region.Both algorithms are belong to iterative projection inethods and do indeed resemble each other.The difference between them lies only in the way of implementation.Nonlinear Arnoldi method has the advantage over nonlinear Krylov method that it can take a flexible and more effieient way to solve the projected eigenvalue problem.But nonlinear rational Krylov method does not require the explicit form of the projected eigenvalue problem and may be more suitable for some particular applications.
Nonliner Krylov method use a linearization to approximate the nonlinear problem and solve the projected eigenvalue problem approximately.By making use of the idea of refined projection and adopting refined vector instead of Ritz vector,we present the refined nonlinear rational Krylov method.
In view of the considerable expense of LU factorization for large system,we nse a inner iteration to solve the precondition system and propose the inexact nonlinear Arnotdi method.
Practical algorithms are given for these methods and numerical examples with them indicate the improved two methods presented in this thesis are superior in speed of convergence.
引文
[1]A.Ruhe.Rational Krylov,a practical algorithm for large sparse nonsymmetric matrix pencils[J].SIAM J Sci Comp.1998,19:1535-1551
[2]JIA Zhong-xiao.Refined iterative algorithms based on Arnoldi's process for large unsymmetric eigenproblems[J].Linear Algebra Appl.1997,259:1-23
[3]F.Tisseur.Backward error analysis of polynomial eigenvalue problems[J].Linear.Algebra Appl.2000,309:339-361
[4]A.Ruhe.A rational Krylov algorithm for nonlinear matrix eigenvalue problems[J].Zapiski Nauchnyh Seminarov POMI.2000,268:176-180
[5]H.Voss.An arnoldi method for nonlinear eigenvalue problems[J].BIT Numerical Mathematics.2004,44:387-401
[6]G.L.G.Sleijpen,H.A.van der vorst.A Jacobi-Davidson iteration method for linear eigenvalue problems[J].SIAM J Matrix Anal Appl.1996,17(2)
[7]Yoursef Saad.Numerical Methods for Large Eigenvalue Problems[M].Manchester University,1993
[8]R.B.Lehoucq,D.C.Sorensen.Deflation techniques within an implicitly restarted Arnoldi iteration[J].SIAM J Matr Anal Appl.1996,17):789-821
[9]A.Ruhe.Eigenvalue algorithms with several factorizations-a unified theory yet?[R].Tech,rep.,Department of Mathematics,Chahners University of Technology,Sweden,1998
[10]A.Ruhe.Computing nonlinear eigenvalues with spectral transformation Arnoldi[J].ZAMM.1996,76:S2::17-20
[11]P.Hager.Eigenfrequency Analysis.FE-Adaptivity and a Nonlinear Eigenvalue Problem [D].Ph.D.thesis,Chalmers University of Technology,Goteborg,2001
[12]P.Hager,N.E.Wiberg.Computational Mechanics for the Twenty-First Century[M],Saxe-Coburg Publications,Edinburgh.2000.379-402
[13]E.Jarlebring.Krylov method for nonlinear eigenvalue problems[D].Master's thesis,Royal lnsiitute of Technology,2003
[14]E.Jarlebring,H.Voss.Rational Krylov for nonlinear eigenproblems,an iterative projection method[R].Tech.rep..Hamburg University of Technology,2003.Submitted to Appl.Math.
[15]JIA Zhong-xiao.The convergence of generalized Lanczos methods for large unsymmetric eigenproblems[J].SIAM J Matrix Anal Appl.1995,16:843-862
[16]JIA Zhong-xiao.Composite orthogonal projection methods for large eigenproblems[J].Science in China,.1999,42:577-585
[17]JIA Zhong-xiao,G.W.Stewa,rt.An analysis of the Rayleigh-Ritz method for approximating eigenspaces[J].Math Comput.2001,70:637-647
[18]A.Ruhe.Algorithms for the nonlinear eigenvalue problem[J].SIAM J Numer Anal.1973,10:674-689
[19]A.Neumaier.Residual inverse iteration for the nonlinear eigenvalue problem[J].SIAM J Numer Anal.1985,22:914 923
[20]Z.Bai,J.Demmel,J.Dongarra,A.Ruhe,H.van der Vorst,eds.Templates for the solution of Algebraic Eigenvalue Problems:A Practical Guide[M].SIAM,Philadelphia,2000
[21]A.Ruhe.Rational Krylov for large nonlinear eigenproblems[R].Tech.rep.,Royal Institute of Technology,Stockhohn,Sweden,2004.To appear in Proceedings of PARA'04,Lyngby,Demmark
[22]V.N.Kublanovskaja.On an application of Newton's method to the determination of eigenvalues[J].Math Dokl.1969,10:1240-1241
[23]v.N.Kublanovskaja.On an application to the solution of the generalized latent value problem[J].SIAM J on Num Anal.1970,7:532-537
[24]F.Tisseur,K.Meerbergen.The quadratic eigenvalue problem[J].SIAM Rev.2001.43:234-286
[25]V.Mehrmann,H.Voss.Nonlinear eigenvalue problems:a challenge for modern eigenvalue methods[R}.Tech.rep.,Arbeitsbereich Mathelnatik,TU Hamburg-Harburg,2(/04
[26]H.Voss.Projection methods for nonlinear sparse eigenvalue problems[R].Tech.rep..Arbeitsbereich Mathematik,TU Hamburg-Harburg,2005
[27]JIA Zhong-xiao.A refined subspace iteration algorithm for large sparse eigenproblems [J].Appl Numer Math.2000,32:35-52
[28]K.Meerbergen.Locking and restarting quadratic eigenvalue solvers[J].SIAM.J Sci Comput.2001,22:1814-1839
[29]W.E.Arnoldi.The principle of minimized iterations in the solution of the matrix eigenvalue problem[J].Quarterly of Applied Mathematics.1951,9:17-29
[30]D.C.Sorensen.Implicit application of polynomial filters in a k-step Arnoldi method[J].SIAM J Matr Anal Appl.1980,34:269-295
[31]R.B.Lehoucq.Analysis and implementation of an implicitly restarted Arnoldi iteration [D].Ph.D.thesis,Rice University,Houston,TX,1995
[32]R.B.Lehoucq,K.Meerbergen.Using generalized Cayley transformations within an inexact rational Krylov sequence method[J].SIAM J Matr Anal Appl.1998,20(1):131-148
[33]R.B.Lehoucq,K.Meerbergen.The inexact rational Krylov sequence method[R].Tech.rep.,Argonne National Laboratory,Argonne,IL,1997
[34]Yousef Saad.A flexible inner-outer preconditioned GMRES algorithm[J].SIAM J Sci Coumput.1993,14(2):461-469
[35]Yoursef Saad.Iterative Methods for Sparse Linear Systems[M].PWS publishing,Boston,MA,1996
[36]Yousef Saad.Inexact Newton preconditioning techniques for large symmetric eigenvalue problems[J].Electronic Transactions on Nunerical Analysis.1998,7:202-214
[37]Y.Saad.SPARSKIT:A basic tool kit for sparse matrix computations[R].Tech.rep.,Research Institute for Advanced Computer Science,NASA Ames Research Center,Moffet Field,CA,1990
[38]G.L.G.Slei.jpen.A.G.L.Booten.D.R.Fokkema.H.A.van der vorst.Jacobi-Davidson type methods for generalized eigenproblems and polynomial eigenproblems [R].Tech.rep.,Department of mathematics.Universiteit Utrecht,1995
[39]G.L.G.SleijPen.H.A.van der vorst.The Jacobi-Davidson method for eigenvalue prohlems and its relation with accelerated inexact newton schemes[J].SIAM J Matrix Anal Appl.1996
[40]Valeria Simoncini.Daniel B.Szyld.Flexible inner-outer Krylov subspace methods[R].Tech,reh.,available in the World Wide Web at http://wwww.math.temple.edn/szyld,2002
[41]Valeria Simoncini,Daniel B.Szyld.Theory of inexact Krylov subspace methods and applications to scientific computing[R].Tech.rep.,available in the World Wide Web at http://wwww.math.temple.edu/szyld,2002
[42]G.H.Golub,Q.Ye,Inexact inverse iteration for generalized eigenvalue problems[J].BIT.2000,40(4):671-684
[43]G.H.Golub,Q.Ye.Inexact preconditioned conjugate gradient method with inner outer iteration[J].SIAM Journal Oil Scientific Computing.1999,21:1305-1320
[44]G.H.Golub,C.F.Van Loan.Matrix Computations[M].The Johns Hopkins University Press,Baltimore,1983
[45]Linzhang lu,Wai ki Ching,Michael K.Ng.Exact algorithm tbr singular tria.ngular systems with application to Markov chains[J].Appl Math Comput.2004,159:275289
[46]Linzhang lu.Michael K.Ng.On sufficient and necessary conditions for the Jacobi matrix inverse eigenvalue problem[J].Numerische Mathematik.2004,98(1):167-176
[47]卢琳璋.两类代数黎卡提方程数值解法的研究进展[J].厦门大学学报(自然科学版).2001,3:182-186
[2]JIA Zhong-xiao.Refined iterative algorithms based on Arnoldi's process for large unsymmetric eigenproblems[J].Linear Algebra Appl.1997,259:1-23
[3]F.Tisseur.Backward error analysis of polynomial eigenvalue problems[J].Linear.Algebra Appl.2000,309:339-361
[4]A.Ruhe.A rational Krylov algorithm for nonlinear matrix eigenvalue problems[J].Zapiski Nauchnyh Seminarov POMI.2000,268:176-180
[5]H.Voss.An arnoldi method for nonlinear eigenvalue problems[J].BIT Numerical Mathematics.2004,44:387-401
[6]G.L.G.Sleijpen,H.A.van der vorst.A Jacobi-Davidson iteration method for linear eigenvalue problems[J].SIAM J Matrix Anal Appl.1996,17(2)
[7]Yoursef Saad.Numerical Methods for Large Eigenvalue Problems[M].Manchester University,1993
[8]R.B.Lehoucq,D.C.Sorensen.Deflation techniques within an implicitly restarted Arnoldi iteration[J].SIAM J Matr Anal Appl.1996,17):789-821
[9]A.Ruhe.Eigenvalue algorithms with several factorizations-a unified theory yet?[R].Tech,rep.,Department of Mathematics,Chahners University of Technology,Sweden,1998
[10]A.Ruhe.Computing nonlinear eigenvalues with spectral transformation Arnoldi[J].ZAMM.1996,76:S2::17-20
[11]P.Hager.Eigenfrequency Analysis.FE-Adaptivity and a Nonlinear Eigenvalue Problem [D].Ph.D.thesis,Chalmers University of Technology,Goteborg,2001
[12]P.Hager,N.E.Wiberg.Computational Mechanics for the Twenty-First Century[M],Saxe-Coburg Publications,Edinburgh.2000.379-402
[13]E.Jarlebring.Krylov method for nonlinear eigenvalue problems[D].Master's thesis,Royal lnsiitute of Technology,2003
[14]E.Jarlebring,H.Voss.Rational Krylov for nonlinear eigenproblems,an iterative projection method[R].Tech.rep..Hamburg University of Technology,2003.Submitted to Appl.Math.
[15]JIA Zhong-xiao.The convergence of generalized Lanczos methods for large unsymmetric eigenproblems[J].SIAM J Matrix Anal Appl.1995,16:843-862
[16]JIA Zhong-xiao.Composite orthogonal projection methods for large eigenproblems[J].Science in China,.1999,42:577-585
[17]JIA Zhong-xiao,G.W.Stewa,rt.An analysis of the Rayleigh-Ritz method for approximating eigenspaces[J].Math Comput.2001,70:637-647
[18]A.Ruhe.Algorithms for the nonlinear eigenvalue problem[J].SIAM J Numer Anal.1973,10:674-689
[19]A.Neumaier.Residual inverse iteration for the nonlinear eigenvalue problem[J].SIAM J Numer Anal.1985,22:914 923
[20]Z.Bai,J.Demmel,J.Dongarra,A.Ruhe,H.van der Vorst,eds.Templates for the solution of Algebraic Eigenvalue Problems:A Practical Guide[M].SIAM,Philadelphia,2000
[21]A.Ruhe.Rational Krylov for large nonlinear eigenproblems[R].Tech.rep.,Royal Institute of Technology,Stockhohn,Sweden,2004.To appear in Proceedings of PARA'04,Lyngby,Demmark
[22]V.N.Kublanovskaja.On an application of Newton's method to the determination of eigenvalues[J].Math Dokl.1969,10:1240-1241
[23]v.N.Kublanovskaja.On an application to the solution of the generalized latent value problem[J].SIAM J on Num Anal.1970,7:532-537
[24]F.Tisseur,K.Meerbergen.The quadratic eigenvalue problem[J].SIAM Rev.2001.43:234-286
[25]V.Mehrmann,H.Voss.Nonlinear eigenvalue problems:a challenge for modern eigenvalue methods[R}.Tech.rep.,Arbeitsbereich Mathelnatik,TU Hamburg-Harburg,2(/04
[26]H.Voss.Projection methods for nonlinear sparse eigenvalue problems[R].Tech.rep..Arbeitsbereich Mathematik,TU Hamburg-Harburg,2005
[27]JIA Zhong-xiao.A refined subspace iteration algorithm for large sparse eigenproblems [J].Appl Numer Math.2000,32:35-52
[28]K.Meerbergen.Locking and restarting quadratic eigenvalue solvers[J].SIAM.J Sci Comput.2001,22:1814-1839
[29]W.E.Arnoldi.The principle of minimized iterations in the solution of the matrix eigenvalue problem[J].Quarterly of Applied Mathematics.1951,9:17-29
[30]D.C.Sorensen.Implicit application of polynomial filters in a k-step Arnoldi method[J].SIAM J Matr Anal Appl.1980,34:269-295
[31]R.B.Lehoucq.Analysis and implementation of an implicitly restarted Arnoldi iteration [D].Ph.D.thesis,Rice University,Houston,TX,1995
[32]R.B.Lehoucq,K.Meerbergen.Using generalized Cayley transformations within an inexact rational Krylov sequence method[J].SIAM J Matr Anal Appl.1998,20(1):131-148
[33]R.B.Lehoucq,K.Meerbergen.The inexact rational Krylov sequence method[R].Tech.rep.,Argonne National Laboratory,Argonne,IL,1997
[34]Yousef Saad.A flexible inner-outer preconditioned GMRES algorithm[J].SIAM J Sci Coumput.1993,14(2):461-469
[35]Yoursef Saad.Iterative Methods for Sparse Linear Systems[M].PWS publishing,Boston,MA,1996
[36]Yousef Saad.Inexact Newton preconditioning techniques for large symmetric eigenvalue problems[J].Electronic Transactions on Nunerical Analysis.1998,7:202-214
[37]Y.Saad.SPARSKIT:A basic tool kit for sparse matrix computations[R].Tech.rep.,Research Institute for Advanced Computer Science,NASA Ames Research Center,Moffet Field,CA,1990
[38]G.L.G.Slei.jpen.A.G.L.Booten.D.R.Fokkema.H.A.van der vorst.Jacobi-Davidson type methods for generalized eigenproblems and polynomial eigenproblems [R].Tech.rep.,Department of mathematics.Universiteit Utrecht,1995
[39]G.L.G.SleijPen.H.A.van der vorst.The Jacobi-Davidson method for eigenvalue prohlems and its relation with accelerated inexact newton schemes[J].SIAM J Matrix Anal Appl.1996
[40]Valeria Simoncini.Daniel B.Szyld.Flexible inner-outer Krylov subspace methods[R].Tech,reh.,available in the World Wide Web at http://wwww.math.temple.edn/szyld,2002
[41]Valeria Simoncini,Daniel B.Szyld.Theory of inexact Krylov subspace methods and applications to scientific computing[R].Tech.rep.,available in the World Wide Web at http://wwww.math.temple.edu/szyld,2002
[42]G.H.Golub,Q.Ye,Inexact inverse iteration for generalized eigenvalue problems[J].BIT.2000,40(4):671-684
[43]G.H.Golub,Q.Ye.Inexact preconditioned conjugate gradient method with inner outer iteration[J].SIAM Journal Oil Scientific Computing.1999,21:1305-1320
[44]G.H.Golub,C.F.Van Loan.Matrix Computations[M].The Johns Hopkins University Press,Baltimore,1983
[45]Linzhang lu,Wai ki Ching,Michael K.Ng.Exact algorithm tbr singular tria.ngular systems with application to Markov chains[J].Appl Math Comput.2004,159:275289
[46]Linzhang lu.Michael K.Ng.On sufficient and necessary conditions for the Jacobi matrix inverse eigenvalue problem[J].Numerische Mathematik.2004,98(1):167-176
[47]卢琳璋.两类代数黎卡提方程数值解法的研究进展[J].厦门大学学报(自然科学版).2001,3:182-186