# RANDOM_MATRIX: Pseudo-random Matrix Generator

## Generator of pseudo-random sparse matrices

C User Guide
This package generates a random sparse matrix of speciﬁed 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.

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:

• random_matrix_generate() generates a random matrix to the supplied speciﬁcation.

#### 3.2.2 Seed initialization

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

For convenience, the preprocessor macro SPRAL_RANDOM_INITIAL_SEED has been deﬁned, 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 deﬁned 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:

• The matrix dimensions must be consistent with the matrix type.
• For symmetric, Hermitian, and skew-symmetric matrices, only the entries in the lower triangle are returned. Otherwise all entries are returned.
• For positive-deﬁnite matrices, generated values are such that the matrix is diagonally dominant (and hence guarunteed to be positive-deﬁnite).

### 3.3 Subroutines

#### 3.3.1 random_matrix_generate()

To generate an $\mathtt{\text{m}}×\mathtt{\text{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 speciﬁes 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 ﬁrst use, as described in Section 3.2.2.
matrix_type
speciﬁes the matrix type to be generated, as described in Section 3.2.3.
m
speciﬁes the number of rows in the matrix. Restriction: m$\ge$1.
n
speciﬁes the number of columns in the matrix. Restriction: n$\ge$1, and consistent with matrix_type.
nnz
speciﬁes the number of non-zeroes in the matrix. Restriction: nnz$\ge$1 (and nnz$\ge min\left(\mathtt{\text{m}},\mathtt{\text{n}}\right)$ if non-singularity requested, or positive-deﬁnite).
ptr[]
must have size at least n+1. On exit, ptr[j] speciﬁes the position in row[] of the ﬁrst entry in column j and ptr[n]$=$nnz.
row[]
must have size at least nnz. On exit, row[j] speciﬁes 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 $\left[-1,1\right]$. In the positive-deﬁnite case only, diagonal entries are given a value equal to the sum of the oﬀ-diagonal entries in the row plus a value chosen uniformally at random from the interval $\left(0,1\right]$.
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 ﬂag 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\left(m,n\right)$. 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-deﬁnite case, this ﬂag is ignored (it is treated as set). In all other cases, if this ﬂag is not set, a maximum transversal is not guaranteed and the generated matrix may be structurally rank deﬁcient.
SPRAL_RANDOM_MATRIX_SORT
if the generated matrix should have its entries sorted to ascending row number within each column. If this ﬂag 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 $\mathtt{\text{nnz}}.

### 3.5 Method

If structural non-singularity is requested, ﬁrst $min\left(m,n\right)$ entries are generated as follows:

Unsymmetric or Rectangular
Random permutations of the rows and columns are generated. The ﬁrst $min\left(m,n\right)$ 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 $\left(-1,1\right)$. In the positive-deﬁnite 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