GALAHAD BSC package#

purpose#

The bsc package takes given matrices \(A\) and (diagonal) \(D\), and builds the Schur complement \(S = A D A^T\) in sparse co-ordinate (and optionally sparse column) format(s). Full advantage is taken of any zero coefficients in the matrix \(A\).

See Section 4 of $GALAHAD/doc/bsc.pdf for a brief description of the method employed and other details.

matrix storage#

unsymmetric storage#

The unsymmetric \(m\) by \(n\) matrix \(A\) may be presented and stored in a variety of convenient input formats.

Dense storage format: The matrix \(A\) is stored as a compact dense matrix by rows, that is, the values of the entries of each row in turn are stored in order within an appropriate real one-dimensional array. In this case, component \(n \ast i + j\) of the storage array A_val will hold the value \(A_{ij}\) for \(1 \leq i \leq m\), \(1 \leq j \leq n\). The string A_type = ‘dense’ should be specified.

Dense by columns storage format: The matrix \(A\) is stored as a compact dense matrix by columns, that is, the values of the entries of each column in turn are stored in order within an appropriate real one-dimensional array. In this case, component \(m \ast j + i\) of the storage array A_val will hold the value \(A_{ij}\) for \(1 \leq i \leq m\), \(1 \leq j \leq n\). The string A_type = ‘dense_by_columns’ should be specified.

Sparse co-ordinate storage format: Only the nonzero entries of the matrices are stored. For the \(l\)-th entry, \(1 \leq l \leq ne\), of \(A\), its row index i, column index j and value \(A_{ij}\), \(1 \leq i \leq m\), \(1 \leq j \leq n\), are stored as the \(l\)-th components of the integer arrays A_row and A_col and real array A_val, respectively, while the number of nonzeros is recorded as A_ne = \(ne\). The string A_type = ‘coordinate’should be specified.

Sparse row-wise storage format: Again only the nonzero entries are stored, but this time they are ordered so that those in row i appear directly before those in row i+1. For the i-th row of \(A\) the i-th component of the integer array A_ptr holds the position of the first entry in this row, while A_ptr(m+1) holds the total number of entries plus one. The column indices j, \(1 \leq j \leq n\), and values \(A_{ij}\) of the nonzero entries in the i-th row are stored in components l = A_ptr(i), \(\ldots\), A_ptr(i+1)-1, \(1 \leq i \leq m\), of the integer array A_col, and real array A_val, respectively. For sparse matrices, this scheme almost always requires less storage than its predecessor. The string A_type = ‘sparse_by_rows’ should be specified.

Sparse column-wise storage format: Once again only the nonzero entries are stored, but this time they are ordered so that those in column j appear directly before those in column j+1. For the j-th column of \(A\) the j-th component of the integer array A_ptr holds the position of the first entry in this column, while A_ptr(n+1) holds the total number of entries plus one. The row indices i, \(1 \leq i \leq m\), and values \(A_{ij}\) of the nonzero entries in the j-th columnsare stored in components l = A_ptr(j), \(\ldots\), A_ptr(j+1)-1, \(1 \leq j \leq n\), of the integer array A_row, and real array A_val, respectively. As before, for sparse matrices, this scheme almost always requires less storage than the co-ordinate format. The string A_type = ‘sparse_by_columns’ should be specified.

symmetric storage#

The symmetric \(n\) by \(n\) Schur complement matrix \(S\) may be returned in a couple of formats. But crucially symmetry is exploited by only storing values from the lower triangular part (i.e, those entries that lie on or below the leading diagonal).

Sparse co-ordinate storage format: Only the nonzero entries of the matrices are stored. For the \(l\)-th entry, \(1 \leq l \leq ne\), of \(S\), its row index i, column index j and value \(S_{ij}\), \(1 \leq j \leq i \leq n\), are stored as the \(l\)-th components of the integer arrays S_row and S_col and real array S_val, respectively, while the number of nonzeros is recorded as S_ne = \(ne\). Note that only the entries in the lower triangle should be stored.

