Spectral division methods for block generalized Schur decompositions

Sun, Xiaobai; Quintana-Ortí, Enrique

doi:10.1090/S0025-5718-04-01667-9

Spectral division methods for block generalized Schur decompositions
HTML articles powered by AMS MathViewer

by Xiaobai Sun and Enrique S. Quintana-Ortí;

Math. Comp. 73 (2004), 1827-1847

DOI: https://doi.org/10.1090/S0025-5718-04-01667-9

Published electronically: May 11, 2004

PDF | Request permission

Abstract:

We provide a different perspective of the spectral division methods for block generalized Schur decompositions of matrix pairs. The new approach exposes more algebraic structures of the successive matrix pairs in the spectral division iterations and reveals some potential computational difficulties. We present modified algorithms to reduce the arithmetic cost by nearly 50%, remove inconsistency in spectral subspace extraction from different sides (left and right), and improve the accuracy of subspaces. In application problems that only require a single-sided deflating subspace, our algorithms can be used to obtain a posteriori estimates on the backward accuracy of the computed subspaces with little extra cost.

References

W. F. Arnold and A. J. Laub. Generalized eigenproblem algorithms and software for algebraic Riccati equations. Proc. IEEE, 72:1746–1754, 1984.
Zhaojun Bai and James Demmel, Using the matrix sign function to compute invariant subspaces, SIAM J. Matrix Anal. Appl. 19 (1998), no. 1, 205–225. MR 1609964, DOI 10.1137/S0895479896297719
Zhaojun Bai, James Demmel, and Ming Gu, An inverse free parallel spectral divide and conquer algorithm for nonsymmetric eigenproblems, Numer. Math. 76 (1997), no. 3, 279–308. MR 1452510, DOI 10.1007/s002110050264
Z. Bai, J. Demmel, J. Dongarra, A. Petitet, H. Robinson, and K. Stanley, The spectral decomposition of nonsymmetric matrices on distributed memory parallel computers, SIAM J. Sci. Comput. 18 (1997), no. 5, 1446–1461. MR 1465666, DOI 10.1137/S1064827595281368
P. Benner. Contributions to the Numerical Solution of Algebraic Riccati Equations and Related Eigenvalue Problems. Logos–Verlag, Berlin, Germany, 1997.
P. Benner and E. S. Quintana-Ortí. Solving stable generalized Lyapunov equations with the matrix sign function. Numer. Alg., 20(1):75–100, 1999.
C. H. Bischof and G. Quintana-Ortí. Computing rank-revealing QR factorizations of dense matrices. Technical Report MCS-P559-0196, Mathematics and Computer Science Division, Argonne National Laboratory, 1996. ACM Trans. Math. Soft., 24(2): 226–253, 1998.
A. Ya. Bulgakov and S. K. Godunov, Circular dichotomy of a matrix spectrum, Sibirsk. Mat. Zh. 29 (1988), no. 5, 59–70, 237 (Russian); English transl., Siberian Math. J. 29 (1988), no. 5, 734–744 (1989). MR 971228, DOI 10.1007/BF00970267
Tony F. Chan, Rank revealing $QR$ factorizations, Linear Algebra Appl. 88/89 (1987), 67–82. MR 882441, DOI 10.1016/0024-3795(87)90103-0
J. Gardiner and A. J. Laub. A generalization of the matrix sign function solution for algebraic Riccati equations. Int. J. Control, 44:823–832, 1986.
S. K. Godunov, The problem of the dichotomy of the spectrum of a matrix, Sibirsk. Mat. Zh. 27 (1986), no. 5, 24–37, 204 (Russian). MR 873707
Gene H. Golub and Charles F. Van Loan, Matrix computations, 2nd ed., Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1989. MR 1002570
Y. P. Hong and C.-T. Pan, Rank-revealing $QR$ factorizations and the singular value decomposition, Math. Comp. 58 (1992), no. 197, 213–232. MR 1106970, DOI 10.1090/S0025-5718-1992-1106970-4
Charles Kenney and Alan J. Laub, Rational iterative methods for the matrix sign function, SIAM J. Matrix Anal. Appl. 12 (1991), no. 2, 273–291. MR 1089159, DOI 10.1137/0612020
Bo Kȧgström and Axel Ruhe (eds.), Matrix pencils, Lecture Notes in Mathematics, vol. 973, Springer-Verlag, Berlin-New York, 1983. MR 697741
V. N. Kublanovskaya, $AB$-algorithm and its modifications for the spectral problems of linear pencils of matrices, Numer. Math. 43 (1984), no. 3, 329–342. MR 738380, DOI 10.1007/BF01390177
Huibert Kwakernaak and Raphael Sivan, Linear optimal control systems, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1972. MR 406607
Alexander N. Malyshev, Parallel algorithm for solving some spectral problems of linear algebra, Linear Algebra Appl. 188/189 (1993), 489–520. MR 1223469, DOI 10.1016/0024-3795(93)90477-6
C. B. Moler and G. W. Stewart, An algorithm for generalized matrix eigenvalue problems, SIAM J. Numer. Anal. 10 (1973), 241–256. MR 345399, DOI 10.1137/0710024
G. Quintana-Ortí and E. S. Quintana-Ortí. Parallel algorithms for computing rank-revealing QR factorizations. In G. Cooperman, G. Micher, and H. Vinck, editors, High Performance Computing and Networking, pages 122–137. Springer-Verlag, Berlin, 1997.
G. Quintana-Ortí, X. Sun, and C. H. Bischof. A BLAS-3 version of the QR factorization with column pivoting. SIAM J. Sci. Comp., 19(5):1486–1494, 1998.
J. D. Roberts, Linear model reduction and solution of the algebraic Riccati equation by use of the sign function, Internat. J. Control 32 (1980), no. 4, 677–687. MR 595962, DOI 10.1080/00207178008922881
G. W. Stewart, On the sensitivity of the eigenvalue problem $Ax=\lambda Bx$, SIAM J. Numer. Anal. 9 (1972), 669–686. MR 311682, DOI 10.1137/0709056
G. W. Stewart, Perturbation theory for the generalized eigenvalue problem, Recent advances in numerical analysis (Proc. Sympos., Math. Res. Center, Univ. Wisconsin, Madison, Wis., 1978) Publication of the Mathematics Research Center, University of Wisconsin, vol. 41, Academic Press, New York-London, 1978, pp. 193–206. MR 519063
G. W. Stewart and Ji Guang Sun, Matrix perturbation theory, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1990. MR 1061154
Bo Kȧgström and Axel Ruhe (eds.), Matrix pencils, Lecture Notes in Mathematics, vol. 973, Springer-Verlag, Berlin-New York, 1983. MR 697741
A. Varga, On stabilization methods of descriptor systems, Systems Control Lett. 24 (1995), no. 2, 133–138. MR 1312350, DOI 10.1016/0167-6911(94)00017-P