J. J. Dongarra
Jeremy Du Croz
Abstract
This paper describes an extension to the set of Basic Linear Algebra Subprograms. The extensions are targeted at matrix-vector operations that should provide for efficient and portable implementations of algorithms for high-performance computers
- 1 BARRON, D. W., AND SWINNERTON-DYER, H. P.F. Solution of simultaneous linear equations using a magnetic-tape store. Comput. J. 3 (1960), 28-33.Google Scholar
- 2 BERRY, M., GALLIVAN, K., HARROD, W., JALBY, W., LO, S., MEIER, U., PHILIPPE, B., AND SAMEH, A. Parallel algorithms on the CEDAR system. CSRD Report 581, 1986.Google Scholar
- 3 BISCHOF, C., AND VAN LOAN, C. The WY representation for products of Householder matrices. SIAM J. Sci. Star. Comput. 8, 1 (Jan. 1987), s2-s13. Google Scholar
- 4 BRONLUND, O. E., AND JOHNSEN, T. QR-factorization of partitioned matrices. Comput. Meth. Appl. Mech. Eng., vol. 3, pp. 153-172, 1974.Google Scholar
- 5 BUCHER, I., AND JORDAN, T. Linear algebra programs for use on a vector computer with a secondary solid state storage device. In Advances in Computer Methods for Partial Differential Equations, R. Vichnevetsky and R. Stepleman, Eds. IMACS, 1984, 546-550.Google Scholar
- 6 CALAHAN, D.A. Block-oriented local-memory-based linear equation solution on the CRAY-2: Uniprocessor algorithms. In Proceedings International Conference on Parallel Processing (Aug. 1986). IEEE Computer Society Press, New York, 1986.Google Scholar
- 7 CARNEVALI, P., RADICATI DI BROZOLO, G., ROBERT, Y., AND SGUAZZERO, P. Efficient Fortran implementation of the Gaussian elimination and Householder reduction algorithms on the IBM 3090 vector multiprocessor. IBM ECSEC Rep. ICE-0012, 1987.Google Scholar
- 8 CHARTRES, B. Adaption of the Jacobi and Givens methods for a computer with magnetic tape backup store. Univ. of Sydney Tech. Rep. 8, 1960.Google Scholar
- 9 DAVE, A. K., AND DUFF, I.S. Sparse matrix calculations on the CRAY-2. Parallel Comput. 5 (July 1987), 55-64.Google Scholar
- 10 DEMMEL, J., DONGARRA, J. J., DU CROZ, J., GREENBAUM, A., HAMMARLING, S., AND SORENSEN, D. Prospectus for the development of a linear algebra library for high-performance computers. Argonne National Lab. Rep. ANL-MCS-TM-97, Sept. 1987.Google Scholar
- 11 DIETRICH, G. A new formulation of the hypermatrix Householder QR-decomposition. Comput. Meth. AppI. Mech. Eng. 9 (1976), 273-280.Google Scholar
- 12 DODSON, D., AND LEWIS, J. Issues relating to extension of the basic linear algebra subprograms. ACM SIGNUM Newsl. 20, 1 (1985), 2-18. Google Scholar
- 13 DONGARRA, J. J., BUNCH, J., MOLER, C., AND STEWART, G. LINPACK Users' Guide. SIAM, Philadelphia, Pa., 1979.Google Scholar
- 14 DONGARRA, J. J., DuCRoz, J., HAMMARLING, S., AND HANSON, R. An extended set of Fortran basic linear algebra subprograms. ACM Trans. Math. Softw. 14, i (Mar. 1988), 1-17. Google Scholar
- 15 DONGARRA, J. J., DuCRoz, Z., HAMMARLING, S., AND HANSON, R. An extended set of Fortran basic linear algebra subprograms: Model implementation and test programs. ACM Trans. Math. Softw. 14, I (Mar. 1988), 18-32. Google Scholar
- 16 DONGARRA, J. J., DuCRoz, J., DUFF, I. S., AND HAMMARLING, S. A set of level 3 basic linear algebra subprograms: Model implementation and test programs. This issue, pp. 18-37. Google Scholar
- 17 DONGARRA, J. J., AND DUFF, I.S. Advanced architecture computers. Univ. of Tennessee, Rep. CS-89-90, Nov. 1989. Google Scholar
- 18 DONGARRA, J. J., GUSTAVSON, F., AND KARP, A. Implementing linear algebra algorithms for dense matrices on a vector pipeline machine. SIAM Rev. 26, 1 (1984), 91-112.Google Scholar
- 19 DONGARRA, J. J., HAMMARLING, S., AND SORENSEN, O. C. Block reduction of matrices to condensed forms for eigenvalue computations. Argonne National Lab. Rep. ANL-MCS-TM-99, Sept. 1987.Google Scholar
- 20 DONGARRA, J. J., AND HEWITT, T. Implementing dense linear algebra using multitasking on the CRAY X-MP-4. J. Comput. Appl. Math. 27 (1989), 215-227.Google Scholar
- 21 DONGARRA, J. J., AND SORENSEN, D.C. Linear algebra on high-performance computers. In Proceedings Parallel Computing 85, U. Schendel, Ed. North Holland, Amsterdam, 1986, 113-136.Google Scholar
- 22 DuCRoz, J., NUGENT, S., REID, J., AND TAYLOR, D. Solving large full sets of linear equations in a paged virtual store. ACM Trans. Math. Softw. 7, 4 (1981), 527-536. Google Scholar
- 23 DUFF, I. S. Full matrix techniques in sparse Gaussian elimination. In Numerical Analysis Proceedings, Dundee 1981, Lecture Notes in Mathematics 912. Springer-Verlag, New York, 1981, 71-84.Google Scholar
- 24 GALLIVAN, K., JALBV, W., AND MEIER, U. The use of BLAS3 in linear algebra on a parallel processor with a hierarchical memory. SIAM J. Sci. Star. Comput. 8, 6 (Nov. 1987), 1079-1084. Google Scholar
- 25 GEORGE, A., AND RASHWAN, S. Auxiliary storage methods for solving finite element systems. SIAM J. Sci. Star. Comput. 6, 4 (Oct. 1985), 882-910.Google Scholar
- 26 IBM. Engineering and scientific subroutine library. Program 5668-863, 1986.Google Scholar
- 27 LAWSON, C., HANSON, R. KINCAID, D., AND KROGH, F. Basic linear algebra subprograms for Fortran usage. ACM Trans. Math. Softw. 5 (1979), 308-323. Google Scholar
- 28 LAWSON, C., HANSON, R., KINCAID, D., AND KROGH, F. Algorithm 539: Basic linear algebra subprograms for Fortran usage. ACM Trans. Math. Softw. 5 (1979), 324-325. Google Scholar
- 29 MCKELLAR, A. C., AND COFFMAN, E. G., JR. Organizing matrices and matrix operations for paged memory systems. Commun. ACM 12, 3 (1969), 153-165. Google Scholar
- 30 ROBERT, Y., AND SGUAZZERO, P. The LU decomposition algorithm and its efficient Fortran implementation on the IBM 3090 vector multiprocessor. IBM ECSEC Rep. ICE-0006, 1987.Google Scholar
- 31 SCHREIBER, R. Module design specification (Version 1.0). SAXPY Computer Corp., 255 San Geronimo Way, Sunnyvale, CA 94086, 1986.Google Scholar
- 32 SCHREIBER, R., AND PARLETT, B. Block reflectors: Theory and computation. SIAM J. Numer. Anal. 25, 1 (Feb. 1988), 189-205. Google Scholar
Index Terms
- A set of level 3 basic linear algebra subprograms
Recommendations
Algorithm 679: A set of level 3 basic linear algebra subprograms: model implementation and test programs
This paper describes a model implementation and test software for the Level 3 Basic Linear Algebra Subprograms (Level3 BLAS). The Level3 BLAS are targeted at matrix-matrix operations with the aim of providing more efficient, but portable, ...
Level 3 basic linear algebra subprograms for sparse matrices: a user-level interface
This article proposes a set of Level 3 Basic Linear Algebra Subprograms and associated kernels for sparse matrices. A major goal is to design and develop a common framework to enable efficient, and portable, implementations of iterative algorithms for ...
Reviews
Chaya Gurwitz
The original set of FORTRAN basic linear algebra subprograms, or Level 1 BLAS, included vector operations [1]; the routines in Level 2 BLAS were later added to provide matrix-vector operations [2]. This paper proposes adding a set of Level 3 BLAS, which would be used to perform matrix-matrix operations. The Level 1 and Level 2 BLAS have been adopted by the mathematical programming community as basic routines that are used as building blocks for software development. Efficient machine code implementations of the BLAS that take advantage of specific hardware features can lead to significant computational speedup. Using the BLAS provides portability and ease of maintenance. The proposed Level 3 BLAS are especially suitable for programming on computers with a hierarchy of memory and on machines using parallel processors. For these types of computers, computation is most efficient if the matrices are partitioned into blocks and matrix-matrix operations are performed on the blocks. On architectures that support parallel processing, operations on different blocks may be performed in parallel. The operations proposed for inclusion in the Level 3 BLAS are: matrix-matrix products, rank- k and rank-2 k updates of symmetric and Hermetian matrices, multiplication of a rectangular matrix by a triangular matrix, and solving triangular systems of equations with multiple right-hand sides. The routines are provided for four different FORTRAN data types: real, double precision, complex, and double complex. The paper describes the naming conventions and calling sequences for the subprograms, which generally follow the conventions used in the Level 2 BLAS. The authors discuss the reasoning used in selecting the operations to be included in the Level 3 BLAS. The paper concludes with a discussion of the application of the Level 3 BLAS to solve numerical linear algebra problems in terms of operations on submatrices (blocks). An example illustrates how the Level 3 BLAS can be used to implement the Cholesky factorization as a block algorithm.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments