naginterfaces.library.matop.real_​modified_​cholesky

naginterfaces.library.matop.real_modified_cholesky(uplo, a, delta)

real_modified_cholesky computes the Cheng–Higham modified Cholesky factorization of a real symmetric matrix.

For full information please refer to the NAG Library document for f01md

https://support.nag.com/numeric/nl/nagdoc_30/flhtml/f01/f01mdf.html

Parameters

uplostr, length 1

Specifies whether the upper or lower triangular part of $A$ is stored and how $A$ is to be factorized.

$uplo=\text{'U'}$

The upper triangular part of $A$ is stored and we compute $P^T(A+E)P=UD{U}^T$.

$uplo=\text{'L'}$

The lower triangular part of $A$ is stored and we compute $P^T(A+E)P=LD{L}^T$.

afloat, array-like, shape $(n,n)$

The $n\times n$ symmetric matrix $A$.

deltafloat

The value of $\delta$.

Returns

afloat, ndarray, shape $(n,n)$

$a$ is overwritten.

See Further Comments for further details.

offdiagfloat, ndarray, shape $\left(n\right)$

The offdiagonals of the symmetric matrix $D$ are returned in $offdiag\left[0\right],offdiag\left[1\right],\dots ,offdiag[n-2]$, for $uplo=\text{'L'}$ and in $offdiag\left[1\right],offdiag\left[2\right],\dots ,offdiag[n-1]$, for $uplo=\text{'U'}$. See Further Comments for further details.

ipivint, ndarray, shape $\left(n\right)$

Gives the permutation information of the factorization. The entries of $ipiv$ are either positive, indicating a $1\times 1$ pivot block, or pairs of negative entries, indicating a $2\times 2$ pivot block.

$ipiv[i-1]=k>0$

The $i$th and $k$th rows and columns of $A$ were interchanged and $d_{ii}$ is a $1\times 1$ block.

$ipiv[i-1]=-k<0$ and $ipiv[i+1-1]=-\ell <0$

The $i$th and $k$th rows and columns, and the $i+1$st and $\ell$th rows and columns, were interchanged and $D$ has the $2\times 2$ block:

$$\begin{array}{c}\left(\begin{array}{cc}{d}_{ii}& d_{i+1,i}\\ d_{i+1,i}& d_{i+1,i+1}\end{array}\right)\end{array}$$

If $uplo=\text{'U'}$, $d_{i+1,i}$ is stored in $offdiag\left[i\right]$. The interchanges were made in the order $i=n,n-1,\dots ,2$.

If $uplo=\text{'L'}$, $d_{i+1,i}$ is stored in $offdiag[i-1]$. The interchanges were made in the order $i=1,2,\dots ,n-1$.

Raises

NagValueError

(errno $1$)

On entry, $uplo=⟨value⟩$.

Constraint: $uplo=\text{'U'}$ or $\text{'L'}$.

(errno $2$)

On entry, $n=⟨value⟩$.

Constraint: $n>0$.

(errno $4$)

On entry, $delta=⟨value⟩$.

Constraint: $delta\ge 0.0$.

(errno $5$)

An intermediate eigenproblem could not be solved. This should not occur. Please contact NAG with details of your call.

Notes

Given a symmetric, possibly indefinite matrix $A$, real_modified_cholesky finds the Cheng–Higham modified Cholesky factorization

$$P^T(A+E)P=LD{L}^T\text{,}$$

when $uplo=\text{'L'}$. Here $L$ is a unit lower triangular matrix, $P$ is a permutation matrix, $D$ is a symmetric block diagonal matrix (with blocks of order $1$ or $2$) with minimum eigenvalue $\delta$, and $E$ is a perturbation matrix of small norm chosen so that such a factorization can be found. Note that $E$ is not computed explicitly.

If $uplo=\text{'U'}$, we compute the factorization $P^T(A+E)P=UD{U}^T$, where $U$ is a unit upper triangular matrix.

If the matrix $A$ is symmetric positive definite, the algorithm ensures that $E=0$. The function real_mod_chol_perturbed_a() can be used to compute the matrix $A+E$.

References

Ashcraft, C, Grimes, R G, and Lewis, J G, 1998, Accurate symmetric indefinite linear equation solvers, SIAM J. Matrix Anal. Appl. (20), 513–561

Cheng, S H and Higham, N J, 1998, A modified Cholesky algorithm based on a symmetric indefinite factorization, SIAM J. Matrix Anal. Appl. (19(4)), 1097–1110