Sparse row-wise storage format: Again only the nonzero entries are stored, but this time they are ordered so that those in row i appear directly before those in row i+1. For the i-th row of \(S\) the i-th component of the integer array S_ptr holds the position of the first entry in this row, while S_ptr(n+1) holds the total number of entries plus one. The column indices j, \(1 \leq j \leq i\), and values \(S_{ij}\) of the entries in the i-th row are stored in components l = S_ptr(i), …, S_ptr(i+1)-1 of the integer array S_col, and real array S_val, respectively. Note that as before only the entries in the lower triangle should be stored. For sparse matrices, this scheme almost always requires less storage than its predecessor.

introduction to function calls#

To solve a given problem, functions from the bsc package must be called in the following order:

  • bsc_initialize - provide default control parameters and set up initial data structures

  • bsc_read_specfile (optional) - override control values by reading replacement values from a file

  • bsc_import - set up matrix data structures for \(A\) and \(S\).

  • bsc_reset_control (optional) - possibly change control parameters if a sequence of problems are being solved

  • bsc_form - form the Schur complement \(S\)

  • bsc_information (optional) - recover information about the process

  • bsc_terminate - deallocate data structures

See the examples section for illustrations of use.

parametric real type T and integer type INT#

Below, the symbol T refers to a parametric real type that may be Float32 (single precision), Float64 (double precision) or, if supported, Float128 (quadruple precision). The symbol INT refers to a parametric integer type that may be Int32 (32-bit integer) or Int64 (64-bit integer).

callable functions#

    function bsc_initialize(T, INT, data, control, status)

Set default control values and initialize private data

Parameters:

data

holds private internal data

control

is a structure containing control information (see bsc_control_type)

status

is a scalar variable of type INT that gives the exit status from the package. Possible values are (currently):

  • 0

    The initialization was successful.

    function bsc_read_specfile(T, INT, control, specfile)

Read the content of a specification file, and assign values associated with given keywords to the corresponding control parameters. An in-depth discussion of specification files is available, and a detailed list of keywords with associated default values is provided in $GALAHAD/src/bsc/BSC.template. See also Table 2.1 in the Fortran documentation provided in $GALAHAD/doc/bsc.pdf for a list of how these keywords relate to the components of the control structure.

Parameters:

control

is a structure containing control information (see bsc_control_type)

specfile

is a one-dimensional array of type Vararg{Cchar} that must give the name of the specification file

function bsc_import(T, INT, control, data, status, m, n,
                    A_type, A_ne, A_row, A_col, A_ptr, S_ne)

Import problem data into internal storage prior to solution.

Parameters:

control

is a structure whose members provide control parameters for the remaining procedures (see bsc_control_type)

data

holds private internal data

status

is a scalar variable of type INT that gives the exit status from the package. Possible values are:

  • 0 The import was successful

  • -1 An allocation error occurred. A message indicating the offending array is written on unit control.error, and the returned allocation status and a string containing the name of the offending array are held in inform.alloc_status and inform.bad_alloc respectively.

  • -2 A deallocation error occurred. A message indicating the offending array is written on unit control.error and the returned allocation status and a string containing the name of the offending array are held in inform.alloc_status and inform.bad_alloc respectively.

  • -3 The restrictions n > 0 or m > 0 or requirement that a type contains its relevant string ‘dense’, ‘coordinate’ or ‘sparse_by_rows’ has been violated.

m

is a scalar variable of type INT that holds the number of rows of \(A\)

n

is a scalar variable of type INT that holds the number of columns of \(A\)

A_type

is a one-dimensional array of type Vararg{Cchar} that specifies the unsymmetric storage scheme used for the matrix \(A\). It should be one of ‘coordinate’, ‘sparse_by_rows’ or ‘dense; lower or upper case variants are allowed.

A_ne

