GALAHAD BLLS package#

purpose#

The blls package uses a preconditioned project-gradient method to solve a given bound-constrained linear least-squares problem. The aim is to minimize the (regularized) least-squares objective function

\[q(x) = \frac{1}{2} \| A_o x - b\|_W^2 + \frac{1}{2}\sigma \|x\|^2\]
subject to the simple bounds
\[x_l \leq x \leq x_u,\]
where the norms \(\|r\|_W = \sqrt{\sum_{i=1}^o w_i r_i^2}\) and \(\|x\| = \sqrt{\sum_{i=1}^n x_i^2}\), \(A_o\) is a given \(o\) by \(n\) matrix, \(b\), and \(w\) are vectors, \(\sigma \geq 0\) is a scalar, and any of the components of the vectors \(x_l\) or \(x_u\) may be infinite. The method offers the choice of direct and iterative solution of the key regularization subproblems, and is most suitable for problems involving a large number of unknowns \(x\).

See Section 4 of $GALAHAD/doc/blls.pdf for additional details.

terminology#

Any required solution \(x\) necessarily satisfies the primal optimality conditions

\[x_l \leq x \leq x_u,\]
the dual optimality conditions
\[A_o^T W( A_o x - b) + \sigma x = z, \;\; z = z_l + z_u, z_l \geq 0 \;\;\mbox{and}\;\; z_u \leq 0,\]
and the complementary slackness conditions
\[(x -x_l )^{T} z_l = 0 \;\;\mbox{and}\;\;(x -x_u )^{T} z_u = 0,\]
where the vector \(z\) is known as the dual variables for the bounds, and where the vector inequalities hold component-wise.

method#

Projected-gradient methods iterate towards a point that satisfies these optimality conditions by ultimately aiming to satisfy \(A_o^T W ( A_o x - b) + \sigma x = z\), while ensuring that the remaining conditions are satisfied at each stage. Appropriate norms of the amounts by which the optimality conditions fail to be satisfied are known as the primal and dual infeasibility, and the violation of complementary slackness, respectively.

The method is iterative. Each iteration proceeds in two stages. Firstly, a search direction \(s\) from the current estimate of the solution \(x\) is computed. This may be in a scaled steepest-descent direction, or, if the working set of variables on bounds has not changed dramatically, in a direction that provides an approximate minimizer of the objective over a subspace comprising the currently free-variables. The latter is computed either using an appropriate sparse factorization by the package SBLS, or by the conjugate-gradient least-squares (CGLS) method; tt may be necessary to regularize the subproblem very slightly to avoid a ill-posedness. Thereafter, a piecewise linesearch (arc search) is carried out along the arc \(x(\alpha) = P( x + \alpha s)\) for \(\alpha > 0\), where the projection operator is defined component-wise at any feasible point \(v\) to be

\[P_j(v) = \min( \max( x_j, x_j^{l}), x_j^{u});\]
thus this arc bends the search direction into the feasible region. The arc search is performed either exactly, by passing through a set of increasing breakpoints at which it changes direction, or inexactly, by evaluating a sequence of different \(\alpha\) on the arc. All computation is designed to exploit sparsity in \(A_o\).

reference#

Full details are provided in

N. I. M. Gould (2022). ``A projection method for bound-constrained linear least-squares’’. STFC-Rutherford Appleton Laboratory Computational Mathematics Group Internal Report 2023-1 (2023).

matrix storage#

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

Dense storage format: The matrix \(A_o\) 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 Ao_val will hold the value \(A_{o\,ij}\) for \(0 \leq i \leq o-1\), \(0 \leq j \leq n-1\). The string Ao_type = ‘dense’ should be specified.

Dense by columns storage format: The matrix \(A_o\) 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 \(o \ast j + i\) of the storage array Ao_val will hold the value \(A_{o\,ij}\) for \(0 \leq i \leq o-1\), \(0 \leq j \leq n-1\). The string Ao_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, \(0 \leq l \leq ne-1\), of \(A_o\), its row index i, column index j and value \(A_{o\,ij}\), \(0 \leq i \leq o-1\), \(0 \leq j \leq n-1\), are stored as the \(l\)-th components of the integer arrays Ao_row and Ao_col and real array Ao_val, respectively, while the number of nonzeros is recorded as Ao_ne = \(ne\). The string Ao_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_o\) the i-th component of the integer array Ao_ptr holds the position of the first entry in this row, while A_ptr(o) holds the total number of entries. The column indices j, \(0 \leq j \leq n-1\), and values \(A_{o\,ij}\) of the nonzero entries in the i-th row are stored in components l = Ao_ptr(i), \(\ldots\), Ao_ptr(i+1)-1, \(0 \leq i \leq o-1,\) of the integer array Ao_col, and real array Ao_val, respectively. For sparse matrices, this scheme almost always requires less storage than its predecessor. The string Ao_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_o\) the j-th component of the integer array Ao_ptr holds the position of the first entry in this column, while Ao_ptr(n) holds the total number of entries. The row indices i, \(0 \leq i \leq o-1\), and values \(A_{o\,ij}\) of the nonzero entries in the j-th columns are stored in components l = Ao_ptr(j), \(\ldots\), Ao_ptr(j+1)-1, \(0 \leq j \leq n-1\), of the integer array Ao_row, and real array Ao_val, respectively. As before, for sparse matrices, this scheme almost always requires less storage than the co-ordinate format. The string Ao_type = ‘sparse_by_columns’ should be specified.

introduction to function calls#

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

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

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

  • set up problem data structures and fixed values by caling one of

    • blls_import - in the case that \(A\) is explicitly available

    • blls_import_without_a - in the case that only the effect of applying \(A\) and its transpose to a vector is possible

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

  • solve the problem by calling one of

  • blls_information (optional) - recover information about the solution and solution process

  • blls_terminate - deallocate data structures

See the examples section for illustrations of use.

callable functions#

overview of functions provided#

// typedefs

typedef float spc_;
typedef double rpc_;
typedef int ipc_;

// structs

struct blls_control_type;
struct blls_inform_type;
struct blls_time_type;

// function calls

void blls_initialize(
    void **data,
    struct blls_control_type* control,
    ipc_ *status
);

void blls_read_specfile(
    struct blls_control_type* control,
    const char specfile[]
);

void blls_import(
    struct blls_control_type* control,
    void **data,
    ipc_ *status,
    ipc_ n,
    ipc_ o,
    const char A_type[],
    ipc_ Ao_ne,
    const ipc_ Ao_row[],
    const ipc_ Ao_col[],
    ipc_ Ao_ptr_ne,
    const ipc_ Ao_ptr[]
);

void blls_import_without_a(
    struct blls_control_type* control,
    void **data,
    ipc_ *status,
    ipc_ n,
    ipc_ m
);

void blls_reset_control(
    struct blls_control_type* control,
    void **data,
    ipc_ *status
);

