[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Estimating error norms in CG-like algorithms for least-squares and least-norm problems

  • Original Paper
  • Published:
Numerical Algorithms Aims and scope Submit manuscript

Abstract

In Meurant et al. (Numer. Algorithms 88(3), 1337–1359, 2021), we presented an adaptive estimate for the energy norm of the error in the conjugate gradient (CG) method. Here we consider algorithms for solving linear approximation problems with a general, possibly rectangular matrix that are based on applying CG to a system with a positive (semi-)definite matrix built from the original matrix. We discuss algorithms based on Hestenes–Stiefel-like implementation (often called CGLS and CGNE in the literature) as well as on bidiagonalization (LSQR and CRAIG), and both unpreconditioned and preconditioned variants. Each algorithm minimizes a certain quantity at each iteration (within the current Krylov subspace), that is related to some error norm. We call this “the quantity of interest”. We show that the adaptive estimate used in CG can be extended for these algorithms to estimate the quantity of interest. Throughout, we emphasize the applicability of the estimate during computations in finite-precision arithmetic. We carefully derive the relations from which the estimate is constructed, without exploiting the global orthogonality that is not preserved during computation. We show that the resulting estimate preserves its key properties: it can be cheaply evaluated, and it is numerically reliable in finite-precision arithmetic under some mild assumptions. These properties make the estimate suitable for use in stopping the iterations. The numerical experiments confirm the robustness and satisfactory behaviour of the estimate.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Algorithm 1
Algorithm 2
Algorithm 3
Algorithm 4
Algorithm 5
Fig. 1
Algorithm 6
Algorithm 7
Algorithm 8
Algorithm 9
Algorithm 10
Algorithm 11
Algorithm 12
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Data Availability

All data generated or analysed during this study are available from the corresponding author on reasonable request.

References

  1. Liesen, J., Strakoš, Z.: Krylov Subspace Methods. Numerical Mathematics and Scientific Computation. Oxford University Press, Oxford (2013)

    Google Scholar 

  2. Meurant, G., Papež, J., Tichý, P.: Accurate error estimation in CG. Numer. Algorithms 88(3), 1337–1359 (2021). https://doi.org/10.1007/s11075-021-01078-w

    Article  MathSciNet  Google Scholar 

  3. Strakoš, Z., Tichý, P.: On error estimation in the conjugate gradient method and why it works in finite precision computations. Electron. Trans. Numer. Anal. 13, 56–80 (2002)

    MathSciNet  Google Scholar 

  4. Meurant, G.: The Lanczos and Conjugate Gradient Algorithms, from Theory to Finite Precision Computations. SIAM, Philadelphia (2006)

    Book  Google Scholar 

  5. Greenbaum, A.: Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences. Linear Algebra Appl. 113, 7–63 (1989)

    Article  MathSciNet  Google Scholar 

  6. Sleijpen, G.L.G., van der Vorst, H.A., Fokkema, D.R.: BiCGstab(l) and other hybrid Bi-CG methods. Numer. Algorithms 7(1), 75–109 (1994)

    Article  MathSciNet  Google Scholar 

  7. Jiránek, P., Titley-Peloquin, D.: Estimating the backward error in LSQR. SIAM J. Matrix Anal. Appl. 31(4), 2055–2074 (2009/10). https://doi.org/10.1137/090770655

  8. Arioli, M., Gratton, S.: Linear regression models, least-squares problems, normal equations, and stopping criteria for the conjugate gradient method. Comput. Phys. Commun. 183(11), 2322–2336 (2012). https://doi.org/10.1016/j.cpc.2012.05.023

    Article  MathSciNet  Google Scholar 

  9. Arioli, M.: Generalized Golub-Kahan bidiagonalization and stopping criteria. SIAM J. Matrix Anal. Appl. 34(2), 571–592 (2013). https://doi.org/10.1137/120866543

    Article  MathSciNet  Google Scholar 

  10. Estrin, R., Orban, D., Saunders, M.A.: Euclidean-norm error bounds for SYMMLQ and CG. SIAM J. Matrix Anal. Appl. 40(1), 235–253 (2019). https://doi.org/10.1137/16M1094816

    Article  MathSciNet  Google Scholar 

  11. Hestenes, M.R., Stiefel, E.: Methods of conjugate gradients for solving linear systems. J. Research Nat. Bur. Standards 49, 409–436 (1952)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  13. Craig, E.J.: Iteration procedures for simultaneous equations. PhD thesis, Massachusetts Institute of Technology (1954)

  14. Craig, E.J.: The \(N\)-step iteration procedures. J. Math. and Phys. 34, 64–73 (1955). https://doi.org/10.1002/sapm195534164

    Article  MathSciNet  Google Scholar 

  15. Faddeev, D.K., Faddeeva, V.N.: Computational Methods of Linear Algebra, p. 621. W. H. Freeman and Co., San Francisco (1963)

    Google Scholar 

  16. Saunders, M.A.: Solution of sparse rectangular systems using LSQR and CRAIG. BIT 35(4), 588–604 (1995). https://doi.org/10.1007/BF01739829

    Article  MathSciNet  Google Scholar 

  17. Papež, J., Tichý, P.: CG-like methods with error estimate, GitHub repository. https://github.com/JanPapez/CGlike-methods-with-error-estimate (2023)

  18. Strakoš, Z., Tichý, P.: Error estimation in preconditioned conjugate gradients. BIT 45(4), 789–817 (2005). https://doi.org/10.1007/s10543-005-0032-1

    Article  MathSciNet  Google Scholar 

  19. Kaasschieter, E.F.: Preconditioned conjugate gradients for solving singular systems. J. Comput. Appl. Math. 24(1), 265–275 (1988). https://doi.org/10.1016/0377-0427(88)90358-5

    Article  MathSciNet  Google Scholar 

  20. Björck, Å., Elfving, T., Strakoš, Z.: Stability of conjugate gradient and Lanczos methods for linear least squares problems. SIAM J. Matrix Anal. Appl. 19(3), 720–736 (1998)

    Article  MathSciNet  Google Scholar 

  21. Estrin, R., Orban, D., Saunders, M.A.: LNLQ: an iterative method for least-norm problems with an error minimization property. SIAM J. Matrix Anal. Appl. 40(3), 1102–1124 (2019). https://doi.org/10.1137/18M1194948

    Article  MathSciNet  Google Scholar 

  22. Estrin, R., Orban, D., Saunders, M.A.: LSLQ: an iterative method for linear least-squares with an error minimization property. SIAM J. Matrix Anal. Appl. 40(1), 254–275 (2019). https://doi.org/10.1137/17M1113552

    Article  MathSciNet  Google Scholar 

  23. Fong, D.C.-l.: Minimum-residual methods for sparse least-squares using Golub- Kahan bidiagonalization. PhD thesis, Stanford University (2011)

  24. Chang, X.-W., Paige, C.C., Titley-Peloquin, D.: Stopping criteria for the iterative solution of linear least squares problems. SIAM J. Matrix Anal. Appl. 31(2), 831–852 (2009). https://doi.org/10.1137/080724071

    Article  MathSciNet  Google Scholar 

  25. Fong, D.C.-L., Saunders, M.: LSMR: an iterative algorithm for sparse leastsquares problems. SIAM J. Sci. Comput. 33(5), 2950–2971 (2011). https://doi.org/10.1137/10079687X

    Article  MathSciNet  Google Scholar 

  26. Golub, G.H., Strakoš, Z.: Estimates in quadratic formulas. Numer. Algorithms 8(2–4), 241–268 (1994)

    Article  MathSciNet  Google Scholar 

  27. Meurant, G.: Estimates of the \(l_2\) norm of the error in the conjugate gradient algorithm. Numer. Algorithms 40(2), 157–169 (2005)

    Article  MathSciNet  Google Scholar 

  28. Hallman, E.: Sharp 2-norm error bounds for LSQR and the conjugate gradient method. SIAM J. Matrix Anal. Appl. 41(3), 1183–1207 (2020). https://doi.org/10.1137/19M1272822

    Article  MathSciNet  Google Scholar 

  29. Meurant, G., Tichý, P.: On computing quadrature-based bounds for the A-norm of the error in conjugate gradients. Numer. Algorithms 62(2), 163–191 (2013). https://doi.org/10.1007/s11075-012-9591-9

  30. Paige, C.C.: Bidiagonalization of matrices and solutions of the linear equations. SIAM J. Numer. Anal. 11, 197–209 (1974)

    Article  MathSciNet  Google Scholar 

  31. Bru, R., Marín, J., Mas, J., Tůma, M.: Preconditioned iterative methods for solving linear least squares problems. SIAM J. Sci. Comput. 36(4), 2002–2022 (2014). https://doi.org/10.1137/130931588

    Article  MathSciNet  Google Scholar 

  32. HSL. A collection of Fortran codes for large-scale scientific computation. http://www.hsl.rl.ac.uk/ (1963-2023)

  33. Regev, S., Saunders, M.A.: SSAI: A symmetric sparse approximate inverse preconditioner for the conjugate gradient methods PCG and PCGLS. (2020). Unpublished report, available at https://web.stanford.edu/group/SOL/reports/20SSAI.pdf

  34. Arridge, S.R., Betcke, M.M., Harhanen, L.: Iterated preconditioned LSQR method for inverse problems on unstructured grids. Inverse Problems 30(7), 075009–27 (2014). https://doi.org/10.1088/0266-5611/30/7/075009

    Article  MathSciNet  Google Scholar 

  35. Davis, T.A., Hu, Y.: The University of Florida sparse matrix collection. ACM Trans. Math. Softw. 38(1) (2011). https://doi.org/10.1145/2049662.2049663. https://sparse.tamu.edu

  36. Papež, J., Tichý, P.: Estimating the error in CG-like algorithms for least-squares and least-norm problems (2023). arXiv:2305.02044

Download references

Acknowledgements

The authors would like to thank Gérard Meurant and anonymous referees for careful readings of the manuscript and helpful and constructive comments, which have greatly improved the presentation. The authors are members of Nečas Center for Mathematical Modeling.

Funding

The work of Jan Papež has been supported by the Czech Academy of Sciences (RVO 67985840) and by the Grant Agency of the Czech Republic (grant no. 23-06159S).

Author information

Authors and Affiliations

  1. Institute of Mathematics, Czech Academy of Sciences, Žitná 25, Prague, 115 67, Czech Republic

    Jan Papež

  2. Faculty of Mathematics and Physics, Charles University, Sokolovská 83, Prague, 186 75, Czech Republic

    Petr Tichý

Authors
  1. Jan Papež
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Petr Tichý
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

These authors contributed equally to this work.

Corresponding author

Correspondence to Jan Papež.

Ethics declarations

Ethical approval

Not applicable.

Competing interests

Not applicable.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Papež, J., Tichý, P. Estimating error norms in CG-like algorithms for least-squares and least-norm problems. Numer Algor 97, 1–28 (2024). https://doi.org/10.1007/s11075-023-01691-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11075-023-01691-x

Keywords

Mathematics Subject Classification (2010)

Search

Navigation