SPRAL

About
Licence
1 Installation
- 1.1 Quick Start
- 1.2 Licence
- 1.3 Third-party libraries
  - 1.3.1 METIS
  - 1.3.2 BLAS
- 1.4 Compilers and compiler options
- 1.5 Other options to configure
- 1.6 Support
2 RANDOM: Pseudo-random Number Generator
- 2.1 Installation
- 2.2 Usage overview
  - 2.2.1 Calling sequences
  - 2.2.2 Seed initialization
- 2.3 Random Generation Subroutines
  - 2.3.1 random_real()
  - 2.3.2 random_integer()
  - 2.3.3 random_logical()
- 2.4 Method
  - 2.4.1 Pseudo-random number generation
  - 2.4.2 random_real()
  - 2.4.3 random_int()
  - 2.4.4 random_logical()
- 2.5 Example
3 RANDOM_MATRIX: Pseudo-random Matrix Generator
- 3.1 Installation
- 3.2 Usage overview
  - 3.2.1 Calling sequences
  - 3.2.2 Seed initialization
  - 3.2.3 Matrix types
- 3.3 Subroutines
  - 3.3.1 random_matrix_generate()
- 3.4 Return codes
- 3.5 Method
- 3.6 Example
4 SCALING: Sparse Matrix Scalings
- 4.1 Installation
- 4.2 Usage overview
  - 4.2.1 Calling sequences
  - 4.2.2 Data formats
- 4.3 Auction Algorithm
  - 4.3.1 spral_scaling_auction_default_options()
  - 4.3.2 spral_scaling_auction_sym()
  - 4.3.3 spral_scaling_auction_unsym()
  - 4.3.4 struct spral_scaling_auction_options
  - 4.3.5 struct spral_scaling_auction_inform
  - 4.3.6 Error Flags
  - 4.3.7 Algorithm description
  - 4.3.8 Example of spral_scaling_auction_sym()
- 4.4 Norm-equilibration algorithm
  - 4.4.1 spral_scaling_equilib_default_options()
  - 4.4.2 spral_scaling_equilib_sym()
  - 4.4.3 spral_scaling_equilib_unsym()
  - 4.4.4 struct spral_scaling_equilib_options
  - 4.4.5 struct spral_scaling_equilib_inform
  - 4.4.6 Error Flags
  - 4.4.7 Algorithm description
  - 4.4.8 Example of spral_scaling_equilib_sym()
- 4.5 Hungarian algorithm
  - 4.5.1 spral_scaling_hungarian_default_options()
  - 4.5.2 spral_scaling_hungarian_sym()
  - 4.5.3 spral_scaling_hungarian_unsym()
  - 4.5.4 struct spral_scaling_hungarian_options
  - 4.5.5 struct spral_scaling_hungarian_inform
  - 4.5.6 Error Flags
  - 4.5.7 Algorithm description
  - 4.5.8 Example usage of spral_scaling_hungarian_unsym()
5 SSIDS: Sparse Symmetric Indeﬁnite Direct Solver
- 5.1 Installation
- 5.2 Usage overview
  - 5.2.1 Calling sequences
  - 5.2.2 Derived types
  - 5.2.3 Achieving bit-compatibility
  - 5.2.4 Data formats
- 5.3 Basic Subroutines
  - 5.3.1 spral_ssids_default_options()
  - 5.3.2 spral_ssids_analyse() and spral_ssids_analyse_coord()
  - 5.3.3 spral_ssids_factor()
  - 5.3.4 spral_ssids_solve()
  - 5.3.5 spral_ssids_free(), spral_ssids_free_akeep(), and spral_ssids_free_fkeep()
- 5.4 Advanced subroutines
  - 5.4.1 spral_ssids_enquire_posdef()
  - 5.4.2 spral_ssids_enquire_indef()
  - 5.4.3 spral_ssids_alter()
- 5.5 Derived types
  - 5.5.1 struct spral_ssids_options
  - 5.5.2 struct spral_ssids_inform
