# NAG FL Interfacef01mcf (real_​vband_​posdef_​fac)

## ▸▿ Contents

Settings help

FL Name Style:

FL Specification Language:

## 1Purpose

f01mcf computes the Cholesky factorization of a real symmetric positive definite variable-bandwidth matrix.

## 2Specification

Fortran Interface
 Subroutine f01mcf ( n, a, lal, nrow, al, d,
 Integer, Intent (In) :: n, lal Integer, Intent (Inout) :: nrow(n), ifail Real (Kind=nag_wp), Intent (In) :: a(lal) Real (Kind=nag_wp), Intent (Out) :: al(lal), d(n)
#include <nag.h>
 void f01mcf_ (const Integer *n, const double a[], const Integer *lal, Integer nrow[], double al[], double d[], Integer *ifail)
The routine may be called by the names f01mcf or nagf_matop_real_vband_posdef_fac.

## 3Description

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 variable-bandwidth matrix $A$ of order $n$. (Such a matrix is sometimes called a ‘sky-line’ 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. 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 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 $Ax=b$. The remaining step, viz. the solution of $LD{L}^{\mathrm{T}}x=b$, may be carried out using f04mcf.

## 4References

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

## 5Arguments

1: $\mathbf{n}$Integer Input
On entry: $n$, the order of the matrix $A$.
Constraint: ${\mathbf{n}}\ge 1$.
2: $\mathbf{a}\left({\mathbf{lal}}\right)$Real (Kind=nag_wp) array Input
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 matrix elements within the band can be assigned to the correct elements of the array using the following code:
```   k = 0
Do 20 i = 1, n
Do 10 j = i-nrow(i)+1, i
k = k + 1
a(k) = matrix (i,j)
10    Continue
20 Continue```
3: $\mathbf{lal}$Integer Input
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)+\cdots +{\mathbf{nrow}}\left(n\right)$.
4: $\mathbf{nrow}\left({\mathbf{n}}\right)$Integer array Input
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: $\mathbf{al}\left({\mathbf{lal}}\right)$Real (Kind=nag_wp) array Output
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: $\mathbf{d}\left({\mathbf{n}}\right)$Real (Kind=nag_wp) array Output
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: $\mathbf{ifail}$Integer Input/Output
On entry: ifail must be set to $0$, $-1$ or $1$ to set behaviour on detection of an error; these values have no effect when no error is detected.
A value of $0$ causes the printing of an error message and program execution will be halted; otherwise program execution continues. A value of $-1$ means that an error message is printed while a value of $1$ means that it is not.
If halting is not appropriate, the value $-1$ or $1$ is recommended. If message printing is undesirable, then the value $1$ is recommended. Otherwise, the value $0$ is recommended. When the value $-\mathbf{1}$ 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).

## 6Error Indicators and Warnings

If on entry ${\mathbf{ifail}}=0$ or $-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, $I=⟨\mathit{\text{value}}⟩$ and ${\mathbf{nrow}}\left(I\right)=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{nrow}}\left(I\right)\ge 1$ and ${\mathbf{nrow}}\left(I\right)\le I$.
On entry, ${\mathbf{lal}}=⟨\mathit{\text{value}}⟩$ and ${\mathbf{nrow}}\left(1\right)+\cdots +{\mathbf{nrow}}\left({\mathbf{n}}\right)=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{lal}}\ge {\mathbf{nrow}}\left(1\right)+\cdots +{\mathbf{nrow}}\left({\mathbf{n}}\right)$.
On entry, ${\mathbf{n}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{n}}\ge 1$.
${\mathbf{ifail}}=2$
$A$ is not positive definite. Factorization abandoned.
${\mathbf{ifail}}=3$
$A$ is not positive definite. Factorization completed.
${\mathbf{ifail}}=-99$
See Section 7 in the Introduction to the NAG Library FL Interface for further information.
${\mathbf{ifail}}=-399$
Your licence key may have expired or may not have been installed correctly.
See Section 8 in the Introduction to the NAG Library FL Interface for further information.
${\mathbf{ifail}}=-999$
Dynamic memory allocation failed.
See Section 9 in the Introduction to the NAG Library FL Interface for further information.

## 7Accuracy

If ${\mathbf{ifail}}={\mathbf{0}}$ on exit, then the computed $L$ and $D$ satisfy the relation $LD{L}^{\mathrm{T}}=A+F$, where
 $‖F‖2 ≤ km2 ε × maxi aii$
and
 $‖F‖2 ≤ km2 ε × ‖A‖2 ,$
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).

## 8Parallelism and Performance

f01mcf is not threaded in any implementation.

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 non-uniform 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 arguments 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.

## 10Example

This example obtains the Cholesky factorization of the symmetric matrix, whose lower triangle is:
 $( 1 2 5 0 3 13 0 0 0 16 5 14 18 8 55 0 0 0 24 17 77 ) .$
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:
 $1, 2, 5, 3, 13, 16, 5, 14, 18, 8, 55, 24, 17, 77 .$

### 10.1Program Text

Program Text (f01mcfe.f90)

### 10.2Program Data

Program Data (f01mcfe.d)

### 10.3Program Results

Program Results (f01mcfe.r)