Integer type:  int32  int64  nag_int  show int32  show int32  show int64  show int64  show nag_int  show nag_int

Chapter Contents
Chapter Introduction
NAG Toolbox

# NAG Toolbox: nag_lapack_dspsvx (f07pb)

## Purpose

nag_lapack_dspsvx (f07pb) uses the diagonal pivoting factorization
 $A=UDUT or A=LDLT$
to compute the solution to a real system of linear equations
 $AX=B ,$
where $A$ is an $n$ by $n$ symmetric matrix stored in packed format and $X$ and $B$ are $n$ by $r$ matrices. Error bounds on the solution and a condition estimate are also provided.

## Syntax

[afp, ipiv, x, rcond, ferr, berr, info] = f07pb(fact, uplo, ap, afp, ipiv, b, 'n', n, 'nrhs_p', nrhs_p)
[afp, ipiv, x, rcond, ferr, berr, info] = nag_lapack_dspsvx(fact, uplo, ap, afp, ipiv, b, 'n', n, 'nrhs_p', nrhs_p)

## Description

nag_lapack_dspsvx (f07pb) performs the following steps:
 1 If ${\mathbf{fact}}=\text{'N'}$, the diagonal pivoting method is used to factor $A$ as $A=UD{U}^{\mathrm{T}}$ if ${\mathbf{uplo}}=\text{'U'}$ or $A=LD{L}^{\mathrm{T}}$ if ${\mathbf{uplo}}=\text{'L'}$, where $U$ (or $L$) is a product of permutation and unit upper (lower) triangular matrices and $D$ is symmetric and block diagonal with $1$ by $1$ and $2$ by $2$ diagonal blocks. 2 If some ${d}_{ii}=0$, so that $D$ is exactly singular, then the function returns with ${\mathbf{info}}=i$. Otherwise, the factored form of $A$ is used to estimate the condition number of the matrix $A$. If the reciprocal of the condition number is less than machine precision, ${\mathbf{info}}\ge {\mathbf{n}}+1$ is returned as a warning, but the function still goes on to solve for $X$ and compute error bounds as described below. 3 The system of equations is solved for $X$ using the factored form of $A$. 4 Iterative refinement is applied to improve the computed solution matrix and to calculate error bounds and backward error estimates for it.

## References

Anderson E, Bai Z, Bischof C, Blackford S, Demmel J, Dongarra J J, Du Croz J J, Greenbaum A, Hammarling S, McKenney A and Sorensen D (1999) LAPACK Users' Guide (3rd Edition) SIAM, Philadelphia http://www.netlib.org/lapack/lug
Golub G H and Van Loan C F (1996) Matrix Computations (3rd Edition) Johns Hopkins University Press, Baltimore
Higham N J (2002) Accuracy and Stability of Numerical Algorithms (2nd Edition) SIAM, Philadelphia

## Parameters

### Compulsory Input Parameters

1:     $\mathrm{fact}$ – string (length ≥ 1)
Specifies whether or not the factorized form of the matrix $A$ has been supplied.
${\mathbf{fact}}=\text{'F'}$
afp and ipiv contain the factorized form of the matrix $A$. afp and ipiv will not be modified.
${\mathbf{fact}}=\text{'N'}$
The matrix $A$ will be copied to afp and factorized.
Constraint: ${\mathbf{fact}}=\text{'F'}$ or $\text{'N'}$.
2:     $\mathrm{uplo}$ – string (length ≥ 1)
If ${\mathbf{uplo}}=\text{'U'}$, the upper triangle of $A$ is stored.
If ${\mathbf{uplo}}=\text{'L'}$, the lower triangle of $A$ is stored.
Constraint: ${\mathbf{uplo}}=\text{'U'}$ or $\text{'L'}$.
3:     $\mathrm{ap}\left(:\right)$ – double array
The dimension of the array ap must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}×\left({\mathbf{n}}+1\right)/2\right)$
The $n$ by $n$ symmetric matrix $A$, packed by columns.
More precisely,
• if ${\mathbf{uplo}}=\text{'U'}$, the upper triangle of $A$ must be stored with element ${A}_{ij}$ in ${\mathbf{ap}}\left(i+j\left(j-1\right)/2\right)$ for $i\le j$;
• if ${\mathbf{uplo}}=\text{'L'}$, the lower triangle of $A$ must be stored with element ${A}_{ij}$ in ${\mathbf{ap}}\left(i+\left(2n-j\right)\left(j-1\right)/2\right)$ for $i\ge j$.
4:     $\mathrm{afp}\left(:\right)$ – double array
The dimension of the array afp must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}×\left({\mathbf{n}}+1\right)/2\right)$
If ${\mathbf{fact}}=\text{'F'}$, afp contains the block diagonal matrix $D$ and the multipliers used to obtain the factor $U$ or $L$ from the factorization $A=UD{U}^{\mathrm{T}}$ or $A=LD{L}^{\mathrm{T}}$ as computed by nag_lapack_dsptrf (f07pd), stored as a packed triangular matrix in the same storage format as $A$.
5:     $\mathrm{ipiv}\left({\mathbf{n}}\right)$int64int32nag_int array
If ${\mathbf{fact}}=\text{'F'}$, ipiv contains details of the interchanges and the block structure of $D$, as determined by nag_lapack_dsptrf (f07pd).
• if ${\mathbf{ipiv}}\left(i\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}}=\text{'U'}$ and ${\mathbf{ipiv}}\left(i-1\right)={\mathbf{ipiv}}\left(i\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}}=\text{'L'}$ and ${\mathbf{ipiv}}\left(i\right)={\mathbf{ipiv}}\left(i+1\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.
6:     $\mathrm{b}\left(\mathit{ldb},:\right)$ – double array
The first dimension of the array b must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$.
The second dimension of the array b must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{nrhs_p}}\right)$.
The $n$ by $r$ right-hand side matrix $B$.

