Contents

SPRAL

RANDOM_MATRIX: Pseudo-random Matrix Generator

SPRAL_RANDOM_MATRIXv1.0.0

Generator of pseudo-random sparse matrices

C User Guide
This package generates a random sparse matrix of specified size and density in compressed sparse column format. Either the pattern or both the pattern and values can be generated. Both symmetric and unsymmetric matrices can be generated, and structural non-degeneracy can optionally be ensured, and the row indices can be sorted within columns.
Jonathan Hogg (STFC Rutherford Appleton Laboratory)

Major Version History

2014-03-06 Version 1.0.0
Initial release

3.1 Installation

Please see the SPRAL install documentation.

3.2 Usage overview

3.2.1 Calling sequences

Access to the package requires inclusion of either spral.h (for the entire SPRALlibrary) or spral_random_matrix.h (for just the relevant routines). i.e.

   #include "spral.h"

The following functions is available to the user:

3.2.2 Seed initialization

The random number generator’s state is stored in the variable state. Before its first use, state should be initialized by the user to an initial seed value.

For convenience, the preprocessor macro SPRAL_RANDOM_INITIAL_SEED has been defined, and state may be declared and initialized using a statement of the following form:

   int state = SPRAL_RANDOM_INITIAL_SEED;

At any time the user may change the seed, for example to restore a previous value. A call to random_matrix_generate() with the same parameters and the same value of state will produces the same pseudo-random matrix.

3.2.3 Matrix types

The enum spral_matrix_type is defined as follows:

enum spral_matrix_type {  
   // User doesn’t wish to specify, use default behaviour  
   SPRAL_MATRIX_UNSPECIFIED=0,  
   // Rectangular matrix, m!=n  
   SPRAL_MATRIX_REAL_RECT=1,        SPRAL_MATRIX_CPLX_RECT=-1,  
   // Square unsymmetric matrix m==n  
   SPRAL_MATRIX_REAL_UNSYM=2,       SPRAL_MATRIX_CPLX_UNSYM=-2,  
   // Symmetric/Hermitian positive-definite matrix  
   SPRAL_MATRIX_REAL_SYM_PSDEF=3,   SPRAL_MATRIX_CPLX_HERM_PSDEF=-3,  
   // Symmetric/Hermitian indefinite matrix  
   SPRAL_MATRIX_REAL_SYM_INDEF=4,   SPRAL_MATRIX_CPLX_HERM_INDEF=-4,  
   // Complex symmetric matrix  
                                    SPRAL_MATRIX_CPLX_SYM=-5,  
   // Skew-symmetric matrix  
   SPRAL_MATRIX_REAL_SKEW=6,        SPRAL_MATRIX_CPLX_SKEW=-6  
};

For the purposes of this package, the behaviour is altered based on the matrix type as follows:

3.3 Subroutines

3.3.1 random_matrix_generate()

To generate an m×n random matrix with nnz non-zero entries, the following routine is provided.

int spral_random_matrix_generate(int *state, enum spral_matrix_type matrix_type,
  int m, int n, int nnz, int *ptr, int *row, double *val, int flags);

A return value of 0 indicates success. For non-zero values, see Section 3.4.

If matrix_type specifies a symmetric or skew symmetric matrix, only the lower half matrix will be returned to the user.

