Sparse extensions to the FORTRAN Basic Linear Algebra Subprograms

ABSTRACT

This paper describes an extension to the set of Basic Linear Algebra Subprograms. The extension is targeted at sparse vector operations, with the goal of providing efficient, but portable, implementations of algorithms for high-performance computers.

REFERENCES

• 1: ASHCRAFT, C. C , GRIMES, R. G., LEWIS, J. G, PEYTON, B. W, AND SIMON, H.D. Progress in sparse matrix methods for large hnear systems on vector supercomputers Int. J. Supercornput. Appl. 1, 4 (Dec., 1987), 10-30.
• 2: David S. Dodson , John G. Lewis, Issues relating to extension of the Basic Linear Algebra Subprograms, ACM SIGNUM Newsletter, v.20 n.1, p.19-22, January 1985 [doi>10.1145/1057935.1057937]
• 3: David S. Dodson , John G. Lewis, Proposed sparse extensions to the Basic Linear Algebra Subprograms, ACM SIGNUM Newsletter, v.20 n.1, p.22-25, January 1985 [doi>10.1145/1057935.1057938]
• 4: David S. Dodson , Roger G. Grimes , John G. Lewis, Algorithm 692; model implementation and test package for the Sparse Basic Linear Algebra Subprograms, ACM Transactions on Mathematical Software (TOMS), v.17 n.2, p.264-272, June 1991 [doi>10.1145/108556.108582]
• 5: DONGARRA, J. J, BUNCH, J. R., MOLER, C. B., AND STEWART, G W. LINPACK User's Guzde, SIAM , Philadelphia, Pa., 1979.
• 6: Jack J. Dongarra , Jeremy Du Croz , Sven Hammarling , Richard J. Hanson, An extended set of FORTRAN basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.14 n.1, p.1-17, March 1988 [doi>10.1145/42288.42291]
• 7: Jack Dongarra , Jeremy Du Croz , Iain Duff , Sven Hammarling, A proposal for a set of level 3 basic linear algebra subprograms, ACM SIGNUM Newsletter, v.22 n.3, p.2-14, July 1987 [doi>10.1145/36318.36319]
• 8: DUFF, I. S. MA28: A Set of FORTRAN Subroutines for Sparse Unsymmetric Linear Systems. AERE Report R.8730, HMSO, London, 1971.
• 9: Iain S Duff , Albert M Erisman , John K Reid, Direct methods for sparse matrices, Oxford University Press, Inc., New York, NY, 1986
• 10: EISENSTAT, S. C., GURSKY, M. C., SCHULTZ, M. H., AND SHERMAN, A.H. Yale sparse matrix package I. The symmetric codes. Int. J. Num. Math. Eng. 18 (1982), 1145-1151.
• 11: GEORGE, A., AND HEATH, M. T. Solution of sparse linear least squares problems using Givens rotations. In Linear Algebra and Its Applications 34 (1980), 69-82.
• 12: Alan George , Joseph W. Liu, Computer Solution of Large Sparse Positive Definite, Prentice Hall Professional Technical Reference, 1981
• 13: GEORGE, A., AND LIU, J. W. Householder reflections versus Givens rotations in sparse orthogonal decomposition. In Linear Algebra and Applications 88-89. (1987), 304-311.
• 14: GRIMES, R. G., LEwIs, J. G. AND SIMON, H. D. Experiences in solving large eigenvalue problems on the CRAY X-MP. In Proceedings of the Eighteenth Semiannual CRAY Users Group Meeting (Garmisch, Germany, Oct. 1986), 95-99.
• 15: GRIMES, R. G., LEwis, J. G. AND SIMON, H. D. Eigenvalue problems and algorithms in structural engineering. In Large Scale Eigenvalue Problems, J. Cullum and R. Willoughby, Eds., Elsevier North-Holland, 1986, pp. 81-93.
• 16: R. J. Hanson , F. T. Krogh , C. L. Lawson, Improving the efficiency of portable software for linear algebra, ACM SIGNUM Newsletter, v.8 n.4, p.16-16, October 1973 [doi>10.1145/1052646.1052653]
• 17: C. L. Lawson , R. J. Hanson , D. R. Kincaid , F. T. Krogh, Basic Linear Algebra Subprograms for Fortran Usage, ACM Transactions on Mathematical Software (TOMS), v.5 n.3, p.308-323, Sept. 1979 [doi>10.1145/355841.355847]
• 18: C. L. Lawson , R. J. Hanson , F. T. Krogh , D. R. Kincaid, Algorithm 539: Basic Linear Algebra Subprograms for Fortran Usage [F1], ACM Transactions on Mathematical Software (TOMS), v.5 n.3, p.324-325, Sept. 1979 [doi>10.1145/355841.355848]
• 19: John G. Lewis , Horst D. Simon, The impact of hardware gather/scatter on sparse Gaussian elimination, SIAM Journal on Scientific and Statistical Computing, v.9 n.2, p.304-311, March 1988 [doi>10.1137/0909019]
• 20: SIMON, H.D. Incomplete LU preconditioners for conjugate gradient type iterative methods. Paper SPE 13533, In Proceedings of the Eighth SPE symposium on Reservoir Simulations (Feb., 1985).

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Software libraries
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: FORTRAN

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Portability**

General Terms:
Algorithms, Standardization

Keywords:
Sparse Blas, utilities