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

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.

Keywords

Linear discrete ill-posed problems / Multiple right-hand sides / Block generalized minimal error (GMERR) method / Simpler block GMERR method / Regularization / 65F10 / 65F22

References

[1] AlqahtaniA, GazzolaS, ReichelL, RodriguezG. On the block Lanczos and block Golub-Kahan reduction methods applied to discrete ill-posed problems. Numer. Linear Algebr. Appl., 2021, 28e2376

[2] BaglamaJ. Dealing with linear dependence during the iterations of the restarted block Lanczos methods. Numer. Algorithms, 2000, 25: 23-36

[3] BaiZ-Z. Motivations and realizations of Krylov subspace methods for large sparse linear systems. J. Comput. Appl. Math., 2015, 283: 71-78

[4] BaiZ-Z, BenziM, ChenF. Modified HSS iteration methods for a class of complex symmetric linear systems. Computing, 2010, 87: 93-111

[5] BaiZ-Z, GolubGH, LuL-Z, YinJ-F. Block triangular and skew-Hermitian splitting methods for positive-definite linear systems. SIAM J. Sci. Comput., 2005, 26: 844-863

[6] BaiZ-Z, GolubGH, NgMK. Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems. SIAM J. Matrix Anal. Appl., 2003, 24: 603-626

[7] BaiZ-Z, GolubGH, PanJ-Y. Preconditioned Hermitian and skew-Hermitian splitting methods for non-Hermitian positive semidefinite linear systems. Numer. Math., 2004, 98: 1-32

[8] BaiZ-Z, PanJ-YMatrix Analysis and Computations, 2021, Philadelphia. SIAM.

[9] BentbibAH, El GuideM, JbilouK. The block Lanczos algorithm for linear ill-posed problems. Calcolo, 2017, 54: 711-732

[10] BrianziP, FavatiP, MenchiO, RomaniF. A framework for studying the regularizing properties of Krylov subspace methods. Inverse Prob., 2006, 22: 1007-1021

[11] BucciniA, OniskL, ReichelL. Range restricted iterative methods for linear discrete ill-posed problems. Electron. Trans. Numer. Anal., 2023, 58: 348-377

[12] CalvettiD, LewisB, ReichelL. GMRES, L-curve, and discrete ill-posed problems. BIT, 2002, 42: 44-65

[13] CalvettiD, LewisB, ReichelL. On the regularizing properties of the GMRES method. Numer. Math., 2002, 91: 605-625

[14] CalvettiD, MorigiS, ReichelL, SgallariF. Tikhonov regularization and the L-curve for large discrete ill-posed problems. J. Comput. Appl. Math., 2000, 123: 423-446

[15] CarassoAS. Determining surface temperatures from interior observations. SIAM J. Appl. Math., 1982, 42: 558-574

[16] Cesa-BianchiN. Applications of regularized least squares to pattern classification. Theoret. Comput. Sci., 2007, 382: 221-231

[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] FreundRW, MalhotraM. A block QMR algorithm for non-Hermitian linear systems with multiple right-hand sides. Linear Algebra Appl., 1997, 254: 119-157

[19] FreundRW, NachtigalNM. QMR: a quasi-minimal residual method for non-Hermitian linear systems. Numer. Math., 1991, 60: 315-339

[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] GazzolaS, NoscheseS, NovatiP, ReichelL. Arnoldi decomposition, GMRES, and preconditioning for linear discrete ill-posed problems. Appl. Numer. Math., 2019, 142: 102-121

[22] GolubGH, HeathMT, WahbaG. Generalized cross-validation as a method for choosing a good ridge parameter. Technometrics, 1979, 21: 215-223

[23] GolubGH, Van LoanCFMatrix Computations, 19963Baltimore. Johns Hopkins University Press.

[24] HansenPC. The truncated SVD as a method for regularization. BIT, 1987, 17: 534-553

[25] HansenPCRank-Deficient and Discrete Ill-Posed Problems, 1998, Philadelphia. SIAM.

[26] Hansen, P.C.: Regularization tools version 4.1 for Matlab 7.3. Numer. Algorithms 46, 189–194 (2007)

[27] HansenPC, DongY, AbeK. Hybrid enriched bidiagonalization for discrete ill-posed problems. Numer. Linear Algebra Appl., 2019, 26e2230

