Geodesic
Error estimators and their analysis for CG, Bi-CG and GMRES
Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 26 (2023) no. 2, pp. 161-181 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The demands of accuracy in measurements and engineering models today render the condition number of problems larger. While a corresponding increase in the precision of floating point numbers ensured a stable computing, the uncertainty in convergence when using residue as a stopping criterion has increased. We present an analysis of the uncertainty in convergence when using relative residue as a stopping criterion for iterative solution of linear systems, and the resulting over/under computation for a given tolerance in error. This shows that error estimation is significant for an efficient or accurate solution even when the condition number of the matrix is not large. An $\mathcal{O}(1)$ error estimator for iterations of the CG algorithm was proposed more than two decades ago. Recently, an $\mathcal{O}(k^2)$ error estimator was described for the GMRES algorithm which allows for non-symmetric linear systems as well, where $k$ is the iteration number. We suggest a minor modification in this GMRES error estimation for increased stability. In this work, we also propose an $\mathcal{O}(n)$ error estimator for $A$-norm and $l_2$-norm of the error vector in Bi-CG algorithm. The robust performance of these estimates as a stopping criterion results in increased savings and accuracy in computation, as condition number and size of problems increase. 
@article{SJVM_2023_26_2_a3,
     author = {P. Jain and K. Manglani and M. Venkatapathi},
     title = {Error estimators and their analysis for {CG,} {Bi-CG} and {GMRES}},
     journal = {Sibirskij \v{z}urnal vy\v{c}islitelʹnoj matematiki},
     pages = {161--181},
     year = {2023},
     volume = {26},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SJVM_2023_26_2_a3/}
}
TY  - JOUR
AU  - P. Jain
AU  - K. Manglani
AU  - M. Venkatapathi
TI  - Error estimators and their analysis for CG, Bi-CG and GMRES
JO  - Sibirskij žurnal vyčislitelʹnoj matematiki
PY  - 2023
SP  - 161
EP  - 181
VL  - 26
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/SJVM_2023_26_2_a3/
LA  - ru
ID  - SJVM_2023_26_2_a3
ER  - 
%0 Journal Article
%A P. Jain
%A K. Manglani
%A M. Venkatapathi
%T Error estimators and their analysis for CG, Bi-CG and GMRES
%J Sibirskij žurnal vyčislitelʹnoj matematiki
%D 2023
%P 161-181
%V 26
%N 2
%U http://geodesic.mathdoc.fr/item/SJVM_2023_26_2_a3/
%G ru
%F SJVM_2023_26_2_a3
P. Jain; K. Manglani; M. Venkatapathi. Error estimators and their analysis for CG, Bi-CG and GMRES. Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 26 (2023) no. 2, pp. 161-181. http://geodesic.mathdoc.fr/item/SJVM_2023_26_2_a3/

[1] Bjorck A., Numerical Methods in Matrix Computations, 1st ed., Springer, Cham, 2015 | DOI | MR | Zbl

[2] Brezinski C., “Error estimates for the solution of linear systems”, SIAM J. Sci. Comput., 21:2 (1999), 764–781 | DOI | MR | Zbl

[3] Brezinski C., Rodriguez G., Seatzu S., “Error estimates for linear systems with applications to regularization”, Numerical Algorithms, 49:1-4 (2008), 85–104 | DOI | MR | Zbl

[4] Fletcher R., “Conjugate gradient methods for indefinite systems”, Numerical Analysis, Lect. Notes in Mathematics, 506, Springer, 1976, 73–89 | DOI | MR

[5] Freund R.W., Nachtigal N.M., “QMR: a quasi-minimal residual method for non-Hermitian linear systems”, Numerische Mathematik, 60:1 (1991), 315–339 | DOI | MR | Zbl

[6] Golub G.H., Meurant G., “Matrices, moments and quadrature II; how to compute the norm of the error in iterative methods”, BIT Numerical Mathematics, 37:3 (1997), 687–705 | DOI | MR | Zbl

[7] Hestenes M.R., Stiefel E., “Methods of conjugate gradients for solving linear systems”, J. Research NBS, 49:6 (1952), 409–436 | MR | Zbl

[8] Meurant G., “The computation of bounds for the norm of the error in the conjugate gradient algorithm”, Numerical Algorithms, 16:1 (1997), 77–87 | DOI | MR | Zbl

[9] Meurant G., “Estimates of the $l_2$ norm of the error in the conjugate gradient algorithm”, Numerical Algorithms, 40:2 (2005), 157–169 | DOI | MR | Zbl

[10] Meurant G., “Estimates of the norm of the error in solving linear systems with FOM and GMRES”, SIAM J. Sci. Comput., 33:5 (2011), 2686–2705 | DOI | MR | Zbl

[11] Meurant G., Strakos Z., “The Lanczos and conjugate gradient algorithms in nite precision arithmetic”, Acta Numer., 15 (2006), 471–542 | DOI | MR | Zbl

[12] Meurant G., Tichy P., “On computing quadrature-based bounds for the A-norm of the error in conjugate gradients”, Numerical Algorithms, 62:2 (2013), 163–191 | DOI | MR | Zbl

[13] Saad Y., “Preconditioning techniques for nonsymmetric and indefinite linear systems”, J. Comput. Appl. Mathematics, 24:1-2 (1988), 89–105 | DOI | MR | Zbl

[14] Saad Y., Schultz M.H., “GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems”, SIAM J. Sci. and Stat. Comput., 7:3 (1986), 856–869 | DOI | MR | Zbl

[15] Saylor P.E., Smolarski D.C., Why Gaussian quadrature in the complex plane?, Numerical Algorithms, 26:3 (2001), 251–280 | DOI | MR | Zbl

[16] Sleijpen G.L., Fokkema D.R., “BiCGstab(l) for linear equations involving unsymmetric matrices with complex spectrum”, Electronic Transactions on Numerical Analysis, 1 (1993), 11–32 | MR | Zbl

[17] Sleijpen G.L., Van der Vorst H.A., Fokkema D.R., “BiCGstab(l) and other hybrid BI-CG methods”, Numerical Algorithms, 7:1 (1994), 75–109 | DOI | MR | Zbl

[18] Strakos Z., Tichy P., “Error estimation in preconditioned conjugate gradients”, BIT Numerical Mathematics, 45:4 (2005), 789–817 | DOI | MR | Zbl

[19] Trefethen L.N., Bau III D., Numerical Linear Algebra, SIAM, 1997 | MR | Zbl

[20] 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. and Stat. Comput., 13:2 (1992), 631–644 | DOI | MR | Zbl