GALAHAD LMS package

purpose

Given a sequence of vectors \(\{s_k\}\) and \(\{y_k\}\) and scale factors \(\{\delta_k\}\), the lms package obtains the product of a limited-memory secant approximation \(H_k\) (or its inverse) with a given vector, using one of a variety of well-established formulae.

Currently only the options and inform dictionaries are exposed; these are provided and used by other GALAHAD packages with Python interfaces. Please contact us if you would like full functionality!

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

method

Given a sequence of vectors \(\{s_k\}\) and \(\{y_k\}\) and scale factors \(\delta_k\), a limited-memory secant approximation \(H_k\) is chosen so that \(H_{\max(k-m,0)} = \delta_k I\), \(H_{k-j} s_{k-j} = y_{k-j}\) and \(\| H_{k-j+1} - H_{k-j}\|\) is ``small’’ for \(j = \min(k-1,m-1), \ldots, 0\). Different ways of quantifying ``small’’ distinguish different methods, but the crucial observation is that it is possible to construct \(H_k\) quickly from \(\{s_k\}\), \(\{y_k\}\) and \(\delta_k\), and to apply it and its inverse to a given vector \(v\). It is also possible to apply similar formulae to the ``shifted’’ matrix \(H_k + \lambda_k I\) that occurs in trust-region methods.

reference

The basic methods are those given by

R. H. Byrd, J. Nocedal and R. B. Schnabel, ``Representations of quasi-Newton matrices and their use in limited memory methods’’. Mathematical Programming **63(2)* (1994) 129–156,

with obvious extensions.

callable functions

overview of functions provided

// namespaces

namespace conf;

// typedefs

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

// structs

struct lms_control_type;
struct lms_inform_type;
struct lms_time_type;

// global functions

void lms_initialize(void **data, struct lms_control_type* control, ipc_ *status);
void lms_information(void **data, struct lms_inform_type* inform, ipc_ *status);

void lms_terminate(
    void **data,
    struct lms_control_type* control,
    struct lms_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 and structure names

The function and structure names described below are appropriate for the default real working precision (double) and integer word length (int32_t). To use the functions and structures with different precisions and integer word lengths, an additional suffix must be added to their names (and the arguments set accordingly). The appropriate suffices are:

_s for single precision (float) reals and standard 32-bit (int32_t) integers;

_q for quadruple precision (__real128) reals (if supported) and standard 32-bit (int32_t) integers;

_64 for standard precision (double) reals and 64-bit (int64_t) integers;

_s_64 for single precision (float) reals and 64-bit (int64_t) integers; and

_q_64 for quadruple precision (__real128) reals (if supported) and 64-bit (int64_t) integers.

Thus a call to lms_initialize below will instead be

void lms_initialize_s_64(void **data, struct lms_control_type_s_64* control,
                         int64_t *status)

if single precision (float) reals and 64-bit (int64_t) integers are required. Thus it is possible to call functions for this package with more that one precision and/or integer word length at same time. An example is provided for the package expo, and the obvious modifications apply equally here.

function calls

void lms_initialize(void **data, struct lms_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 lms_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 lms_information(void **data, struct lms_inform_type* inform, ipc_ *status)

Provides output information

Parameters:

data	holds private internal data
inform	is a struct containing output information (see lms_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 lms_terminate(
    void **data,
    struct lms_control_type* control,
    struct lms_inform_type* inform
)

Deallocate all internal private storage

Parameters:

data	holds private internal data
control	is a struct containing control information (see lms_control_type)
inform	is a struct containing output information (see lms_inform_type)

available structures

lms_control_type structure

#include <galahad_lms.h>

struct lms_control_type {
    // fields

    bool f_indexing;
    ipc_ error;
    ipc_ out;
    ipc_ print_level;
    ipc_ memory_length;
    ipc_ method;
    bool any_method;
    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

unit for error messages

ipc_ out

unit for monitor output

ipc_ print_level

controls level of diagnostic output

ipc_ memory_length

limited memory length

ipc_ method

limited-memory formula required (others may be added in due course):

• 1 BFGS (default).

• 2 Symmetric Rank-One (SR1).

• 3 The inverse of the BFGS formula.

• 4 The inverse of the shifted BFGS formula. This should be used instead of .method = 3 whenever a shift is planned.

bool any_method

allow space to permit different methods if required (less efficient)

bool space_critical

if space is critical, ensure allocated arrays are no bigger than needed

bool deallocate_error_fatal

exit if any deallocation fails

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’

lms_time_type structure

#include <galahad_lms.h>

struct lms_time_type {
    // fields

    rpc_ total;
    rpc_ setup;
    rpc_ form;
    rpc_ apply;
    rpc_ clock_total;
    rpc_ clock_setup;
    rpc_ clock_form;
    rpc_ clock_apply;
};

detailed documentation

time derived type as a C struct

components

rpc_ total

total cpu time spent in the package

rpc_ setup

cpu time spent setting up space for the secant approximation

rpc_ form

cpu time spent updating the secant approximation

rpc_ apply

cpu time spent applying the secant approximation

rpc_ clock_total

total clock time spent in the package

rpc_ clock_setup

clock time spent setting up space for the secant approximation

rpc_ clock_form

clock time spent updating the secant approximation

rpc_ clock_apply

clock time spent applying the secant approximation

lms_inform_type structure

#include <galahad_lms.h>

struct lms_inform_type {
    // fields

    ipc_ status;
    ipc_ alloc_status;
    ipc_ length;
    bool updates_skipped;
    char bad_alloc[81];
    struct lms_time_type time;
};

detailed documentation

inform derived type as a C struct

components

ipc_ status

the return status. Possible values are:

• 0

  the update 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

  One of the restrictions n > 0, delta > 0, lambda > 0 or s^T y > 0 has been violated and the update has been skipped.

• -10

  The matrix cannot be built from the current vectors {s_k} and {y_k} and values delta_k and lambda_k and the update has been skipped.

• -31

  A call to the function lhs_apply has been made without a prior call to lhs_form_shift or lhs_form with lambda specified when control.method = 4, or lhs_form_shift has been called when control.method = 3, or lhs_change_method has been called after control.any_method = false was specified when calling lhs_setup.

ipc_ alloc_status

the status of the last attempted allocation/deallocation

ipc_ length

the number of pairs (s,y) currently used to represent the limited-memory matrix.

bool updates_skipped

have (s,y) pairs been skipped when forming the limited-memory matrix?

char bad_alloc[81]

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

struct lms_time_type time

timings (see above)

Index