f07 Chapter Contents
f07 Chapter Introduction
NAG C Library Manual

NAG Library Function Documentnag_dsytrf (f07mdc)

1  Purpose

nag_dsytrf (f07mdc) computes the Bunch–Kaufman factorization of a real symmetric indefinite matrix.

2  Specification

 #include #include
 void nag_dsytrf (Nag_OrderType order, Nag_UploType uplo, Integer n, double a[], Integer pda, Integer ipiv[], NagError *fail)

3  Description

nag_dsytrf (f07mdc) factorizes a real symmetric matrix $A$, using the Bunch–Kaufman diagonal pivoting method. $A$ is factorized as either $A=PUD{U}^{\mathrm{T}}{P}^{\mathrm{T}}$ if ${\mathbf{uplo}}=\mathrm{Nag_Upper}$ or $A=PLD{L}^{\mathrm{T}}{P}^{\mathrm{T}}$ if ${\mathbf{uplo}}=\mathrm{Nag_Lower}$, where $P$ is a permutation matrix, $U$ (or $L$) is a unit upper (or lower) triangular matrix and $D$ is a symmetric block diagonal matrix with $1$ by $1$ and $2$ by $2$ diagonal blocks; $U$ (or $L$) has $2$ by $2$ unit diagonal blocks corresponding to the $2$ by $2$ blocks of $D$. Row and column interchanges are performed to ensure numerical stability while preserving symmetry.
This method is suitable for symmetric matrices which are not known to be positive definite. If $A$ is in fact positive definite, no interchanges are performed and no $2$ by $2$ blocks occur in $D$.

4  References

Golub G H and Van Loan C F (1996) Matrix Computations (3rd Edition) Johns Hopkins University Press, Baltimore

5  Arguments

1:     orderNag_OrderTypeInput
On entry: the order argument specifies the two-dimensional storage scheme being used, i.e., row-major ordering or column-major ordering. C language defined storage is specified by ${\mathbf{order}}=\mathrm{Nag_RowMajor}$. See Section 3.2.1.3 in the Essential Introduction for a more detailed explanation of the use of this argument.
Constraint: ${\mathbf{order}}=\mathrm{Nag_RowMajor}$ or Nag_ColMajor.
2:     uploNag_UploTypeInput
On entry: specifies whether the upper or lower triangular part of $A$ is stored and how $A$ is to be factorized.
${\mathbf{uplo}}=\mathrm{Nag_Upper}$
The upper triangular part of $A$ is stored and $A$ is factorized as $PUD{U}^{\mathrm{T}}{P}^{\mathrm{T}}$, where $U$ is upper triangular.
${\mathbf{uplo}}=\mathrm{Nag_Lower}$
The lower triangular part of $A$ is stored and $A$ is factorized as $PLD{L}^{\mathrm{T}}{P}^{\mathrm{T}}$, where $L$ is lower triangular.
Constraint: ${\mathbf{uplo}}=\mathrm{Nag_Upper}$ or $\mathrm{Nag_Lower}$.
3:     nIntegerInput
On entry: $n$, the order of the matrix $A$.
Constraint: ${\mathbf{n}}\ge 0$.
4:     a[$\mathit{dim}$]doubleInput/Output
Note: the dimension, dim, of the array a must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{pda}}×{\mathbf{n}}\right)$.
On entry: the $n$ by $n$ symmetric indefinite matrix $A$.
If ${\mathbf{order}}=\mathrm{Nag_ColMajor}$, ${A}_{ij}$ is stored in ${\mathbf{a}}\left[\left(j-1\right)×{\mathbf{pda}}+i-1\right]$.
If ${\mathbf{order}}=\mathrm{Nag_RowMajor}$, ${A}_{ij}$ is stored in ${\mathbf{a}}\left[\left(i-1\right)×{\mathbf{pda}}+j-1\right]$.
If ${\mathbf{uplo}}=\mathrm{Nag_Upper}$, the upper triangular part of $A$ must be stored and the elements of the array below the diagonal are not referenced.
If ${\mathbf{uplo}}=\mathrm{Nag_Lower}$, the lower triangular part of $A$ must be stored and the elements of the array above the diagonal are not referenced.
On exit: the upper or lower triangle of $A$ is overwritten by details of the block diagonal matrix $D$ and the multipliers used to obtain the factor $U$ or $L$ as specified by uplo.
5:     pdaIntegerInput
On entry: the stride separating row or column elements (depending on the value of order) of the matrix $A$ in the array a.
Constraint: ${\mathbf{pda}}\ge \mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$.
6:     ipiv[$\mathit{dim}$]IntegerOutput
Note: the dimension, dim, of the array ipiv must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$.
On exit: details of the interchanges and the block structure of $D$. More precisely,
• if ${\mathbf{ipiv}}\left[i-1\right]=k>0$, ${d}_{ii}$ is a $1$ by $1$ pivot block and the $i$th row and column of $A$ were interchanged with the $k$th row and column;
• if ${\mathbf{uplo}}=\mathrm{Nag_Upper}$ and ${\mathbf{ipiv}}\left[i-2\right]={\mathbf{ipiv}}\left[i-1\right]=-l<0$, $\left(\begin{array}{cc}{d}_{i-1,i-1}& {\stackrel{-}{d}}_{i,i-1}\\ {\stackrel{-}{d}}_{i,i-1}& {d}_{ii}\end{array}\right)$ is a $2$ by $2$ pivot block and the $\left(i-1\right)$th row and column of $A$ were interchanged with the $l$th row and column;
• if ${\mathbf{uplo}}=\mathrm{Nag_Lower}$ and ${\mathbf{ipiv}}\left[i-1\right]={\mathbf{ipiv}}\left[i\right]=-m<0$, $\left(\begin{array}{cc}{d}_{ii}& {d}_{i+1,i}\\ {d}_{i+1,i}& {d}_{i+1,i+1}\end{array}\right)$ is a $2$ by $2$ pivot block and the $\left(i+1\right)$th row and column of $A$ were interchanged with the $m$th row and column.
7:     failNagError *Input/Output
The NAG error argument (see Section 3.6 in the Essential Introduction).