void blls_solve_given_a(
    void **data,
    void *userdata,
    ipc_ *status,
    ipc_ n,
    ipc_ o,
    ipc_ Ao_ne,
    const rpc_ Ao_val[],
    const rpc_ b[],
    const rpc_ x_l[],
    const rpc_ x_u[],
    rpc_ x[],
    rpc_ z[],
    rpc_ r[],
    rpc_ g[],
    ipc_ x_stat[],
    const rpc_ w[],
    ipc_(*)(ipc_, const rpc_[], rpc_[], const void*) eval_prec
);

void blls_solve_reverse_a_prod(
    void **data,
    ipc_ *status,
    ipc_ *eval_status,
    ipc_ n,
    ipc_ o,
    const rpc_ b[],
    const rpc_ x_l[],
    const rpc_ x_u[],
    rpc_ x[],
    rpc_ z[],
    rpc_ r[],
    rpc_ g[],
    ipc_ x_stat[],
    rpc_ v[],
    const rpc_ p[],
    ipc_ nz_v[],
    ipc_ *nz_v_start,
    ipc_ *nz_v_end,
    const ipc_ nz_p[],
    ipc_ nz_p_end,
    const rpc_ w[]
);

void blls_information(void **data, struct blls_inform_type* inform, ipc_ *status);

