The block LSMR algorithm for solving linear systems with multiple right-hand sides

Document Type : Research Article

Authors

• M. Mojarrab
• F. T

Department of Applied Mathematics, Faculty of Mathematical Sciences, Ferdowsi University of Mashhad, Iran.

10.22067/ijnao.v5i2.34330

Abstract

LSMR (Least Squares Minimal Residual) is an iterative method for the solution of the linear system of equations and leastsquares problems. This paper presents a block version of the LSMR algorithm for solving linear systems with multiple right-hand sides. The new algorithm is based on the block bidiagonalization and derived by minimizing the Frobenius norm of the resid ual matrix of normal equations. In addition, the convergence of the proposed algorithm is discussed. In practice, it is also observed that the Frobenius norm of the residual matrix decreases monotonically. Finally, numerical experiments from real applications are employed to verify the effectiveness of the presented method.

Keywords

• LSMR method
• Bidiagonalization
• Block methods
• Iterative methods
• Multiple right-hand sides

20.1001.1.24236977.2015.5.2.2.9

---

References

1. Abdel-Rehim, A. M., Morgan, R. B. and Wilcox, W. Improved seed methods for symmetric positive denite linear equations with multiple right- hand sides, 2008, Arxivpreprint arXiv:0810.0330v1.

2. Bellalij, M., Jbilou, K. and Sadok, H.New convergence results on the global GMRES method for diagonalizable matrices, J. Comput. Appl. Math. 219 (2008) 350-358.

3. Chan,T. F. and Wang, W.Analysis of projection methods for solving linear systems with multiple right-hand sides, SIAM J. Sci. Comput. 18 (1997) 1698-1721.

4. Chin-Lung Fong, D. and Saunders, M. LSMR: An iterative algorithm for sparse least-squares problems, SIAM J. Sci. Comput. 33 (2011) 2950-2971.

5. Dai, H. Two algorithms for symmetric linear systems with multiple right-hand sides, Numer. Math. J. Chin. Univ. (Engl. Ser.) 9 (2000) 91-110.

6. Darnell, D., Morgan, R. B. and Wilcox, W. De ated GMRES for systems with multiple shifts and multiple right-hand sides, Linear Algebra Appl. 429 (2008) 2415-2434.

7. Davis, T. A. University of Florida Sparse Matrix Collection, http://www.cise.u .edu/research/sparse / matrices.

8. Freund, R. and Malhotra, M. A Block-QMR algorithm for non-hermitian linear systems with multiple right-hand sides, Linear Algebra Appl. 254 (1997) 119-157.

9. Golub, G. H., Luk, F. T. and Overton, M. L. A Block Lanczos method for computing the singular values and corresponding singular vectors of the matrix, ACM Trans. Math. Software 7 (1981) 149-169.

10. Golub, G. H. and Kahan, W. Calculating the singular values and pseu-doinverse of a matrix, SIAM J. Numer. Anal, 2 (1965) 205-224.

11. Golub, G. H. and Van Loan, C. F. Matrix Computations, Johns Hopkins University Press, Baltimore, MD, 1983.

12. Gu, G. and Cao, Z.A block GMRES method augmented with eigenvectors, Appl. Math. Comput. 121 (2001) 271-289.

13. Gu, G. and Qian, H. Skew-symmetric methods for solving nonsymmetric linear systems with multiple right-hand sides, J. Comput. Appl. Math. 223 (2009) 567-577.

14. Gu, C. and Yang, Z. Global SCD algorithm for real positive denite linear systems with multiple right-hand sides, Appl. Math. Comput. 189 (2007) 59-67.

15. Guennouni, A. El., Jbilou, K. and Sadok, H. A block version of BICGSTAB for linear systems with multiple right-hand sides, Elec. Trans. Numer. Anal. 16 (2003) 129-142.

16. Guennouni, A. El., Jbilou, K. and Sadok, H. The block Lanczos method for linear systems with multiple right-hand sides, Appl. Numer. Math. 51 (2004) 243-256.

17. Gutknecht, M. H. Block Krylov space methods for linear systems with multiple right-hand sides: an introduction, in: A. H. Siddiqi, I. S. Du, O. Christensen (Eds.), Modern Mathematical Models, Methods and Al-

gorithms for Real Word Systems, Anamaya Publishers, New Delhi, India, 2007, 420-447.

18. Haase, G. and Reitzinger, S. Cache issues of algebraic multigrid methods for linear systems with multiple right-hand sides, SIAM J. Sci. Comput. 27 (2005) 1-18.

19. Heyouni, M.The global Hessenberg and global CMRH methods for linear systems with multiple right-hand sides, Numer. Algorithms 26 (2001) 317-332.

