The IMSL_CHNNDFAC function solves a real symmetric non-negative definite system of linear equations Ax = b. Computes the solution to Ax = b given the Cholesky factor.

This routine requires an IDL Advanced Math and Stats license. For more information, contact your sales or technical support representative.

The factorization algorithm is based on the work of Healy (1968) and proceeds sequentially by columns. The i-th column is declared to be linearly dependent on the first i – 1 columns if:

where ε (specified in TOLERANCE) may be set. When a linear dependence is declared, all elements in the i-th row of R (column of L) are set to zero.

Modifications due to Farebrother and Berry (1974) and Barrett and Healy (1978) for checking for matrices that are not non-negative definite also are incorporated. The IMSL_CHNNDFAC procedure declares A to not be non-negative definite and issues an error message if either of the following conditions is satisfied:

 

Healy’s (1968) algorithm and the IMSL_CHNNDFAC procedure permit the matrices A and R to occupy the same storage. Barrett and Healy (1978) in their remark neglect this fact. The IMSL_CHNNDFAC procedure uses:

in condition 2 above to remedy this problem.

If an inverse of the matrix A is required and the matrix is not (numerically) positive definite, then the resulting inverse is a symmetric g2 inverse of A. For a matrix G to be a g2 inverse of a matrix A, G must satisfy conditions 1 and 2 for the Moore- Penrose inverse but generally fail conditions 3 and 4. The four conditions for G to be a Moore-Penrose inverse of A are as follows:

  1. AGA = A
  2. GAG = G
  3. AG is symmetric
  4. GA is symmetric

Example

The symmetric nonnegative definite matrix in the initial example of IMSL_CHNNDSOL is used to compute the factorization only in the first call to IMSL_CHNNDFAC. Then, IMSL_CHNNDSOL is called with both the LLT factorization and the right-hand side vector as the input to compute a solution x.

RM, a, 4, 4
; Define the coefficient matrix.
row 0: 36 12 30 6
row 1: 12 20 2 10
row 2: 30 2 29 1
row 3: 6 10 1 14
IMSL_CHNNDFAC, a, fac
PM, fac, Title = 'Factor', Format = '(4f12.3)'

IDL prints:

Factor
  6.000 2.000 5.000 1.000
  2.000 4.000 -2.000 2.000
  5.000 -2.000 0.000 0.000
  1.000 2.000 0.000 3.000
RM, b, 4, 1
; Define the right-hand side.
row 0: 18
row 1: 22
row 2: 7
row 3: 20
; Compute the solution and output.
x = IMSL_CHNNDSOL(b, Factor = fac)
PM, x, Title = 'Solution'

IDL prints:

Solution
  0.166667
  0.500000
  0.00000
  1.00000

Syntax

IMSL_CHNNDFAC, A, Fac [, /DOUBLE] [, INVERSE=variable] [, TOLERANCE=value]

Arguments

A

Two-dimensional matrix containing the coefficient matrix. Element A(i, j) contains the j-th coefficient of the i-th equation.

Fac

Matrix containing the LLT factorization of A.

Keywords

DOUBLE (optional)

If present and nonzero, double precision is used.

INVERSE (optional)

Named variable into which the inverse of the matrix A is stored.

TOLERANCE (optional)

Tolerance used in determining linear dependence. Default: 100ε, where ε is machine precision.

Errors

Warning Errors

MATH_INCONSISTENT_EQUATIONS_2: Linear system of equations is inconsistent.

MATH_NOT_NONNEG_DEFINITE: Matrix A is not non-negative definite.

Version History

6.4

Introduced

See Also

IMSL_CHNNDSOL, IMSL_LINLSQ, IMSL_QRFAC, IMSL_SVDCOMP