Sparse Matrix Representation in NetSolve

NetSolve uses the Compressed Row Storage (CRS) for storing sparse matrices. The Compressed Row Storage (CRS) format puts the subsequent nonzeros of the matrix rows in contiguous memory locations. Assuming we have a nonsymmetric sparse matrix, we create vectors: one for floating-point numbers (val), and the other two for integers (col_ind, row_ptr). The val vector stores the values of the nonzero elements of the matrix, as they are traversed in a row-wise fashion. The col_ind vector stores the column indexes of the elements in the val vector. The row_ptr vector stores the locations in the val vector that start a row.

For example, if

1 0 3 1 A = 0 0 5 2 6 1 0 8 4 0 0 0 then, val: 1 3 1 5 2 6 1 8 4 col_ind: 0 2 3 2 3 0 1 3 0 row_ptr: 0 3 5 8 9

Thus, if a problem in NetSolve has the following specifications:

-- sm_prob -- * 1 object in INPUT - input 0: Sparse Matrix Double Precision Real. the sparse matrix * Calling sequence from C or Fortran 11 arguments - Argument #0: - number of rows of input object #0 (sm) - number of columns of input object #0 (sm) - Argument #1: - number of non-zero values of input object #0 (sm) - Argument #2: - pointer to input object #0 (sm) - Argument #3: - column indices of non-zeros of input object #0 (sm) - Argument #4: - row pointers of the sparse matrix #0 (sm)

a Matlab user would call this program as:

>> netsolve('sm_prob', SM);

where SM is a Matlab constructed sparse matrix object.

and a C user would invoke this problem as:

double* val; int* col_index; int* row_ptr; int rows, num_nzeros; /* initialize the arrays and variables */ ... ... ... status = netsl("sm_prob()", rows, num_nzeros, val, col_index, row_ptr);

Problem ID and General Information

The following keywords are required and must occur in the order in which they are presented.

• '@PROBLEM <nickname>' specifies the name of a problem as it will be visible to the NetSolve users (clients).

• '@INCLUDE <name>' specifies a C header file to include (See the example in the section called A Simple Example). There can be several such lines as a problem can call several functions.

• '@DASHI <path>' specifies a default directory in which header files are to be looked for, in a similar way as the -I option of most C compilers. There can be several such lines as a problem can call several functions.

• '@LIB <name>' specifies a library or an object file to link to, or a -L option for the linker (See the example in the section called A Simple Example). If multiple libraries are required, a separate @LIB line must be specified for each library, and the libraries will be linked in the order in which they are specified. The @LIB line(s) can contain variable name substitutions such as $(NETSOLVE_ROOT).

• '@FUNCTION <name>' specifies the name of a function from the underlying numerical software library that is being called to solve the problem. There can be several such lines as a problem can call several functions.

• '@LANGUAGE [C|FORTRAN]' specifies whether the underlying numerical library is written in C or in Fortran. This is used in conjunction with the function names specified with '@FUNCTION' to handle multi-language interoperability.

• '@MAJOR [COL|ROW]' specifies what major should be used to store the input matrices before calling the underlying numerical software. For instance, if the numerical library is LAPACK [lapack], the major must be 'COL'.

• '@PATH <path>' specifies a path-like name for the problems. This path is only a naming convention and is used for presentation purposes.

• '@DESCRIPTION' marks the beginning of the textual description of the problem. This sub-section is mandatory as it is used by the NetSolve management tools to provide information to the NetSolve users (clients) about a specific problem.

Input Specification

• '@INPUT <number>' specifies the number of objects in input to the problem. This line is followed by that corresponding <number> of object descriptions (see below).

• '@OBJECT <object type> <data type> <name>' specifies an object type, data type, and name. The name is only used for presentation purposes. This line is followed by a mandatory textual description of the object. The data types are abbreviated by replacing NETSOLVE_I by I, NETSOLVE_CHAR by CHAR, NETSOLVE_BYTE by B, NETSOLVE_FLOAT by S, NETSOLVE_DOUBLE by D, NETSOLVE_SCOMPLEX by C, and NETSOLVE_DCOMPLEX by Z, (see Table 17-1). Similarly, the object types are abbreviated by replacing NETSOLVE_SCALAR by SCALAR, NETSOLVE_VECTOR by VECTOR, NETSOLVE_MATRIX by MATRIX, NETSOLVE_SPARSEMATRIX by SPARSEMATRIX, NETSOLVE_FILE by FILE, NETSOLVE_PACKEDFILES by PACKEDFILES, NETSOLVE_UPF by UPF, NETSOLVE_STRING by STRING, and NETSOLVE_STRINGLIST by STRINGLIST, (see Table 17-2). The objects of object type FILE, STRING, UPF, and PACKEDFILES do not have a data type. Here are a few examples:

  @OBJECT VECTOR I X An integer vector named 'X' @OBJECT MATRIX D A A double precision real matrix named 'A' @OBJECT FILE foo A file named 'foo'

