×

Fast verified computation for the solution of the T-congruence Sylvester equation. (English) Zbl 1434.65047

An algorithm is proposed to compute an interval matrix that contains the symmetric matrix \(X\) that solves \(AX+X^TB=C\) (all matrices are in \(\mathbb{C}^{n\times n}\)). It was shown in [M. Oozawa et al., J. Comput. Appl. Math. 329, 51–56 (2018; Zbl 1373.15023)] how, under certain conditions, the problem can be transformed into a Lyapunov equation. Based on this result, conditions on the numerically computed generalized eigendecomposition of the pencil \((B,A^T)\) or \((A,B^T)\) are formulated to guarantee the existence of a unique solution. The algorithm finding the required interval matrix has complexity \(O(n^3)\) assuming that the employed enclosure routines for products and inverses of matrices have complexity at most \(O(n^3)\). The MATLAB code using INTLAB (interval arithmetic toolbox) is available online.

MSC:

65F45 Numerical methods for matrix equations
15A24 Matrix equations and identities
65G20 Algorithms with automatic result verification

Citations:

Zbl 1373.15023

Software:

VERSOFT; INTLAB
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bavely, A.; Stewart, G., An algorithm for computing reducing subspaces by block diagonalization, SIAM J. Numer. Anal., 16, 359-367, (1979) · Zbl 0413.65034 · doi:10.1137/0716028
[2] Byers, R.; Kressner, D., Structured condition numbers for invariant subspaces, SIAM J. Matrix Anal. Appl., 28, 326-347, (2006) · Zbl 1116.65052 · doi:10.1137/050637601
[3] Frommer, A.; Hashemi, B., Verified error bounds for solutions of Sylvester matrix equations, Linear Algebra Appl., 436, 405-420, (2012) · Zbl 1236.65045 · doi:10.1016/j.laa.2010.12.002
[4] Golub, G.H., Van Loan, C.F.: Matrix Computations, 4th edn. Johns Hopkins University Press, Baltimore (2013) · Zbl 1268.65037
[5] Horn, R.A., Johnson, C.R.: Topics in Matrix Analysis. Cambridge University Press, Cambridge (1994) · Zbl 0801.15001
[6] Kressner, D.; Schroder, C.; Watkins, DS, Implicit QR algorithms for palindromic and even eigenvalue problems, Numer. Algorithms, 51, 209-238, (2009) · Zbl 1181.65054 · doi:10.1007/s11075-008-9226-3
[7] Mackey, DS; Mackey, N.; Mehl, C.; Mehrmann, V., Structured polynomial eigenvalue problems: good vibrations from good linearizations, SIAM J. Matrix Anal. Appl., 28, 1029-1051, (2006) · Zbl 1132.65028 · doi:10.1137/050628362
[8] Minamihata, A.: private communication (2013)
[9] Miyajima, S., Numerical enclosure for each eigenvalue in generalized eigenvalue problem, J. Comput. Appl. Math., 236, 2545-2552, (2012) · Zbl 1248.65039 · doi:10.1016/j.cam.2011.12.013
[10] Miyajima, S., Fast enclosure for solutions of Sylvester equations, Linear Algebra Appl., 439, 856-878, (2013) · Zbl 1281.65069 · doi:10.1016/j.laa.2012.07.001
[11] Miyajima, S., Fast enclosure for solutions of generalized Sylvester equations, Jpn. J. Ind. Appl. Math., 31, 293-304, (2014) · Zbl 1310.65048 · doi:10.1007/s13160-014-0139-3
[12] Miyajima, S., Fast enclosure for all eigenvalues and invariant subspaces in generalized eigenvalue problems, SIAM J. Matrix Anal. Appl., 35, 1205-1225, (2014) · Zbl 1307.65044 · doi:10.1137/140953150
[13] Oozawa, M.; Sogabe, T.; Miyatake, Y.; Zhang, S-L, On a relationship between the T-congruence Sylvester equation and the Lyapunov equation, J. Comput. Appl. Math., 329, 51-56, (2018) · Zbl 1373.15023 · doi:10.1016/j.cam.2017.05.044
[14] Rohn, J.: VERSOFT: Verification Software in MATLAB/INTLAB. http://uivtx.cs.cas.cz/ rohn/matlab. Accessed 09 May 2018
[15] Rump, SM; Csendes, T. (ed.), INTLAB—INTerval LABoratory, 77-107, (1999), Dordrecht · Zbl 0949.65046 · doi:10.1007/978-94-017-1247-7_7
[16] Terán, F. De; Dopico, FM, Consistency and efficient solution of the Sylvester equation for \(\star \)-congruence: \(AX + X^\star B = C\), Electron. J. Linear Algebra, 22, 849-863, (2011) · Zbl 1256.65035
[17] Terán, F. De; Dopico, FM; Guillery, N.; Montealegre, D.; Reyes, N., The solution of the equation \(AX +X^\star B = 0\), Linear Algebra Appl., 438, 2817-2860, (2013) · Zbl 1264.15016 · doi:10.1016/j.laa.2012.11.014
[18] Zhang, H.; Ding, F., On the Kronecker products and their applications, J. Appl. Math., 2013, 1-8, (2013) · Zbl 1275.15019
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.