SparseBLAS

Sparse Basic Linear Algebra Subprograms (BLAS) Library




This page contains software for various libaries developed at NIST for the Sparse Basic Linear Algebra Subprograms (BLAS), which describes kernels operations for sparse vectors and matrices. The current distribution adheres to the ANSI C interface of the BLAS Technical Forum Standard. Older libraries corresponding to previous designs are also included for archival and historical purposes.

Libraries for BLAS Technical Forum (BLAST) interfaces

Original NIST Sparse BLAS (non-compliant interface)


The BLAS Technical Forum Standard defines the following sparse matrix and vector operations:

Sparse Vector (Level 1) Operations

 (1) r <-- op(x) * y sparse dot-product 
 (2) y <-- alpha * x + y sparse vector update
 (3) x <-- y|x sparse gather
 (4) x <-- y|x ; y|x = 0 sparse gather and zero
 (5) y|x <-- x sparse scatter
where r is a scalar, x is a sparse vector, y is a dense vector, y|x denotes the elements of y that are indexed by x.

Matrix-Vector (Level 2) and Matrix-Matrix (Level 3) operations

 (6) y <-- alpha * op(A) * x + y matrix-vector multiply
 (7) C <--- alpha * op(A) * B + C matrix-matrix multiply
 (8) x <-- alpha * op(T) ^(-1) * x matrix-vector triangular solve
 (9) B <-- alpha * op(T) ^(-1) * B matrix-matrix triangular solve
where A is a sparse matrix, T is an triangular sparse matrix, x and y are dense vectors, B and C are (usually tall and thin) dense matrices, and op(A) is either A, the transpose of A, or the Hermitian of A.

Unlike their dense-matrix counterpart routines, the underlying matrix storage format is NOT described by the interface. Rather, sparse matrices must be first constructed before being used in the Level 2 and 3 computationalroutines.

There are various operations available for sparse matrix construction:
 (A) xuscr_begin() point (scalar) construction
 (B) xuscr_block_begin() block construction
 (C) xuscr_variable_block_begin() variable block construction

(D) xuscr_insert_entry() insert single (i,j) value
 (E) xuscr_insert_entries() insert list of (i,j) values
 (F) xuscr_insert_col() insert a sparse colum of values
 (G) xuscr_insert_row() insert a sparse row of values
 (H) xuscr_insert_clique() insert a clique of values
 (I) xuscr_insert_block() insert a block of values
 (J) xuscr_end() terminate matrix construction

(K) usgp() get matrix property
 (L) ussp() set matrix property
 (M) usds() destroy matrix


Each BLAS routine (except for (K), (L), and (M) above) there is a specification for four floating point types (single precision, double precision, complex single precision, and complex double precision) hence, the above specification yields 79 Sparse BLAS routines.

See the following references for further information on [1] the Sparse BLAS specification, and [2] examples and discussion about the interface from some of the key members who worked on the standard:


(1) I. Duff, M. Heroux, R. Pozo, "An Overview of the Sparse Basic Linear Algebra Subprograms: The New Standard from the BLAS Technical Forum," ACM TOMS, Vol. 28, No. 2, June 2002, pp. 239-267.

(2) The BLAS Technical Forum Standard www.netlib.org/blas/blast-forum.





Development Status: Active Maintenance
Privacy Policy
Last Modified: 01/01/2006

Author: Roldan Pozo