is a scalar variable of type INT that holds the number of entries in \(A\) in the sparse co-ordinate storage scheme. It need not be set for any of the other schemes.

A_row

is a one-dimensional array of size A_ne and type INT that holds the row indices of \(A\) in the sparse co-ordinate storage scheme. It need not be set for any of the other schemes, and in this case can be C_NULL.

A_col

is a one-dimensional array of size A_ne and type INT that holds the column indices of \(A\) in either the sparse co-ordinate, or the sparse row-wise storage scheme. It need not be set when the dense or diagonal storage schemes are used, and in this case can be C_NULL.

A_ptr

is a one-dimensional array of size n+1 and type INT that holds the starting position of each row of \(A\), as well as the total number of entries, in the sparse row-wise storage scheme. It need not be set when the other schemes are used, and in this case can be C_NULL.

S_ne

is a scalar variable of type INT that gives the number of entries in \(S\).

function bsc_reset_control(T, INT, control, data, status)

Reset control parameters after import if required.

Parameters:

control

is a structure whose members provide control parameters for the remaining procedures (see bsc_control_type)

data

holds private internal data

status

is a scalar variable of type INT that gives the exit status from the package. Possible values are:

  • 0 The import was successful.

function bsc_form_s(T, INT, data, status, m, n, a_ne, A_val,
                    S_ne, S_row, S_col, S_ptr, S_val, D)

Form the Schur complement matrix, \(S\).

Parameters:

data

holds private internal data

status

is a scalar variable of type INT that gives the entry and exit status from the package.

Possible exit values are:

  • 0 The run was successful.

  • -1 An allocation error occurred. A message indicating the offending array is written on unit control.error, and the returned allocation status and a string containing the name of the offending array are held in inform.alloc_status and inform.bad_alloc respectively.

  • -2 A deallocation error occurred. A message indicating the offending array is written on unit control.error and the returned allocation status and a string containing the name of the offending array are held in inform.alloc_status and inform.bad_alloc respectively.

  • -3 The restrictions n > 0 or m > 0 or requirement that a type contains its relevant string ‘dense’, ‘coordinate’ or ‘sparse_by_rows’ has been violated.

m

is a scalar variable of type INT that holds the number of rows of \(A\)

n

is a scalar variable of type INT that holds the number of columns of \(A\)

A_ne

is a scalar variable of type INT that holds the number of entries in \(A\).

A_val

is a one-dimensional array of size a_ne and type T that holds the values of the entries of the matrix \(A\) in any of the available storage schemes.

S_ne

is a scalar variable of type INT that holds the number of entries in the lower traingle of \(S\) in the sparse co-ordinate storage scheme.

S_row

is a one-dimensional array of size S_ne and type INT that gives the row indices the lower traingle of \(S\) in the sparse co-ordinate storage scheme.

S_col

is a one-dimensional array of size S_ne and type INT that gives the column indices the lower traingle of \(S\) in either the sparse co-ordinate, or the sparse row-wise storage scheme.

S_ptr

is a one-dimensional array of size n+1 and type INT that gives the starting position of each row the lower traingle of \(S\), as well as the total number of entries, in the sparse row-wise storage scheme. If this scheme is not wanted, S_ptr can be NULL to save storage.

S_val

is a one-dimensional array of size S_ne and type T that gives the values of the entries of the lower traingle of the matrix \(S\).

D

is a one-dimensional array of size n and type T that gives the values of the diagonal entries in \(D\). If \(D\) is the identity matrix, D can be NULL to save storage.

    function bsc_information(T, INT, data, inform, status)

Provides output information

Parameters:

data

holds private internal data

inform

is a structure containing output information (see bsc_inform_type)

status

is a scalar variable of type INT that gives the exit status from the package. Possible values are (currently):

  • 0

    The values were recorded successfully

    function bsc_terminate(T, INT, data, control, inform)

Deallocate all internal private storage

Parameters:

data

holds private internal data

control

is a structure containing control information (see bsc_control_type)

inform

