×

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)

Software:

BLAS
PDFBibTeX XMLCite
Full Text: DOI

References:

[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)
[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.