LEVEL-3 BASIC LINEAR ALGEBRA SUBPROGRAMS FOR SPARSE MATRICES - A USER-LEVEL INTERFACE

This article proposes a set of Level 3 Basic Linear Algebra Subprogram s and associated kernels for sparse matrices. A major goal is to desig n and develop a common framework to enable efficient, and portable, im plementations of iterative algorithms for sparse matrices on high-perf ormance computers. We have designed the routines to shield the develop er of mathematical software from most of the complexities of the vario us data structures used for sparse matrices. We have kept the interfac e and suite of codes as simple as possible while at the same time incl uding sufficient functionality to cover most of the requirements of it erative solvers and sufficient flexibility to cover most sparse matrix data structures. An important aspect of our framework is that it can be easily extended to incorporate new kernels if the need arises. We d iscuss the design, implementation, and use of subprograms for the mult iplication of a full matrix by a sparse one and for the solution of sp arse triangular systems with one or more (full) right-hand sides. We i nclude a routine for checking the input data, generating a new sparse data structure from that input, and scaling a sparse matrix. The new d ata structure for the transformation can be specified by the user or c an be chosen automatically by vendors to be efficient on their machine s. We also include a routine for permuting the columns of a sparse mat rix and one for permuting the rows of a full matrix.