- 5.6 Error ﬂags
- 5.7 Method
- 5.8 Example
6 SSMFE: Sparse Symmetric Matrix-Free Eigensolver
- 6.1 Installation
- 6.2 Usage overview
  - 6.2.1 Calling sequences
  - 6.2.2 Derived types
- 6.3 Argument lists
- 6.4 Derived types
  - 6.4.1 struct spral_ssmfe_options
  - 6.4.2 struct spral_ssmfe_inform
- 6.5 Error ﬂags
- 6.6 Method
- 6.7 Examples
  - 6.7.1 Preconditioning example
  - 6.7.2 Shift-and-invert example
  - 6.7.3 Hermitian example
7 SSMFE_CORE: Sparse Symmetric Matrix-Free Eigensolver (Core Algorithm)
- 7.1 Installation
- 7.2 Usage overview
  - 7.2.1 Calling sequences
  - 7.2.2 Derived types
- 7.3 Argument lists
  - 7.3.1 spral_ssmfe_core_default_options()
  - 7.3.2 spral_ssmfe_type() and spral_ssmfe_largest_type()
  - 7.3.3 spral_ssmfe_core_free()
- 7.4 Derived types
  - 7.4.1 struct spral_ssmfe_core_options
  - 7.4.2 struct spral_ssmfe_inform
- 7.5 Error ﬂags
- 7.6 Method
  - 7.6.1 The algorithm
  - 7.6.2 Error estimation
- 7.7 Examples
  - 7.7.1 Preconditioning example
8 SSMFE_EXPERT: Sparse Symmetric Matrix-Free Eigensolver (Expert Interface)
- 8.1 Installation
- 8.2 Usage overview
  - 8.2.1 Calling sequences
  - 8.2.2 Derived types
- 8.3 Argument lists
- 8.4 Derived types
  - 8.4.1 struct spral_ssmfe_options
  - 8.4.2 struct spral_ssmfe_inform
- 8.5 Error ﬂags
- 8.6 Method
  - 8.6.1 The algorithm
  - 8.6.2 Stopping criteria
  - 8.6.3 Improving eigenvector accuracy
  - 8.6.4 The use of shifted matrix factorization
  - 8.6.5 Error estimation
- 8.7 Examples
  - 8.7.1 Preconditioning example

RANDOM: Pseudo-random Number Generator

SPRAL_RANDOMv1.0.0

Pseudo-random Number Generator

C User Guide

This package generates pseudo-random numbers using a linear congruential generator. It should generate the same random numbers using any standards compliant Fortran compiler on any architecture so long as the default integer and real kinds are the same.

The seed can optionally be observed or speciﬁed by the user.

Jonathan Hogg (STFC Rutherford Appleton Laboratory)

Major version history

2014-04-07 Version 1.0.0: Initial release

2.1 Installation

Please see the SPRAL install documentation.

2.2 Usage overview

2.2.1 Calling sequences

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

#include "spral.h"

The following functions are available to the user:

random_real() generates a real uniformally at random from the interval $(- 1, 1)$ or $(0, 1)$ .
random_integer() generates an integer uniformally at random from the interval $[1, \dots, n]$ .
random_logical() generates a random boolean value.

2.2.2 Seed initialization

The random number generator’s state is stored in the variable state that is common to all calls. 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. The same sequence of calls following the (re-)initialization of seed to the same value will produce the same pseudo-random values.

2.3 Random Generation Subroutines

2.3.1 random_real()

To generate a real uniformly at random from the interval $(- 1, 1)$ or $(0, 1)$ , the following routine is provided.
double spral_random_real(int *state, bool positive);

The return value is a sample from $U n i f (0, 1)$ if positive is true, or from $U n i f (- 1, 1)$ if it is false.

*state: is the current state of the random number generator. Before the ﬁrst call (only) to a package routine, it must be initialized by the user as described in Section 2.2.2.
positive: controls whether the return value is required to be positive. If positive is true, the sample will be returned from the interval $(0, 1)$ . Otherwise, the sample will be returned from the interval $(- 1, 1)$ .