[28] HoffmannBRegularization for Applied Inverse and Ill-Posed Problems, 1986, Leipzig. B. G. Teubner Verlag.

[29] HuangY, JiaZ-X. Some results on the regularization of LSQR for large-scale discrete ill-posed problems. Sci. China Math., 2017, 60: 701-718

[30] HuangY, JiaZ-X. On regularizing effects of MINRES and MR-II for large scale symmetric discrete ill-posed problems. J. Comput. Appl. Math., 2017, 320: 145-163

[31] JensenTK, HansenPC. Iterative regularization with minimum-residual methods. BIT Numer. Math., 2007, 47: 103-120

[32] KarimiS, ToutounianF. The block least squares method for solving nonsymmetric linear systems with multiple right-hand sides. Appl. Math. Comput., 2006, 177: 852-862

[33] KilmerME, HansenPC, EspanolMI. A projection-based approach to general-form Tikhonov regularization. SIAM J. Sci. Comput., 2007, 29: 315-330

[34] KilmerME, O’LearyDP. Choosing regularization parameters in iterative methods for ill-posed problems. SIAM J. Matrix Anal. Appl., 2001, 22: 1204-1221

[35] KilmerME, StewartGW. Iterative regularization and MINRES. SIAM J. Matrix Anal. Appl., 1999, 21: 613-628

[36] LewisB, ReichelL. Arnoldi-Tikhonov regularization methods. J. Comput. Appl. Math., 2009, 226: 92-102

[37] LiuH, ZhongB. Simpler block GMRES for nonsymmetric systems with multiple right-hand sides. Electron. Trans. Numer. Anal., 2008, 30: 1-9

[38] MorozovVAMethods for Solving Incorrectly Posed Problems, 1984, New York. Springer.

[39] NagyJG, O’LearyDP. Restoring images degraded by spatially-variant blur. SIAM J. Sci. Comput., 1998, 19: 1063-1082

[40] NovatiP, RussoMR. A GCV based Arnoldi-Tikhonov regularization method. BIT Numer. Math., 2014, 54: 501-521

[41] OniskL, ReichelL, SadokH. Numerical considerations of block GMRES methods when applied to linear discrete ill-posed problems. J. Comput. Appl. Math., 2023, 430115262

[42] PaigeCC, SaundersMA. Solution of sparse indefinite systems of linear equations. SIAM J. Numer. Anal., 1975, 12: 617-629

[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] RozloznikM, WeissR. On the stable implementation of the generalizalized minimal error method. J. Comput. Appl. Math., 1998, 98: 49-62

[45] SaadYIterative Methods for Sparse Linear Systems, 20032Philadelphia. SIAM.

[46] SaadY, SchultzMH. GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Stat. Comput., 1986, 7: 856-869

[47] SmithCF, PetersonAF, MittraR. A conjugate gradient algorithm for the treatment of multiple incident electromagnetic fields. IEEE Trans. Antennas Propag., 1989, 37: 1490-1493

[48] Soodhalter, K.M.: A block MINRES algorithm based on the band Lanczos method. Numer. Algorithms 69, 473–494 (2015)

[49] SunJ-G. Perturbation bounds for the Cholesky and QR factorizations. BIT, 1991, 31: 341-352

[50] SunJ-GMatrix Perturbation Analysis (in Chinese), 20012Beijing. Science Press.

[51] TikhonovAN. Solution of incorrectly formulated problems and the regularization method. Soviet Mathematics Doklady, 1963, 4: 1035-1038

[52] Van der VorstHA. Bi-CGSTAB: a fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems. SIAM J. Sci. Statist. Comput., 1992, 13: 631-644

[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] WangG, WeiY, QiaoSGeneralized Inverses: Theory and Computations, 2004, Beijing. Science Press.

[55] WangQ, DaiH. A regularizing GMERR method for solving discrete ill-posed problems (in Chinese). Math. Numer. Sin., 2013, 35: 195-204

[56] WeissR. Error-minimizing Krylov subspace method. SIAM J. Sci. Comput., 1994, 15: 511-527

[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)

Funding

National Natural Science Foundation of China(No.11571171)

RIGHTS & PERMISSIONS

Shanghai University