[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Algorithms for Square Root of Semi-Infinite Quasi-Toeplitz M-Matrices

  • Published:
Journal of Scientific Computing Aims and scope Submit manuscript

Abstract

A quasi-Toeplitz M-matrix A is an infinite M-matrix that can be written as the sum of a semi-infinite Toeplitz matrix and a correction matrix. This paper is concerned with computing the square root of invertible quasi-Toeplitz M-matrices which preserves the quasi-Toeplitz structure. We show that the Toeplitz part of the square root can be easily computed through evaluation/interpolation. This advantage allows us to propose algorithms solely for the computation of correction part, whence we propose a fixed-point iteration and a structure-preserving doubling algorithm. Additionally, we show that the correction part can be approximated by solving a nonlinear matrix equation with coefficients of finite size followed by extending the solution to infinity. Numerical experiments showing the efficiency of the proposed algorithms are performed.

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
$34.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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Algorithm 1
Fig. 1
Fig. 2

Similar content being viewed by others

Data Availability

All data used in the manuscript is numerically generated using MATLAB. The MATLAB source code used to generate the numerical results is available at https://github.com/JieMeng00/structured_sqrtm_square_root_m-matrices.

References

  1. Alefeld, G., Schneider, N.: On square roots of \(M\)-matrices. Linear Algebra Appl. 42, 119–132 (1982)

    Article  MathSciNet  Google Scholar 

  2. B\(\ddot{\rm o}\)ttcher, A. and Grudsky, S.M.: Spectral Properties of Banded Toeplitz Matrices. SIAM, Philadelphia, PA (2005)

  3. Bini, D.A., Iannazzo, B., and Meng, J.: Algorithms for approximating means of semi-definite quasi-Toeplitz matrices, in: International Conference on Geometric Science of Information, GSI 2021: Geometric Science of Information, 2021, pp. 405–414

  4. Bini, D.A., Iannazzo, B. and Meini, B.: Numerical Solution of Algebraic Riccati Equations. Volume 9 of Fundamentals of Algorithms. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA (2012)

  5. Bini, D.A. and Meini, B.: A defect-correction algorithm for quadratic matrix equations, with applications to quasi-Toeplitz matrices. arXiv preprint (2022)

  6. Bini, D.A., Massei, S., Meini, B.: On functions of quasi Toeplitz matrices. Sb. Math. 208, 56–74 (2017)

    Article  MathSciNet  Google Scholar 

  7. Bini, D.A., Massei, S., Meini, B.: Semi-infinite quasi-Toeplitz matrices with applications to QBD stochastic processes. Math. Comp. 87, 2811–2830 (2018)

    Article  MathSciNet  Google Scholar 

  8. Bini, D.A., Massei, S., Meini, B., Robol, L.: On quadratic matrix equations with infinite size coefficients encountered in QBD stochastic processes. Numer. Linear Algebra Appl. 25, e2128 (2018)

    Article  MathSciNet  Google Scholar 

  9. Bini, D.A., Massei, S., Robol, L.: Quasi-Toeplitz matrix arithmetic: a MATLAB toolbox. Numer. Algorithms 81, 741–769 (2019)

    Article  MathSciNet  Google Scholar 

  10. Bini, D.A., Meini, B., Meng, J.: Solving quadratic matrix equations arising in random walks in the quarter plane. SIAM J. Matrix Anal. Appl. 41, 691–714 (2020)

    Article  MathSciNet  Google Scholar 

  11. Bini, D.A., Massei, S., Meini, B., Robol, L.: A computational framework for two-dimensional random walks with restarts. SIAM J. Sci. Comput. 42(4), A2108–A2133 (2020)

    Article  MathSciNet  Google Scholar 

  12. Bini, D.A., Iannazzo, B., Meng, J.: Geometric mean of quasi-Toeplitz matrices. BIT 63, 20 (2023)

    Article  MathSciNet  Google Scholar 

  13. Bini, D.A., Iannazzo, B., Meini, B., Meng, J., Robol, L.: Computing eigenvalues of semi-infinite quasi-Toeplitz matrices. Numer. Algorithms 92, 89–118 (2023)

    Article  MathSciNet  Google Scholar 

  14. Higham, N.J.: Functions of Matrices: Theory and Computation. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2008)

    Book  Google Scholar 

  15. Huang, T.-M., Li, R.-C. and Lin, W.-W.: Structure-preserving Doubling Algorithms for Nonlinear Matrix Equations. Volume 14 of Fundamentals of Algorithms. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA (2018)

  16. Kadison, R.V. and Ringrose, J.R.: Fundamentals of the Theory of Operator Algebras. Vol. I, volume 100 of Pure and Applied Mathematics. Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York, 1983. Elementary theory

  17. Kannan, M.R., Sivakumar, K.C.: On certain positivity classes of operators. Numer. Funct. Anal. Optim. 37, 206–224 (2017)

    Article  MathSciNet  Google Scholar 

  18. Kim, H.-M., Meng, J.: Structured perturbation analysis for an infinite size quasi-Toeplitz matrix equation with applications. BIT. 61, 859–879 (2021)

    Article  MathSciNet  Google Scholar 

  19. Marek, I.: Frobenius theory of positive operators: comparison theorems and applications. SIAM J. Appl. Math. 19, 607–628 (1970)

    Article  MathSciNet  Google Scholar 

  20. Marek, I.: On square roots of M-operators. Linear Algebra Appl. 223(224), 501–520 (1995)

    Article  MathSciNet  Google Scholar 

  21. Marek, I., Szyld, D.B.: Splittings of \(M\)-operators: irreducibility and the index of the iteration operator. Numer. Funct. Anal. Optim. 11, 529–553 (1990)

    Article  MathSciNet  Google Scholar 

  22. Meng, J.: Theoretical and computational properties of semi-infinite quasi-Toeplitz \(M\)-matrices. Linear Algebra Appl. 653, 66–85 (2022)

    Article  MathSciNet  Google Scholar 

  23. Motyer, A.J., Taylor, P.G.: Decay rates for quasi-birth-and-death processes with countably many phases and tridiagonal block generators. Adv. Appl. Prob. 38, 522–544 (2006)

    Article  MathSciNet  Google Scholar 

  24. Robol, L.: Rational Krylov and ADI iteration for infinite size quasi-Toeplitz matrix equations. Linear Algebra Appl. 604, 210–235 (2020)

    Article  MathSciNet  Google Scholar 

  25. Shivakumar, P.N., Sivakumar, K.C. and Zhang,Y.: Infinite Matrices and Their Recent Applications. Springer International Publishing Switzerland (2016)

