An incomplete generalized minimum backward perturbation algorithm for large nonsymmetric linear systems

Abstract

This paper gives the truncated version of the generalized minimum backward error algorithm (GMBACK)—the incomplete generalized minimum backward perturbation algorithm (IGMBACK) for large nonsymmetric linear systems. It is based on an incomplete orthogonalization of the Krylov vectors in question, and gives an approximate or quasi-minimum backward perturbation solution over the Krylov subspace. Theoretical properties of IGMBACK including finite termination, existence and uniqueness are discussed in details, and practical implementation issues associated with the IGMBACK algorithm are considered. Numerical experiments show that, the IGMBACK method is usually more efficient than GMBACK and GMRES, and IMBACK, GMBACK often have better convergence performance than GMRES. Specially, for sensitive matrices and right-hand sides being parallel to the left singular vectors corresponding to the smallest singular values of the coefficient matrices, GMRES does not necessarily converge, and IGMBACK, GMBACK usually converge and outperform GMRES.

Key words： Nonsymmetric linear systems; Krylov subspace methods; minimum backward perturbation; incomplete orthogonalization process; GMBACK; GMRES

References

1 Arioli M, Duff I, Ruiz D. Stopping criteria for iterative solvers. SIAM J Matrix Anal Appl 1992; 13(1): 138–144

2 Baker A H, Jessup E R, Kolev T V. A simple strategy for varying the restart parameter in GMRES(m). J Comput Appl Math 2009; 230(2): 751–761

3 Ben-IsraelAGrevilleT N E. Generalized Inverses: Theory and Applications. New York: Wiley Interscience, 1974

4 Brown P N. A theoretical comparison of the Arnoldi and GMRES algorithms. SIAM J Sci Stat Comput 1991; 12(1): 58–78

5 Brown P N, Hindmarsh A C. Reduced storage matrix methods in stiff ODE systems. Appl Math Comput 1989; 31: 40–91

6 Brown P N, Saad Y. Hybrid Krylov methods for nonlinear systems of equations. SIAM J Sci Stat Comput 1990; 11(3): 450–481

7 Cao Z H. On a deflation method for the symmetric generalized eigenvalue problem. Linear Algebra Appl 1987; 92: 187–196

8 Cao Z H. Total generalized minimum backward error algorithm for solving nonsymmetric linear systems. J Comput Math 1998; 16(6): 539–550

9 GolubG HVan LoanC F. Matrix Computations, 2nd ed. Baltimore, MD: John Hopkins Univ Press, 1990

10 Higham D J, Higham N J. Backward error and condition of structured linear systems. SIAM J Matrix Anal Appl 1992; 13(1): 162–175

11 Huhtanen M, Permki A. Orthogonal polynomials of the R-linear generalized minimal residual method. J Approx Theory 2013; 167(3): 220–239

12 Jia Z X. On IOM(q): the incomplete orthogonalization method for large unsymmetric linear systems. Numer Linear Algebra Appl 1996; 3(6): 491–512

13 Kasenally E M. GMBACK: a generalized minimum backward error algorithm for nonsymmetric linear systems. SIAM J Sci Comput 1995; 16(3): 698–719

14 Kasenally E M, Simoncini V. Analysis of a minimum perturbation algorithm for nonsymmetric linear systems. SIAM J Numer Anal 1997; 34(1): 48–66

15 Li X A, Chen Y H, Zhang Y, Wang X P. Development of the Krylov subspace method for solving large sparse linear systems. science & Technology Review 2013; 11: 68–73

16 LiesenJTichyP. The field of values bound on ideal GMRES, 2012, arXiv: 1211.5969v1

17 Liu Y Q, Yin K X, WU E H. Fast GMRES-GPU algorithm for solving large scale sparse linear systems. Journal of Computer-Aided Design & Computer Graphics 2011; 23(4): 553–560

18 Ma X F. An overview of recent developments and applications of the GMRES method. Pure Math 2013; 3: 181–187

19 Najafi H S, Zareamonghaddam H. A new computational GMRES method. Appl Math Comput 2008; 199(2): 527–534

20 Saad Y. Krylov subspace methods for solving large unsymmetric linear systems. Math Comp 1981; 37(155): 105–126

21 Saad Y. Practical use of some Krylov subspace methods for solving indefinite and nonsymmetric linear systems. SIAM J Sci Stat Comput 1984; 5(1): 203–228

22 Saad Y, Schultz M H. GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J Sci Stat Comput 1986; 7(3): 856–869

23 Sterck H D. Steepest descent preconditioning for nonlinear GMRES optimization. Numer Linear Algebra Appl 2013; 20(3): 453–471

24 StewartG WSunJ-G. Matrix Perturbation Theory. New York: Academic Press, 1990

25 Sun L, Wang X H, Guan Y. IMinpert: an incomplete minimum perturbation algorithm for large unsymmetric linear systems. Numer Math J Chinese Univ 2007; 16(4): 300–312

26 Van HuffelSVandewalleJ. The Total Least Squares Problem: Computational Aspects and Analysis. Frontiers in Applied Mathematics, Vol 9. Philadelphia, PA: SIAM, 1991