Sun S3L 4.0 Software Programming Guide
|    
|
| Sun S3L 4.0 Software Programming Guide
|
|
| C H A P T E R 12 |
|
Basic Sparse Matrix Routines |
This section describes various Sun S3L routines that perform fundamental linear algebra operations on sparse matrices. They are described in the following sections:
All of the sparse matrix functions work with both real and complex data types.
A matrix is considered to be sparse if special techniques can be used to take advantage of the structure of the matrix (that is, the nonzero elements and their locations).
Many different ways of storing sparse matrices have been devised to realize these advantages, which can mean better efficiency in both memory use and arithmetic operations. The differences among these sparse storage schemes are mostly reflections of such issues as the amount of storage required, the degree of indirect addressing necessary to perform the kernel operations (such as matrix-vector product), and the suitability for a range of different processor architectures.
The Sun S3L sparse routines support the following widely used sparse formats:
The Coordinate format consists of the following three arrays:
To illustrate the Coordinate format, consider the following sample 4 x 6 sparse matrix:
3.14 0 0 20.04 0 0 0 27 0 0 -0.6 0 0 0 -0.01 0 0 0 -0.031 0 0 0.08 0 314.0 |
Using zero-based indexing, the contents of the indx, jndx, and val arrays might be as follows:
indx = ( 3, 1, 0, 3, 2, 0, 1, 3 ), jndx = ( 5, 1, 3, 3, 2, 0, 4, 0 ), val = ( 314.0, 27.0, 20.04, 0.08, -0.01, 3.14, -0.6, -0.031 ) |
For example, the row and column indices 0 and 3 show that the value 20.04 belongs in the first row and fourth column of the sparse matrix.
The Compressed Sparse Row format stores the sparse matrix values in the following three arrays:
The contents of the ptr, indx, and val arrays might be as follows:
ptr = ( 0, 2, 4, 5, 8 ), indx = ( 0, 3, 1, 4, 2, 0, 3, 5 ), val = ( 3.14, 20.04, 27.0, -0.6, -0.01, -0.031, 0.08, 314.0 ) |
For example, ptr[1] = 2 indicates that the first nonzero element in row 1 is stored in val[2] (= val[ptr[1]]), which is 27.0.
The Compressed Sparse Column format also stores the sparse matrix in three arrays, but the pointer and index references swap axes. In other words, the Compressed Sparse Column format can be viewed as the Compressed Sparse Row format for the transpose of the sparse matrix. In the Compressed Sparse Column format, the three internal arrays are:
This matrix-transpose relationship can be seen by comparing the following values in the ptr and indx arrays with the corresponding arrays in the Compressed Sparse Row example:
ptr = ( 0, 2, 3, 4, 6, 7, 8 ), indx = ( 0, 3, 1, 2, 0, 3, 1, 3 ), val = ( 3.14, -0.031, 27.0, -0.01, 20.04, 0.08, -0.6, 314.0 ) |
Note that, in the Compressed Sparse Column format, the nonzero elements in val are stored column by column, instead of row by row, as in the Compressed Sparse Column format.
For example, ptr[5] = 7 means that the first nonzero element of column 5 is stored in val[7] (= val[ptr[5]]), which is 314.0, and its row index is stored in indx[7] (= indx[ptr[5]]), which is 3.
The first three sparse matrix formats all provide natural layouts for point sparse matrices. However, for matrices with nonzero elements clustered in blocks, Variable Block Row (VBR) format offers a more efficient representation. For any block-structured matrices, such as those derived from a discretized partial differential equation, using VBR format can reduce the amount of integer storage, and the block representation of the matrix enables the numerical algorithms to perform the kernel matrix operations more efficiently on the block entries.
The data structure of the VBR format consists of the following six arrays:
To illustrate the Variable Block Row data layout, consider the following 6 x 8 sparse matrix with a variable block partitioning:
Using zero-based indexing, the matrix could be stored in VBR format, as follows:
In array rptr, 0, 2, 3, and 6 are pointers to the boundaries of the block rows. Likewise in cptr, 0, 2, 5, 6, and 8 are pointers to the boundaries of the block columns.
In array bptr, 0, 2, 4, and 6 are pointers to the location in bindx of the first nonzero block entry of each block row.
These block-based pointers are illustrated in the following figure, which represents the block structure of the original 6 x 8 sparse matrix. It shows the first block row with two nonzero blocks, one in block column 0 and the other in block column 2. The next nonzero block is at block row 1 and block column 1, and so forth. Block 6 is the outer boundary of the block rows.
0 1 2 3 4 +----+----+----+----+ 0 | b0 | | b1 | | +----+----+----+----+ 1 | | b2 | b3 | | +----+----+----+----+ 2 | | | b4 | b5 | +----+----+----+----+ 3 |
In array bindx, 0, 2, 1, 2, 2, and 3 are block column indices for each of the six nonzero block entries.
In array indx, 0, 4, 6, 9, 10, 13, and 19 point to the locations in val of the first nonzero block entry from each block row.
The last array, val, stores nonzero blocks b0, b1, ..., b5 block by block with each block stored as a dense matrix in standard column-by-column form. Moreover, the starting location in val where the first element of each block gets stored is indexed by array indx.
The VBR data structure can be understood by analyzing the representation of block row 1 for example.
First, bptr[1] = 2 indicates that b2, the first nonzero block from block row 1 is from block column 1, as indicated by bindx[2] = bindx[bptr[1]] = 1.
Second, bptr[1] = 2 also indexes into indx. That is, indx[bptr[1]] = indx[2] = 6 points to val[6] = val[indx[bptr[1]] = val[indx[2]]), where 6 is the location in val at which the first element of b2, 7.0, is stored.
The next nonzero block in block row 1 is b3, its block column index is 2, as indicated by bindx[bptr[1]+1] = bindx[3] = 2, and the first element of block b3 is stored in val[9] (= val[indx[bptr[1]+1]] = val[indx[3]]), which is 10.0.
The Sun S3L routine S3L_declare_sparse can be used to create a sparse matrix Sun S3L array handle that describes an array that conforms to the Coordinate, Compressed Sparse Row, or Compressed Sparse Column format.
|
Note - A method for using S3L_declare_sparse to create a Sun S3L array handle for an array with a Variable Block Row format is described later in Converting a Sparse Matrix From One Format to Another. |
S3L_declare_sparse has the following argument syntax:
S3L_declare_sparse(A, spfmt, m, n, row, col, val, ier) |
Upon exit, A contains a Sun S3L array handle for the global general sparse matrix. This handle can be used in subsequent calls to other Sun S3L sparse array functions.
spfmt indicates which sparse format is to be used in representing the sparse matrix. Its value can be any one of:
m indicates the number of rows in the sparse matrix.
n indicates the number of columns in the sparse matrix.
row is an integer parallel array of rank 1. Its length and content can vary, depending on which sparse format is used:
col is an integer global array of rank 1 with the same length as array val. Its use will vary, depending on which sparse format is used:
val is a parallel array of rank 1, containing the nonzero elements of the sparse matrix. The storage pattern varies, depending on which sparse format is used:
|
Note - Because row, col, and val are copied to the working arrays described earlier (indx, jndx, ptr, and val), they can be deallocated immediately following the S3L_declare_sparse call. |
If the call is made from a Fortran program, error status will be in ier.
For detailed descriptions of the Fortran and C bindings for this routine, see the S3L_declare_sparse(3) man page or the corresponding description in the Sun S3L Software Reference Manual.
Examples showing S3L_declare_sparse in use can be found in:
/opt/SUNWhpc/examples/s3l/sparse/ex_sparse2.c |
S3L_read_sparse reads sparse matrix data from an ASCII file and distributes the data to all participating processes. Upon successful completion, S3L_read_sparse returns a Sun S3L array handle in A that represents the distributed sparse matrix.
S3L_read_sparse supports the following sparse matrix formats:
Under the S3L_SPARSE_COO format, S3L_read_sparse can also read data supplied in either of two Coordinate formats that are distributed by MatrixMarket
(http://gams.nist.gov/MatrixMarket/). The two supported MatrixMarket formats are real general and complex general.
MatrixMarket files always use one-based indexing. Consequently, they can only be used directly by Fortran programs. For a C or C++ program to use a MatrixMarket file, it must call the F77 application program interface. This is illustrated by the program example:
/opt/SUNWhpc/examples/s3l/sparse/ex_sparse.c |
S3L_read_sparse has the following argument syntax:
S3L_read_sparse(A, spfmt, m, n, nnz, type, fname, dfmt, ier) |
Upon exit, A contains a Sun S3L array handle for the global general sparse matrix. This handle can be used in subsequent calls to other Sun S3L sparse array functions.
spfmt indicates which sparse format is to be used. Its value can be any one of:
m indicates the number of rows in the sparse matrix.
n indicates the number of columns in the sparse matrix.
nnz indicates the number of nonzero elements in the sparse matrix.
type indicates the Sun S3L data type of the sparse array. It must be one of:
fname is a scalar character variable that names the ASCII file that contains the sparse matrix data.
dfmt specifies the format of the data to be read from the file named by fname. Allowed values are ascii and ASCII.
If the call is made from a Fortran program, error status will be in ier.
For detailed descriptions of the Fortran and C bindings for this routine, see the S3L_read_sparse(3) man page or the corresponding description in the Sun S3L Software Reference Manual.
Examples showing S3L_read_sparse in use can be found in:
/opt/SUNWhpc/examples/s3l/sparse/ex_sparse.c /opt/SUNWhpc/examples/s3l/sparse-f/ex_sparse2.f |
If you want to create a sparse matrix but don't have a source of data for its contents, you can use S3L_rand_sparse to create a global general sparse matrix that is populated with a set of random values. You specify the sparsity pattern to be used, as well as density of nonzero values, as part of the S3L_rand_sparse call.
S3L_rand_sparse supports all four sparse formats.
S3L_rand_sparse has the following argument syntax:
S3L_rand_sparse(A, spfmt, stype, m, n, density, type, seed, ...,ier) |
Upon exit, A contains a Sun S3L array handle for the global general sparse matrix. This handle can be used in subsequent calls to other Sun S3L sparse array functions.
spfmt indicates which sparse format is to be used. Its value can be any one of:
If S3L_SPARSE_VBR is specified, two additional arguments should also be supplied:
For all formats except VBR, m indicates the number of rows in the sparse matrix. For the S3L_SPARSE_VBR format, m denotes the number of block rows in the sparse matrix.
For all formats except VBR, n indicates the number of columns in the sparse matrix. For the S3L_SPARSE_VBR format, n denotes the number of block columns in the sparse matrix.
density is a positive number less than or equal to 1.0. It suggests the approximate density of the array. For example, if 0.1 is supplied as the density argument, approximately 10% of the array elements will have nonzero values.
type specifies the data type of the sparse array. It must be one of:
seed is an integer that is used internally to initialize the random number generators. It affects both the pattern and the values of the array elements. The results are independent of the number of processes on which the function is invoked.
If the call is made from a Fortran program, error status will be in ier.
For detailed descriptions of the Fortran and C bindings for this routine, see the S3L_rand_sparse(3) man page or the corresponding description in the Sun S3L Software Reference Manual.
Examples showing S3L_rand_sparse in use can be found in:
/opt/SUNWhpc/examples/s3l/iter/ex_iter.c /opt/SUNWhpc/examples/s3l/iter-f/ex_iter.f |
S3L_write_sparse causes the process with MPI rank 0 to write the global sparse matrix A into a file. The matrix data will be written in a user-specified format, which can be any one of:
S3L_write_sparse has the following argument syntax:
S3L_write_sparse(A, spfmt, fname, dfmt, ier) |
A is a Sun S3L array handle for the global general sparse matrix to be written.
spfmt indicates which sparse format is to be used. Its value can be any one of:
fname is a scalar character variable that names the file to which the sparse matrix data will be written.
dfmt is a scalar character variable that specifies the data file format to be used in writing the sparse matrix data. The allowed values are ascii and ASCII.
If the call is made from a Fortran program, error status will be in ier.
For detailed descriptions of the Fortran and C bindings for this routine, see the S3L_write_sparse(3) man page or the corresponding description in the Sun S3L Software Reference Manual.
Examples showing S3L_write_sparse in use can be found in:
/opt/SUNWhpc/examples/s3l/sparse/ex_sparse.c /opt/SUNWhpc/examples/s3l/sparse-f/ex_sparse.f |
S3L_print_sparse prints all nonzero values of a global general sparse matrix and their corresponding row and column indices to standard output.
For example, the following 4 x 6 sample matrix:
3.14 0 0 20.04 0 0 0 27 0 0 -0.6 0 0 0 -0.01 0 0 0 -0.031 0 0 0.08 0 314.0 |
could be printed by a C program in the following manner.
4 6 8 (0,0) 3.140000 (0,3) 200.040000 (1,1) 27.000000 (1,4) -0.600000 (2,2) -0.010000 (3,0) -0.031000 (3,3) 0.080000 (3,5) 314.000000 |
The first line prints three integers, m, n, and nnz, which represent the number of rows, columns, and the total number of nonzero elements in the matrix, respectively.
If the matrix is represented in the S3L_SPARSE_VBR format, three additional integers are printed: bm, bn, and bnnz. These integers indicate the number of block rows and block columns and the total number of nonzero block entries.
Note that, in the previous example, the row and column indices are zero-based, which means that the call to S3L_print_sparse was made from a C program. If the call had used the Fortran interface, the row and column indices would be one-based, as shown below:
4 6 8 (1,1) 3.140000 (1,4) 200.040000 (2,2) 27.000000 (2,5) -0.600000 (3,3) -0.010000 (4,1) -0.031000 (4,4) 0.080000 (4,6) 314.000000 |
S3L_print_sparse has the following argument syntax:
S3L_print_sparse(A, ier) |
A is a Sun S3L array handle for the global general sparse matrix to be printed.
If the call is made from a Fortran program, error status will be in ier.
For detailed descriptions of the Fortran and C bindings for this routine, see the S3L_print_sparse(3) man page or the corresponding description in the Sun S3L Software Reference Manual.
Examples showing S3L_print_sparse in use can be found in:
/opt/SUNWhpc/examples/s3l/sparse/ex_sparse.c /opt/SUNWhpc/examples/s3l/sparse/ex_sparse2.c /opt/SUNWhpc/examples/s3l/sparse-f/ex_sparse.f |
S3L_convert_sparse converts a Sun S3L sparse matrix that is represented in one sparse format to a different sparse format. It supports all four of the Sun S3L sparse formats.
S3L_convert_sparse has the following argument syntax:
S3L_convert_sparse(A, B, spfmt, ..., ier) |
A is a Sun S3L array handle for the global general sparse matrix whose format is to be converted--that is, the source matrix.
On exit, A is the Sun S3L array handle for the global general sparse matrix that resulted from the conversion.
B is a Sun S3L array handle for the converted global general sparse matrix--that is, the destination matrix.
The next argument, spfmt, specifies the sparse format to be used for the destination matrix. The value of spfmt must be one of:
If the spfmt value is S3L_SPARSE_VBR, you can control the block-partitioning structure by supplying the following additional arguments after spfmt:
|
Note - To use the Sun S3L internal blocking algorithm rather than controlling the block partitioning explicitly, specify these four arguments as NULL pointers (for C/C++) or set to -1 (for F77/F90). |
If the call is made from a Fortran program, error status will be in ier.
For detailed descriptions of the Fortran and C bindings for this routine, see the S3L_convert_sparse(3) man page or the corresponding description in the Sun S3L Software Reference Manual.
Examples showing S3L_convert_sparse in use can be found in:
/opt/SUNWhpc/examples/s3l/sparse/ex_sparse1.c /opt/SUNWhpc/examples/s3l/sparse-f/ex_sparse1.f |
S3L_matvec_sparse computes the product of a global general sparse matrix with a global dense vector. The sparse matrix is described by the Sun S3L array handle A. The global dense vector is described by the Sun S3L array handle x. The product is stored in the global dense vector described by the Sun S3L array handle y.
The array handle A is produced by a prior call to one of the following routines:
S3L_matvec_sparse has the following argument syntax:
S3L_matvec_sparse(y, A, x, ier) |
y is a global array of rank 1, with the same data type and precision as A and x. Its length is equal to the number of rows in the sparse matrix. Upon completion, y contains the product of the sparse matrix A and the vector x.
A is a Sun S3L array handle for the global general sparse matrix.
x is a global array of rank 1, with the same data type and precision as A and y and with a length equal to the number of columns in the sparse matrix.
If the call is made from a Fortran program, error status will be in ier.
For detailed descriptions of the Fortran and C bindings for this routine, see the S3L_matvec_sparse(3) man page or the corresponding description in the Sun S3L Software Reference Manual.
Examples showing S3L_matvec_sparse in use can be found in:
/opt/SUNWhpc/examples/s3l/sparse/ex_sparse.c /opt/SUNWhpc/examples/s3l/sparse-f/ex_sparse.f /opt/SUNWhpc/examples/s3l/iter/ex_iter.c /opt/SUNWhpc/examples/s3l/iter-f/ex_iter.f |
S3L_free_sparse deallocates the memory reserved for a sparse matrix and the associated array handle.
S3L_free_sparse has the following argument syntax:
S3L_free_sparse(A, ier) |
A is a Sun S3L array handle for the parallel Sun S3L array that was allocated by a previous call to S3L_declare_sparse, S3L_read_sparse, S3L_rand_sparse, or S3L_convert_sparse.
If the call is made from a Fortran program, error status will be in ier.
For detailed descriptions of the Fortran and C bindings for this routine, see the S3L_free_sparse(3) man page or the corresponding description in the Sun S3L Software Reference Manual.
| Sun S3L 4.0 Software Programming Guide
| 817-0086-10 |
|
Copyright © 2003, Sun Microsystems, Inc. All rights reserved.