2.3.2 random_integer()

To generate an integer uniformly at random from the interval $[1, n]$ , the following routine is provided.
int spral_random_integer(int *state, int n);

The return value is a sample from $U n i f (1, \dots, n)$ .

*state: is the current state of the random number generator. Before the ﬁrst call (only) to a package routine, it must be initialized by the user as described in Section 2.2.2.
n: speciﬁes the upper bound of the range to be sampled.

2.3.3 random_logical()

To generate a logical with equal probability of being .true. or .false., the following routine is provided.
bool spral_random_logical(int *state);

The return value has an equal probability of being true or false.

*state: is the current state of the random number generator. Before the ﬁrst call (only) to a package routine, it must be initialized by the user as described in Section 2.2.2.

2.4 Method

2.4.1 Pseudo-random number generation

We use a linear congruential generator (LCG) of the following form:

X_{n + 1} = (a X_{n} + c) m o d m

with the following constants

\begin{array}{rcl} a & = & 1103515245, \\ c & = & 12345, \\ m & = & 2^{31} . \end{array}

According to Wikipedia, this is the same as used in glibc.

The LCG is evolved before each sample is taken, and the sample is based on the new value.

The variable state stores the current value of $X_{n}$ , and the macro SPRAL_RANDOM_INITIAL_SEED speciﬁes the seed $X_{0} = 486502$ .

2.4.2 random_real()

If positive is present with value .true., a sample from $U n i f (0, 1)$ is generated as

\frac{real (X_{n})}{real (m)},

otherwise, a sample from $U n i f (- 1, 1)$ is generated as

1 - \frac{real (2 X_{n})}{real (m)} .

2.4.3 random_int()

A random sample from the discrete distribution $U n i f (1, \dots, n)$ is generated as

int (X_{n} \frac{real (n)}{real (m)}) + 1 .

2.4.4 random_logical()

A random logical value is generated by evaluating the expression

(1 . e q . s p r a l_r a n d o m_i n t e g e r (s t a t e, 2)) .

2.5 Example

The following example code:

/* examples/C/random.c - Example code for SPRAL_RANDOM package */
#include "spral.h"
#include <stdio.h>

#define bool2str(VAL) ( (VAL) ? "true" : "false" )

void main(void) {
   int state = SPRAL_RANDOM_INITIAL_SEED;

   // Store initial random seed so we can reuse it later
   int initial_seed = state;

   // Generate some random values
   printf("\nSome random values\n");
   printf("Sample Unif(-1,1)       = %16.12f\n",
         spral_random_real(&state, false));
   printf("Sample Unif(0,1)        = %16.12f\n",
         spral_random_real(&state, true));
   printf("Sample Unif(1, ..., 20) = %16d\n",
         spral_random_integer(&state, 20));
   printf("Sample B(1,0.5)         = %16s\n",
         bool2str(spral_random_logical(&state)));

   // Restore initial seed
   state = initial_seed;

   // Generate the same random values
   printf("\nThe same random values again\n");
   printf("Sample Unif(-1,1)       = %16.12f\n",
         spral_random_real(&state, false));
   printf("Sample Unif(0,1)        = %16.12f\n",
         spral_random_real(&state, true));
   printf("Sample Unif(1, ..., 20) = %16d\n",
         spral_random_integer(&state, 20));
   printf("Sample B(1,0.5)         = %16s\n",
         bool2str(spral_random_logical(&state)));
}

Produces the following output:

Some random values
Sample Unif(-1,1)       =   0.951878630556
Sample Unif(0,1)        =   0.395779648796
Sample Unif(1, ..., 20) =                3
Sample B(1,0.5)         =            false

The same random values again
Sample Unif(-1,1)       =   0.951878630556
Sample Unif(0,1)        =   0.395779648796
Sample Unif(1, ..., 20) =                3
Sample B(1,0.5)         =            false

Contents