|
Spectral division methods for block generalized Schur decompositions
Author(s):
Xiaobai
Sun;
Enrique
S.
Quintana-Ortí.
Journal:
Math. Comp.
73
(2004),
1827-1847.
MSC (2000):
Primary 65F15;
Secondary 15A18, 15A22
Posted:
May 11, 2004
Retrieve article in:
PDF DVI PostScript
Abstract |
References |
Similar articles |
Additional information
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:
-
- 1.
- W. F. Arnold and A. J. Laub.
Generalized eigenproblem algorithms and software for algebraic Riccati equations.
Proc. IEEE, 72:1746-1754, 1984. - 2.
- Z. Bai and J. Demmel.
Using the matrix sign function to compute invariant subspaces.
SIAM J. Matrix Anal. Appl., 19(1):205-225, 1998. MR 99c:65066 - 3.
- Z. Bai, J. Demmel, and M. Gu.
An inverse free parallel spectral divide and conquer algorithm for nonsymmetric eigenproblems.
Numer. Math., 76(3):279-308, 1997. MR 98d:65043 - 4.
- Z. Bai, J. W. Demmel, J. Dongarra, A. Petitet, and H. Robinson.
The spectral decomposition of nonsymmetric matrices on distributed memory multiprocessors.
SIAM J. Sci. Comp., 18:1446-1461, 1997. MR 98d:65027 - 5.
- P. Benner.
Contributions to the Numerical Solution of Algebraic Riccati Equations and Related Eigenvalue Problems.
Logos-Verlag, Berlin, Germany, 1997. - 6.
- P. Benner and E. S. Quintana-Ortí.
Solving stable generalized Lyapunov equations with the matrix sign function.
Numer. Alg., 20(1):75-100, 1999. - 7.
- 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. - 8.
- A. Y. Bulgakov and S. K. Godunov.
Circular dichotomy of the spectrum of a matrix.
Siberian Math. J., 29(5):734-744, 1988. MR 89m:15005 - 9.
- T. Chan.
Rank-revealing QR factorizations.
Lin. Alg. Appl., 88/89:67-82, 1987. MR 88c:15011 - 10.
- 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. - 11.
- S. K. Godunov.
The problem of dichotomy of the spectrum of a matrix.
Siberian Math. J., 27(5):649-660, 1986. MR 88d:34066 - 12.
- G. Golub and C. Van Loan.
Matrix Computations.
The Johns Hopkins University Press, 1989. MR 90d:65055 - 13.
- P. Hong and C. T. Pan.
The rank revealing QR and SVD.
Math. Comp., 58:213-232, 1992. MR 93d:65031 - 14.
- C. Kenney and A. J. Laub.
Rational iterative methods for the matrix sign function.
SIAM J. Mat. Anal. Appl., 12:273-291, 1991. MR 92j:15009 - 15.
- V. N. Kublanovskaya.
An approach to solving the spectral problem of  .
In B. Kåagström and A. Ruhe, editors, Matrix Pencils, pages 17-29. Springer-Verlag, New York, 1983. MR 84c:65009 - 16.
- V. N. Kublanovskaya.
AB algorithm and its modifications for the spectral problem of linear pencils of matrices.
Numer. Math., 43:329-342, 1984. MR 85k:65034 - 17.
- H. Kwakernaak and R. Sivan.
Linear Optimal Control Systems.
Wiley-Interscience, New York, 1972. MR 53:10394 - 18.
- A. N. Malyshev.
Parallel algorithm for solving some spectral problems of linear algebra.
Lin. Alg. Appl., 188/189:489-520, 1993. MR 94i:65052 - 19.
- C. Moler and G. W. Stewart.
An algorithm for generalized matrix eigenvalue problems.
SIAM J. Numer. Anal., 10:241-256, 1973. MR 49:10135 - 20.
- 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. - 21.
- 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. - 22.
- J. Roberts.
Linear model reduction and solution of algebraic Riccati equations by the use of the sign function.
Int. J. Control, 32:677-687, 1980. MR 81m:93042 - 23.
- G. W. Stewart.
On the sensitivity of the eigenvalue problem.
SIAM J. Numer. Anal., 9:669-686, 1972. MR 47:244 - 24.
- G. W. Stewart.
Perturbation theory for the generalized eigenvalue problem.
In G. Golub C. de Boor, editor, Recent Advances in Numerical Analysis, pages 193-206. Academic Press, New York, 1978. MR 80c:65092 - 25.
- G. W. Stewart and J. G. Sun.
Matrix Perturbation Theory.
Academic Press, New York, 1990. MR 92a:65017 - 26.
- P. Van Dooren.
Reducing subspaces: Definitions, properties and algorithms.
In B. Kågström and A. Ruhe, editors, Matrix Pencils, pages 17-29. Springer-Verlag, New York, 1983. MR 84c:65009 - 27.
- A. Varga.
On stabilization methods of descriptor systems.
System Control Let., 24:133-138, 1995.MR 95i:93130
Similar Articles:
Retrieve articles in Mathematics of Computation
with MSC
(2000):
65F15,
15A18, 15A22
Retrieve articles in all Journals with MSC
(2000):
65F15,
15A18, 15A22
Additional Information:
Xiaobai
Sun
Affiliation:
Department of Computer Science, Duke University, D107, Levine Science Research Center, Durham, North Carolina 27708-0129
Email:
xiaobai@cs.duke.edu
Enrique
S.
Quintana-Ortí
Affiliation:
Departmento de Ingeniería y Ciencia de Computadores, Universidad Jaime I, 12080 Castellón, Spain
Email:
quintana@icc.uji.es
DOI:
10.1090/S0025-5718-04-01667-9
PII:
S 0025-5718(04)01667-9
Keywords:
Generalized eigenproblem,
matrix sign and disc functions,
spectral divide-and-conquer algorithms
Received by editor(s):
August 13, 2002
Posted:
May 11, 2004
Copyright of article:
Copyright
2004,
American Mathematical Society
|
Comments: webmaster@ams.org