FDC#

purpose#

Given an under-determined set of linear equations/constraints \(a_i^T x = b_i^{}\), \(i = 1, \ldots, m\) involving \(n \geq m\) unknowns \(x\), the fdc package determines whether the constraints are consistent, and if so how many of the constraints are dependent; a list of dependent constraints, that is, those which may be removed without changing the solution set, will be found and the remaining \(a_i\) will be linearly independent. Full advantage is taken of any zero coefficients in the matrix \(A\) whose columns are the vectors \(a_i^T\).

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

method#

A choice of two methods is available. In the first, the matrix

\[\begin{split}K = \begin{pmatrix}\alpha I & A^T \\ A & 0 \end{pmatrix}\end{split}\]
is formed and factorized for some small \(\alpha > 0\) using the SLS package — the factors \(K = P L D L^T P^T\) are used to determine whether \(A\) has dependent rows. In particular, in exact arithmetic dependencies in \(A\) will correspond to zero pivots in the block diagonal matrix \(D\).

The second choice of method finds factors \(A = P L U Q\) of the rectangular matrix \(A\) using the ULS package. In this case, dependencies in \(A\) will be reflected in zero diagonal entries in \(U\) in exact arithmetic.

The factorization in either case may also be used to determine whether the system is consistent.

matrix storage#

The unsymmetric \(m\) by \(n\) matrix \(A\) must be presented and stored in sparse row-wise storage format. For this, only the nonzero entries are stored, and 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.

functions#

fdc.initialize()#

Set default option values and initialize private data

Returns:

optionsdict
dictionary containing default control options:
errorint

error and warning diagnostics occur on stream error.

outint

general output occurs on stream out.

print_levelint

the level of output required is specified by print_level. Possible values are

  • <=0

    gives no output.

  • 1

    a summary of the progress made.

  • >=2

    an ever increasing amount of debugging information.

indminint

initial estimate of integer workspace for sls (obsolete).

valminint

initial estimate of real workspace for sls (obsolete).

pivot_tolfloat

the relative pivot tolerance (obsolete).

zero_pivotfloat

the absolute pivot tolerance used (obsolete).

max_infeasfloat

the largest permitted residual.

use_slsbool

choose whether sls or uls is used to determine dependencies.

scalebool

should the rows of A be scaled to have unit infinity norm or should no scaling be applied?

space_criticalbool

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

deallocate_error_fatalbool

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

symmetric_linear_solverstr

symmetric (indefinite) linear equation solver. For current choices, see sls.initialize.

unsymmetric_linear_solverstr

unsymmetric linear equation solver. For current choices, see uls.initialize.

prefixstr

all output lines will be prefixed by the string contained in quotes within prefix, e.g. ‘word’ (note the qutoes) will result in the prefix word.

sls_optionsdict

default control options for SLS (see sls.initialize).

uls_optionsdict

default control options for ULS (see uls.initialize).

fdc.find_dependent_rows(m, n, A_ptr, A_col, A_val, b, options=None)#

Find dependent rows of \(A\) and, if any, check if \(Ax = b\) is consistent.

Parameters:

mint

holds the number of constraints (rows of \(A\)).

nint

holds the number of variables (columns of \(A\)).

A_ptrndarray(m+1)

holds the starting position of each row of \(A\), as well as the total number of entries.

A_colndarray(A_ptr(m)-1)

holds the column indices of the nonzeros of \(A\) in the sparse co-ordinate storage scheme.

A_valndarray(A_ptr(m)-1)

holds the values of the nonzeros of \(A\) in the sparse co-ordinate storage scheme.

bndarray(m)

holds the values of the llinear term \(b\) in the constraints.

optionsdict, optional

dictionary of control options (see fdc.initialize).

Returns:

m_depenint

holds the number of dependent constraints, if any.

depenndarray(m)

the first m_depen components hold the indices of the dependent comstraints.

informdict
dictionary containing output information:
statusint

return status. Possible values are:

  • 0

    The run was successful.

  • -1

    An allocation error occurred. A message indicating the offending array is written on unit options[‘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 options[‘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 m > 0 or requirement that type contains its relevant string ‘dense’, ‘coordinate’, ‘sparse_by_rows’, ‘diagonal’, ‘scaled_identity’, ‘identity’, ‘zero’ or ‘none’ has been violated.

  • -5

    The constraints appear to be inconsistent.

  • -9

    The analysis phase of the factorization failed; the return status from the factorization package is given by inform[‘factor_status’].

  • -10

    The factorization failed; the return status from the factorization package is given by 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 by inform[‘factor_status’].

  • -12

    The analysis phase of an unsymmetric factorization failed; the return status from the factorization package is given by inform[‘factor_status’].

  • -13

    An unsymmetric factorization failed; the return status from the factorization package is given by inform[‘factor_status’].

  • -14

    The solution of a set of linear equations using factors from an unsymmetric factorization package failed; the return status from the factorization package is given by inform[‘factor_status’].

  • -16

    The resuduals are large, the factorization may be unsatisfactory.

alloc_statusint

the status of the last attempted allocation/deallocation.

bad_allocstr

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

factorization_statusint

the return status from the factorization.

factorization_integerlong

the total integer workspace required for the factorization.

factorization_reallong

the total real workspace required for the factorization.

non_negligible_pivotfloat

the smallest pivot which was not judged to be zero when detecting linear dependent constraints.

timedict
dictionary containing timing information:
totalfloat

the total CPU time spent in the package.

analysefloat

the CPU time spent analysing the required matrices prior to factorization.

factorizefloat

the CPU time spent factorizing the required matrices.

clock_totalfloat

the total clock time spent in the package.

clock_analysefloat

the clock time spent analysing the required matrices prior to factorization.

clock_factorizefloat

the clock time spent factorizing the required matrices.

sls_informdict

inform parameters for SLS (see sls.information).

uls_informdict

inform parameters for ULS (see uls.information).

fdc.terminate()#

Deallocate all internal private storage.

example code#

from galahad import fdc
import numpy as np

#  describe problem:
#  ( 1  2 3  4 )     (  5 )
#  ( 2 -4 6 -8 ) x = ( 10 )
#  (    5   10 )     (  0 )

m = 3
n = 4
A_ptr = np.array([0,4,8,10])
A_col = np.array([0,1,2,3,0,1,2,3,1,3])
A_val = np.array([1.0,2.0,3.0,4.0,2.0,-4.0,6.0,-8.0,5.0,10.0])
b = np.array([5.0,10.0,0.0])

# allocate internal data and set default options
options = fdc.initialize()

# set some non-default options
#options['print_level'] = 1
options['use_sls'] = True
options['symmetric_linear_solver'] = "sytr "
#print("options:", options)

# load data (and optionally non-default options), and find dependent rows
n_depen, depen, inform = fdc.find_dependent_rows(m, n, A_ptr, A_col, A_val,
                                                 b, options)
print("# dependent rows:", n_depen)
print("these are:", depen[0:n_depen])

# deallocate internal data

fdc.terminate()

This example code is available in $GALAHAD/src/fdc/Python/test_fdc.py .