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#
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 \(0 \leq i \leq m-1\), \(0 \leq j \leq n-1\). The string A_type = ‘dense’ should be specified.
Sparse co-ordinate storage format: Only the nonzero entries of the matrices are stored. For the \(l\)-th entry, \(0 \leq l \leq ne-1\), of \(A\), its row index i, column index j and value \(A_{ij}\), \(0 \leq i \leq m-1\), \(0 \leq j \leq n-1\), 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) holds the total number of entries. The column indices j, \(0 \leq j \leq n-1\), 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, \(0 \leq i \leq m-1,\) 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) holds the total number of entries. The row indices i, \(0 \leq i \leq m-1\), and values \(A_{ij}\) of the nonzero entries in the j-th columns are stored in components l = A_ptr(j), \(\ldots\), A_ptr(j+1)-1, \(0 \leq j \leq n-1\), 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.
The symmetric \(n\) by \(n\) Schur complement matrix \(S\) may be returned in a couple of formats. But now 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, \(0 \leq l \leq ne-1\), of \(S\), its row index i, column index j and value \(S_{ij}\), \(0 \leq j \leq i \leq n-1\), 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 will be returned.
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) holds the total number of entries. The column indices j, \(0 \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, \(0 \leq i \leq n-1,\) of the integer array S_col, and real array S_val, respectively. Note that as before only the entries in the lower triangle will 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_s - 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.
callable functions#
overview of functions provided#
// namespaces namespace conf; // typedefs typedef float spc_; typedef double rpc_; typedef int ipc_; // structs struct bsc_control_type; struct bsc_inform_type; // global functions void bsc_initialize(void **data, struct bsc_control_type* control, ipc_ *status); void bsc_read_specfile(struct bsc_control_type* control, const char specfile[]); void bsc_import( struct bsc_control_type* control, void **data, ipc_ *status, ipc_ m, ipc_ n, const char A_type[], ipc_ A_ne, const ipc_ A_row[], const ipc_ A_col[], const ipc_ A_ptr[], ipc_ S_ne ); void bsc_reset_control( struct bsc_control_type* control, void **data, ipc_ *status ); void bsc_form_s( void **data, ipc_ *status, ipc_ m, ipc_ n, ipc_ A_ne, const rpc_ A_val[], ipc_ S_ne, ipc_ S_row[], ipc_ S_col[], ipc_ S_ptr[], ipc_ S_val[], const rpc_ D[] ); void bsc_information(void **data, struct bsc_inform_type* inform, ipc_ *status); void bsc_terminate( void **data, struct bsc_control_type* control, struct bsc_inform_type* inform );
typedefs#
typedef float spc_
spc_ is real single precision
typedef double rpc_
rpc_ is the real working precision used, but may be changed to float by
defining the preprocessor variable REAL_32 or (if supported) to
__real128 using the variable REAL_128.
typedef int ipc_
ipc_ is the default integer word length used, but may be changed to
int64_t by defining the preprocessor variable INTEGER_64.
function calls#
void bsc_initialize(void **data, struct bsc_control_type* control, ipc_ *status)
Set default control values and initialize private data
Parameters:
data |
holds private internal data |
control |
is a struct containing control information (see bsc_control_type) |
status |
is a scalar variable of type ipc_, that gives the exit status from the package. Possible values are (currently):
|
void bsc_read_specfile(struct bsc_control_type* control, const char 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 struct containing control information (see bsc_control_type) |
specfile |
is a character string containing the name of the specification file |
void bsc_import( struct bsc_control_type* control, void **data, ipc_ *status, ipc_ m, ipc_ n, const char A_type[], ipc_ A_ne, const ipc_ A_row[], const ipc_ A_col[], const ipc_ A_ptr[], ipc_ S_ne )
Import data into internal storage prior to solution and set up structure of \(S\),
Parameters:
control |
is a struct whose members provide control paramters for the remaining prcedures (see bsc_control_type) |
data |
holds private internal data |
status |
is a scalar variable of type ipc_, that gives the exit status from the package. Possible values are:
|
m |
is a scalar variable of type ipc_, that holds the number of rows of \(A\). |
n |
is a scalar variable of type ipc_, that holds the number of columns of \(A\). |
A_type |
is a one-dimensional array of type char 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 ipc_, 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 ipc_, 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 NULL. |
A_col |
is a one-dimensional array of size A_ne and type ipc_, 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 NULL. |
A_ptr |
is a one-dimensional array of size m+1 and type ipc_, 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 NULL. |
S_ne |
is a scalar variable of type ipc_, that holds the number of entries required to hold \(S\) in the sparse co-ordinate storage scheme. |
void bsc_reset_control( struct bsc_control_type* control, void **data, ipc_ *status )
Reset control parameters after import if required.
Parameters:
control |
is a struct whose members provide control paramters for the remaining prcedures (see bsc_control_type) |
data |
holds private internal data |
status |
is a scalar variable of type ipc_, that gives the exit status from the package. Possible values are:
|
void bsc_form_s( void **data, ipc_ *status, ipc_ m, ipc_ n, ipc_ A_ne, const rpc_ A_val[], ipc_ S_ne, ipc_ S_row[], ipc_ S_col[], ipc_ S_ptr[], ipc_ S_val[], const rpc_ D[] )
Form the Schur complement matrix, \(S\).
Parameters:
data |
holds private internal data |
status |
is a scalar variable of type ipc_, that gives the entry and exit status from the package. Possible exit values are:
|
m |
is a scalar variable of type ipc_, that holds the number of rows of \(A\). |
n |
is a scalar variable of type ipc_, that holds the number of columns of \(A\). |
A_ne |
is a scalar variable of type ipc_, that holds the number of entries in \(A\). |
A_val |
is a one-dimensional array of size A_ne and type rpc_, 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 ipc_, 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 ipc_, 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 ipc_, 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 ipc_, 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. |
S_val |
is a one-dimensional array of size S_ne and type rpc_, 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 rpc_, that gives the values of the diagonal entries in \(D\). If \(D\) is the identity matrix, D can be NULL to save storage. |
void bsc_information(void **data, struct bsc_inform_type* inform, ipc_ *status)
Provides output information
Parameters:
data |
holds private internal data |
inform |
is a struct containing output information (see bsc_inform_type) |
status |
is a scalar variable of type ipc_, that gives the exit status from the package. Possible values are (currently):
|
void bsc_terminate( void **data, struct bsc_control_type* control, struct bsc_inform_type* inform )
Deallocate all internal private storage
Parameters:
data |
holds private internal data |
control |
is a struct containing control information (see bsc_control_type) |
inform |
is a struct containing output information (see bsc_inform_type) |
available structures#
bsc_control_type structure#
#include <galahad_bsc.h> struct bsc_control_type { // fields bool f_indexing; ipc_ error; ipc_ out; ipc_ print_level; ipc_ max_col; ipc_ new_a; ipc_ extra_space_s; bool s_also_by_column; bool space_critical; bool deallocate_error_fatal; char prefix[31]; };
detailed documentation#
control derived type as a C struct
components#
bool f_indexing
use C or Fortran sparse matrix indexing
ipc_ error
error and warning diagnostics occur on stream error
ipc_ out
general output occurs on stream out
ipc_ print_level
the level of output required is specified by print_level
ipc_ max_col
maximum permitted number of nonzeros in a column of \(A\); -ve means unlimit
ipc_ 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
ipc_ 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
char prefix[31]
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#
#include <galahad_bsc.h> struct bsc_inform_type { // fields ipc_ status; ipc_ alloc_status; char bad_alloc[81]; ipc_ max_col_a; ipc_ exceeds_max_col; rpc_ time; rpc_ clock_time; };
detailed documentation#
inform derived type as a C struct
components#
ipc_ 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.
ipc_ alloc_status
the status of the last attempted allocation/deallocation
char bad_alloc[81]
the name of the array for which an allocation/deallocation error occurred.
ipc_ max_col_a
the maximum number of entries in a column of \(A\)
ipc_ exceeds_max_col
the number of columns of \(A\) that have more than control.max_col entries
rpc_ time
the total CPU time spent in the package
rpc_ clock_time
the total clock time spent in the package
example calls#
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/C/bsct.c . A variety of supported Hessian and constraint matrix storage formats are shown.
Notice that C-style indexing is used, and that this is flagged by setting
control.f_indexing to false. The floating-point type rpc_
is set in galahad_precision.h to double by default, but to float
if the preprocessor variable SINGLE is defined. Similarly, the integer
type ipc_ from galahad_precision.h is set to int by default,
but to int64_t if the preprocessor variable INTEGER_64 is defined.
/* bsct.c */
/* Full test for the BSC C interface using C sparse matrix indexing */
#include <stdio.h>
#include <math.h>
#include <string.h>
#include "galahad_precision.h"
#include "galahad_cfunctions.h"
#include "galahad_bsc.h"
#ifdef REAL_128
#include <quadmath.h>
#endif
int main(void) {
// Derived types
void *data;
struct bsc_control_type control;
struct bsc_inform_type inform;
// Set problem data
ipc_ m = 3; // row dimension of A
ipc_ n = 4; // column dimension of A
ipc_ A_ne = 6; // nonzeros in lower triangle of A
ipc_ A_dense_ne = 12; // positions in lower triangle of A
ipc_ A_row[] = {0, 0, 1, 1, 2, 2}; // row indices
ipc_ A_col[] = {0, 1, 2, 3, 0, 3}; // column indices
ipc_ A_ptr[] = {0, 2, 4, 6}; // row pointers
rpc_ A_val[] = {1.0, 1.0, 1.0, 1.0, 1.0, 1.0}; // values
rpc_ A_dense[] = {1.0, 1.0, 0.0, 0.0, 0.0, 0.0,
1.0, 1.0, 1.0, 0.0, 0.0, 1.0}; // dense values
rpc_ D[] = {1.0, 2.0, 3.0, 4.0}; // diagonals of D
// Set output storage
char st = ' ';
ipc_ status, S_ne;
printf(" C sparse matrix indexing\n\n");
printf(" basic tests of storage formats\n\n");
for( ipc_ d=1; d <= 3; d++){
// Initialize BSC
bsc_initialize( &data, &control, &status );
// Set user-defined control options
control.f_indexing = false; // C sparse matrix indexing
//control.print_level = 1;
switch(d){
case 1: // sparse co-ordinate storage
st = 'C';
bsc_import( &control, &data, &status, m, n,
"coordinate", A_ne, A_row, A_col, NULL, &S_ne );
break;
case 2: // sparse by rows
st = 'R';
bsc_import( &control, &data, &status, m, n,
"sparse_by_rows", A_ne, NULL, A_col, A_ptr, &S_ne );
break;
case 3: // dense
st = 'D';
bsc_import( &control, &data, &status, m, n,
"dense", A_dense_ne, NULL, NULL, NULL, &S_ne );
break;
}
ipc_ S_row[S_ne], S_col[S_ne], S_ptr[m+1];
rpc_ S_val[S_ne];
for( ipc_ ptr=0; ptr <= 1; ptr++){
if(ptr == 0){
switch(d){
case 3: // dense
bsc_form_s( &data, &status, m, n, A_dense_ne, A_dense,
S_ne, S_row, S_col, NULL, S_val, NULL );
break;
default:
bsc_form_s( &data, &status, m, n, A_ne, A_val,
S_ne, S_row, S_col, NULL, S_val, NULL );
}
} else {
switch(d){
case 3: // dense
bsc_form_s( &data, &status, m, n, A_dense_ne, A_dense,
S_ne, S_row, S_col, S_ptr, S_val, D );
break;
default:
bsc_form_s( &data, &status, m, n, A_ne, A_val,
S_ne, S_row, S_col, S_ptr, S_val, D );
}
}
bsc_information( &data, &inform, &status );
if(inform.status == 0){
#ifdef REAL_128
printf(" format %c: status = %1" i_ipc_ "\n", st, inform.status);
#else
printf(" format %c: status = %1" i_ipc_ "\n", st, inform.status);
#endif
}else{
printf(" format %c: BSC_solve exit status = %1" i_ipc_ "\n",
st, inform.status);
}
printf("S_row: ");
for( ipc_ i = 0; i < S_ne; i++) printf("%1" i_ipc_ " ", S_row[i]);
printf("\n");
printf("S_col: ");
for( ipc_ i = 0; i < S_ne; i++) printf("%1" i_ipc_ " ", S_col[i]);
printf("\n");
printf("S_val: ");
#ifdef REAL_128
for( ipc_ i = 0; i < S_ne; i++) printf("%.2f ", (double)S_val[i]);
#else
for( ipc_ i = 0; i < S_ne; i++) printf("%.2f ", S_val[i]);
#endif
printf("\n");
if(ptr == 1){
printf("S_ptr: ");
for( ipc_ i = 0; i < m + 1; i++) printf("%1" i_ipc_ " ", S_ptr[i]);
printf("\n");
}
}
// Delete internal workspace
bsc_terminate( &data, &control, &inform );
}
printf("Tests complete\n");
}
This is the same example, but now fortran-style indexing is used; the code is available in $GALAHAD/src/bsc/C/bsctf.c .
/* bsctf.c */
/* Full test for the BSC C interface using Fortran sparse matrix indexing */
#include <stdio.h>
#include <math.h>
#include <string.h>
#include "galahad_precision.h"
#include "galahad_cfunctions.h"
#include "galahad_bsc.h"
#ifdef REAL_128
#include <quadmath.h>
#endif
int main(void) {
// Derived types
void *data;
struct bsc_control_type control;
struct bsc_inform_type inform;
// Set problem data
ipc_ m = 3; // row dimension of A
ipc_ n = 4; // column dimension of A
ipc_ A_ne = 6; // nonzeros in lower triangle of A
ipc_ A_dense_ne = 12; // positions in lower triangle of A
ipc_ A_row[] = {1, 1, 2, 2, 3, 3}; // row indices
ipc_ A_col[] = {1, 2, 3, 4, 1, 4}; // column indices
ipc_ A_ptr[] = {1, 3, 5, 7}; // row pointers
rpc_ A_val[] = {1.0, 1.0, 1.0, 1.0, 1.0, 1.0}; // values
rpc_ A_dense[] = {1.0, 1.0, 0.0, 0.0, 0.0, 0.0,
1.0, 1.0, 1.0, 0.0, 0.0, 1.0}; // dense values
rpc_ D[] = {1.0, 2.0, 3.0, 4.0}; // diagonals of D
// Set output storage
char st = ' ';
ipc_ status, S_ne;
printf(" Fortran sparse matrix indexing\n\n");
printf(" basic tests of storage formats\n\n");
for( ipc_ d=1; d <= 3; d++){
// Initialize BSC
bsc_initialize( &data, &control, &status );
// Set user-defined control options
control.f_indexing = true; // Fortran sparse matrix indexing
//control.print_level = 1;
switch(d){
case 1: // sparse co-ordinate storage
st = 'C';
bsc_import( &control, &data, &status, m, n,
"coordinate", A_ne, A_row, A_col, NULL, &S_ne );
break;
case 2: // sparse by rows
st = 'R';
bsc_import( &control, &data, &status, m, n,
"sparse_by_rows", A_ne, NULL, A_col, A_ptr, &S_ne );
break;
case 3: // dense
st = 'D';
bsc_import( &control, &data, &status, m, n,
"dense", A_dense_ne, NULL, NULL, NULL, &S_ne );
break;
}
ipc_ S_row[S_ne], S_col[S_ne], S_ptr[m+1];
rpc_ S_val[S_ne];
for( ipc_ ptr=0; ptr <= 1; ptr++){
if(ptr == 0){
switch(d){
case 3: // dense
bsc_form_s( &data, &status, m, n, A_dense_ne, A_dense,
S_ne, S_row, S_col, NULL, S_val, NULL );
break;
default:
bsc_form_s( &data, &status, m, n, A_ne, A_val,
S_ne, S_row, S_col, NULL, S_val, NULL );
}
} else {
switch(d){
case 3: // dense
bsc_form_s( &data, &status, m, n, A_dense_ne, A_dense,
S_ne, S_row, S_col, S_ptr, S_val, D );
break;
default:
bsc_form_s( &data, &status, m, n, A_ne, A_val,
S_ne, S_row, S_col, S_ptr, S_val, D );
}
}
bsc_information( &data, &inform, &status );
if(inform.status == 0){
#ifdef REAL_128
printf(" format %c: status = %1" i_ipc_ "\n", st, inform.status);
#else
printf(" format %c: status = %1" i_ipc_ "\n", st, inform.status);
#endif
}else{
printf(" format %c: BSC_solve exit status = %1" i_ipc_ "\n",
st, inform.status);
}
printf("S_row: ");
for( ipc_ i = 0; i < S_ne; i++) printf("%1" i_ipc_ " ", S_row[i]);
printf("\n");
printf("S_col: ");
for( ipc_ i = 0; i < S_ne; i++) printf("%1" i_ipc_ " ", S_col[i]);
printf("\n");
printf("S_val: ");
#ifdef REAL_128
for( ipc_ i = 0; i < S_ne; i++) printf("%.2f ", (double)S_val[i]);
#else
for( ipc_ i = 0; i < S_ne; i++) printf("%.2f ", S_val[i]);
#endif
printf("\n");
if(ptr == 1){
printf("S_ptr: ");
for( ipc_ i = 0; i < m + 1; i++) printf("%1" i_ipc_ " ", S_ptr[i]);
printf("\n");
}
}
// Delete internal workspace
bsc_terminate( &data, &control, &inform );
}
printf("Tests complete\n");
}