is a structure containing output information (see bsc_inform_type)

available structures#

bsc_control_type structure#

    struct bsc_control_type
      f_indexing::Bool
      error::INT
      out::INT
      print_level::INT
      max_col::INT
      new_a::INT
      extra_space_s::INT
      s_also_by_column::Bool
      space_critical::Bool
      deallocate_error_fatal::Bool
      prefix::NTuple{31,Cchar}

detailed documentation#

control derived type as a Julia structure

components#

Bool f_indexing

use C or Fortran sparse matrix indexing

INT error

error and warning diagnostics occur on stream error

INT out

general output occurs on stream out

INT print_level

the level of output required is specified by print_level

INT max_col

maximum permitted number of nonzeros in a column of \(A\); -ve means unlimit

INT new_a

how much has \(A\) changed since it was last accessed:

  • 0 = not changed,

  • 1 = values changed,

  • 2 = structure changed

  • 3 = structure changed but values not required

INT extra_space_s

how much extra space is to be allocated in \(S\) above that needed to hold the Schur complement

Bool s_also_by_column

should s.ptr also be set to indicate the first entry in each column of \(S\)

Bool space_critical

if .space_critical true, every effort will be made to use as little space as possible. This may result in longer computation time

Bool deallocate_error_fatal

if .deallocate_error_fatal is true, any array/pointer deallocation error will terminate execution. Otherwise, computation will continue

NTuple{31,Cchar} prefix

all output lines will be prefixed by .prefix(2:LEN(TRIM(.prefix))-1) where .prefix contains the required string enclosed in quotes, e.g. “string” or ‘string’

bsc_inform_type structure#

    struct bsc_inform_type{T,INT}
      status::INT
      alloc_status::INT
      bad_alloc::NTuple{81,Cchar}
      max_col_a::INT
      exceeds_max_col::INT
      time::T
      clock_time::T

detailed documentation#

inform derived type as a Julia structure

components#

INT status

the return status from the package. Possible values are:

  • 0

    The call was succcesful

  • -1

    An allocation error occurred. A message indicating the offending array is written on unit control.error, and the returned allocation status and a string containing the name of the offending array are held in inform.alloc_status and inform.bad_alloc respectively.

  • -2

    A deallocation error occurred. A message indicating the offending array is written on unit control.error and the returned allocation status and a string containing the name of the offending array are held in inform.alloc_status and inform.bad_alloc respectively.

  • -3

    The restrictions n > 0 or m > 0 or requirement that a type contains its relevant string ‘dense’, ‘coordinate’ or ‘sparse_by_rows’ has been violated.

INT alloc_status

the status of the last attempted allocation/deallocation

NTuple{81,Cchar} bad_alloc

the name of the array for which an allocation/deallocation error occurred.

INT max_col_a

the maximum number of entries in a column of \(A\)

INT exceeds_max_col

the number of columns of \(A\) that have more than control.max_col entries

T time

the total CPU time spent in the package

T clock_time

the total clock time spent in the package

example call#

This is an example of how to use the package to find the Schur complement from given data \(A\) and \(D\); the code is available in $GALAHAD/src/bsc/Julia/test_bsc.jl . A variety of supported Hessian and constraint matrix storage formats are shown.

# test_bsc.jl
# Simple code to test the Julia interface to BSC

using GALAHAD
using Test
using Quadmath