### Optional Input Parameters

1:     $\mathrm{n}$int64int32nag_int scalar
Default: the dimension of the array ipiv.
$n$, the number of linear equations, i.e., the order of the matrix $A$.
Constraint: ${\mathbf{n}}\ge 0$.
2:     $\mathrm{nrhs_p}$int64int32nag_int scalar
Default: the second dimension of the array b.
$r$, the number of right-hand sides, i.e., the number of columns of the matrix $B$.
Constraint: ${\mathbf{nrhs_p}}\ge 0$.

### Output Parameters

1:     $\mathrm{afp}\left(:\right)$ – double array
The dimension of the array afp will be $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}×\left({\mathbf{n}}+1\right)/2\right)$
If ${\mathbf{fact}}=\text{'N'}$, afp contains the block diagonal matrix $D$ and the multipliers used to obtain the factor $U$ or $L$ from the factorization $A=UD{U}^{\mathrm{T}}$ or $A=LD{L}^{\mathrm{T}}$ as computed by nag_lapack_dsptrf (f07pd), stored as a packed triangular matrix in the same storage format as $A$.
2:     $\mathrm{ipiv}\left({\mathbf{n}}\right)$int64int32nag_int array
If ${\mathbf{fact}}=\text{'N'}$, ipiv contains details of the interchanges and the block structure of $D$, as determined by nag_lapack_dsptrf (f07pd), as described above.
3:     $\mathrm{x}\left(\mathit{ldx},:\right)$ – double array
The first dimension of the array x will be $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$.
The second dimension of the array x will be $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{nrhs_p}}\right)$.
If ${\mathbf{info}}={\mathbf{0}}$ or $\mathbf{n}+{\mathbf{1}}$, the $n$ by $r$ solution matrix $X$.
4:     $\mathrm{rcond}$ – double scalar
The estimate of the reciprocal condition number of the matrix $A$. If ${\mathbf{rcond}}=0.0$, the matrix may be exactly singular. This condition is indicated by ${\mathbf{info}}>{\mathbf{0}} \text{and} {\mathbf{info}}\le \mathbf{n}$. Otherwise, if rcond is less than the machine precision, the matrix is singular to working precision. This condition is indicated by ${\mathbf{info}}\ge {\mathbf{n}}+1$.
5:     $\mathrm{ferr}\left({\mathbf{nrhs_p}}\right)$ – double array
If ${\mathbf{info}}={\mathbf{0}}$ or $\mathbf{n}+{\mathbf{1}}$, an estimate of the forward error bound for each computed solution vector, such that ${‖{\stackrel{^}{x}}_{j}-{x}_{j}‖}_{\infty }/{‖{x}_{j}‖}_{\infty }\le {\mathbf{ferr}}\left(j\right)$ where ${\stackrel{^}{x}}_{j}$ is the $j$th column of the computed solution returned in the array x and ${x}_{j}$ is the corresponding column of the exact solution $X$. The estimate is as reliable as the estimate for rcond, and is almost always a slight overestimate of the true error.
6:     $\mathrm{berr}\left({\mathbf{nrhs_p}}\right)$ – double array
If ${\mathbf{info}}={\mathbf{0}}$ or $\mathbf{n}+{\mathbf{1}}$, an estimate of the component-wise relative backward error of each computed solution vector ${\stackrel{^}{x}}_{j}$ (i.e., the smallest relative change in any element of $A$ or $B$ that makes ${\stackrel{^}{x}}_{j}$ an exact solution).
7:     $\mathrm{info}$int64int32nag_int scalar
${\mathbf{info}}=0$ unless the function detects an error (see Error Indicators and Warnings).

