On Error Estimation in the Conjugate Gradient Method and why it Works in Finite Precision Computations

0404211 - UIVT-O 20020143 RIV US eng J - Journal Article
Strakoš, Zdeněk - Tichý, Petr
On Error Estimation in the Conjugate Gradient Method and why it Works in Finite Precision Computations.
Electronic Transactions on Numerical Analysis. Roč. 13, - (2002), s. 56-80. ISSN 1068-9613. E-ISSN 1068-9613
R&D Projects: GA ČR GA201/02/0595
Institutional research plan: AV0Z1030915
Keywords : conjugate gradient method * Gauss kvadrature * evaluation of convergence * error bounds * finite precision arithmetic * rounding errors * loss of orthogonality
Subject RIV: BA - General Mathematics
Impact factor: 0.565, year: 2002
http://etna.mcs.kent.edu/volumes/2001-2010/vol13/abstract.php?vol=13&pages=56-80

Cited: 47

--- ARIOLI, M. - MANZINI, G. A network programming approach in solving Darcy's equations by mixed finite-element methods. ELECTRONIC TRANSACTIONS ON NUMERICAL ANALYSIS. ISSN 1068-9613, 2006, vol. 22, p. 41-70. [WOS]
--- MEURANT, G. Estimates of the l(2) norm of the error in the conjugate gradient algorithm. NUMERICAL ALGORITHMS. ISSN 1017-1398, OCT 2005, vol. 40, no. 2, p. 157-169. [WOS]
--- WULLING, W. The stabilization of weights in the Lanczos and Conjugate Gradient method. BIT NUMERICAL MATHEMATICS. ISSN 0006-3835, JUN 2005, vol. 45, no. 2, p. 395-414. [WOS]
--- ARIOLI, M. - LOGHIN, D. - WATHEN, A.J. Stopping criteria for iterations in finite element methods. NUMERISCHE MATHEMATIK. ISSN 0029-599X, JAN 2005, vol. 99, no. 3, p. 381-410. [WOS]
--- SIMONCINI, V. - SZYLD, D.B. Recent computational developments in Krylov subspace methods for linear systems. NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS. ISSN 1070-5325, FEB 2007, vol. 14, no. 1, p. 1-59. [WOS]
--- Meurant, G., The Lanczos and conjugate gradient algorithms. From theory to finite precision computations. Software, Environments, and Tools, 19. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2006
--- FROMMER, A. MONOTONE CONVERGENCE OF THE LANCZOS APPROXIMATIONS TO MATRIX FUNCTIONS OF HERMITIAN MATRICES. ELECTRONIC TRANSACTIONS ON NUMERICAL ANALYSIS. ISSN 1068-9613, 2009, vol. 35, p. 118-128. [WOS]
--- DIENE, O. - BHAYA, A. A Study of the Robustness of Iterative Methods for Linear Systems. NUMERICAL ANALYSIS AND APPLIED MATHEMATICS, VOLS 1 AND 2. ISSN 0094-243X, 2009, vol. 1168, p. 440-443. [WOS]
--- GOLUB, G.H. - STOLL, M. - WATHEN, A. APPROXIMATION OF THE SCATTERING AMPLITUDE AND LINEAR SYSTEMS. ELECTRONIC TRANSACTIONS ON NUMERICAL ANALYSIS. ISSN 1068-9613, 2008, vol. 31, p. 178-203. [WOS]
--- CHANG, X.W. - PAIGE, C.C. - TITLEY-PELOQUIN, D. STOPPING CRITERIA FOR THE ITERATIVE SOLUTION OF LINEAR LEAST SQUARES PROBLEMS. SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS. ISSN 0895-4798, 2009, vol. 31, no. 2, p. 831-852. [WOS]
--- BOUYOULI, R. - MEURANT, G. - SMOCH, L. - SADOK, H. New results on the convergence of the conjugate gradient method. NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS. ISSN 1070-5325, MAR 2009, vol. 16, no. 3, p. 223-236. [WOS]
--- BURNEY, S.M.A. - JILANI, T.A. - ARDIL, C. A Comparison of First and Second Order Training Algorithms for Artificial Neural Networks. PROCEEDINGS OF WORLD ACADEMY OF SCIENCE, ENGINEERING AND TECHNOLOGY, VOL 1. ISSN 1307-6884, 2005, vol. 1, p. 9-15. [WOS]
--- DANILOV, D. - MAGNUS, J.R. On the estimation of a large sparse Bayesian system: The Snaer program. COMPUTATIONAL STATISTICS & DATA ANALYSIS. ISSN 0167-9473, MAY 15 2008, vol. 52, no. 9, p. 4203-4224. [WOS]
--- FROMMER, A. - SIMONCINI, V. Stopping criteria for rational matrix functions of Hermitian and symmetric matrices. SIAM JOURNAL ON SCIENTIFIC COMPUTING. ISSN 1064-8275, 2007, vol. 30, no. 3, p. 1387-1412. [WOS]
--- JIRANEK, P. - ROZLOZNIK, M. Maximum attainable accuracy of inexact saddle point solvers. SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS. ISSN 0895-4798, 2006, vol. 29, no. 4, p. 1297-1321. [WOS]
--- VAN DEN ESHOF, J. - SLEIJPEN, G.L.G. Accurate conjugate gradient methods for families of shifted systems. APPLIED NUMERICAL MATHEMATICS. ISSN 0168-9274, APR 2004, vol. 49, no. 1, p. 17-37. [WOS]
--- ARIOLI, M. - MANZINI, G. Null space algorithm and spanning trees in solving Darcy's equation. BIT. ISSN 0006-3835, 2003, vol. 43, p. 839-848. [WOS]
--- ARIOLI, M. A stopping criterion for the conjugate gradient algorithm in a finite element method framework. NUMERISCHE MATHEMATIK. ISSN 0029-599X, MAR 2004, vol. 97, no. 1, p. 1-24. [WOS]
--- ARIOLI, M. - MANZINI, G. Null space algorithm and spanning trees in solving Darcy's equation. BIT. ISSN 0006-3835, 2003, vol. 43, no. 5, p. 839-848. [WOS]
--- ORTIGOSA, E.M. - ROMERO, L.F. - RAMOS, J.I. Parallel scheduling of the PCG method for banded matrices rising from FDM/FEM. JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING. ISSN 0743-7315, DEC 2003, vol. 63, no. 12, p. 1243-1256. [WOS]
--- SILVESTER, D.J. - SIMONCINI, V. An Optimal Iterative Solver for Symmetric Indefinite Systems Stemming from Mixed Approximation. ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE. ISSN 0098-3500, FEB 2011, vol. 37, no. 4. [WOS]
--- MEURANT, G. ESTIMATES OF THE NORM OF THE ERROR IN SOLVING LINEAR SYSTEMS WITH FOM AND GMRES. SIAM JOURNAL ON SCIENTIFIC COMPUTING. ISSN 1064-8275, 2011, vol. 33, no. 5, p. 2686-2705. [WOS]
--- BRUNNER, D.O. - PRUESSMANN, K.P. Optimal Design of Multiple-Channel RF Pulses Under Strict Power and SAR Constraints. MAGNETIC RESONANCE IN MEDICINE. ISSN 0740-3194, MAY 2010, vol. 63, no. 5, p. 1280-1291. [WOS]
--- JIRANEK, P. - TITLEY-PELOQUIN, D. ESTIMATING THE BACKWARD ERROR IN LSQR. SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS. ISSN 0895-4798, 2010, vol. 31, no. 4, p. 2055-2074. [WOS]
--- GOLUB, G.H. - MEURANT, G. Matrices, Moments and Quadrature with Applications. MATRICES, MOMENTS AND QUADRATURE WITH APPLICATIONS. 2010, p. 1-363. [WOS]
--- VANNIEUWENHOVEN, N. - VANDEBRIL, R. - MEERBERGEN, K. A randomized algorithm for testing nonsingularity of structured matrices with an application to asserting nondefectivity of Segre varieties. IMA JOURNAL OF NUMERICAL ANALYSIS. ISSN 0272-4979, JAN 2015, vol. 35, no. 1, p. 289-324. [WOS]
--- KRESSNER, D. - PLESINGER, M. - TOBLER, C. A preconditioned low-rank CG method for parameter-dependent Lyapunov matrix equations. NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS. ISSN 1070-5325, OCT 2014, vol. 21, no. 5, p. 666-684. [WOS]
--- NAESS, S.K. - LOUIS, T. A fast map-making preconditioner for regular scanning patterns. JOURNAL OF COSMOLOGY AND ASTROPARTICLE PHYSICS. ISSN 1475-7516, AUG 2014, no. 8. [WOS]
--- AXELSSON, O. - KARATSON, J. Reaching the superlinear convergence phase of the CG method. JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS. ISSN 0377-0427, APR 2014, vol. 260, p. 244-257. [WOS]
--- DU, L. - FUTAMURA, Y. - SAKURAI, T. Block conjugate gradient type methods for the approximation of bilinear form C(H)A(-1)B. COMPUTERS & MATHEMATICS WITH APPLICATIONS. ISSN 0898-1221, JAN 2014, vol. 66, no. 12, p. 2446-2455. [WOS]
--- ZLATEV, Z. - GEORGIEV, K. Applying approximate LU-factorizations as preconditioners in eight iterative methods for solving systems of linear algebraic equations. CENTRAL EUROPEAN JOURNAL OF MATHEMATICS. ISSN 1895-1074, AUG 2013, vol. 11, no. 8, p. 1510-1530. [WOS]
--- FROMMER, A. - KAHL, K. - LIPPERT, T. - RITTICH, H. 2-NORM ERROR BOUNDS AND ESTIMATES FOR LANCZOS APPROXIMATIONS TO LINEAR SYSTEMS AND RATIONAL MATRIX FUNCTIONS. SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS. ISSN 0895-4798, 2013, vol. 34, no. 3, p. 1046-1065. [WOS]
--- ARIOLI, M. GENERALIZED GOLUB-KAHAN BIDIAGONALIZATION AND STOPPING CRITERIA. SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS. ISSN 0895-4798, 2013, vol. 34, no. 2, p. 571-592. [WOS]
--- ARIOLI, M. - GEORGOULIS, E.H. - LOGHIN, D. STOPPING CRITERIA FOR ADAPTIVE FINITE ELEMENT SOLVERS. SIAM JOURNAL ON SCIENTIFIC COMPUTING. ISSN 1064-8275, 2013, vol. 35, no. 3, p. A1537-A1559. [WOS]
--- WU, P. - LIU, K. - ZHANG, Q. - XUE, Z.W. - LI, Y.B. - NING, N.A. - YANG, X. - LI, X.D. - TIAN, J. Detection of mouse liver cancer via a parallel iterative shrinkage method in hybrid optical/microcomputed tomography imaging. JOURNAL OF BIOMEDICAL OPTICS. ISSN 1083-3668, DEC 2012, vol. 17, no. 12. [WOS]
--- ARIOLI, M. - GRATTON, S. Linear regression models, least-squares problems, normal equations, and stopping criteria for the conjugate gradient method. COMPUTER PHYSICS COMMUNICATIONS. ISSN 0010-4655, NOV 2012, vol. 183, no. 11, p. 2322-2336. [WOS]
--- GEORGIEV, K. - ZLATEV, Z. Numerical Experiments with Applying Approximate LU-factorizations as Preconditioners for Solving SLAEs with Coefficient Matrices from the "Sparse Matrix Market". APPLICATION OF MATHEMATICS IN TECHNICAL AND NATURAL SCIENCES. ISSN 0094-243X, 2012, vol. 1487, p. 104-111. [WOS]
--- COOLS, S. - VANROOSE, W. The communication-hiding pipelined BiCGstab method for the parallel solution of large unsymmetric linear systems. PARALLEL COMPUTING. ISSN 0167-8191, JUL 2017, vol. 65, p. 1-20. [WOS]
--- GAAF, S.W. - SIMONCINI, V. Approximating the leading singular triplets of a large matrix function. APPLIED NUMERICAL MATHEMATICS. ISSN 0168-9274, MAR 2017, vol. 113, p. 26-43. [WOS]
--- ALIAGA, J.I. - BADIA, R.M. - BARREDA, M. - BOLLHOFER, M. - DUFRECHOU, E. - EZZATTI, P. - QUINTANA-ORTI, E.S. Exploiting task and data parallelism in ILUPACK's preconditioned CG solver on NUMA architectures and many-core accelerators. PARALLEL COMPUTING. ISSN 0167-8191, MAY 2016, vol. 54, SI, p. 97-107. [WOS]
--- DIENE, O. - BHAYA, A. On the robustness of numerical algorithms for linear systems and signal processing in finite precision arithmetic. INTERNATIONAL JOURNAL OF ADAPTIVE CONTROL AND SIGNAL PROCESSING. ISSN 0890-6327, DEC 2015, vol. 29, no. 12, p. 1539-1560. [WOS]
--- GOTSCHEL, S. - WEISER, M. Lossy compression for PDE-constrained optimization: adaptive error control. COMPUTATIONAL OPTIMIZATION AND APPLICATIONS. ISSN 0926-6003, SEP 2015, vol. 62, no. 1, SI, p. 131-155. [WOS]
--- COOLS, S. Analyzing and improving maximal attainable accuracy in the communication hiding pipelined BiCGStab method. PARALLEL COMPUTING. ISSN 0167-8191, AUG 2019, vol. 86, p. 16-35. [WOS]
--- ESTRIN, R. - ORBAN, D. - SAUNDERS, M. EUCLIDEAN-NORM ERROR BOUNDS FOR SYMMLQ AND CG. SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS. ISSN 0895-4798, 2019, vol. 40, no. 1, p. 235-253. [WOS]
--- ESTRIN, R. - ORBAN, D. - SAUNDERS, M.A. LSLQ: AN ITERATIVE METHOD FOR LINEAR LEAST-SQUARES WITH AN ERROR MINIMIZATION PROPERTY. SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS. ISSN 0895-4798, 2019, vol. 40, no. 1, p. 254-275. [WOS]
--- ROBINI, M.C. - YANG, F. - ZHU, Y.M. Inexact Half-Quadratic Optimization for Linear Inverse Problems. SIAM JOURNAL ON IMAGING SCIENCES. ISSN 1936-4954, 2018, vol. 11, no. 2, p. 1078-1133. [WOS]
--- COOLS, S. - YETKIN, E.F. - AGULLO, E. - GIRAUD, L. - VANROOSE, W. ANALYZING THE EFFECT OF LOCAL ROUNDING ERROR PROPAGATION ON THE MAXIMAL ATTAINABLE ACCURACY OF THE PIPELINED CONJUGATE GRADIENT METHOD. SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS. ISSN 0895-4798, 2018, vol. 39, no. 1, p. 426-450. [WOS]

Permanent Link: http://hdl.handle.net/11104/0124477