Skip to main content
Log in

Lanczos Conjugate-Gradient Method and Pseudoinverse Computation on Indefinite and Singular Systems

  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

This paper extends some theoretical properties of the conjugate gradient-type method FLR (Ref. 1) for iteratively solving indefinite linear systems of equations. The latter algorithm is a generalization of the conjugate gradient method by Hestenes and Stiefel (CG, Ref. 2). We develop a complete relationship between the FLR algorithm and the Lanczos process, in the case of indefinite and possibly singular matrices. Then, we develop simple theoretical results for the FLR algorithm in order to construct an approximation of the Moore-Penrose pseudoinverse of an indefinite matrix. Our approach supplies the theoretical framework for applications within unconstrained optimization.

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

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. 1 Fasano, G., Planar-Conjugate Gradient Algorithm for Large-Scale Unconstrained Optimization, Part 1: Theory, Journal of Optimization Theory and Applications, Vol. 125, pp. 523–541, 2005.

    Article  MATH  MathSciNet  Google Scholar 

  2. 2 Hestenes, M. R., and Stiefel, E., Methods of Conjugate Gradients for Solving Linear Systems, Journal of Research of the National Bureau of Standards, Vol. 49B, pp. 409–436, 1952.

    MathSciNet  Google Scholar 

  3. 3 Golub, G. H., and Van Loan, C. F., Matrix Computations, 3rd Edition, John Hopkins Press, Baltimore, Maryland, 1989.

    MATH  Google Scholar 

  4. 4 Greenbaum, A., Iterative Methods for Solving Linear Systems, SIAM, Frontiers in Applied Mathematics, Philadelphia, Pennsylvania, 1997.

    MATH  Google Scholar 

  5. 5 Saad, Y., and Van Der Vorst, H. A., Iterative Solution of Linear Systems in the 20th Century, Journal of Computational and Applied Mathematics, Vol. 123, pp. 1–33, 2000.

    Article  MATH  MathSciNet  Google Scholar 

  6. 6 Hansen, P. C., Rank-Deficient and Discrete Ill-Posed Problems, SIAM, Philadelphia, Pennsylvania, 1998.

    Google Scholar 

  7. 7 Bjorck, A., Numerical Methods for Least-Squares Problems, SIAM, Philadelphia, Pennsylvania, 1996.

    Google Scholar 

  8. 8 McCormick, G. P., Nonlinear Programming: Theory, Algorithms, and Applications, Wiley and Sons, New York, NY, 1983.

    MATH  Google Scholar 

  9. 9 Campbell, S. L., and Meyer Jr., C. D., Generalized Inverses of Linear Transformations, Dover Publications, New York, NY, 1979.

    MATH  Google Scholar 

  10. 10 Lampariello, F., and Sciandrone, M., Use of the Minimum-Norm Search Direction in a Nonmonotone Version of the Gauss-Newton Method, Journal of Optimization Theory and Applications, Vol. 119, pp. 65–82, 2003.

    Article  MATH  MathSciNet  Google Scholar 

  11. 11 Fasano, G., Lampariello, F., and Sciandrone, M., A Truncated Nonmonotone Gauss-Newton Method for Large-Scale Nonlinear Least-Squares Problems, Technical Report 590, IASI-CNR, Rome, Italy, 2004; Computational Optimization and Applications (to appear).

    Google Scholar 

  12. 12 Hestenes, M. R., Pseudoinverses and Conjugate Gradients, Communications of the ACM, Vol. 18, pp. 40–43, 1975.

    Article  MathSciNet  Google Scholar 

  13. 13 Wu, K., Saad, Y., and Stathopoulos, A., Inexact Newton Preconditioning Techniques for Large Symmetric Eigenvalue Problems, Electronic Transactions on Numerical Analysis, Vol. 7, pp. 202–214, 1998.

    MATH  MathSciNet  Google Scholar 

  14. 14 Sleijpen, G. L. G., and Van Der Vorst, H. A., The Jacobi-Davidson Method for Eigenvalue Problems as an Accelerated Inexact Newton Scheme, Iterative Methods in Linear Algebra II: Proceedings of the IMACS International Symposium on Iterative Methods in Linear Algebra, Blagoevgrad, Bulgaria, pp. 377–389, 1995; Elsevier, Amsterdam, Netherlands, 1996.

    Google Scholar 

  15. 15 Luenberger, D. G., Hyperbolic Pairs in the Method of Conjugate Gradients, SIAM Journal on Applied Mathematics, Vol. 17, pp. 1263–1267, 1969.

    Article  MATH  MathSciNet  Google Scholar 

  16. 16 Hestenes, M. R., Conjugate Direction Methods in Optimization, Springer Verlag, New York, NY, 1980.

    MATH  Google Scholar 

  17. 17 Liu, Y., and Storey, C., Efficient Generalized Conjugate Gradient Algorithms, Part 1: Theory, Journal of Optimization Theory and Applications, Vol. 69, pp. 129–137, 1991.

    Article  MATH  MathSciNet  Google Scholar 

  18. 18 Dixon, L. C. W., Ducksbury, P. G., and Singh, P., A New Three-Term Conjugate Gradient Method, Technical Report 130, Numerical Optimization Centre, Hatfield Polytechnic, Hatfield, Hertfordshire, England, 1985.

    Google Scholar 

  19. 19 Miele, A., and Cantrell, J. W., Study on a Memory Gradient Method for the Minimization of Functions, Journal of Optimization Theory and Applications, Vol. 3, pp. 459–470, 1969.

    Article  MATH  MathSciNet  Google Scholar 

  20. 20 Bank, R. E., and Chan, T. F., A Composite Step Biconjugate Gradient Algorithm for Nonsymmetric Linear Systems, Numerical Algorithms, Vol. 7, pp. 1–16, 1994.

    Article  MATH  MathSciNet  Google Scholar 

  21. 21 Saad, Y., Iterative Methods for Sparse Linear Systems, 2nd Edition, SIAM, Philadelphia, Pennsylvania, 2003.

    MATH  Google Scholar 

  22. 22 Eijkhout, V., LAPACK Working Note 66; A Characterization of Polynomial Iterative Methods, Technical Report UT-CS-93-216, Department of Computer Science, University of Tennessee, 1993.

  23. 23 Eijkhout, V., LAPACK Working Note 51: Qualitative Properties of the Conjugate Gradient and Lanczos Methods in a Matrix Framework, Technical Report UT-CS-92-170, Department of Computer Science, University of Tennessee, 1992.

  24. 24 Fasano, G., Use of Conjugate Directions inside Newton-Type Algorithms for Large-Scale Unconstrained Optimization, PhD Dissertation, Rome, Italy, 2001.

  25. 25 Fasano, G., Lanczos-Conjugate Gradient Method and Pseudoinverse Computation in Unconstrained Optimization, Technical Report INSEAN 2004-036, Rome, Italy, 2004.

    Google Scholar 

  26. 26 Conn, A. R., Gould, N. I. M., and Toint, P. L., Trust-Region Methods, SIAM, Philadelphia, Pennsylvania, 2000.

    MATH  Google Scholar 

  27. 27 Koschinski, C., New Methods for Adapting and for Approximating Inverses as Precon-ditioners, Applied Numerical Mathematics, Vol. 41, pp. 179–218, 2002.

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Additional information

Communicated by L. C. W. Dixon

This work was partially supported by the MIUR, FIRB Research Program on Large-Scale Nonlinear Optimization and by the Ministero delle Infrastrutture e dei Trasporti in the framework of the Research Program on Safety.

The author thanks Stefano Lucidi and Massimo Roma for fruitful discussions plus the Associate Editor for effective comments.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Fasano, G. Lanczos Conjugate-Gradient Method and Pseudoinverse Computation on Indefinite and Singular Systems. J Optim Theory Appl 132, 267–285 (2007). https://doi.org/10.1007/s10957-006-9119-3

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10957-006-9119-3

Keywords

Navigation