## Error Indicators and Warnings

Cases prefixed with W are classified as warnings and do not generate an error of type NAG:error_n. See nag_issue_warnings.

${\mathbf{info}}<0$
If ${\mathbf{info}}=-i$, argument $i$ had an illegal value. An explanatory message is output, and execution of the program is terminated.
W  ${\mathbf{info}}>0 \text{and} {\mathbf{info}}\le {\mathbf{n}}$
Element $_$ of the diagonal is exactly zero. The factorization has been completed, but the factor $D$ is exactly singular, so the solution and error bounds could not be computed. ${\mathbf{rcond}}=0.0$ is returned.
W  ${\mathbf{info}}={\mathbf{n}}+1$
$D$ is nonsingular, but rcond is less than machine precision, meaning that the matrix is singular to working precision. Nevertheless, the solution and error bounds are computed because there are a number of situations where the computed solution can be more accurate than the value of rcond would suggest.

## Accuracy

For each right-hand side vector $b$, the computed solution $\stackrel{^}{x}$ is the exact solution of a perturbed system of equations $\left(A+E\right)\stackrel{^}{x}=b$, where
 $E1 = Oε A1 ,$
where $\epsilon$ is the machine precision. See Chapter 11 of Higham (2002) for further details.
If $\stackrel{^}{x}$ is the true solution, then the computed solution $x$ satisfies a forward error bound of the form
 $x-x^∞ x^∞ ≤ wc condA,x^,b$
where $\mathrm{cond}\left(A,\stackrel{^}{x},b\right)={‖\left|{A}^{-1}\right|\left(\left|A\right|\left|\stackrel{^}{x}\right|+\left|b\right|\right)‖}_{\infty }/{‖\stackrel{^}{x}‖}_{\infty }\le \mathrm{cond}\left(A\right)={‖\left|{A}^{-1}\right|\left|A\right|‖}_{\infty }\le {\kappa }_{\infty }\left(A\right)$. If $\stackrel{^}{x}$ is the $j$th column of $X$, then ${w}_{c}$ is returned in ${\mathbf{berr}}\left(j\right)$ and a bound on ${‖x-\stackrel{^}{x}‖}_{\infty }/{‖\stackrel{^}{x}‖}_{\infty }$ is returned in ${\mathbf{ferr}}\left(j\right)$. See Section 4.4 of Anderson et al. (1999) for further details.

The factorization of $A$ requires approximately $\frac{1}{3}{n}^{3}$ floating-point operations.
For each right-hand side, computation of the backward error involves a minimum of $4{n}^{2}$ floating-point operations. Each step of iterative refinement involves an additional $6{n}^{2}$ operations. At most five steps of iterative refinement are performed, but usually only one or two steps are required. Estimating the forward error involves solving a number of systems of equations of the form $Ax=b$; the number is usually $4$ or $5$ and never more than $11$. Each solution involves approximately $2{n}^{2}$ operations.
The complex analogues of this function are nag_lapack_zhpsvx (f07pp) for Hermitian matrices, and nag_lapack_zspsvx (f07qp) for symmetric matrices.

## Example

This example solves the equations
 $AX=B ,$
where $A$ is the symmetric matrix
 $A = -1.81 2.06 0.63 -1.15 2.06 1.15 1.87 4.20 0.63 1.87 -0.21 3.87 -1.15 4.20 3.87 2.07 and B = 0.96 3.93 6.07 19.25 8.38 9.90 9.50 27.85 .$
Error estimates for the solutions, and an estimate of the reciprocal of the condition number of the matrix $A$ are also output.
```function f07pb_example

fprintf('f07pb example results\n\n');

% Symmetric matrix, upper triangle stored in packed format
uplo = 'U';
ap = [-1.81;
2.06;    1.15;
0.63;    1.87;   -0.21;
-1.15;    4.2;     3.87;    2.07];
% RHS
b = [0.96,  3.93;
6.07, 19.25;
8.38,  9.90;
9.50, 27.85];

% Factorize and solve
fact = 'Not Factorized';
ipiv = zeros(4,1,'int64');
afp  = ap;

[afp, ipiv, x, rcond, ferr, berr, info] = ...
f07pb(...
fact, uplo, ap, afp, ipiv, b);

disp('Solution');
disp(x);
fprintf('Condition number      = %7.3f\n',1/rcond);
fprintf('Forward  error bounds = %10.3e  %10.3e\n',ferr);
fprintf('Backward error bounds = %10.3e  %10.3e\n',berr);

```
```f07pb example results

Solution
-5.0000    2.0000
-2.0000    3.0000
1.0000    4.0000
4.0000    1.0000

Condition number      =  75.687
Forward  error bounds =  2.424e-14   3.379e-14
Backward error bounds =  9.514e-17   8.933e-17
```