void blls_terminate(
    void **data,
    struct blls_control_type* control,
    struct blls_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 blls_initialize(
    void **data,
    struct blls_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 blls_control_type)

status

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

  • 0

    The initialization was successful.

 
void blls_read_specfile(
    struct blls_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/blls/BLLS.template. See also Table 2.1 in the Fortran documentation provided in $GALAHAD/doc/blls.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 blls_control_type)

specfile

is a character string containing the name of the specification file

 
void blls_import(
    struct blls_control_type* control,
    void **data,
    ipc_ *status,
    ipc_ n,
    ipc_ o,
    const char A_type[],
    ipc_ A_ne,
    const ipc_ A_row[],
    const ipc_ A_col[],
    ipc_ A_ptr_ne,
    const ipc_ A_ptr[]
)

Import problem data into internal storage prior to solution.

Parameters:

control

is a struct whose members provide control paramters for the remaining prcedures (see blls_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:

  • **1

    The import was successful, and the package is ready for the solve phase

  • -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, o > 0 or requirement that type contains its relevant string ‘coordinate’, ‘sparse_by_rows’, ‘sparse_by_columns’, ‘dense_by_rows’, or ‘dense_by_columns’; has been violated**

n

is a scalar variable of type ipc_, that holds the number of variables.

o

is a scalar variable of type ipc_, that holds the number of residuals.

Ao_type

is a one-dimensional array of type char that specifies the symmetric storage scheme used for the design matrix \(A_o\). It should be one of ‘coordinate’, ‘sparse_by_rows’, ‘sparse_by_columns’, ‘dense_by_rows’, or ‘dense_by_columns’; lower or upper case variants are allowed.

Ao_ne

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

Ao_row

is a one-dimensional array of size Ao_ne and type ipc_, that holds the row indices of \(A_o\) in the sparse co-ordinate or sparse column-wise storage scheme. It need not be set for any of the other schemes, and in this case can be NULL.

Ao_col

is a one-dimensional array of size Ao_ne and type ipc_, that holds the column indices of \(A_o\) in either the sparse co-ordinate, or the sparse row-wise storage scheme. It need not be set for any of the other schemes, and in this case can be NULL.

Ao_ptr_ne

is a scalar variable of type ipc_, that holds the length of the pointer array if sparse row or column storage scheme is used for \(A_o\). For the sparse row scheme, Ao_ptr_ne should be at least o+1, while for the sparse column scheme, it should be at least n+1, It need not be set when the other schemes are used.

Ao_ptr

is a one-dimensional array of size Ao_ptr_ne and type ipc_, that holds the starting position of each row of \(A_o\), as well as the total number of entries, in the sparse row-wise storage scheme. By contrast, it holds the starting position of each column of \(A_o\), as well as the total number of entries, in the sparse column-wise storage scheme. It need not be set when the other schemes are used, and in this case can be NULL.

 
void blls_import_without_a(
    struct blls_control_type* control,
    void **data,
    ipc_ *status,
    ipc_ n,
    ipc_ o
)

Import problem data into internal storage prior to solution.

Parameters:

control

is a struct whose members provide control paramters for the remaining prcedures (see blls_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:

  • **1

    The import was successful, and the package is ready for the solve phase

  • -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 restriction n > 0 or o > 0 has been violated**

n

is a scalar variable of type ipc_, that holds the number of variables.

o

is a scalar variable of type ipc_, that holds the number of residuals.

 
void blls_reset_control(
    struct blls_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 blls_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:

    1. The import was successful, and the package is ready for the solve phase

 
void blls_solve_given_a(
    void **data,
    void *userdata,
    ipc_ *status,
    ipc_ n,
    ipc_ o,
    ipc_ Ao_ne,
    const rpc_ Ao_val[],
    const rpc_ b[],
    const rpc_ x_l[],
    const rpc_ x_u[],
    rpc_ x[],
    rpc_ z[],
    rpc_ r[],
    rpc_ g[],
    ipc_ x_stat[],
    const rpc_ w[],
    ipc_(*)(ipc_, const rpc_[], rpc_[], const void*) eval_prec
)

Solve the bound-constrained linear least-squares problem when the design matrix \(A_o\) is available.

Parameters:

data

holds private internal data

userdata

is a structure that allows data to be passed into the function and derivative evaluation programs.

status

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

On initial entry, status must be set to 1.

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, o > 0 or requirement that a type contains its relevant string ‘coordinate’, ‘sparse_by_rows’, ‘sparse_by_columns’, ‘dense_by_rows’ or ‘dense_by_columns’ has been violated.

  • -4

    The simple-bound constraints are inconsistent.

  • -9

    The analysis phase of the factorization failed; the return status from the factorization package is given in the component inform.factor_status

  • -10

    The factorization failed; the return status from the factorization package is given in the component inform.factor_status.

  • -18

    Too many iterations have been performed. This may happen if control.maxit is too small, but may also be symptomatic of a badly scaled problem.

  • -19

    The CPU time limit has been reached. This may happen if control.cpu_time_limit is too small, but may also be symptomatic of a badly scaled problem.

n

is a scalar variable of type ipc_, that holds the number of variables

o

is a scalar variable of type ipc_, that holds the number of residuals.

Ao_ne

is a scalar variable of type ipc_, that holds the number of entries in the design matrix \(A_o\).

A_val

is a one-dimensional array of size A_ne and type rpc_, that holds the values of the entries in the design matrix \(A_o\) in any of the available storage schemes.

b

is a one-dimensional array of size o and type rpc_, that holds the constant term \(b\) in the residuals. The i-th component of b, i = 0, … , o-1, contains \(b_i\).

x_l

is a one-dimensional array of size n and type rpc_, that holds the lower bounds \(x^l\) on the variables \(x\). The j-th component of x_l, j = 0, … , n-1, contains \(x^l_j\).

x_u

is a one-dimensional array of size n and type rpc_, that holds the upper bounds \(x^l\) on the variables \(x\). The j-th component of x_u, j = 0, … , n-1, contains \(x^l_j\).

x

is a one-dimensional array of size n and type rpc_, that holds the values \(x\) of the optimization variables. The j-th component of x, j = 0, … , n-1, contains \(x_j\).

z

is a one-dimensional array of size n and type rpc_, that holds the values \(z\) of the dual variables. The j-th component of z, j = 0, … , n-1, contains \(z_j\).

r

is a one-dimensional array of size o and type rpc_, that holds the values of the residuals \(r = A_o x - b\). The i-th component of r, i = 0, … , o-1, contains \(r_i\).

g

is a one-dimensional array of size n and type rpc_, that holds the values of the gradient \(g = A^T c\). The j-th component of g, j = 0, … , n-1, contains \(g_j\).

x_stat

is a one-dimensional array of size n and type ipc_, that gives the optimal status of the problem variables. If x_stat(j) is negative, the variable \(x_j\) most likely lies on its lower bound, if it is positive, it lies on its upper bound, and if it is zero, it lies between its bounds.

w

is an optional one-dimensional array of size o and type rpc_, that holds the values \(w\) of the weights on the residuals in the least-squares objective function. It need not be set if the weights are all ones, and in this case can be NULL.

eval_prec

is an optional user-supplied function that may be NULL. If non-NULL, it must have the following signature:

ipc_ eval_prec( ipc_ n, const rpc_ v[], rpc_ p[],
               const void *userdata )

The product \(p = P^{-1} v\) involving the user’s preconditioner \(P\) with the vector v = \(v\), the result \(p\) must be retured in p, and the function return value set to 0. If the evaluation is impossible, return should be set to a nonzero value. Data may be passed into eval_prec via the structure userdata.

 
void blls_solve_reverse_a_prod(
    void **data,
    ipc_ *status,
    ipc_ *eval_status,
    ipc_ n,
    ipc_ o,
    const rpc_ b[],
    const rpc_ x_l[],
    const rpc_ x_u[],
    rpc_ x[],
    rpc_ z[],
    rpc_ r[],
    rpc_ g[],
    ipc_ x_stat[],
    rpc_ v[],
    const rpc_ p[],
    ipc_ nz_v[],
    ipc_ *nz_v_start,
    ipc_ *nz_v_end,
    const ipc_ nz_p[],
    ipc_ nz_p_end,
    const rpc_ w[]
)

Solve the bound-constrained linear least-squares problem when the products of the Jacobian \(A_o\) and its transpose with specified vectors may be computed by the calling program.

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:

  • 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 restriction n > 0 or requirement that a type contains its relevant string ‘coordinate’, ‘sparse_by_rows’, ‘sparse_by_columns’, ‘dense_by_rows’ or ‘dense_by_columns’ has been violated.

  • -4

    The simple-bound constraints are inconsistent.

  • -9

    The analysis phase of the factorization failed; the return status from the factorization package is given in the component inform.factor_status

  • -10

    The factorization failed; the return status from the factorization package is given in the component inform.factor_status.

  • -11

    The solution of a set of linear equations using factors from the factorization package failed; the return status from the factorization package is given in the component inform.factor_status.

  • -18

    Too many iterations have been performed. This may happen if control.maxit is too small, but may also be symptomatic of a badly scaled problem.

  • -19

    The CPU time limit has been reached. This may happen if control.cpu_time_limit is too small, but may also be symptomatic of a badly scaled problem.

  • 2

    The product \(A_ov\) of the design matrix \(A_o\) with a given output vector \(v\) is required from the user. The vector \(v\) will be stored in v and the product \(A_ov\) must be returned in p, status_eval should be set to 0, and blls_solve_reverse_a_prod re-entered with all other arguments unchanged. If the product cannot be formed, v need not be set, but blls_solve_reverse_a_prod should be re-entered with eval_status set to a nonzero value.

  • 3

    The product \(A_o^Tv\) of the transpose of the design matrix \(A_o\) with a given output vector \(v\) is required from the user. The vector \(v\) will be stored in v and the product \(A_o^Tv\) must be returned in p, status_eval should be set to 0, and blls_solve_reverse_a_prod re-entered with all other arguments unchanged. If the product cannot be formed, v need not be set, but blls_solve_reverse_a_prod should be re-entered with eval_status set to a nonzero value.

  • 4

    The product \(A_ov\) of the design matrix \(A_o\) with a given sparse output vector \(v\) is required from the user. The nonzero components of the vector \(v\) will be stored as entries nz_in[nz_in_start-1:nz_in_end-1] of v and the product \(A_ov\) must be returned in p, status_eval should be set to 0, and blls_solve_reverse_a_prod re-entered with all other arguments unchanged; The remaining components of v should be ignored. If the product cannot be formed, v need not be set, but blls_solve_reverse_a_prod should be re-entered with eval_status set to a nonzero value.

  • 5

    The nonzero components of the product \(A_o v\) of the design matrix \(A_o\) with a given sparse output vector \(v\) is required from the user. The nonzero components of the vector \(v\) will be stored as entries nz_in[nz_in_start-1:nz_in_end-1] of v; the remaining components of v should be ignored. The resulting nonzeros in the product \(A_ov\) must be placed in their appropriate comnponents of p, while a list of indices of the nonzeros placed in nz_out[0 : nz_out_end-1] and the number of nonzeros recorded in nz_out_end. Additionally, status_eval should be set to 0, and blls_solve_reverse_a_prod re-entered with all other arguments unchanged. If the product cannot be formed, v, nz_out_end and nz_out need not be set, but blls_solve_reverse_a_prod should be re-entered with eval_status set to a nonzero value.

  • 6

    A subset of the product \(A_o^T v\) of the transpose of the design matrix \(A_o\) with a given output vector \(v\) is required from the user. The vector \(v\) will be stored in v and components nz_in[nz_in_start-1:nz_in_end-1] of the product \(A_o^Tv\) must be returned in the relevant components of p (the remaining components should not be set), status_eval should be set to 0, and blls_solve_reverse_a_prod re-entered with all other arguments unchanged. If the product cannot be formed, v need not be set, but blls_solve_reverse_a_prod should be re-entered with eval_status set to a nonzero value.

  • 7

    The product \(P^{-1}v\) of the inverse of the preconditioner \(P\) with a given output vector \(v\) is required from the user. The vector \(v\) will be stored in v and the product \(P^{-1} v\) must be returned in p, status_eval should be set to 0, and blls_solve_reverse_a_prod re-entered with all other arguments unchanged. If the product cannot be formed, v need not be set, but blls_solve_reverse_a_prod should be re-entered with eval_status set to a nonzero value. This value of status can only occur if the user has set control.preconditioner = 2.

eval_status

is a scalar variable of type ipc_, that is used to indicate if the matrix products can be provided (see status above)

n

is a scalar variable of type ipc_, that holds the number of variables

o

is a scalar variable of type ipc_, that holds the number of residuals.

b

is a one-dimensional array of size o and type rpc_, that holds the constant term \(b\) in the residuals. The i-th component of b, i = 0, … , o-1, contains \(b_i\).

x_l

is a one-dimensional array of size n and type rpc_, that holds the lower bounds \(x^l\) on the variables \(x\). The j-th component of x_l, j = 0, … , n-1, contains \(x^l_j\).

x_u

is a one-dimensional array of size n and type rpc_, that holds the upper bounds \(x^l\) on the variables \(x\). The j-th component of x_u, j = 0, … , n-1, contains \(x^l_j\).

x

is a one-dimensional array of size n and type rpc_, that holds the values \(x\) of the optimization variables. The j-th component of x, j = 0, … , n-1, contains \(x_j\).

r

is a one-dimensional array of size m and type rpc_, that holds the values of the residuals \(r = A x - b\). The i-th component of r, i = 0, … , o-1, contains \(r_i\).

g

is a one-dimensional array of size n and type rpc_, that holds the values of the gradient \(g = A^T W r\). The j-th component of g, j = 0, … , n-1, contains \(g_j\).

z

is a one-dimensional array of size n and type rpc_, that holds the values \(z\) of the dual variables. The j-th component of z, j = 0, … , n-1, contains \(z_j\).

x_stat

is a one-dimensional array of size n and type ipc_, that gives the optimal status of the problem variables. If x_stat(j) is negative, the variable \(x_j\) most likely lies on its lower bound, if it is positive, it lies on its upper bound, and if it is zero, it lies between its bounds.

v

is a one-dimensional array of size n and type rpc_, that is used for reverse communication (see status=2-4 above for details).

p

is a one-dimensional array of size n and type rpc_, that is used for reverse communication (see status=2-4 above for details).

nz_v

is a one-dimensional array of size n and type ipc_, that is used for reverse communication (see status=3-4 above for details).

nz_v_start

is a scalar of type ipc_, that is used for reverse communication (see status=3-4 above for details).

nz_v_end

is a scalar of type ipc_, that is used for reverse communication (see status=3-4 above for details).

nz_p

is a one-dimensional array of size n and type ipc_, that is used for reverse communication (see status=4 above for details).

nz_p_end

is a scalar of type ipc_, that is used for reverse communication (see status=4 above for details).

w

is an optional one-dimensional array of size m and type rpc_, that holds the values \(w\) of the weights on the residuals in the least-squares objective function. It need not be set if the weights are all ones, and in this case can be NULL.

 
void blls_information(void **data, struct blls_inform_type* inform, ipc_ *status)

Provides output information

Parameters:

data

holds private internal data

inform

is a struct containing output information (see blls_inform_type)

status

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

  • 0

    The values were recorded successfully

 
void blls_terminate(
    void **data,
    struct blls_control_type* control,
    struct blls_inform_type* inform
)

Deallocate all internal private storage

Parameters:

data

holds private internal data

control

is a struct containing control information (see blls_control_type)

inform

is a struct containing output information (see blls_inform_type)

available structures#

blls_control_type structure#

#include <galahad_blls.h>

struct blls_control_type {
    // components

    bool f_indexing;
    ipc_ error;
    ipc_ out;
    ipc_ print_level;
    ipc_ start_print;
    ipc_ stop_print;
    ipc_ print_gap;
    ipc_ maxit;
    ipc_ cold_start;
    ipc_ preconditioner;
    ipc_ ratio_cg_vs_sd;
    ipc_ change_max;
    ipc_ cg_maxit;
    ipc_ arcsearch_max_steps;
    ipc_ sif_file_device;
    rpc_ weight;
    rpc_ infinity;
    rpc_ stop_d;
    rpc_ identical_bounds_tol;
    rpc_ stop_cg_relative;
    rpc_ stop_cg_absolute;
    rpc_ alpha_max;
    rpc_ alpha_initial;
    rpc_ alpha_reduction;
    rpc_ arcsearch_acceptance_tol;
    rpc_ stabilisation_weight;
    rpc_ cpu_time_limit;
    bool direct_subproblem_solve;
    bool exact_arc_search;
    bool advance;
    bool space_critical;
    bool deallocate_error_fatal;
    bool generate_sif_file;
    char sif_file_name[31];
    char prefix[31];
    struct sbls_control_type sbls_control;
    struct convert_control_type convert_control;
};

detailed documentation#

control derived type as a C struct

components#

bool f_indexing

use C or Fortran sparse matrix indexing

ipc_ error

unit number for error and warning diagnostics

ipc_ out

general output unit number

ipc_ print_level

the level of output required

ipc_ start_print

on which iteration to start printing

ipc_ stop_print

on which iteration to stop printing

ipc_ print_gap

how many iterations between printing

ipc_ maxit

how many iterations to perform (-ve reverts to HUGE(1)-1)

ipc_ cold_start

cold_start should be set to 0 if a warm start is required (with variable assigned according to X_stat, see below), and to any other value if the values given in prob.X suffice

ipc_ preconditioner

the preconditioner (scaling) used. Possible values are: /li 0. no preconditioner. /li 1. a diagonal preconditioner that normalizes the rows of \(A\). /li anything else. a preconditioner supplied by the user either via a subroutine call of eval_prec} or via reverse communication.

ipc_ ratio_cg_vs_sd

the ratio of how many iterations use CGLS rather than steepest descent

ipc_ change_max

the maximum number of per-iteration changes in the working set permitted when allowing CGLS rather than steepest descent

ipc_ cg_maxit

how many CG iterations to perform per BLLS iteration (-ve reverts to n+1)

ipc_ arcsearch_max_steps

the maximum number of steps allowed in a piecewise arcsearch (-ve=infini

ipc_ sif_file_device

the unit number to write generated SIF file describing the current probl

rpc_ weight

the value of the non-negative regularization weight sigma, i.e., the quadratic objective function q(x) will be regularized by adding 1/2 weight ||x||^2; any value smaller than zero will be regarded as zero.

rpc_ infinity

any bound larger than infinity in modulus will be regarded as infinite

rpc_ stop_d

the required accuracy for the dual infeasibility

rpc_ identical_bounds_tol

any pair of constraint bounds (x_l,x_u) that are closer than identical_bounds_tol will be reset to the average of their values

rpc_ stop_cg_relative

the CG iteration will be stopped as soon as the current norm of the preconditioned gradient is smaller than max( stop_cg_relative * initial preconditioned gradient, stop_cg_absolute)

rpc_ alpha_max

the largest permitted arc length during the piecewise line search

rpc_ alpha_initial

the initial arc length during the inexact piecewise line search

rpc_ alpha_reduction

the arc length reduction factor for the inexact piecewise line search

rpc_ arcsearch_acceptance_tol

the required relative reduction during the inexact piecewise line search

rpc_ stabilisation_weight

the stabilisation weight added to the search-direction subproblem

rpc_ cpu_time_limit

the maximum CPU time allowed (-ve = no limit)

bool direct_subproblem_solve

direct_subproblem_solve is true if the least-squares subproblem is to be solved using a matrix factorization, and false if conjugate gradients are to be preferred

bool exact_arc_search

exact_arc_search is true if an exact arc_search is required, and false if an approximation suffices

bool advance

advance is true if an inexact exact arc_search can increase steps as well as decrease them

bool space_critical

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

bool deallocate_error_fatal

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

bool generate_sif_file

if generate_sif_file is true, a SIF file describing the current problem will be generated

char sif_file_name[31]

name (max 30 characters) of generated SIF file containing input problem

char prefix[31]

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

struct sbls_control_type sbls_control

control parameters for SBLS

struct convert_control_type convert_control

control parameters for CONVERT

blls_time_type structure#

#include <galahad_blls.h>

struct blls_time_type {
    // components

    rpc_ total;
    rpc_ analyse;
    rpc_ factorize;
    rpc_ solve;
    rpc_ clock_total;
    rpc_ clock_analyse;
    rpc_ clock_factorize;
    rpc_ clock_solve;
};

detailed documentation#

time derived type as a C struct

components#

rpc_ total

the total CPU time spent in the package

rpc_ analyse

the CPU time spent analysing the required matrices prior to factorization

rpc_ factorize

the CPU time spent factorizing the required matrices

rpc_ solve

the CPU time spent in the linear solution phase

rpc_ clock_total

the total clock time spent in the package

rpc_ clock_analyse

the clock time spent analysing the required matrices prior to factorization

rpc_ clock_factorize

the clock time spent factorizing the required matrices

rpc_ clock_solve

the clock time spent in the linear solution phase

blls_inform_type structure#

#include <galahad_blls.h>

struct blls_inform_type {
    // components

    ipc_ status;
    ipc_ alloc_status;
    ipc_ factorization_status;
    ipc_ iter;
    ipc_ cg_iter;
    rpc_ obj;
    rpc_ norm_pg;
    char bad_alloc[81];
    struct blls_time_type time;
    struct sbls_inform_type sbls_inform;
    struct convert_inform_type convert_inform;
};

detailed documentation#

inform derived type as a C struct

components#

ipc_ status

reported return status.

ipc_ alloc_status

Fortran STAT value after allocate failure.

ipc_ factorization_status

status return from factorization

ipc_ iter

number of iterations required

ipc_ cg_iter

number of CG iterations required

rpc_ obj

current value of the objective function, r(x).

rpc_ norm_pg

current value of the Euclidean norm of projected gradient of r(x).

char bad_alloc[81]

name of array which provoked an allocate failure

struct blls_time_type time

times for various stages

struct sbls_inform_type sbls_inform

inform values from SBLS

struct convert_inform_type convert_inform

inform values for CONVERT

Index

example calls#

This is an example of how to use the package to solve a bound-constrained linear least-squares problem; the code is available in $GALAHAD/src/blls/C/bllst.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.

/* bllst.c */
/* Full test for the BLLS 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_blls.h"
#ifdef REAL_128
#include <quadmath.h>
#endif

// Define imax
ipc_ imax(ipc_ a, ipc_ b) {
    return (a > b) ? a : b;
};

// Custom userdata struct
struct userdata_type {
   rpc_ scale;
};

// Function prototypes
ipc_ prec( ipc_ n, const rpc_ v[], rpc_ p[], const void * );

int main(void) {

    // Derived types
    void *data;
    struct blls_control_type control;
    struct blls_inform_type inform;

    // Set user data
    struct userdata_type userdata;
    userdata.scale = 1.0;

    // Set problem data
    ipc_ n = 10; // dimension
    ipc_ o = n + 1; // number of residuals
    ipc_ Ao_ne = 2 * n; // sparse Jacobian elements
    ipc_ Ao_dense_ne = o * n; // dense Jacobian elements
    // row-wise storage
    ipc_ Ao_row[Ao_ne]; // row indices,
    ipc_ Ao_col[Ao_ne]; // column indices
    ipc_ Ao_ptr_ne = o+1; // number of row pointers
    ipc_ Ao_ptr[ Ao_ptr_ne];  // row pointers
    rpc_ Ao_val[Ao_ne]; // values
    rpc_ Ao_dense[Ao_dense_ne]; // dense values
    // column-wise storage
    ipc_ Ao_by_col_row[Ao_ne]; // row indices,
    ipc_ Ao_by_col_ptr_ne = n+1; // number of column pointers
    ipc_ Ao_by_col_ptr[Ao_by_col_ptr_ne];  // column pointers
    rpc_ Ao_by_col_val[Ao_ne]; // values
    rpc_ Ao_by_col_dense[Ao_dense_ne]; // dense values
    rpc_ b[o];  // linear term in the objective
    rpc_ x_l[n]; // variable lower bound
    rpc_ x_u[n]; // variable upper bound
    rpc_ x[n]; // variables
    rpc_ z[n]; // dual variables
    rpc_ r[o]; // residual
    rpc_ g[n]; // gradient
    rpc_ w[o]; // weights

    // Set output storage
    ipc_ x_stat[n]; // variable status
    char st[3];
    ipc_ i, l, status;

    x_l[0] = -1.0;
    for( ipc_ i = 1; i < n; i++) x_l[i] = - INFINITY;
    x_u[0] = 1.0;
    x_u[1] = INFINITY;
    for( ipc_ i = 2; i < n; i++) x_u[i] = 2.0;

    //   A = (  I  )  and b = ( i * e )
    //       ( e^T )          ( n + 1 )

    for( ipc_ i = 0; i < n; i++) b[i] = i + 1;
    b[n] = n+1;

    //w[0] = 2.0;
    w[0] = 1.0;
    for( ipc_ i = 1; i < o; i++) w[i] = 1.0;

    // A by rows

    for( ipc_ i = 0; i < n; i++)
    {
      Ao_ptr[i] = i;
      Ao_row[i] = i; Ao_col[i] = i; Ao_val[i] = 1.0;
    }
    Ao_ptr[n] = n;
    for( ipc_ i = 0; i < n; i++)
    {
      Ao_row[n+i] = n; Ao_col[n+i] = i; Ao_val[n+i] = 1.0;
    }
    Ao_ptr[o] = Ao_ne;
    l = - 1;
    for( ipc_ i = 0; i < n; i++)
    {
      for( ipc_ j = 0; j < n; j++)
      {
        l = l + 1;
        if ( i == j ) {
          Ao_dense[l] = 1.0;
        }
        else {
          Ao_dense[l] = 0.0;
        }
      }
    }
    for( ipc_ j = 0; j < n; j++)
    {
      l = l + 1;
      Ao_dense[l] = 1.0;
    }

    // A by columns

    l = - 1;
    for( ipc_ j = 0; j < n; j++)
    {
      l = l + 1;  Ao_by_col_ptr[j] = l ;
      Ao_by_col_row[l] = j ; Ao_by_col_val[l] = 1.0;
      l = l + 1;
      Ao_by_col_row[l] = n ; Ao_by_col_val[l] = 1.0;
    }
    Ao_by_col_ptr[n] = Ao_ne;
    l = - 1;
    for( ipc_ j = 0; j < n; j++)
    {
      for( ipc_ i = 0; i < n; i++)
      {
        l = l + 1;
        if ( i == j ) {
          Ao_by_col_dense[l] = 1.0;
        }
        else {
          Ao_by_col_dense[l] = 0.0;
        }
      }
      l = l + 1;
      Ao_by_col_dense[l] = 1.0;
    }

    printf(" C sparse matrix indexing\n\n");

    printf(" basic tests of blls storage formats\n\n");

    for( ipc_ d=1; d <= 5; d++){

        // Initialize BLLS
        blls_initialize( &data, &control, &status );
        strcpy(control.sbls_control.symmetric_linear_solver, "sytr ") ;
        strcpy(control.sbls_control.definite_linear_solver, "potr ") ;

        // Set user-defined control options
        control.f_indexing = false; // C sparse matrix indexing
        //control.print_level = 1;

        // Start from 0
        for( ipc_ i = 0; i < n; i++) x[i] = 0.0;
        for( ipc_ i = 0; i < n; i++) z[i] = 0.0;

        switch(d){
            case 1: // sparse co-ordinate storage
                strcpy( st, "CO" );
                blls_import( &control, &data, &status, n, o,
                            "coordinate", Ao_ne, Ao_row, Ao_col, 0, NULL );
                blls_solve_given_a( &data, &userdata, &status, n, o,
                                    Ao_ne, Ao_val, b, x_l, x_u,
                                    x, z, r, g, x_stat, w, prec );
                break;
            case 2: // sparse by rows
                strcpy( st, "SR" );
                blls_import( &control, &data, &status, n, o,
                             "sparse_by_rows", Ao_ne, NULL, Ao_col,
                             Ao_ptr_ne, Ao_ptr );
                blls_solve_given_a( &data, &userdata, &status, n, o,
                                    Ao_ne, Ao_val, b, x_l, x_u,
                                    x, z, r, g, x_stat, w, prec );
                break;
            case 3: // dense by rows
                strcpy( st, "DR" );
                blls_import( &control, &data, &status, n, o,
                             "dense_by_rows", Ao_dense_ne,
                              NULL, NULL,0,  NULL );
                blls_solve_given_a( &data, &userdata, &status, n, o,
                                    Ao_dense_ne, Ao_dense, b, x_l, x_u,
                                    x, z, r, g, x_stat, w, prec );
                break;
            case 4: // sparse by columns
                strcpy( st, "SC" );
                blls_import( &control, &data, &status, n, o,
                             "sparse_by_columns", Ao_ne, Ao_by_col_row,
                             NULL, Ao_by_col_ptr_ne, Ao_by_col_ptr );
                blls_solve_given_a( &data, &userdata, &status, n, o,
                                    Ao_ne, Ao_by_col_val, b, x_l, x_u,
                                    x, z, r, g, x_stat, w, prec );
                break;
            case 5: // dense by columns
                strcpy( st, "DC" );
                blls_import( &control, &data, &status, n, o,
                             "dense_by_columns", Ao_dense_ne,
                             NULL, NULL, 0, NULL);
                blls_solve_given_a( &data, &userdata, &status, n, o,
                                    Ao_dense_ne, Ao_by_col_dense, b, x_l, x_u,
                                    x, z, r, g, x_stat, w, prec );
                break;
            }
        blls_information( &data, &inform, &status );

        if(inform.status == 0){
#ifdef REAL_128
// interim replacement for quad output: $GALAHAD/include/galahad_pquad_sf.h
#include "galahad_pquad_sf.h"
#else
            printf("%s:%6" i_ipc_ " iterations. Optimal objective "
                   "value = %.2f status = %1" i_ipc_ "\n",
                   st, inform.iter, inform.obj, inform.status);
#endif
        }else{
            printf("%s: BLLS_solve exit status = %1" i_ipc_ "\n",
                    st, inform.status);
        }
        //printf("x: ");
        //for( ipc_ i = 0; i < n; i++) printf("%f ", x[i]);
        //printf("\n");
        //printf("gradient: ");
        //for( ipc_ i = 0; i < n; i++) printf("%f ", g[i]);
        //printf("\n");

        // Delete internal workspace
        blls_terminate( &data, &control, &inform );
    }

    printf("\n tests reverse-communication options\n\n");

    // reverse-communication input/output
    ipc_ on;
    on = imax( o, n );
    ipc_ eval_status, nz_v_start, nz_v_end, nz_p_end;
    ipc_ nz_v[on], nz_p[o], mask[o];
    rpc_ v[on], p[on];

    nz_p_end = 0;

    // Initialize BLLS
    blls_initialize( &data, &control, &status );

    // Set user-defined control options
    control.f_indexing = false; // C sparse matrix indexing
    // control.print_level = 1;

    // Start from 0
    for( ipc_ i = 0; i < n; i++) x[i] = 0.0;
    for( ipc_ i = 0; i < n; i++) z[i] = 0.0;

    strcpy( st, "RC" );
    for( ipc_ i = 0; i < o; i++) mask[i] = 0;
    blls_import_without_a( &control, &data, &status, n, o ) ;
    while(true){ // reverse-communication loop
        blls_solve_reverse_a_prod( &data, &status, &eval_status, n, o, b,
                                   x_l, x_u, x, z, r, g, x_stat, v, p,
                                   nz_v, &nz_v_start, &nz_v_end,
                                   nz_p, nz_p_end, w );
        if(status == 0){ // successful termination
            break;
        }else if(status < 0){ // error exit
            break;
        }else if(status == 2){ // evaluate p = Av
          p[n]=0.0;
          for( ipc_ i = 0; i < n; i++){
            p[i] = v[i];
            p[n] = p[n] + v[i];
          }
        }else if(status == 3){ // evaluate p = A^Tv
          for( ipc_ i = 0; i < n; i++) p[i] = v[i] + v[n];
        }else if(status == 4){ // evaluate p = Av for sparse v
          p[n]=0.0;
          for( ipc_ i = 0; i < n; i++) p[i] = 0.0;
          for( ipc_ l = nz_v_start - 1; l < nz_v_end; l++){
            i = nz_v[l];
            p[i] = v[i];
            p[n] = p[n] + v[i];
          }
        }else if(status == 5){ // evaluate p = sparse Av for sparse v
          nz_p_end = 0;
          for( ipc_ l = nz_v_start - 1; l < nz_v_end; l++){
            i = nz_v[l];
            if (mask[i] == 0){
              mask[i] = 1;
              nz_p[nz_p_end] = i;
              nz_p_end = nz_p_end + 1;
              p[i] = v[i];
            }
            if (mask[n] == 0){
              mask[n] = 1;
              nz_p[nz_p_end] = n;
              nz_p_end = nz_p_end + 1;
              p[n] = v[i];
            }else{
              p[n] = p[n] + v[i];
            }
          }
          for( ipc_ l = 0; l < nz_p_end; l++) mask[nz_p[l]] = 0;
        }else if(status == 6){ // evaluate p = sparse A^Tv
          for( ipc_ l = nz_v_start - 1; l < nz_v_end; l++){
            i = nz_v[l];
            p[i] = v[i] + v[n];
          }
        }else if(status == 7){ // evaluate p = P^{-}v
          for( ipc_ i = 0; i < n; i++) p[i] = userdata.scale * v[i];
        }else{
            printf(" the value %1" i_ipc_ " of status should not occur\n",
                   status);
            break;
        }
        eval_status = 0;
    }

    // Record solution information
    blls_information( &data, &inform, &status );

    // Print solution details
    if(inform.status == 0){
#ifdef REAL_128
// interim replacement for quad output: $GALAHAD/include/galahad_pquad_sf.h
#include "galahad_pquad_sf.h"
#else
            printf("%s:%6" i_ipc_ " iterations. Optimal objective "
                   "value = %.2f status = %1" i_ipc_ "\n",
                   st, inform.iter, inform.obj, inform.status);
#endif
    }else{
        printf("%s: BLLS_solve exit status = %1" i_ipc_ "\n",
               st, inform.status);
    }
    //printf("x: ");
    //for( ipc_ i = 0; i < n; i++) printf("%f ", x[i]);
    //printf("\n");
    //printf("gradient: ");
    //for( ipc_ i = 0; i < n; i++) printf("%f ", g[i]);
    //printf("\n");

    // Delete internal workspace
    blls_terminate( &data, &control, &inform );
}

// Apply preconditioner
ipc_ prec( ipc_ n, const rpc_ v[], rpc_ p[], const void *userdata ){
  struct userdata_type *myuserdata = (struct userdata_type *) userdata;
  rpc_ scale = myuserdata->scale;
  for( ipc_ i = 0; i < n; i++) p[i] = scale * v[i];
   return 0;
}

This is the same example, but now fortran-style indexing is used; the code is available in $GALAHAD/src/blls/C/bllstf.c .

/* bllstf.c */
/* Full test for the BLLS 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_blls.h"
#ifdef REAL_128
#include <quadmath.h>
#endif

// Define imax
ipc_ imax(ipc_ a, ipc_ b) {
    return (a > b) ? a : b;
};

// Custom userdata struct
struct userdata_type {
   rpc_ scale;
};

// Function prototypes
ipc_ prec( ipc_ n, const rpc_ v[], rpc_ p[], const void * );

int main(void) {

    // Derived types
    void *data;
    struct blls_control_type control;
    struct blls_inform_type inform;

    // Set user data
    struct userdata_type userdata;
    userdata.scale = 1.0;

    // Set problem data
    ipc_ n = 10; // dimension
    ipc_ o = n + 1; // number of residuals
    ipc_ Ao_ne = 2 * n; // sparse Jacobian elements
    ipc_ Ao_dense_ne = o * n; // dense Jacobian elements
    // row-wise storage
    ipc_ Ao_row[Ao_ne]; // row indices,
    ipc_ Ao_col[Ao_ne]; // column indices
    ipc_ Ao_ptr_ne = o+1; // number of row pointers
    ipc_ Ao_ptr[ Ao_ptr_ne];  // row pointers
    rpc_ Ao_val[Ao_ne]; // values
    rpc_ Ao_dense[Ao_dense_ne]; // dense values
    // column-wise storage
    ipc_ Ao_by_col_row[Ao_ne]; // row indices,
    ipc_ Ao_by_col_ptr_ne = n+1; // number of column pointers
    ipc_ Ao_by_col_ptr[Ao_by_col_ptr_ne];  // column pointers
    rpc_ Ao_by_col_val[Ao_ne]; // values
    rpc_ Ao_by_col_dense[Ao_dense_ne]; // dense values
    rpc_ b[o];  // linear term in the objective
    rpc_ x_l[n]; // variable lower bound
    rpc_ x_u[n]; // variable upper bound
    rpc_ x[n]; // variables
    rpc_ z[n]; // dual variables
    rpc_ r[o]; // residual
    rpc_ g[n]; // gradient
    rpc_ w[o]; // weights

    // Set output storage
    ipc_ x_stat[n]; // variable status
    char st[3];
    ipc_ i, l, status;

    x_l[0] = -1.0;
    for( ipc_ i = 1; i < n; i++) x_l[i] = - INFINITY;
    x_u[0] = 1.0;
    x_u[1] = INFINITY;
    for( ipc_ i = 2; i < n; i++) x_u[i] = 2.0;

    //   A = (  I  )  and b = ( i * e )
    //       ( e^T )          ( n + 1 )

    for( ipc_ i = 0; i < n; i++) b[i] = i + 1;
    b[n] = n+1;

    // w[0] = 2.0;
    w[0] = 1.0;
    for( ipc_ i = 1; i < o; i++) w[i] = 1.0;

    // A by rows

    for( ipc_ i = 0; i < n; i++)
    {
      Ao_ptr[i] = i + 1;
      Ao_row[i] = i + 1; Ao_col[i] = i + 1; Ao_val[i] = 1.0;
    }
    Ao_ptr[n] = n + 1;
    for( ipc_ i = 0; i < n; i++)
    {
      Ao_row[n+i] = o; Ao_col[n+i] = i + 1; Ao_val[n+i] = 1.0;
    }
    Ao_ptr[o] = Ao_ne + 1;
    l = - 1;
    for( ipc_ i = 0; i < n; i++)
    {
      for( ipc_ j = 0; j < n; j++)
      {
        l = l + 1;
        if ( i == j ) {
          Ao_dense[l] = 1.0;
        }
        else {
          Ao_dense[l] = 0.0;
        }
      }
    }
    for( ipc_ j = 0; j < n; j++)
    {
      l = l + 1;
      Ao_dense[l] = 1.0;
    }

    // A by columns

    l = - 1;
    for( ipc_ j = 0; j < n; j++)
    {
      l = l + 1;  Ao_by_col_ptr[j] = l + 1;
      Ao_by_col_row[l] = j + 1; Ao_by_col_val[l] = 1.0;
      l = l + 1;
      Ao_by_col_row[l] = o; Ao_by_col_val[l] = 1.0;
    }
    Ao_by_col_ptr[n] = Ao_ne + 1;
    l = - 1;
    for( ipc_ j = 0; j < n; j++)
    {
      for( ipc_ i = 0; i < n; i++)
      {
        l = l + 1;
        if ( i == j ) {
          Ao_by_col_dense[l] = 1.0;
        }
        else {
          Ao_by_col_dense[l] = 0.0;
        }
      }
      l = l + 1;
      Ao_by_col_dense[l] = 1.0;
    }

    printf(" fortran sparse matrix indexing\n\n");

    printf(" basic tests of blls storage formats\n\n");

    for( ipc_ d=1; d <= 5; d++){

        // Initialize BLLS
        blls_initialize( &data, &control, &status );
        strcpy(control.sbls_control.symmetric_linear_solver, "sytr ") ;
        strcpy(control.sbls_control.definite_linear_solver, "potr ") ;

        // Set user-defined control options
        control.f_indexing = true; // fortran sparse matrix indexing

        // Start from 0
        for( ipc_ i = 0; i < n; i++) x[i] = 0.0;
        for( ipc_ i = 0; i < n; i++) z[i] = 0.0;

        switch(d){
            case 1: // sparse co-ordinate storage
                strcpy( st, "CO" );
                blls_import( &control, &data, &status, n, o,
                            "coordinate", Ao_ne, Ao_row, Ao_col, 0, NULL );
                blls_solve_given_a( &data, &userdata, &status, n, o,
                                    Ao_ne, Ao_val, b, x_l, x_u,
                                    x, z, r, g, x_stat, w, prec );
                break;
            case 2: // sparse by rows
                strcpy( st, "SR" );
                blls_import( &control, &data, &status, n, o,
                             "sparse_by_rows", Ao_ne, NULL, Ao_col,
                             Ao_ptr_ne, Ao_ptr );
                blls_solve_given_a( &data, &userdata, &status, n, o,
                                    Ao_ne, Ao_val, b, x_l, x_u,
                                    x, z, r, g, x_stat, w, prec );
                break;
            case 3: // dense by rows
                strcpy( st, "DR" );
                blls_import( &control, &data, &status, n, o,
                             "dense_by_rows", Ao_dense_ne,
                             NULL, NULL, 0, NULL );
                blls_solve_given_a( &data, &userdata, &status, n, o,
                                    Ao_dense_ne, Ao_dense, b, x_l, x_u,
                                    x, z, r, g, x_stat, w, prec );
                break;
            case 4: // sparse by columns
                strcpy( st, "SC" );
                blls_import( &control, &data, &status, n, o,
                             "sparse_by_columns", Ao_ne, Ao_by_col_row,
                             NULL,  Ao_by_col_ptr_ne, Ao_by_col_ptr );
                blls_solve_given_a( &data, &userdata, &status, n, o,
                                    Ao_ne, Ao_by_col_val, b, x_l, x_u,
                                    x, z, r, g, x_stat, w, prec );
                break;
            case 5: // dense by columns
                strcpy( st, "DC" );
                blls_import( &control, &data, &status, n, o,
                             "dense_by_columns", Ao_dense_ne,
                             NULL, NULL, 0, NULL);
                blls_solve_given_a( &data, &userdata, &status, n, o,
                                    Ao_dense_ne, Ao_by_col_dense, b, x_l, x_u,
                                    x, z, r, g, x_stat, w, prec );
                break;
            }
        blls_information( &data, &inform, &status );

        if(inform.status == 0){
#ifdef REAL_128
// interim replacement for quad output: $GALAHAD/include/galahad_pquad_sf.h
#include "galahad_pquad_sf.h"
#else
            printf("%s:%6" i_ipc_ " iterations. Optimal objective "
                   "value = %.2f status = %1" i_ipc_ "\n",
                   st, inform.iter, inform.obj, inform.status);
#endif
        }else{
            printf("%s: BLLS_solve exit status = %1" i_ipc_ "\n",
                   st, inform.status);
        }
        //printf("x: ");
        //for( ipc_ i = 0; i < n; i++) printf("%f ", x[i]);
        //printf("\n");
        //printf("gradient: ");
        //for( ipc_ i = 0; i < n; i++) printf("%f ", g[i]);
        //printf("\n");

        // Delete internal workspace
        blls_terminate( &data, &control, &inform );
    }

    printf("\n tests reverse-communication options\n\n");

    // reverse-communication input/output
    ipc_ on;
    on = imax( o, n );
    ipc_ eval_status, nz_v_start, nz_v_end, nz_p_end;
    ipc_ nz_v[on], nz_p[o], mask[o];
    rpc_ v[on], p[on];

    nz_p_end = 0;

    // Initialize BLLS
    blls_initialize( &data, &control, &status );

    // Set user-defined control options
    control.f_indexing = true; // fortran sparse matrix indexing

    // Start from 0
    for( ipc_ i = 0; i < n; i++) x[i] = 0.0;
    for( ipc_ i = 0; i < n; i++) z[i] = 0.0;

    strcpy( st, "RC" );
    for( ipc_ i = 0; i < o; i++) mask[i] = 0;
    blls_import_without_a( &control, &data, &status, n, o ) ;
    while(true){ // reverse-communication loop
        blls_solve_reverse_a_prod( &data, &status, &eval_status, n, o, b,
                                   x_l, x_u, x, z, r, g, x_stat, v, p,
                                   nz_v, &nz_v_start, &nz_v_end,
                                   nz_p, nz_p_end, w );
        if(status == 0){ // successful termination
            break;
        }else if(status < 0){ // error exit
            break;
        }else if(status == 2){ // evaluate p = Av
          p[n]=0.0;
          for( ipc_ i = 0; i < n; i++){
            p[i] = v[i];
            p[n] = p[n] + v[i];
          }
        }else if(status == 3){ // evaluate p = A^Tv
          for( ipc_ i = 0; i < n; i++) p[i] = v[i] + v[n];
        }else if(status == 4){ // evaluate p = Av for sparse v
          p[n]=0.0;
          for( ipc_ i = 0; i < n; i++) p[i] = 0.0;
          for( ipc_ l = nz_v_start - 1; l < nz_v_end; l++){
            i = nz_v[l]-1;
            p[i] = v[i];
            p[n] = p[n] + v[i];
          }
        }else if(status == 5){ // evaluate p = sparse Av for sparse v
          nz_p_end = 0;
          for( ipc_ l = nz_v_start - 1; l < nz_v_end; l++){
            i = nz_v[l]-1;
            if (mask[i] == 0){
              mask[i] = 1;
              nz_p[nz_p_end] = i+1;
              nz_p_end = nz_p_end + 1;
              p[i] = v[i];
            }
            if (mask[n] == 0){
              mask[n] = 1;
              nz_p[nz_p_end] = o;
              nz_p_end = nz_p_end + 1;
              p[n] = v[i];
            }else{
              p[n] = p[n] + v[i];
            }
          }
          for( ipc_ l = 0; l < nz_p_end; l++) mask[nz_p[l]-1] = 0;
        }else if(status == 6){ // evaluate p = sparse A^Tv
          for( ipc_ l = nz_v_start - 1; l < nz_v_end; l++){
            i = nz_v[l]-1;
            p[i] = v[i] + v[n];
          }
        }else if(status == 7){ // evaluate p = P^{-}v
          for( ipc_ i = 0; i < n; i++) p[i] = userdata.scale * v[i];
        }else{
            printf(" the value %1" i_ipc_ " of status should not occur\n",
                   status);
            break;
        }
        eval_status = 0;
    }

    // Record solution information
    blls_information( &data, &inform, &status );

    // Print solution details
    if(inform.status == 0){
#ifdef REAL_128
// interim replacement for quad output: $GALAHAD/include/galahad_pquad_sf.h
#include "galahad_pquad_sf.h"
#else
            printf("%s:%6" i_ipc_ " iterations. Optimal objective "
                   "value = %.2f status = %1" i_ipc_ "\n",
                   st, inform.iter, inform.obj, inform.status);
#endif
    }else{
        printf("%s: BLLS_solve exit status = %1" i_ipc_ "\n",
               st, inform.status);
    }
    //printf("x: ");
    //for( ipc_ i = 0; i < n; i++) printf("%f ", x[i]);
    //printf("\n");
    //printf("gradient: ");
    //for( ipc_ i = 0; i < n; i++) printf("%f ", g[i]);
    //printf("\n");

    // Delete internal workspace
    blls_terminate( &data, &control, &inform );
}

// Apply preconditioner
ipc_ prec( ipc_ n, const rpc_ v[], rpc_ p[], const void *userdata ){
  struct userdata_type *myuserdata = (struct userdata_type *) userdata;
  rpc_ scale = myuserdata->scale;
  for( ipc_ i = 0; i < n; i++) p[i] = scale * v[i];
  return 0;
}