6  Error Indicators and Warnings

NE_ALLOC_FAIL
Dynamic memory allocation failed.
On entry, argument $〈\mathit{\text{value}}〉$ had an illegal value.
NE_INT
On entry, ${\mathbf{n}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{n}}\ge 0$.
On entry, ${\mathbf{pda}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{pda}}>0$.
NE_INT_2
On entry, ${\mathbf{pda}}=〈\mathit{\text{value}}〉$ and ${\mathbf{n}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{pda}}\ge \mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$.
NE_INTERNAL_ERROR
An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact NAG for assistance.
NE_SINGULAR
$D\left(〈\mathit{\text{value}}〉,〈\mathit{\text{value}}〉\right)$ is exactly zero. The factorization has been completed, but the block diagonal matrix $D$ is exactly singular, and division by zero will occur if it is used to solve a system of equations.

7  Accuracy

If ${\mathbf{uplo}}=\mathrm{Nag_Upper}$, the computed factors $U$ and $D$ are the exact factors of a perturbed matrix $A+E$, where
 $E≤cnεPUDUTPT ,$
$c\left(n\right)$ is a modest linear function of $n$, and $\epsilon$ is the machine precision.
If ${\mathbf{uplo}}=\mathrm{Nag_Lower}$, a similar statement holds for the computed factors $L$ and $D$.

The elements of $D$ overwrite the corresponding elements of $A$; if $D$ has $2$ by $2$ blocks, only the upper or lower triangle is stored, as specified by uplo.
The unit diagonal elements of $U$ or $L$ and the $2$ by $2$ unit diagonal blocks are not stored. The remaining elements of $U$ or $L$ are stored in the corresponding columns of the array a, but additional row interchanges must be applied to recover $U$ or $L$ explicitly (this is seldom necessary). If ${\mathbf{ipiv}}\left[\mathit{i}-1\right]=\mathit{i}$, for $\mathit{i}=1,2,\dots ,n$ (as is the case when $A$ is positive definite), then $U$ or $L$ is stored explicitly (except for its unit diagonal elements which are equal to $1$).
The total number of floating point operations is approximately $\frac{1}{3}{n}^{3}$.
A call to nag_dsytrf (f07mdc) may be followed by calls to the functions:
The complex analogues of this function are nag_zhetrf (f07mrc) for Hermitian matrices and nag_zsytrf (f07nrc) for symmetric matrices.

9  Example

This example computes the Bunch–Kaufman factorization of the matrix $A$, where
 $A= 2.07 3.87 4.20 -1.15 3.87 -0.21 1.87 0.63 4.20 1.87 1.15 2.06 -1.15 0.63 2.06 -1.81 .$

9.1  Program Text

Program Text (f07mdce.c)

9.2  Program Data

Program Data (f07mdce.d)

9.3  Program Results

Program Results (f07mdce.r)