RANDOM_MATRIX: Pseudo-random Matrix Generator


Generator of pseudo-random sparse matrices

Fortran 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 a USE statement:

   use spral_random_matrix

The following procedure is available to the user:

3.2.2 Derived types

The user must supply a random number generator state using the type defined in the spral_random module. The following pseudo-code illustrates how such a generator may be defined.

      use spral_random, only : random_state  
      type (random_state) :: state  

Further details are given in the documentation for the spral_random module. The user may wish to use the routines get_random_seed() and set_random_seed() to control the matrix generated.

3.2.3 Optional arguments

We use square brackets [ ] to indicate optional arguments. In each call, optional arguments follow the argument info. Since we reserve the right to add additional optional arguments in future releases of the code, we strongly recommend that all optional arguments be called by keyword, not by position.

3.3 Subroutines

3.3.1 random_matrix_generate()

To generate an m×n random matrix with nnz non-zero entries,
call random_matrix_generate(state, matrix_type, m, n, nnz, ptr, row, flag[, stat, val, nonsingular, sort])

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

is an INTENT(INOUT) scalar of type random_state. It is used as the state of the pseudo-random number generator used.
is an INTENT(IN) scalar of type default INTEGER. It specifies the matrix type to be generated, and must be one of:
  • Undefined (matrix generated will be unsymmetric/rectangular)
  • Rectangular matrix (mn)
  • Unsymmetric (m = n)
  • Symmetric positive-definite (m = n, nnz entries in lower triangle returned, matrix made diagonally dominant if val is present, non-singularity assured regardless of the value of the optional argument nonsingular)
  • Symmetric indefinite (m = n, nnz entries in lower triangle returned)
  • Skew symmetric (m = n, nnz entries in lower triangle returned)
is an INTENT(IN) scalar of type default INTEGER that specifies the number of rows in the matrix. Restriction: m 1.
is an INTENT(IN) scalar of type default INTEGER that specifies the number of columns in the matrix. Restriction: n 1, and consistent with matrix_type.
is an INTENT(IN) scalar of type default INTEGER that specifies the number of non-zeroes in the matrix. Restriction: nnz 1 (and nnz min(m,n) if non-singularity requested, or positive-definite).
is an INTENT(OUT) array of type default INTEGER and size n+1. On exit, ptr(j) specifies the position in row(:) of the first entry in column j and ptr(n+1) =nnz+1.
is an INTENT(OUT) array of type default INTEGER and size nnz. On exit, row(j) specifies the row to which the j-th entry belongs.
is an INTENT(OUT) scalar of type default INTEGER. On exit, it specifies a return code that indicates success with the value 0 or failure with a negative value detailed in Section 3.4.
is an optional INTENT(OUT) scalar of type default INTEGER. If present, on exit it returns the value of the Fortran stat parameter on the last allocate() call. In particular, if flag indicates an allocation failure, it returns further information on the failure.
is an optional INTENT(OUT) array of type REAL(wp) and size 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].
is an optional INTENT(IN) scalar of type LOGICAL. If present with the value .true., the generated 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 value is ignored (it is treated as .true.). In all other cases, if nonsingular is not present, or is present with the value .false., a maximum transversal is not guaranteed and the generated matrix may be structurally rank deficient.
is an optional INTENT(IN) scalar of type LOGICAL. If present with the value .true., the row entries of the generated matrix will be sorted into ascending order within each column. Otherwise, if sort is not present, or is present with the value .false., entries may be returned in a random order within each column.

3.4 Return codes

A successful return is indicated by flag having the value zero. A negative value is associated with an error message.

Possible negative values are:

1 An allocation error has occurred. If present, stat will contain the Fortran stat value returned by the failed allocate() call.
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.
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 range (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/Fortran/random_matrix.f90 - Example code for SPRAL_RANDOM_MATRIX pkg  
program random_matrix_example  
   use spral_matrix_util, only : print_matrix  
   use spral_random, only : random_state  
   use spral_random_matrix  
   implicit none  
   integer, parameter :: wp = kind(0d0)  
   integer, parameter :: m=4, n=5, nnz=8  
   integer :: ptr(n+1), row(nnz)  
   real(wp) :: val(nnz)  
   integer :: flag  
   type(random_state) :: state  
   ! Generate matrix  
   write(*, "(a,i3,a,i3,a,i3,a)") &  
      "Generating a ", m, " x", n, " non-singular matrix with ", nnz, &  
      " non-zeroes"  
   call random_matrix_generate(state, 0, m, n, nnz, ptr, row, flag, val=val, &  
   ! Print matrix using utility routine from SPRAL_MATRIX_UTILS package  
   write(*, "(a)") "Generated matrix:"  
   call print_matrix(6, -1, 0, m, n, ptr, row, val=val)  
end program random_matrix_example
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.  
1:                                         -1.0744E-01   9.1000E-01  
2:                             9.5364E-01                1.0912E-01  
3:                                          1.1631E-01  -5.8957E-01  
4:  -9.0631E-01                                          7.7313E-01

Funded by EPSRC grant EP/J010553/1