The Regularized Block GMERR Method and Its Simpler Version for Solving Large-Scale Linear Discrete Ill-Posed Problems

doi:10.1007/s42967-024-00405-x

Abstract

Abstract: Based on the block Arnoldi process and minimizing the Frobenius norm of the error, the block generalized minimal error (GMERR) method and its simpler version are proposed for solving large-scale linear systems of equations with multiple right-hand sides. However, little is known about the behavior of these methods when they are applied to the solution of linear discrete ill-posed problems with multiple right-hand sides contaminated by errors. In this paper, the regularizing properties of the block GMERR method and the simpler block GMERR method are examined. Both a regularized block GMERR method and a regularized simpler block GMERR method are developed for solving large-scale linear discrete ill-posed problems with multiple right-hand sides. Numerical experiments on typical test matrices show the efficiency of the proposed methods.

Key words: Linear discrete ill-posed problems, Multiple right-hand sides, Block generalized minimal error (GMERR) method, Simpler block GMERR method, Regularization

Hui Zhang, Hua Dai. The Regularized Block GMERR Method and Its Simpler Version for Solving Large-Scale Linear Discrete Ill-Posed Problems[J]. Communications on Applied Mathematics and Computation, 2025, 7(5): 1826-1847.

TrendMD

References

[1] Alqahtani, A., Gazzola, S., Reichel, L., Rodriguez, G.: On the block Lanczos and block Golub-Kahan reduction methods applied to discrete ill-posed problems. Numer. Linear Algebr. Appl. 28, e2376 (2021)
[2] Baglama, J.: Dealing with linear dependence during the iterations of the restarted block Lanczos methods. Numer. Algorithms 25, 23-36 (2000)
[3] Bai, Z.-Z.: Motivations and realizations of Krylov subspace methods for large sparse linear systems. J. Comput. Appl. Math. 283, 71-78 (2015)
[4] Bai, Z.-Z., Benzi, M., Chen, F.: Modified HSS iteration methods for a class of complex symmetric linear systems. Computing 87, 93-111 (2010)
[5] Bai, Z.-Z., Golub, G.H., Lu, L.-Z., Yin, J.-F.: Block triangular and skew-Hermitian splitting methods for positive-definite linear systems. SIAM J. Sci. Comput. 26, 844-863 (2005)
[6] Bai, Z.-Z., Golub, G.H., Ng, M.K.: Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems. SIAM J. Matrix Anal. Appl. 24, 603-626 (2003)
[7] Bai, Z.-Z., Golub, G.H., Pan, J.-Y.: Preconditioned Hermitian and skew-Hermitian splitting methods for non-Hermitian positive semidefinite linear systems. Numer. Math. 98, 1-32 (2004)
[8] Bai, Z.-Z., Pan, J.-Y.: Matrix Analysis and Computations. SIAM, Philadelphia (2021)
[9] Bentbib, A.H., El Guide, M., Jbilou, K.: The block Lanczos algorithm for linear ill-posed problems. Calcolo 54, 711-732 (2017)
[10] Brianzi, P., Favati, P., Menchi, O., Romani, F.: A framework for studying the regularizing properties of Krylov subspace methods. Inverse Prob. 22, 1007-1021 (2006)
[11] Buccini, A., Onisk, L., Reichel, L.: Range restricted iterative methods for linear discrete ill-posed problems. Electron. Trans. Numer. Anal. 58, 348-377 (2023)
[12] Calvetti, D., Lewis, B., Reichel, L.: GMRES, L-curve, and discrete ill-posed problems. BIT 42, 44-65 (2002)
[13] Calvetti, D., Lewis, B., Reichel, L.: On the regularizing properties of the GMRES method. Numer. Math. 91, 605-625 (2002)
[14] Calvetti, D., Morigi, S., Reichel, L., Sgallari, F.: Tikhonov regularization and the L-curve for large discrete ill-posed problems. J. Comput. Appl. Math. 123, 423-446 (2000)
[15] Carasso, A.S.: Determining surface temperatures from interior observations. SIAM J. Appl. Math. 42, 558-574 (1982)
[16] Cesa-Bianchi, N.: Applications of regularized least squares to pattern classification. Theoret. Comput. Sci. 382, 221-231 (2007)
[17] Daniel, G.W., Gragg, W.B., Kaufmann, L., Stewart, G.W.: Reorthogonalization and stable algorithms for updating the Gram-Schmidt QR factorization. Math. Comput. 30, 772-795 (1976)
[18] Freund, R.W., Malhotra, M.: A block QMR algorithm for non-Hermitian linear systems with multiple right-hand sides. Linear Algebra Appl. 254, 119-157 (1997)
[19] Freund, R.W., Nachtigal, N.M.: QMR: a quasi-minimal residual method for non-Hermitian linear systems. Numer. Math. 60, 315-339 (1991)
[20] Gazzola, S., Hansen, P.C., Nagy, J.G.: IR tools: a MATLAB package of iterative regularization methods and large-scale test problems. Numer. Algorithms 81, 773-811 (2019)
[21] Gazzola, S., Noschese, S., Novati, P., Reichel, L.: Arnoldi decomposition, GMRES, and preconditioning for linear discrete ill-posed problems. Appl. Numer. Math. 142, 102-121 (2019)
[22] Golub, G.H., Heath, M.T., Wahba, G.: Generalized cross-validation as a method for choosing a good ridge parameter. Technometrics 21, 215-223 (1979)
[23] Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. Johns Hopkins University Press, Baltimore (1996)
[24] Hansen, P.C.: The truncated SVD as a method for regularization. BIT 17, 534-553 (1987)
[25] Hansen, P.C.: Rank-Deficient and Discrete Ill-Posed Problems. SIAM, Philadelphia (1998)
[26] Hansen, P.C.: Regularization tools version 4.1 for Matlab 7.3. Numer. Algorithms 46, 189-194 (2007)
[27] Hansen, P.C., Dong, Y., Abe, K.: Hybrid enriched bidiagonalization for discrete ill-posed problems. Numer. Linear Algebra Appl. 26, e2230 (2019)
[28] Hoffmann, B.: Regularization for Applied Inverse and Ill-Posed Problems. B. G. Teubner Verlag, Leipzig (1986)
[29] Huang, Y., Jia, Z.-X.: Some results on the regularization of LSQR for large-scale discrete ill-posed problems. Sci. China Math. 60, 701-718 (2017)
[30] Huang, Y., Jia, Z.-X.: On regularizing effects of MINRES and MR-II for large scale symmetric discrete ill-posed problems. J. Comput. Appl. Math. 320, 145-163 (2017)
[31] Jensen, T.K., Hansen, P.C.: Iterative regularization with minimum-residual methods. BIT Numer. Math. 47, 103-120 (2007)
[32] Karimi, S., Toutounian, F.: The block least squares method for solving nonsymmetric linear systems with multiple right-hand sides. Appl. Math. Comput. 177, 852-862 (2006)
[33] Kilmer, M.E., Hansen, P.C., Espanol, M.I.: A projection-based approach to general-form Tikhonov regularization. SIAM J. Sci. Comput. 29, 315-330 (2007)
[34] Kilmer, M.E., O’Leary, D.P.: Choosing regularization parameters in iterative methods for ill-posed problems. SIAM J. Matrix Anal. Appl. 22, 1204-1221 (2001)
[35] Kilmer, M.E., Stewart, G.W.: Iterative regularization and MINRES. SIAM J. Matrix Anal. Appl. 21, 613-628 (1999)
[36] Lewis, B., Reichel, L.: Arnoldi-Tikhonov regularization methods. J. Comput. Appl. Math. 226, 92-102 (2009)
[37] Liu, H., Zhong, B.: Simpler block GMRES for nonsymmetric systems with multiple right-hand sides. Electron. Trans. Numer. Anal. 30, 1-9 (2008)
[38] Morozov, V.A.: Methods for Solving Incorrectly Posed Problems. Springer, New York (1984)
[39] Nagy, J.G., O’Leary, D.P.: Restoring images degraded by spatially-variant blur. SIAM J. Sci. Comput. 19, 1063-1082 (1998)
[40] Novati, P., Russo, M.R.: A GCV based Arnoldi-Tikhonov regularization method. BIT Numer. Math. 54, 501-521 (2014)
[41] Onisk, L., Reichel, L., Sadok, H.: Numerical considerations of block GMRES methods when applied to linear discrete ill-posed problems. J. Comput. Appl. Math. 430, 115262 (2023)
[42] Paige, C.C., Saunders, M.A.: Solution of sparse indefinite systems of linear equations. SIAM J. Numer. Anal. 12, 617-629 (1975)
[43] Paige, C.C., Saunders, M.A.: LSQR: an algorithm for sparse linear equations and sparse least squares. ACM Trans. Math. Software 8, 43-71 (1982)
[44] Rozloznik, M., Weiss, R.: On the stable implementation of the generalizalized minimal error method. J. Comput. Appl. Math. 98, 49-62 (1998)
[45] Saad, Y.: Iterative Methods for Sparse Linear Systems, 2nd edn. SIAM, Philadelphia (2003)
[46] Saad, Y., Schultz, M.H.: GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Stat. Comput. 7, 856-869 (1986)
[47] Smith, C.F., Peterson, A.F., Mittra, R.: A conjugate gradient algorithm for the treatment of multiple incident electromagnetic fields. IEEE Trans. Antennas Propag. 37, 1490-1493 (1989)
[48] Soodhalter, K.M.: A block MINRES algorithm based on the band Lanczos method. Numer. Algorithms 69, 473-494 (2015)
[49] Sun, J.-G.: Perturbation bounds for the Cholesky and QR factorizations. BIT 31, 341-352 (1991)
[50] Sun, J.-G.: Matrix Perturbation Analysis (in Chinese), 2nd edn. Science Press, Beijing (2001)
[51] Tikhonov, A.N.: Solution of incorrectly formulated problems and the regularization method. Soviet Mathematics Doklady 4, 1035-1038 (1963)
[52] Van der Vorst, H.A.: Bi-CGSTAB: a fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems. SIAM J. Sci. Statist. Comput. 13, 631-644 (1992)
[53] Vital, B.: Etude de quelques méthodes de résolution de problèmes linéaires de grande taille sur multiprocesseur. Ph.D. Thesis, Univérsité de Rennes, Rennes, France (1990)
[54] Wang, G., Wei, Y., Qiao, S.: Generalized Inverses: Theory and Computations. Science Press, Beijing (2004)
[55] Wang, Q., Dai, H.: A regularizing GMERR method for solving discrete ill-posed problems (in Chinese). Math. Numer. Sin. 35, 195-204 (2013)
[56] Weiss, R.: Error-minimizing Krylov subspace method. SIAM J. Sci. Comput. 15, 511-527 (1994)
[57] Zhang, X., Dai, H.: Block GMERR method and its variant for solving linear systems with multiple right-hand sides (in Chinese). Numer. Math. J. Chinese Univ. 45, 56-71 (2023)