NAG Library Routine Document
F01MCF
1 Purpose
F01MCF computes the Cholesky factorization of a real symmetric positive definite variablebandwidth matrix.
2 Specification
INTEGER 
N, LAL, NROW(N), IFAIL 
REAL (KIND=nag_wp) 
A(LAL), AL(LAL), D(N) 

3 Description
F01MCF determines the unit lower triangular matrix $L$ and the diagonal matrix $D$ in the Cholesky factorization $A=LD{L}^{\mathrm{T}}$ of a symmetric positive definite variablebandwidth matrix $A$ of order $n$. (Such a matrix is sometimes called a ‘skyline’ matrix.)
The matrix
$A$ 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
${\mathbf{NROW}}\left(i\right)$ 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 routine 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 fillin outside the envelope.
The determination of
$L$ and
$D$ is normally the first of two steps in the solution of the system of equations
$Ax=b$. The remaining step, viz. the solution of
$LD{L}^{\mathrm{T}}x=b$, may be carried out using
F04MCF.
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 Parameters
 1: $\mathrm{N}$ – INTEGERInput

On entry: $n$, the order of the matrix $A$.
Constraint:
${\mathbf{N}}\ge 1$.
 2: $\mathrm{A}\left({\mathbf{LAL}}\right)$ – REAL (KIND=nag_wp) arrayInput

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
DO 20 I = 1, N
DO 10 J = INROW(I)+1, I
K = K + 1
A(K) = matrix (I,J)
10 CONTINUE
20 CONTINUE
 3: $\mathrm{LAL}$ – INTEGERInput

On entry: the dimension of the arrays
A and
AL as declared in the (sub)program from which F01MCF is called.
Constraint:
${\mathbf{LAL}}\ge {\mathbf{NROW}}\left(1\right)+{\mathbf{NROW}}\left(2\right)+\dots +{\mathbf{NROW}}\left(n\right)$.
 4: $\mathrm{NROW}\left({\mathbf{N}}\right)$ – INTEGER arrayInput

On entry: ${\mathbf{NROW}}\left(i\right)$ must contain the width of row $i$ of the matrix $A$, i.e., the number of elements between the first (leftmost) nonzero element and the element on the diagonal, inclusive.
Constraint:
$1\le {\mathbf{NROW}}\left(\mathit{i}\right)\le \mathit{i}$, for $\mathit{i}=1,2,\dots ,n$.
 5: $\mathrm{AL}\left({\mathbf{LAL}}\right)$ – REAL (KIND=nag_wp) arrayOutput

On exit: the elements within the envelope of the lower triangular matrix
$L$, taken in row by row order. The envelope of
$L$ is identical to that of the lower triangle of
$A$. The unit diagonal elements of
$L$ are stored explicitly. See also
Section 9.
 6: $\mathrm{D}\left({\mathbf{N}}\right)$ – REAL (KIND=nag_wp) arrayOutput

On exit: the diagonal elements of the diagonal matrix $D$. Note that the determinant of $A$ is equal to the product of these diagonal elements. If the value of the determinant is required it should not be determined by forming the product explicitly, because of the possibility of overflow or underflow. The logarithm of the determinant may safely be formed from the sum of the logarithms of the diagonal elements.
 7: $\mathrm{IFAIL}$ – INTEGERInput/Output

On entry:
IFAIL must be set to
$0$,
$1\text{ or}1$. If you are unfamiliar with this parameter you should refer to
Section 3.3 in the Essential Introduction for details.
For environments where it might be inappropriate to halt program execution when an error is detected, the value
$1\text{ or}1$ is recommended. If the output of error messages is undesirable, then the value
$1$ is recommended. Otherwise, if you are not familiar with this parameter, the recommended value is
$0$.
When the value $\mathbf{1}\text{ or}\mathbf{1}$ is used it is essential to test the value of IFAIL on exit.
On exit:
${\mathbf{IFAIL}}={\mathbf{0}}$ unless the routine detects an error or a warning has been flagged (see
Section 6).
6 Error Indicators and Warnings
If on entry
${\mathbf{IFAIL}}={\mathbf{0}}$ or
${{\mathbf{1}}}$, explanatory error messages are output on the current error message unit (as defined by
X04AAF).
Errors or warnings detected by the routine:
 ${\mathbf{IFAIL}}=1$

On entry,  ${\mathbf{N}}<1$, 
or  for some $i$, ${\mathbf{NROW}}\left(i\right)<1$ or ${\mathbf{NROW}}\left(i\right)>i$, 
or  ${\mathbf{LAL}}<{\mathbf{NROW}}\left(1\right)+{\mathbf{NROW}}\left(2\right)+\dots +{\mathbf{NROW}}\left({\mathbf{N}}\right)$. 
 ${\mathbf{IFAIL}}=2$

$A$ is not positive definite, or this property has been destroyed by rounding errors. The factorization has not been completed.
 ${\mathbf{IFAIL}}=3$

$A$ is not positive definite, or this property has been destroyed by rounding errors. The factorization has not been completed.
 ${\mathbf{IFAIL}}=99$
An unexpected error has been triggered by this routine. Please
contact
NAG.
See
Section 3.8 in the Essential Introduction for further information.
 ${\mathbf{IFAIL}}=399$
Your licence key may have expired or may not have been installed correctly.
See
Section 3.7 in the Essential Introduction for further information.
 ${\mathbf{IFAIL}}=999$
Dynamic memory allocation failed.
See
Section 3.6 in the Essential Introduction for further information.
7 Accuracy
If
${\mathbf{IFAIL}}={\mathbf{0}}$ on exit, then the
computed
$L$ and
$D$ satisfy the relation
$LD{L}^{\mathrm{T}}=A+F$, where
and
where
$k$ is a constant of order unity,
$m$ is the largest value of
${\mathbf{NROW}}\left(i\right)$, and
$\epsilon $ is the
machine precision. See pages 25–27 and 54–55 of
Wilkinson and Reinsch (1971).
8 Parallelism and Performance
Not applicable.
The time taken by F01MCF is approximately proportional to the sum of squares of the values of ${\mathbf{NROW}}\left(i\right)$.
The distribution of row widths may be very nonuniform without undue loss of efficiency. Moreover, the routine has been designed to be as competitive as possible in speed with routines designed for full or uniformly banded matrices, when applied to such matrices.
Unless otherwise stated in the
Users' Note for your implementation, the routine may be called with the same actual array supplied for parameters
A and
AL, in which case
$L$ overwrites the lower triangle of
A. However this is not standard Fortran and may not work in all implementations.
10 Example
This example obtains the Cholesky factorization of the symmetric matrix, whose lower triangle is:
For this matrix, the elements of
NROW must be set to
$1$,
$2$,
$2$,
$1$,
$5$,
$3$, and the elements within the envelope must be supplied in row order as:
10.1 Program Text
Program Text (f01mcfe.f90)
10.2 Program Data
Program Data (f01mcfe.d)
10.3 Program Results
Program Results (f01mcfe.r)