*state
is the state of the pseudo-random number generator used. It should be initialized before the first use, as described in Section 3.2.2.
matrix_type
specifies the matrix type to be generated, as described in Section 3.2.3.
m
specifies the number of rows in the matrix. Restriction: m ≥1.
n
specifies the number of columns in the matrix. Restriction: n ≥1, and consistent with matrix_type.
nnz
specifies the number of non-zeroes in the matrix. Restriction: nnz ≥1 (and nnz ≥ min(m,n) if non-singularity requested, or positive-definite).
ptr[]
must have size at least n+1. On exit, ptr[j] specifies the position in row[] of the first entry in column j and ptr[n] =nnz.
row[]
must have size at least nnz. On exit, row[j] specifies the row to which the j-th entry belongs.
val[]
may be NULL. If it is non-NULL, it must have size at least nnz. On exit, val[j] gives the value of the j-th entry. Entries are generated from a uniform distribution on the interval [−1,1]. In the positive-definite case only, diagonal entries are given a value equal to the sum of the off-diagonal entries in the row plus a value chosen uniformally at random from the interval (0,1].
flags
is the logical combination (i.e. bitwise-or) of the following possible values:
SPRAL_RANDOM_MATRIX_FINDEX
if the entries of the arrays ptr[] and row[] should be numbered from should be numbered from 1 (i.e. Fortran indexing). If this flag is not set, these arrays will be numbered from 0 (i.e. C indexing).
SPRAL_RANDOM_MATRIX_NONSINGULAR
if the generated matrix should be non-singular. The matrix is guaranteed to have a transversal of size min(m,n). In the symmetric or skew symmetric case this will be the natural diagonal. In the unsymmetric and rectangular cases a random matching is used. In the symmetric positive-definite case, this flag is ignored (it is treated as set). In all other cases, if this flag is not set, a maximum transversal is not guaranteed and the generated matrix may be structurally rank deficient.
SPRAL_RANDOM_MATRIX_SORT
if the generated matrix should have its entries sorted to ascending row number within each column. If this flag is not set, entries may be returned in a random order within each column.

If none of the above options is desired, this value should be set to 0.

3.4 Return codes

A successful call is indicated by a return value of zero. A negative value is associated with an error message.

Possible negative values are:

−1 An allocation error has occurred.
−2 An invalid value of matrix_type was supplied.
−3 At least one of m, n, or nnz was less than 1.
−4 The (in)equality of m and n was inconsistent with matrix_type.
−5 A non-singular matrix was requested, but nnz < min(m,n).

3.5 Method

If structural non-singularity is requested, first min(m,n) entries are generated as follows:

Unsymmetric or Rectangular
Random permutations of the rows and columns are generated. The first min(m,n) entries of these permutations are used to specify the entries of a maximum transversal.
Symmetric
The diagonal is added to the matrix explicitly.

The remaining non-zero entries are then assigned to columns uniformally at random. In the symmetric case, a weighting is used in proportion to the number of entries below the diagonal. If the selected column for a given non-zero is already full, a new random sample is drawn.

Once the number of entries in each column has been determined, and any required maximum transversal inserted, row indices are determined uniformally at random. Should a non-zero in that row already be present in the column, a new random sample is drawn.

In all cases, values are drawn uniformally at random from the interval (−1,1). In the positive-definite case, a post-processing step sums the absolute values of all the entries in each column and replaces the diagonal with this value.

3.6 Example

The following code generates a random 4 × 5 matrix with 8 non-zeroes that is non-singular.

/* examples/C/random_matrix.c - Example code for SPRAL_RANDOM_MATRIX package */  
#include "spral.h"  
#include <stdio.h>  
#include <stdlib.h>  
 
void main(void) {  
   int state = SPRAL_RANDOM_INITIAL_SEED;  
 
   int m=4, n=5, nnz=8;  
   int ptr[n+1], row[nnz];  
   double val[nnz];  
 
   /* Generate matrix */  
   printf("Generating a %d x %d non-singular matrix with %d non-zeroes\n",  
         m, n, nnz);  
   if(spral_random_matrix_generate(&state, 0, m, n, nnz, ptr, row, val,  
            SPRAL_RANDOM_MATRIX_NONSINGULAR)) {  
      printf("Error return from spral_random_matrix_generate()\n");  
      exit(1);  
   }  
 
   /* Print matrix using utility routine from SPRAL_MATRIX_UTILS package */  
   printf("Generated matrix:\n");  
   spral_print_matrix(-1, 0, m, n, ptr, row, val, 0);  
}
This produces the following output:
Generating a 4 x 5 non-singular matrix with 8 non-zeroes  
Generated matrix:  
Matrix of undefined type, dimension 4x5 with 8 entries.  
0:                                         -1.0744E-01   9.1000E-01  
1:                             9.5364E-01                1.0912E-01  
2:                                          1.1631E-01  -5.8957E-01  
3:  -9.0631E-01                                          7.7313E-01

Funded by EPSRC grant EP/J010553/1