20. Heyouni, M. and Essai, A. Matrix Krylov subspace methods for linear systems with multiple right-hand sides, Numer. Algorithms 40 (2005) 137-156.

21. Jbilou, K., Messaoudi, A. and Sadok, H. Global FOM and GMRES algo-rithms for matrix equations, Appl. Numer. Math. 31 (1999) 49-63.

22. Jbilou, K. and Sadok, H. Global Lanczos-based methods with applications,Technical Report LMA 42, Universiti du Littoral, Calais, France, 1997.

23. Jbilou, K, Sadok, H. and Tinzefte, A. Oblique projection methods for linear systems with multiple right-hand sides, Elec. Trans. Numer. Anal. 20 (2005)119-138.

24. Joly, P. Resolution de Systems Lineaires Avec Plusieurs Second Members par la Methode du Gradient Conjugue, Tech. Rep. R-91012, Publications du Laboratire d'Analyse Numerique, Universite Pierre et Marie Curie,

Paris, 1991.

25. Karimi, S. and Toutounian, F. The block least squares method for solving nonsymmetric linear systems with multiple right-hand sides, Appl. Math. Comput. 177 (2006) 852-862.

26. Lin, Y. Implicitly restarted global FOM and GMRES for nonsymmetric matrix equations and Sylvester equations, Appl. Math. Comput. 167(2005) 1004-1025.

27. Liu, H. and Zhong, B. Simpler block GMRES for nonsymmetric systems with multiple right-hand sides, Elec. Trans. Numer. Anal. 30 (2008) 1-9.

28. Mojarrab, M. The Block least square methods for matrix equations, PhD thesis, Ferdowsi University of Mashhad, Iran, 2014.

29. Morgan, R. B. Restarted block-GMRES with de ation of eignvalues, Appl. Numer. Math. 54 (2005) 222-236.

30. Nikishin, A. and Yeremin, A. Variable block CG algorithms for solving large sparse symmetric positive denite linear systems on parallel com-puters I: general iterative scheme, SIAM J. Matrix Anal. 16 (1995) 1135-1153.

31. OLeary, D. The block conjugate gradient algorithm and related methods, Linear Algebra Appl. 29 (1980) 293-322.

32. Paige, C. C. and Saunders, M. A. LSQR: an algorithm for sparse linear equations and sparse least squares, ACM Trans. Math. Software 8 (1982)43-71.

33. Robbe, M. and Sadkane, M. Exact and inexact breakdowns in the block GMRES method, Linear Algebra Appl. 419 (2006) 265-285.

34. Saad, Y. Iterative methods for sparse linear systems, SIAM, 2nd edn,2003.

35. Saad, Y. On the Lanczos method for solving symmetric linear systems with several right-hand sides, Math. Comput. 48 (1987) 651-662.

36. Salkuyeh, D. K. CG-type algorithms to solve symmetric matrix equations, Appl. Math. Comput. 172 (2006) 985-999.

37. Simoncini, V. A stabilized QMR version of block BICG, SIAM J. Matrix Anal. Appl. 18 (1997) 419-434.

38. Simoncini, V. and Gallopoulos, E. Convergence properties of block GM-RES and matrix polynomials, Linear Algebra Appl. 247 (1996) 97-119.

39. Simoncini, V. and Gallopoulos, E. An iterative method for nonsymmetricsystems with multiple right-hand sides, SIAM J. Sci. Comput. 16 (1995)917-933.

40. Smith, C., Peterson, A. and Mittra, R. A conjugate gradient algorithmfor treatment of multiple incident electromagnetic elds, IEEE Trans.Antennas Propagation 37 (1989) 1490-1493.

41. Toutounian, F. and Karimi, S. Global least squares method (Gl-LSQR)for solving general linear systems with several right-hand sides, Appl.Math. Comput. 178 (2006) 452-460.

42. Van Der Vorst, H. An iterative solution method for solving f(A) = b, using Krylov subspace information obtained for the symmetric positive denite matrix A, J. Comput. Appl. 18 (1987) 249-263.

43. Vital, B. Etude de Quelques Methodes de Resolution de Problems Lineaires de Grande Taille sur Multiprocesseur, Ph.D. Thesis, Universite de Rennes, Rennes, France, 1990.

44. Zhang, J. and Dai, H. Global CGS algorithm for linear systems with multiple right-hand sides, Numer. Math. J. Chin. Univ. 30 (2008) 390-399 (in Chinese).

45. Zhang, J., Dai, H. and Zhao, J. A new family of global methods for linear systems with multiple right-hand sides, J. Comput. Appl. Math. 236 (2011) 1562-1575.

46. Zhang, J., Dai, H. and Zhao, J. Generalized global conjugate gradient squared algorithm, Appl. Math. Comput. 216 (2010) 3694-3706.