Skip to main content
SpringerLink
Log in

Convergence analysis of an algorithm for accurate inverse Cholesky factorization

  • Original Paper
  • Area 2
  • Published:
Japan Journal of Industrial and Applied Mathematics Aims and scope Submit manuscript

Abstract

This paper is concerned with factorization of symmetric and positive definite matrices which are extremely ill-conditioned. Following the results by Rump (1990), Oishi et al. (2007, 2009) and Ogita (2010), Ogita and Oishi (2012) derived an iterative algorithm for an accurate inverse matrix factorization based on Cholesky factorization for such ill-conditioned matrices. We analyze the behavior of the algorithm in detail and give reasons for convergency by the use of numerical error analysis. Main analysis is that each iteration reduces the condition number of a preconditioned matrix by a factor around the relative rounding error unit until convergence. This behavior is consistent with the numerical results.

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

Access this article

Log in via an institution

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. Ogita, T., Oishi, S.: Accurate and robust inverse Cholesky factorization. Nonlinear Theory Appl. IEICE 3, 103–111 (2012)

    Article  Google Scholar 

  2. Rump, S.M.: Approximate inverses of almost singular matrices still contain useful information, Forschungsschwerpunktes Informations—und Kommunikationstechnik, Technical Report 90.1, Hamburg University of Technology (1990)

  3. Oishi, S., Tanabe, K., Ogita, T., Rump, S.M.: Convergence of Rumps method for inverting arbitrarily ill-conditioned matrices. J. Comput. Appl. Math. 205(1), 533–544 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  4. Rump, S.M.: Inversion of extremely ill-conditioned matrices in floationg-point. Jpn. J. Ind. Appl. Math. 26, 249–277 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  5. Ogita, T.: Accurate matrix factorization: inverse LU and inverse QR factorizations. SIAM J. Matrix Anal. Appl. 31(5), 2477–2497 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  6. GMP: GNU multiple precision arithmetic library, version 5.1.0. Code and documentation available at http://gmplib.org/ (2012)

  7. MPFR: The multiple precision floating-point reliable library, version 3.1.2. Code and documentation available at http://www.mpfr.org/ (2013)

  8. Yanagisawa, Y., Ogita, T.: Convergence analysis of accurate inverse Cholesky factorization. JSIAM Lett. 5, 25–28 (2013)

    Article  MathSciNet  Google Scholar 

  9. Yanagisawa, Y., Ogita, T., Oishi, S.: A modified algorithm for accurate inverse Cholesky factorization. Nonlinear Theory Appl. 5(1), 35–46 (2014)

    Article  Google Scholar 

  10. Ogita, T., Rump, S.M., Oishi, S.: Accurate sum and dot product. SIAM J. Sci. Comput. 26, 1955–1988 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  11. Rump, S.M., Ogita, T., Oishi, S.: Accurate floating-point summation part I: faithful rounding. SIAM J. Sci. Comput. 31, 189–224 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  12. Rump, S.M., Ogita, T., Oishi, S.: Accurate floating-point summation part II: sign, K-fold faithful and rounding to nearest. SIAM J. Sci. Comput. 31, 1269–1302 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  13. Ozaki, K., Ogita, T., Oishi, S., Rump, S.M.: Error-free transformations of matrix multiplication by using fast routines of matrix multiplication and its applications. Numer. Algorithms 59, 95–118 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  14. Demmel, J.: On floating point errors in Cholesky, LAPACK Working Note 14 CS-89-87. Department of Computer Science, University of Tennessee, Knoxville, TN, USA (1989)

  15. Rump, S.M.: Verification of positive definiteness. BIT Numer. Math. 46, 433–452 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  16. Higham, N.J.: Accuracy and Stability of Numerical Algorithms, 2nd edn. SIAM, Philadelphia (2002)

    Book  MATH  Google Scholar 

  17. Rump, S.M.: A class of arbitrarily ill-conditioned floating-point matrices. SIAM J. Matrix Anal. Appl. 12(4), 645–653 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  18. Rump, S.M.: INTLAB—INTerval LABoratory, Developments in Reliable Computing (TiborCsendes ed.). Kluwer Academic Publishers, Dordrecht, pp. 77–104 (1999)

Download references

Acknowledgments

The authors would like to thank the referees for their helpful comments.

Author information

Authors and Affiliations

  1. Graduate School of Fundamental Science and Engineering, Waseda University, 3-4-1 Okubo, Shinjuku-ku, Tokyo, 169-8555, Japan

    Yuka Yanagisawa

  2. School of Arts and Sciences, Tokyo Woman’s Christian University, 2-6-1 Zempukuji, Suginami-ku, Tokyo, 167-8585, Japan

    Takeshi Ogita

  3. Faculty of Science and Engineering, Waseda University, 3-4-1 Okubo, Shinjuku-ku, Tokyo, 169-8555, Japan

    Shin’ichi Oishi

Authors
  1. Yuka Yanagisawa
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Takeshi Ogita
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Shin’ichi Oishi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yuka Yanagisawa.

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Yanagisawa, Y., Ogita, T. & Oishi, S. Convergence analysis of an algorithm for accurate inverse Cholesky factorization. Japan J. Indust. Appl. Math. 31, 461–482 (2014). https://doi.org/10.1007/s13160-014-0154-4

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s13160-014-0154-4

Keywords

Mathematics Subject Classification

Search

Navigation