Block reduction of matrices to condensed forms for eigenvalue computations. (English) Zbl 0679.65025
The authors describe block algorithms for the reduction of a (real) symmetric matrix to a tridiagonal form and that of a general matrix to a bidiagonal form by using Householder transformations. The same approach can be used in the reduction to Hessenberg form. These reductions to condensed forms comprise a preliminary step in the computation of eigenvalues or singular values. The authors also show how these reductions may be pipelined with the divide and conquer technique for computing the eigensystem of a symmetric matrix or the singular value decomposition of a general matrix. These considerations have significant performance advantages on parallel-vector processors.
Reviewer: F.Móricz
MSC:
65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
65Y05 | Parallel numerical computation |
65F30 | Other matrix algorithms (MSC2010) |
Keywords:
reduction to tridiagonal form; block algorithms; Householder transformations; reduction to Hessenberg form; reductions to condensed forms; eigenvalues; divide and conquer technique; singular value decomposition; parallel-vector processorsSoftware:
BLASReferences:
[1] | Berry, M.; Gallivan, K.; Harrod, W.; Jalby, W.; Lo, S.; Meier, U.; Philippe, B.; Sameh, A., Parallel algorithms on the CEDAR system, CSRD Report No. 581 (1986) |
[2] | Bischof, C.; Van Loan, C., The WY representation for products of Householder matrices, SIAM J. Sci. Statist. Comput., 8, 1, s2-s13 (1987) · Zbl 0628.65033 |
[3] | Bucher, I.; Jordan, T., Linear algebra programs for use on a vector computer with a secondary solid state storage device, (Vichnevetsky, R.; Stepleman, R., Advances in Computer Methods for Partial Differential Equations (1984), IMACS: IMACS New Brunswick, NJ), 546-550 |
[4] | Calahan, D. A., Block-oriented local-memory-based linear equation solution on the CRAY-2: Uniprocessor algorithms, (Proc. International Conference on Parallel Processing (1986), IEEE Computer Society Press: IEEE Computer Society Press Silver Spring, MD), 375-378 |
[5] | J.J. Dongarra, J. DuCroz, I. Duff and S. Hammarling, A set of level 3 basic linear algebra subprograms, ACM Trans. Math. Software; J.J. Dongarra, J. DuCroz, I. Duff and S. Hammarling, A set of level 3 basic linear algebra subprograms, ACM Trans. Math. Software · Zbl 0900.65115 |
[6] | Dongarra, J. J.; Duff, I. S., Advanced architecture computers, Argonne National Laboratory Report (1987), ANL-MCS-TM-57 (Revision 1) |
[7] | Dongarra, J. J.; Eisenstat, S. C., Squeezing the most out of an algorithm in Cray Fortran, ACM Trans. Math. Software, 10, 3, 221-230 (1984) |
[8] | Dongarra, J. J.; Hewitt, T., Implementing dense linear algebra algorithms using multitasking on the CRAY X-MP-4, SIAM J. Sci. Statist. Comput., 7, 1, 347-350 (1986) · Zbl 0591.65026 |
[9] | Dongarra, J. J.; Kaufman, L.; Hammarling, S., Squeezing the most out of eigenvalue solvers on high-performance computers, Linear Algebra Appl., 77, 113-136 (1986) · Zbl 0587.65027 |
[10] | Dongarra, J. J.; Sorensen, D. C., Linear algebra on high-performance computers, (Feilmeier, M., Parallel Computing 85 (1986), North-Holland: North-Holland Amsterdam), 3-32 · Zbl 0628.65016 |
[11] | Dongarra, J. J.; Sorensen, D. C., A fully parallel algorithm for the symmetric eigenvalue problem, SIAM J. Sci. Statist. Comput., 8, 2, 139-157 (1987) · Zbl 0627.65033 |
[12] | IBM, Engineering and Scientific Subroutine Library, IBM, Program Number 5668-683 (1986) |
[13] | Jessup, L.; Sorensen, D., A parallel algorithm for computing the singular value decomposition of a matrix, Argonne National Laboratory Report (1987), ANL-MCS-TM-102 |
[14] | Parlett, B., Analysis of algorithms for reflections in bisectors, SIAM Rev., 13, 2, 197-208 (1971) · Zbl 0217.52606 |
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.