×

Linear algebra on high performance computers. (English) Zbl 0628.65016

A survey is given of ways of constructing numerical software for high performance computers to handle linear algebra problems involving dense matrices. The focus is on utilization of new hardware rather than on the development of new algorithms. Typical recasting that occurs within LINPACK and EISPACK is described. Examples are presented in three areas: banded systems, sparse QR-factorization and symmetric eigenvalue problems.
Reviewer: R.P.Tewarson

MSC:

65Fxx Numerical linear algebra
65-02 Research exposition (monographs, survey articles) pertaining to numerical analysis
65F05 Direct numerical methods for linear systems and matrix inversion
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65F50 Computational methods for sparse matrices
65Y05 Parallel numerical computation

Software:

EISPACK; LINPACK; symrcm
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Babb, R. G., Parallel Processing with Large Grain Data Flow Techniques, IEEE Computer, Vol. 17, No. 7, 55-61 (1984)
[2] Bunch, J. R.; Nielsen, C. P.; Sorensen, D. C., Rank-One Modification of the Symmetric Eigenproblem, Numerische Mathematik, 31, 31-48 (1978) · Zbl 0369.65007
[3] Cuppen, J. J.M., A Divide and Conquer Method for the Symmetric Tridiagonal Eigenproblem, Numerische Mathematik, 36, 177-195 (1981) · Zbl 0431.65022
[4] Dongarra, J. J.; Eisenstat, S. C., Squeezing the Most out of an Algorithm in CRAY Fortran, ACM Trans. Math. Software, Vol. 10, No. 3 (1984)
[5] Dongarra, J. J.; Sorensen, D. C., A Fully Parallel Algorithm for the Symmetric Eigenvalue Problem, Argonne National Laboratory Report ANL/MCS-TM-62 (1986) · Zbl 0591.65027
[6] Dongarra, J. J.; Sameh, A. H.; Sorensen, D. C., Some Implementations of the QR Factorization on an MIMD Machine, Argonne National Laboratory Report ANL/MCS-TM-25 (1984), to appear in Parallel Computing
[7] Dongarra, J. J., Performance of Various Computers Using Standard Linear Equations Software in a Fortran Environment, Argonne National Laboratory Report MCS-TM-23 (1984), updated
[8] Dongarra, J. J.; Bunch, J. R.; Moler, C. B.; Stewart, G. W., LINPACK Users’ Guide (1979), SIAM Publications: SIAM Publications Philadelphia · Zbl 0476.68025
[9] Dongarra, J. J.; Du Croz, J.; Hammarling, S.; Hanson, R. J., A Proposal for an Extended Set of Fortran Basic Linear Algebra Subroutines, Argonne National Laboratory Report MCS/TM 41 (1985), Revision 1
[10] Dongarra, J. J.; Kaufman, L.; Hammarling, S., Squeezing the Most out of Eigenvalue Solvers on High-Performance Computers, Argonne National Laboratory Report ANLMCS-TM 46 (1985), to appear in Linear Algebra and Its Applications · Zbl 0587.65027
[11] Fong, K.; Jordan, T. L., Some Linear Algebra Algorithms and Their Performance on CRAY-1 (1977), Los Alamos Scientific Laboratory, UC-32
[12] Garbow, B. S.; Boyle, J. M.; Dongarra, J. J.; Moler, C. B., Matrix Eigensystem Routines-EISPACK Guide Extension, (Lecture Notes in Computer Science, Vol. 51 (1977), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0368.65020
[13] Gentleman, W., Error Analysis of the QR Decomposition by Givens Transformations, Linear Algebra and Its Applications, Vol. 10, 189-197 (1975) · Zbl 0308.65022
[14] Gentleman, M.; Kung, H. T., Matrix Triangularization by Systolic Arrays, Proceedings SPIE 298 Real-Time Signal Processing IV (1981), San Diego, California
[15] George, A.; Heath, M. T., Solution of Sparse Linear Least Squares Problems Using Givens Rotations, Linear Algebra and Its Applications, Vol. 34, 69-83 (1980) · Zbl 0459.65025
[16] George, J. A.; Heath, M. T.; Plemmons, R. J., Solution of Large-Scale Sparse Least Squares Problems Using Auxiliary Storage, SIAM Journal on Scientific and Statistical Computing, Vol. 2, 416-429 (1981) · Zbl 0469.65021
[17] George, A.; Liu, J., Computer Solution of Large Sparse Positive Definite Systems (1981), Prentice-Hall: Prentice-Hall Englewood Cliffs, New Jersey · Zbl 0516.65010
[18] Givens, W., Numerical Computation of the Characteristic Values of a Real Symmetric Matrix, Oak Ridge National Laboratory Report ORNL-1574 (1954), Oak Ridge, Tenn. · Zbl 0055.35005
[19] Golub, G. H., Some Modified Matrix Eigenvalue Problems, SIAM Review, 15, 318-334 (1973) · Zbl 0254.65027
[20] Golub, G. H.; Plemmons, R. J., Large Scale Geodetic Least Squares Adjustments by Dissection and Orthogonal Decomposition, Linear Algebra and Its Applications, Vol. 34, 3-28 (1980) · Zbl 0468.65012
[21] Heath, M. T.; Sorensen, D. C., A Pipelined Givens Method for Computing the QR-Factorization of a Sparse Matrix, Argonne National Laboratory Report ANL MCS-TM 47 (1985), Linear Algebra and Its Applications, (to appear) · Zbl 0587.65018
[22] Lawson, C.; Hanson, R.; Kincaid, D.; Krogh, F., Basic Linear Algebra Subprograms for Fortran Usage, ACM Trans. Math. Software, 5, 308-371 (1979) · Zbl 0412.65022
[23] Lusk, E.; Overbeek, R., Implementation of Monitors with Macros: A Programming Aid for the HEP and Other Parallel Processors, ANL-83-97 (1983)
[24] Lusk, E.; Overbeek, R., An Approach to Programming Multiprocessing Algorithms on the Denelcor HEP, ANL-83-96 (1983)
[25] Moré, J. J., The Levenberg-Marquardt Algorithm: Implementation and Theory, (Watson, G. A., Proceedings of the Dundee Conference on Numerical Analysis (1978), Springer-Verlag) · Zbl 0372.65022
[26] Reinsh, C. H., Smoothing by Spline Functions, Numerische Mathematik, 10, 177-183 (1967) · Zbl 0161.36203
[27] Reinsh, C. H., Smoothing by Spline Functions II, Numerische Mathematik, 16, 451-454 (1971) · Zbl 1248.65020
[28] Sameh, A.; Kuck, D., On Stable Parallel Linear System Solvers, Journal of the ACM, Vol. 25, 81-91 (1978) · Zbl 0364.68051
[29] Smith, B. T.; Boyle, J. M.; Dongarra, J. J.; Garbow, B. S.; Ikebe, Y.; Klema, V. C.; Moler, C. B., Matrix Eigensystem Routines - EISPACK Guide, (Lecture Notes in Computer Science, Vol. 6 (1976), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0325.65016
[30] Stewart, G. W., Introduction to Matrix Computations (1973), Academic Press: Academic Press New York · Zbl 0302.65021
[31] Sorensen, D. C., Buffering for Vector Performance on a Pipelined MIMD Machine, Parallel Computing, Vol. 1, 143-164 (1984) · Zbl 0547.65036
[32] Wilkinson, J. H., The Algebraic Eigenvalue Problem (1965), Clarendon Press: Clarendon Press Oxford · Zbl 0258.65037
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.