NAG Library Function Document

nag_real_cholesky_skyline (f01mcc)

is represented by the elements lying within the envelope of its lower triangular part, that is, between the first nonzero of each row and the diagonal (see Section 10 for an example). The width

row [i]

of the

i

th row is the number of elements between the first nonzero element and the element on the diagonal, inclusive. Although, of course, any matrix possesses an envelope as defined, this function is primarily intended for the factorization of symmetric positive definite matrices with an average bandwidth which is small compared with

n

(also see Section 9).

The method is based on the property that during Cholesky factorization there is no fill-in outside the envelope.

The determination of

L

and

D

is normally the first of two steps in the solution of the system of equations

A x = b

. The remaining step, viz. the solution of

{L D L}^{T} x = b

may be carried out using nag_real_cholesky_skyline_solve (f04mcc).

4 References

Jennings A (1966) A compact storage scheme for the solution of symmetric linear simultaneous equations Comput. J. 9 281–285

Wilkinson J H and Reinsch C (1971) Handbook for Automatic Computation II, Linear Algebra Springer–Verlag

5 Arguments

1: n – IntegerInput

On entry:

n

, the order of the matrix

A

Constraint:

n \geq 1

2: a[lal] – const doubleInput

On entry: the elements within the envelope of the lower triangle of the positive definite symmetric matrix

A

, taken in row by row order. The following code assigns the matrix elements within the envelope to the correct elements of the array

 k=0;
 for(i=0; i<n; ++i)
   for(j=i-row[i]+1; j<=i; ++j)
    a[k++]=matrix[i][j];

6 Error Indicators and Warnings

NE_2_INT_ARG_GT: On entry, $row [⟨value⟩] = ⟨value⟩$ while $i = ⟨value⟩$ . These arguments must satisfy $row [i] \leq i + 1$ .
NE_2_INT_ARG_LT: On entry, $lal = ⟨value⟩$ while $row [0] + \dots + row [n - 1] = ⟨value⟩$ . These arguments must satisfy $lal \geq row [0] + \dots + row [n - 1]$ .
NE_INT_ARG_LT: On entry, $n = ⟨value⟩$ .
Constraint: $n \geq 1$ .
On entry, $row [⟨value⟩]$ must not be less than 1: $row [⟨value⟩] = ⟨value⟩$ .
NE_NOT_POS_DEF: The matrix is not positive definite, possibly due to rounding errors.
NE_NOT_POS_DEF_FACT: The matrix is not positive definite, possibly due to rounding errors. The factorization has been completed but may be very inaccurate.

7 Accuracy

On successful exit then the computed

L

and

D

satisfy the relation

{L D L}^{T} = A + F

, where

{‖F‖}_{2} \leq k m^{2} ε \max_{i} a_{i i}

and

{‖F‖}_{2} \leq k m^{2} ε {‖A‖}_{2},

where

k

is a constant of order unity,

m

is the largest value of

row [i]

, and

ε

is the machine precision. See pages 25–27 and 54–55 or Wilkinson and Reinsch (1971). If the error NE_NOT_POS_DEF_FACT is reported then the factorization has been completed although the matrix was not positive definite. However the factorization may be very inaccurate and should be used only with great caution. For instance, if it is used to solve a set of equations

A x = b

using nag_real_cholesky_skyline_solve (f04mcc), the residual vector

b - A x

should be checked.

8 Parallelism and Performance

Not applicable.

9 Further Comments

The time taken by nag_real_cholesky_skyline (f01mcc) is approximately proportional to the sum of squares of the values of

row [i]

The distribution of row widths may be very non-uniform without undue loss of efficiency. Moreover, the function has been designed to be as competitive as possible in speed with functions designed for full or uniformly banded matrices, when applied to such matrices.

The function may be called with the same actual array supplied for arguments a and al, in which case

L

overwrites the lower triangle of

A

10 Example

To obtain the Cholesky factorization of the symmetric matrix, whose lower triangle is

.

For this matrix, the elements of row must be set to 1, 2, 2, 1, 5, 3, and the elements within the envelope must be supplied in row order as

1, 2, 5, 3, 13, 16, 5, 14, 18, 8, 55, 24, 17, 77 .

NAG Library Function Documentnag_real_cholesky_skyline (f01mcc)

+− Contents

1 Purpose

2 Specification

3 Description