function test_bsc(::Type{T}, ::Type{INT}) where {T,INT}
  # Derived types
  data = Ref{Ptr{Cvoid}}()
  control = Ref{bsc_control_type{INT}}()
  inform = Ref{bsc_inform_type{T,INT}}()

  # Set problem data
  m = INT(3)  # row dimension of A
  n = INT(4)  # column dimension of A
  A_ne = INT(6)  # number of entries in A
  A_row = INT[1, 1, 2, 2, 3, 3]  # row indices
  A_col = INT[1, 2, 3, 4, 1, 4]  # column indices
  A_ptr = INT[1, 3, 5, 7]  # row pointers
  A_val = T[1.0, 1.0, 1.0, 1.0, 1.0, 1.0]  # values
  A_dense_ne = INT(12) # number of elements in A as a dense matrix
  A_dense = T[1.0, 1.0, 0.0, 0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 0.0, 0.0, 1.0]
  D = T[1.0, 2.0, 3.0, 4.0] # optional diagonal

  # Set output storage
  st = ' '
  status = Ref{INT}()
  @printf(" basic tests of storage formats\n\n")
  S_ne = Ref{INT}()

  # loop over storage types
  for d in 1:3
    # Initialize BSC
    bsc_initialize(T, INT, data, control, status)

    # sparse co-ordinate storage
    if d == 1
      st = 'C'
      bsc_import(T, INT, control, data, status, n, m,
                 "coordinate", A_ne, A_row, A_col, C_NULL, S_ne)
    end

    # sparse by rows
    if d == 2
      st = 'R'
      bsc_import(T, INT, control, data, status, n, m,
                 "sparse_by_rows", A_ne, C_NULL, A_col, A_ptr, S_ne)
    end

    # dense
    if d == 3
      st = 'D'
      A_dense = T[2.0, 1.0, 0.0, 0.0, 1.0, 1.0]

      bsc_import(T, INT, control, data, status, n, m,
                 "dense", A_ne, C_NULL, C_NULL, C_NULL, S_ne)
    end

    S_row = Vector{INT}(undef, S_ne)
    S_col = Vector{INT}(undef, S_ne)
    S_ptr = Vector{INT}(undef, m+1)
    S_val = Vector{T}(undef, S_ne)

    for ptr in 0:1
      if ptr == 0
        if d == 3
          bsc_form_s(T, INT, data, status, n, m, A_dense_ne, A_dense,
                     S_ne, S_row, S_col, C_NULL, S_val, C_NULL)
        else
          bsc_form_s(T, INT, data, status, n, m, A_ne, A_val,
                     S_ne, S_row, S_col, C_NULL, S_val, C_NULL)
        end
      else
        if d == 3
          bsc_form_s(T, INT, data, status, n, m, A_dense_ne, A_dense,
                     S_ne, S_row, S_col, S_ptr, S_val, D)
        else
          bsc_form_s(T, INT, data, status, n, m, A_ne, A_val,
                     S_ne, S_row, S_col, S_ptr, S_val, D)
        end
      end

      bsc_information(T, INT, data, inform, status)

      if inform[].status == 0
        @printf(" format %c: status = %1i\n", st, inform[].status)
      else
        @printf(" format %c: error status = %1i\n", st, inform[].status)
      end

      @printf("S_row: ")
      for i = 1:S_ne
        @printf("%1i ", S_row[i])
      end
      @printf("\n");
      @printf("S_col: ")
      for i = 1:S_ne
        @printf("%1i ", S_col[i])
      end
      @printf("\n")
      @printf("S_val: ")
      for i = 1:S_ne
        @printf("%.2f ", S_val[i])
      end
      printf("\n")
      if ptr == 1
        @printf("S_ptr: ")
        for i = 1:m+1
          @printf("%1i ", S_ptr[i])
        end
        @printf("\n")
      end
    end
  end

  return 0
end

for (T, INT, libgalahad) in ((Float32 , Int32, GALAHAD.libgalahad_single      ),
                             (Float32 , Int64, GALAHAD.libgalahad_single_64   ),
                             (Float64 , Int32, GALAHAD.libgalahad_double      ),
                             (Float64 , Int64, GALAHAD.libgalahad_double_64   ),
                             (Float128, Int32, GALAHAD.libgalahad_quadruple   ),
                             (Float128, Int64, GALAHAD.libgalahad_quadruple_64))
  if isfile(libgalahad)
    @testset "BSC -- $T -- $INT" begin
      @test test_bsc(T, INT) == 0
    end
  end
end