The AMS website will be down for maintenance on May 23 between 6:00am - 8:00am EDT. For questions please contact AMS Customer Service at or (800) 321-4267 (U.S. & Canada), (401) 455-4000 (Worldwide).


Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Efficient computation of the extreme solutions of $X+A^*X^{-1}A=Q$ and $X-A^*X^{-1}A=Q$

Author: Beatrice Meini
Journal: Math. Comp. 71 (2002), 1189-1204
MSC (2000): Primary 15A24; Secondary 65F10, 65H05
Published electronically: November 20, 2001
MathSciNet review: 1898750
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We propose a new quadratically convergent algorithm, having a low computational cost per step and good numerical stability properties, which allows the simultaneous approximation of the extreme solutions of the matrix equations $X+A^* X^{-1}A=Q$ and $X-A^*X^{-1}A=Q$. The algorithm is based on the cyclic reduction method.

References [Enhancements On Off] (What's this?)

  • 1. N. Akar and K. Sohraby, An invariant subspace approach in M/G/1 and G/M/1 type Markov chains, Commun. Statist. Stochastic Models 13 (1997), 381-416. MR 98a:60091
  • 2. W. N. Anderson Jr., T. D. Morley, and G. E. Trapp, Positive solutions to $X=A-BX^{-1}B^*$, Linear Algebra Appl. 134 (1990), 53-62. MR 91c:47031
  • 3. D. A. Bini, L. Gemignani, and B. Meini, Computations with infinite Toeplitz matrices and polynomials, Linear Algebra Appl., to appear.
  • 4. -, Factorization of analytic functions by means of Koenig's theorem and Toeplitz computations, Numer. Math. 89 (2001), 49-82.
  • 5. D. A. Bini and B. Meini, On the solution of a nonlinear matrix equation arising in queueing problems, SIAM J. Matrix Anal. Appl. 17 (1996), 906-926. MR 97g:15015
  • 6. -, Improved cyclic reduction for solving queueing problems, Numerical Algorithms 15 (1997), 57-74. MR 98i:65125
  • 7. -, Effective methods for solving banded Toeplitz systems, SIAM J. Matrix Anal. Appl. 20 (1999), 700-719. MR 2000a:15002
  • 8. H. Dym, Hermitian block Toeplitz matrices, orthogonal polynomials, reproducing kernel pontryagin spaces, interpolation and extension, Oper. Theory, Adv. Appl. 34 (1998), 79-135, Orthogonal matrix-valued polynomials and applications, Pap. Semin. Oper. Theory, Tel Aviv/Isr. CMP 90:03
  • 9. J. C. Engwerda, On the existence of a positive definite solution of the matrix equation $X+A^TX^{-1}A=I$, Linear Algebra Appl. 194 (1993), 91-108. MR 94j:15013
  • 10. J. C. Engwerda, A. C. M. Ran, and A. L. Rijkeboer, Necessary and sufficient conditions for the existence of a positive definite solution of the matrix equation $X+A^*X^{-1}A=Q$, Linear Algebra Appl. 186 (1993), 255-275. MR 94j:15012
  • 11. A. Ferrante and B. C. Levy, Hermitian solutions of the equation $X=Q+NX^{-1}N^*$, Linear Algebra Appl. 247 (1996), 359-373. MR 97m:93071
  • 12. J. D. Gardiner, A. J. Laub, J. J. Amato, and C. B. Moler, Solution of the Sylvester matrix equation $AXB^T+CXD^T=E$, ACM Trans. Math. Software 18 (1992), 223-231. CMP 92:13
  • 13. G.H. Golub and C.F. Van Loan, Matrix computations, The Johns Hopkins University Press, Baltimore, 1989. MR 90d:65055
  • 14. C.-H. Guo, Newtons's method for discrete algebraic Riccati equations when the closed-loop matrix has eigenvalues on the unit circle, SIAM J. Matrix Anal. Appl. 20 (1999), 279-294. MR 99j:65086
  • 15. C.-H. Guo and P. Lancaster, Iterative solution of two matrix equations, Math. Comp. 68 (1999), 1589-1603. MR 99m:65061
  • 16. G. Latouche, A note on two matrices occurring in the solution of quasi-birth-and-death processes, Commun. Statist. Stochastic Models 3 (1987), 251-257. MR 89d:60151
  • 17. G. Latouche and V. Ramaswami, A logarithmic reduction algorithm for Quasi-Birth-Death processes, J. Appl. Probability 30 (1993), 650-674. MR 94c:60159
  • 18. G. Latouche and V. Ramaswami, Introduction to matrix analytic methods in stochastic modeling, ASA-SIAM Series on Statistics and Applied Probability 5, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1999. MR 2000b:60224
  • 19. G. Latouche and G.W. Stewart, Numerical methods for M/G/1 type queues, Computations with Markov Chains (W. J. Stewart, ed.), Kluwer Academic Publishers, 1995, pp. 571-581.
  • 20. B. Meini, New convergence results on functional iteration techniques for the numerical solution of M/G/1 type Markov chains, Numer. Math. 78 (1997), 39-58. MR 98g:60122
  • 21. M. Miranda and P. Tilli, Block Toeplitz matrices and preconditioning, Calcolo 33 (1996), no. 1-2, 79-86 (1998), Toeplitz matrices: structures, algorithms and applications (Cortona, 1996). MR 99e:65079
  • 22. -, Asymptotic spectra of Hermitian block Toeplitz matrices and preconditioning results, SIAM J. Matrix Anal. Appl. 21 (2000), no. 3, 867-881 (electronic). MR 2001a:65031
  • 23. M. F. Neuts, Matrix-geometric solutions in stochastic models: An algorithmic approach, The Johns Hopkins University Press, Baltimore, MD, 1981. MR 82j:60177
  • 24. S. Serra, Asymptotic results on the spectra of block Toeplitz preconditioned matrices, SIAM J. Matrix Anal. Appl. 20 (1999), no. 1, 31-44 (electronic). MR 99k:65039
  • 25. -, Spectral and computational analysis of block Toeplitz matrices having nonnegative definite matrix-valued generating functions, BIT 39 (1999), no. 1, 152-175. MR 2000a:65057
  • 26. R. L. Smith, Some interlacing properties of the Schur complement of a Hermitian matrix, Linear Algebra Appl. 177 (1992), 137-144. MR 93j:15018
  • 27. P. Tilli, Asymptotic spectral distribution of Toeplitz-related matrices, Fast reliable algorithms for matrices with structure (T. Kailath and A. H. Sayed, eds.), SIAM, Philadelphia, 1999, pp. 153-187. CMP 2000:02
  • 28. X. Zhan, Computing the extremal positive definite solutions of a matrix equation, SIAM J. Sci. Comput. 17 (1996), 1167-1174. MR 97g:65074
  • 29. X. Zhan and J. Xie, On the matrix equation $X+A^T X^{-1} A=I$, Linear Algebra Appl. 247 (1996), 337-345. MR 97k:15036

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 15A24, 65F10, 65H05

Retrieve articles in all journals with MSC (2000): 15A24, 65F10, 65H05

Additional Information

Beatrice Meini
Affiliation: Dipartimento di Matematica, Università di Pisa, via Buonarroti 2, 56127 Pisa, Italy

Keywords: Matrix equation, cyclic reduction, block Toeplitz matrix
Received by editor(s): January 25, 2000
Received by editor(s) in revised form: September 19, 2000
Published electronically: November 20, 2001
Article copyright: © Copyright 2001 American Mathematical Society

American Mathematical Society