Abstract
Modifying complex plane rotations, we derive a new Jacobi-type algorithm for the Hermitian eigendecomposition, which uses only real arithmetic. When the fast-scaled rotations are incorporated, the new algorithm brings a substantial reduction in computational costs. The new method has the same convergence properties and parallelism as the symmetric Jacobi algorithm. Computational test results show that it produces accurate eigenvalues and eigenvectors and achieves great reduction in computational time.
Similar content being viewed by others
References
A. A. Anda and H. Park:Fast plane rotations with dynamic scaling. To appear in SIAM J. Matrix Anal. Appl.
J. Demmel and K. Veselić:Jacobi's method is more accurate than QR. Courant Institute of Mathematical Sciences, Department of Computer Science, New York University, 1989.
P. J. Eberlein and H. Park:Efficient implementation of Jacobi algorithms and Jacobi sets on distributed memory architectures. Journal of Parallel and Distributed Computing, special issue on Algorithms for Hypercube Computers, 8, pp. 358–366, 1990.
W. M. Gentleman:Least squares computations by Givens transformations without square roots. J. Inst. Maths. Applics, 12, 329–336, 1973.
S. Hammarling:A note on modifications to the Givens plane rotation. J. Inst. Maths. Applics., 13, 215–218, 1974.
V. Hari:On the convergence of cyclic Jacobi-like processes. Linear Algebra and its Appl. 81 (1986) 105–127.
V. Hari:On sharp quadratic convergence bounds for the serial Jacobi methods. Numer. Math. 60 (1991), 375–406.
M. R. Hestenes:Inversion of matrices by biorthogonalization and related results. J. SIAM 6 (1958) 51–90.
F. T. Luk and H. Park:On parallel Jacobi orderings. SIAM J. Sci. Statist. Comput. 10 (1989) 18–26.
F. T. Luk and H. Park:A proof of convergence for two parallel Jacobi SVD algorithms. IEEE Trans. Comput. 38 (1989) 806–811.
H. Park and P. J. Eberlein:Factored Jacobi-like algorithms for eigensystem computations on vector processors. Tech. Report TR90-11, Comp. Sci. Dept., Univ. of Minn., Feb., 1990.
M. Petkov:Numerical Solution of Linear Algebraic Problems in the Complex Case. (Bulgarian.) Annuarie de l'Université de Sofia “Kliment Ohridski”, Tome 71, 2e Partie, Faculté de Mathenatiques et Mecanique 1976/77.
W. Rath:Fast Givens rotations for orthogonal similarity transformations. Numer. Math. 40 (1982) 47–56.
A. van der Veen and E. F. Deprettere:Parallel VLSI matrix pencil algorithm for high resolution direction finding. IEEE Tran. on Signal Processing 39 (1991) 383–394.
K. Veselić and V. Hari:A note on the one-sided Jacobi algorithm. Numer. Math. 56 (1989) 627–633.
J. H. Wilkinson:Note on the quadratic convergence of the cyclic Jacobi process. Numer. Math. 4 (1962) 296–300.
J. H. Wilkinson:Some Recent Advances in Numerical Linear Algebra. The State of Art in Numerical Analysis, ed. D. A. H. Jacobs, Academic press, New York, pp. 1–53.
Author information
Authors and Affiliations
Additional information
The work of this author was supported in part by the National Science Foundation grant CCR-8813493 and by the University of Minnesota Army High Performance Computing Research Center contract DAAL 03-89-C-0038.
The work of this author was supported in part by the University of Minnesota Army High Performance Computing Research Center contract DAAL 03-89-C-0038.
Rights and permissions
About this article
Cite this article
Park, H., Hari, V. A real algorithm for the Hermitian eigenvalue decomposition. BIT 33, 158–171 (1993). https://doi.org/10.1007/BF01990351
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01990351