On inexact alternating direction implicit iteration for continuous Sylvester equations. (English) Zbl 1474.65112
In this paper the authors study the alternating direction implicit (ADI) iteration for solving the continuous Sylvester equation \(AX+XB=C\), where the coefficient matrices \(A\) and \(B\) are assumed to be positive semi-definite matrices (not necessarily Hermitian), and at least one of them to be positive definite. First an analysis for the convergence of the ADI iteration to solve such a class of Sylvester equations is carried, and then derivation of an upper bound for the contraction factor of this ADI iteration. To reduce its computational complexity, it is further proposed an inexact variant of the ADI iteration, which employs some Krylov subspace methods as its inner iteration processes at each step of the outer ADI iteration. The convergence is also analyzed in detail. Some numerical experiments are shown to illustrate the effectiveness of both ADI and inexact ADI iterations.
Reviewer: Carlos A. De Moura (Rio de Janeiro)
Keywords:
ADI iteration; continuous Sylvester equations; convergence; inexact ADI iteration; positive definite matricesSoftware:
MatlabReferences:
| [1] | HornRA, JohnsonCR. Topics in matrix analysis. Cambridge, UK: Cambridge University Press, 1991. · Zbl 0729.15001 |
| [2] | LancasterP, TismenetskyM. The theory of matrices. 2nd ed.Orlando, FL: Academic Press, 1985. · Zbl 0558.15001 |
| [3] | BaiZZ, GuoXX, XuSF. Alternately linearized implicit iteration methods for the minimal nonnegative solutions of the nonsymmetric algebraic Riccati equations. Numer Linear Algebra Appl. 2006;13:655-674. · Zbl 1174.65381 |
| [4] | BaiZZ. On Hermitian and skew‐Hermitian splitting iteration methods for continuous Sylvester equations. J Comput Math. 2011;29:185-198. · Zbl 1249.65090 |
| [5] | BennerP, LiRC, TruharN. On the ADI method for Sylvester equations. J Comput Appl Math. 2009;233:1035-1045. · Zbl 1176.65050 |
| [6] | BhatiaR, RosenthalP. How and why to solve the operator equation AX − XB = Y. Bull Lond Math Soc. 1997;29:1-21. · Zbl 0909.47011 |
| [7] | GolubGH, Van LoanCF. Matrix computations. 3rd ed.Baltimore, Maryland: Johns Hopkins University Press, 1996. · Zbl 0865.65009 |
| [8] | WachspressEL. Trail to a Lyapunov equation solver. Comput Math Appl. 2008;55:1653-1659. · Zbl 1139.65033 |
| [9] | BartelsRH, StewartGW. Solution of the matrix equation AX + XB = C. Commun ACM. 1972;15:820-826. · Zbl 1372.65121 |
| [10] | GolubGH, NashS, Van LoanCF. A Hessenberg‐Schur method for the problem AX + XB = C. IEEE Trans Automat Control. 1979;24:909-913. · Zbl 0421.65022 |
| [11] | SmithRA. Matrix equation XA+BX=C. SIAM J Appl Math. 1968;16:198-201. · Zbl 0157.22603 |
| [12] | BirkhoffG, VargaRS, YoungDM. Alternating direction implicit methods. Adv Comput. 1962;3:189-273. · Zbl 0111.31402 |
| [13] | KürschnerP, BennerP, SaakJ. Self‐generating and efficient shift parameters in ADI methods for large Lyapunov and Sylvester equations. Electr Trans Numer Anal. 2014;43:142-162. · Zbl 1312.65068 |
| [14] | LevenbergN, ReichelL. A generalized ADI iterative method. Numer Math. 1993;66:215-233. · Zbl 0797.65030 |
| [15] | LuA, WachspressEL. Solution of Lyapunov equations by alternating direction implicit iteration. Comput Math Appl. 1991;21:43-58. · Zbl 0724.65041 |
| [16] | SaadY. Iterative methods for sparse linear systems. 2nd ed.Philadelphia, PA: SIAM, 2003. · Zbl 1031.65046 |
| [17] | BaiZZ, GolubGH, NgMK. Hermitian and skew‐Hermitian splitting methods for non‐Hermitian positive definite linear systems. SIAM J Matrix Anal Appl. 2003;24:603-626. · Zbl 1036.65032 |
| [18] | BaiZZ, GolubGH, LuLZ, YinJF. Block triangular and skew‐Hermitian splitting methods for positive‐definite linear systems. SIAM J Sci Comput. 2005;26:844-863. · Zbl 1079.65028 |
| [19] | BaiZZ, GolubGH, NgMK. On successive‐overrelaxation acceleration of the Hermitian and skew‐Hermitian splitting iterations. Numer Linear Algebra Appl. 2007;14:319-335. · Zbl 1199.65097 |
| [20] | LiuZY, WuNC, QinXR, ZhangYL. Trigonometric transform splitting methods for real symmetric Toeplitz systems. Comput Math Appl. 2018;75:2782-2794. · Zbl 1415.65078 |
| [21] | WangX, LiWW, MaoLZ. On positive‐definite and skew‐Hermitian splitting iterative methods for continuous Sylvester equation AX+XB=C. Comput Math Appl. 2013;66:2352-2361. · Zbl 1350.65038 |
| [22] | ZhengQQ, MaCF. On normal and skew‐Hermitian splitting iterative methods for large sparse continuous Sylvester equations. J Comput Appl Math.2014;268:145-154. · Zbl 1293.65074 |
| [23] | BaiZZ, YinJF, SuYF. A shift‐splitting preconditioner for non‐Hermitian positive definite matrices. J Comput Math. 2006;24:539-552. · Zbl 1120.65054 |
| [24] | BaiZZ. A class of modified block SSOR preconditioners for symmetric positive definite systems of linear equations. Adv Comput Math. 1999;10:169-186. · Zbl 0922.65033 |
| [25] | BaiZZ. Modified block SSOR preconditioners for symmetric positive definite linear systems. Ann Operat Res. 2001;103:263-282. · Zbl 1028.65018 |
| [26] | BaiZZ. On SSOR‐like preconditioners for non‐Hermitian positive definite matrices. Numer Linear Algebra Appl. 2016;23:37-60. · Zbl 1413.65040 |
| [27] | BaiZZ, NgMK. Erratum. Numer Linear Algebra Appl. 2012;19:891. |
| [28] | BaiZZ, RozloznikM. On the numerical behavior of matrix splitting iteration methods for solving linear systems. SIAM J Numer Anal. 2015;53:1716-1737. · Zbl 1317.65089 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