Output Specification

• '@OUTPUT <number>' specifies the number of objects in output from the problem. This line is followed by that corresponding <number> of object descriptions (see below).

• '@OBJECT <object type> <data type> <name>' specifies an object type, a data type and a name. This line is followed by a mandatory textual description of the object. The abbreviations for data types and object types are as defined previously in the section called Input Specification.

Additional Information

The following list of tags are optional.

• '@MATLAB_MERGE <number1>,<number2>' specifies that the output objects number <number1> and <number2> can be merged as a complex object upon receipt of the numerical results from the Matlab client interface (see Chapter 6).

• '@COMPLEXITY <number1>,<number2>' specifies that given the size of the problem, say n, the asymptotic complexity, say C, of the problem in number of floating point operations is

  C = number1 * n^(number2)

• '@CUSTOMIZED <name>' is an internal customization used by the code developers. It means that the NetSolve server code will do something different (or custom) before invoking a routine. For example, this option is used for the enablement of ScaLAPACK and the sparse solvers. The functionality of this keyword will be expanded in the future. Novice users are advised to avoid using this keyword.

• '@PARALLEL MPI' specifies that the software enabled in the problem description file is parallel and uses MPI. Thus, MPI must be installed on the server to which you are enabling this service.

Pseudo-Code

• '@CODE' marks the beginning of the pseudo-code section.

• '@END_CODE' marks the end of the pseudo-code section.

The pseudo-code is C code that uses the mnemonics described in the section called Mnemonics. This code contains call(s) to the numerical library function(s) that the problem is supposed to use as part of its algorithm. The arguments in the calling sequences of these library routines will be primarily the different mnemonics. In the pseudo-code, the mnemonics are pre- and ap-pended by a '@' to facilitate the parsing. Let us review again the meaning of some possible mnemonics in the pseudo-code:

• '@I0@': pointer to the elements of the first object in input.

• '@mI0@': pointer to an integer that is number of rows of the first object in input.

• '@nO1@': pointer to an integer that is number of columns of the second object in output.

Usually, the pseudo-code is organized in three parts. First, the preparation of the input (if necessary). Second, the call to the numerical library function(s). Third, the update of the output (pointer and sizes). At this point, it is best to give an example. Let us assume that we have access to a hypothetical numerical C library that possesses a function matvec() that performs a matrix-vector multiply for square matrices. The prototype of the function is

void matvec(float *a, float *b, int n, int l);

where a is a pointer to the matrix, b is a pointer to the vector, n is the dimension of the matrix, l is the leading dimension of the matrix and the result is stored in b (overwriting the input). We may define the problem such that the matrix is the first object in the input, the vector the second object in the input, and the result the only object in output. Possible preparations could be for instance the creation of workspace, test of input values to detect mistakes, test of matching dimensions. In this case, we may want to check that the dimension of vector b agrees with the number of columns of matrix a. This can be done as follows:

@CODE if (*@mI1@ != *@nI0@) return NS_PROT_DIM_MISMATCH;

The macro NS_PROT_DIM_MISMATCH is defined by NetSolve. Other macros available are NS_PROT_BAD_VALUES (for invalid input parameters), NS_PROT_INTERNAL_FAILURE (for a malfunction of the numerical software) or NS_PROT_NO_SOLUTION (sometimes useful if no numerical solution has been found and the client is interactive). Notice the use of '*' for accessing the integers at addresses @mI1@ and @nI0@.

The second part of the pseudo-code consists of calling the function matvec and is:

matvec(@I0@,@I1@,*@mI0@,*@mI0@);

A few things can be said on this call. First, we use the '*' to access integers via the pointers. Note that if matvec() were a Fortran subroutine, we would pass the addresses themselves (see Example below). Second, the leading dimension is taken to be equal to the dimension. This code is executed at the server level where the matrix (or sub-matrix) has been received from the client over the network. As such, it has been stored contiguously in memory and has a leading dimension equal to its number of rows. As a general rule, the mnemonics @l[I|O]*@ never appear in the pseudo-code. The last thing to do at this point is to update the output:

@O0@ = @I1@; *@mO0@ = *@mI1@; @END_CODE

The first line expresses the fact that the input has been overwritten by the output. The second line sets the number of rows of the output. The following section gives a complete example, with all of the sections of the problem description.