Download references

Acknowledgements

The authors wish to thank the anonymous referees for providing useful comments that helped to improve this presentation.

Funding

The work of the first author was partly supported by the National Natural Science Foundation of China under grant Nos. 12001262, 12371379, 12361080 and by Jiangxi Provincial Natural Science Foundation under grant No. 20224BAB211006. The work of the third author was partly supported by the National Natural Science Foundation of China under grant No. 12201591 and Qingdao Natural Science Foundation under project 23-2-1-158-zyyd-jch.

Author information

Authors and Affiliations

  1. Department of Mathematics, Nanchang University, Nanchang, 330031, China

    Hongjia Chen

  2. Department of Mathematics, Pusan National University, Busan, 46241, Republic of Korea

    Hyun-Min Kim

  3. School of Mathematical Sciences, Ocean University of China, Qingdao, 266100, China

    Jie Meng

Authors
  1. Hongjia Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hyun-Min Kim
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jie Meng
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jie Meng.

Ethics declarations

Conflict of interest

The authors declare no competing interests.

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

Chen, H., Kim, HM. & Meng, J. Algorithms for Square Root of Semi-Infinite Quasi-Toeplitz M-Matrices. J Sci Comput 99, 66 (2024). https://doi.org/10.1007/s10915-024-02491-8

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s10915-024-02491-8

Keywords

Mathematics Subject Classification