naginterfaces.library.sparse.real_​symm_​basic_​setup

naginterfaces.library.sparse.real_symm_basic_setup(method, precon, n, tol, maxitn, anorm, sigmax, maxits, monit, sigcmp='N', norm=None, weight='N', iterm=1, sigtol=0.01)

real_symm_basic_setup is a setup function, the first in a suite of three functions for the iterative solution of a symmetric system of simultaneous linear equations. real_symm_basic_setup must be called before the iterative solver, real_symm_basic_solver(). The third function in the suite, real_symm_basic_diag(), can be used to return additional information about the computation.

These three functions are suitable for the solution of large sparse symmetric systems of equations.

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

https://support.nag.com/numeric/nl/nagdoc_30/flhtml/f11/f11gdf.html

Parameters

methodstr

The iterative method to be used.

$method=\text{'CG'}$

Conjugate gradient method (CG).

$method=\text{'SYMMLQ'}$

Lanczos method (SYMMLQ).

$method=\text{'MINRES'}$

Minimum residual method (MINRES).

preconstr, length 1

Determines whether preconditioning is used.

$precon=\text{'N'}$

No preconditioning.

$precon=\text{'P'}$

Preconditioning.

nint

$n$, the order of the matrix $A$.

tolfloat

The tolerance $\tau$ for the termination criterion.

If $tol\le 0.0$, $\tau =max(\sqrt{ϵ},\sqrt{n}ϵ)$ is used, where $ϵ$ is the machine precision.

Otherwise $\tau =max(tol,10ϵ,\sqrt{n}ϵ)$ is used.

maxitnint

The maximum number of iterations.

anormfloat

If $anorm>0.0$, the value of ${\parallel A\parallel }_p$ to be used in the termination criterion (2) ($iterm=1$).

If $anorm\le 0.0$, $iterm=1$ and $norm=\text{'1'}$ or $\text{'I'}$, ${\parallel A\parallel }_1={\parallel A\parallel }_{\infty }$ is estimated internally by real_symm_basic_solver().

If $iterm=2$, $anorm$ is not referenced.

It has no effect if $method=\text{'MINRES'}$.

sigmaxfloat

If $sigmax>0.0$, the value of ${\sigma }_1\left(\overline{A}\right)={\Vert E^{-1}A{E}^{-T}\Vert }_2$.

If $sigmax\le 0.0$, ${\sigma }_1\left(\overline{A}\right)$ is estimated by real_symm_basic_solver() when either $sigcmp=\text{'S'}$ or termination criterion (3) ($iterm=2$) is employed, though it will be used only in the latter case.

Otherwise, or if $method=\text{'MINRES'}$, $sigmax$ is not referenced.

maxitsint

The maximum iteration number $k=maxits$ for which ${\sigma }_1\left(T_k\right)$ is computed by bisection (see also Notes). If $sigcmp=\text{'N'}$ or $sigmax>0.0$, or if $method=\text{'MINRES'}$, $maxits$ is not referenced.

Suggested value: $maxits=min(10,n)$ when $sigtol$ is of the order of its default value $\left(0.01\right)$.

monitint

If $monit>0$, the frequency at which a monitoring step is executed by real_symm_basic_solver(): the current solution and residual iterates will be returned by real_symm_basic_solver() and a call to real_symm_basic_diag() made possible every $monit$ iterations, starting from the ($monit$)th. Otherwise, no monitoring takes place.

There are some additional computational costs involved in monitoring the solution and residual vectors when the Lanczos method (SYMMLQ) is used.

sigcmpstr, length 1, optional

Determines whether an estimate of ${\sigma }_1\left(\overline{A}\right)={\Vert E^{-1}A{E}^{-T}\Vert }_2$, the largest singular value of the preconditioned matrix of the coefficients, is to be computed using the bisection method on the sequence of tridiagonal matrices $\left\{T_k\right\}$ generated during the iteration. Note that $\overline{A}=A$ when a preconditioner is not used.

If $sigmax>0.0$ (see $sigmax$), i.e., when ${\sigma }_1\left(\overline{A}\right)$ is supplied, the value of $sigcmp$ is ignored.

$sigcmp=\text{'S'}$

${\sigma }_1\left(\overline{A}\right)$ is to be computed using the bisection method.

$sigcmp=\text{'N'}$

The bisection method is not used.

If the termination criterion (3) is used, requiring ${\sigma }_1\left(\overline{A}\right)$, an inexpensive estimate is computed and used (see Notes).

It is not used if $method=\text{'MINRES'}$.

normNone or str, length 1, optional

Note: if this argument is None then a default value will be used, determined as follows: if $iterm=1$: $\text{'I'}$; otherwise: $\text{'2'}$.

If $method=\text{'CG'}$ or $\text{'SYMMLQ'}$, $norm$ defines the matrix and vector norm to be used in the termination criteria.

$norm=\text{'1'}$

Use the $l_1$ norm.

$norm=\text{'I'}$

Use the $l_{\infty }$ norm.

$norm=\text{'2'}$

Use the $l_2$ norm.

It has no effect if $method=\text{'MINRES'}$.

weightstr, length 1, optional

Specifies whether a vector $w$ of user-supplied weights is to be used in the vector norms used in the computation of termination criterion (2) ($iterm=1$): ${\parallel v\parallel }_p^{\left(w\right)}={\Vert v^{\left(w\right)}\Vert }_p$, where $v_{\text{i}}^{\left(w\right)}=w_{\text{i}}{v}_{\text{i}}$, for $\text{i}=1,2,\dots ,n$. The suffix $p=1,2,\infty$ denotes the vector norm used, as specified by the argument $norm$. Note that weights cannot be used when $iterm=2$, i.e., when criterion (3) is used.

$weight=\text{'W'}$

User-supplied weights are to be used and must be supplied on initial entry to real_symm_basic_solver().

$weight=\text{'N'}$

All weights are implicitly set equal to one. Weights do not need to be supplied on initial entry to real_symm_basic_solver().

It has no effect if $method=\text{'MINRES'}$.

itermint, optional

Defines the termination criterion to be used.

$iterm=1$

Use the termination criterion defined in (2) (both conjugate gradient and Lanczos (SYMMLQ) methods).

$iterm=2$

Use the termination criterion defined in (3) (Lanczos method (SYMMLQ) only).

It has no effect if $method=\text{'MINRES'}$.

sigtolfloat, optional

The tolerance used in assessing the convergence of the estimate of ${\sigma }_1\left(\overline{A}\right)={\Vert \overline{A}\Vert }_2$ when the bisection method is used.

If $sigtol\le 0.0$, the default value $sigtol=0.01$ is used.

The actual value used is $max(sigtol,ϵ)$.

If $sigcmp=\text{'N'}$ or $sigmax>0.0$, $sigtol$ is not referenced.

It has no effect if $method=\text{'MINRES'}$.

Returns

commdict, communication object

Communication structure.

Raises

NagValueError

(errno $-14$)

On entry, $monit=⟨value⟩$ and $maxitn=⟨value⟩$.

Constraint: $monit\le maxitn$.

(errno $-13$)

On entry, $sigcmp=\text{'S'}$, $sigmax\le 0.0$, $maxits=⟨value⟩$ and $maxitn=⟨value⟩$.

Constraint: if $sigcmp=\text{'S'}$ and $sigmax\le 0.0$, $maxits\le maxitn$.

(errno $-13$)

On entry, $sigcmp=\text{'S'}$, $sigmax\le 0.0$ and $maxits=⟨value⟩$.

Constraint: if $sigcmp=\text{'S'}$ and $sigmax\le 0.0$, $maxits\ge 1$.

(errno $-12$)

On entry, $sigcmp=\text{'S'}$, $sigmax\le 0.0$ and $sigtol=⟨value⟩$.

Constraint: if $sigcmp=\text{'S'}$ and $sigmax\le 0.0$, $sigtol<1.0$.

(errno $-10$)

On entry, $iterm=1$, $norm=\text{'2'}$ and $anorm=⟨value⟩$.

Constraint: if $iterm=1$ and $norm=\text{'2'}$, $anorm>0.0$.

(errno $-9$)

On entry, $maxitn=⟨value⟩$.

Constraint: $maxitn>0$.

(errno $-8$)

On entry, $tol=⟨value⟩$.

Constraint: $tol<1.0$.

(errno $-7$)

On entry, $n=⟨value⟩$.

Constraint: $n>0$.

(errno $-6$)

On entry, $iterm=2$ and $method=\text{'CG'}$.

Constraint: if $iterm=2$, $method\ne \text{'CG'}$.

(errno $-6$)

On entry, $iterm=2$ and $norm=⟨value⟩$.

Constraint: if $iterm=2$, $norm=\text{'2'}$.

(errno $-6$)

On entry, $iterm=2$ and $weight=⟨value⟩$.

Constraint: if $iterm=2$, $weight=\text{'N'}$.

(errno $-6$)

On entry, $iterm=⟨value⟩$.

Constraint: $iterm=1$ or $2$.

(errno $-5$)

On entry, $weight=⟨value⟩$.

Constraint: $weight=\text{'N'}$ or $\text{'W'}$.

(errno $-4$)

On entry, $norm=⟨value⟩$.

Constraint: $norm=\text{'1'}$, $\text{'I'}$ or $\text{'2'}$.

(errno $-3$)

On entry, $sigcmp=⟨value⟩$.

Constraint: $sigcmp=\text{'S'}$ or $\text{'N'}$.

(errno $-2$)

On entry, $precon=⟨value⟩$.

Constraint: $precon=\text{'N'}$ or $\text{'P'}$.

(errno $-1$)

On entry, $method=⟨value⟩$.

Constraint: $method=\text{'CG'}$, $\text{'SYMMLQ'}$ or $\text{'MINRES'}$.

(errno $1$)

real_symm_basic_setup has been called out of sequence: either real_symm_basic_setup has been called twice or real_symm_basic_solver() has not terminated its current task.

Notes

The suite consisting of the functions real_symm_basic_setup, real_symm_basic_solver() and real_symm_basic_diag() is designed to solve the symmetric system of simultaneous linear equations $Ax=b$ of order $n$, where $n$ is large and the matrix of the coefficients $A$ is sparse.

real_symm_basic_setup is a setup function which must be called before real_symm_basic_solver(), the iterative solver. The third function in the suite, real_symm_basic_diag() can be used to return additional information about the computation. One of the following methods can be used:

1. Conjugate Gradient Method (CG)

   For this method (see Hestenes and Stiefel (1952), Golub and Van Loan (1996), Barrett et al. (1994) and Dias da Cunha and Hopkins (1994)), the matrix $A$ should ideally be positive definite. The application of the Conjugate Gradient method to indefinite matrices may lead to failure or to lack of convergence.

2. Lanczos Method (SYMMLQ)

   This method, based upon the algorithm SYMMLQ (see Paige and Saunders (1975) and Barrett et al. (1994)), is suitable for both positive definite and indefinite matrices. It is more robust than the Conjugate Gradient method but less efficient when $A$ is positive definite.

3. Minimum Residual Method (MINRES)

   This method may be used when the matrix is indefinite. It seeks to reduce the norm of the residual at each iteration and often takes fewer iterations than the other methods. It does however require slightly more memory.

The CG and SYMMLQ methods start from the residual $r_0=b-A{x}_0$, where $x_0$ is an initial estimate for the solution (often $x_0=0$), and generate an orthogonal basis for the Krylov subspace $span\left\{A^{\text{k}}{r}_0\right\}$, for $\text{k}=0,1,\dots ,$, by means of three-term recurrence relations (see Golub and Van Loan (1996)). A sequence of symmetric tridiagonal matrices $\left\{T_k\right\}$ is also generated. Here and in the following, the index $k$ denotes the iteration count. The resulting symmetric tridiagonal systems of equations are usually more easily solved than the original problem. A sequence of solution iterates $\left\{x_k\right\}$ is thus generated such that the sequence of the norms of the residuals $\left\{\parallel r_k\parallel \right\}$ converges to a required tolerance. Note that, in general, the convergence is not monotonic.

In exact arithmetic, after $n$ iterations, this process is equivalent to an orthogonal reduction of $A$ to symmetric tridiagonal form, $T_n=Q^{T}AQ$; the solution $x_n$ would thus achieve exact convergence. In finite-precision arithmetic, cancellation and round-off errors accumulate causing loss of orthogonality. These methods must, therefore, be viewed as genuinely iterative methods, able to converge to a solution within a prescribed tolerance.

The orthogonal basis is not formed explicitly in either method. The basic difference between the Conjugate Gradient and Lanczos methods lies in the method of solution of the resulting symmetric tridiagonal systems of equations: the conjugate gradient method is equivalent to carrying out an $LD{L}^T$ (Cholesky) factorization whereas the Lanczos method (SYMMLQ) uses an $LQ$ factorization.

Faster convergence for all the methods can be achieved using a preconditioner (see Golub and Van Loan (1996) and Barrett et al. (1994)). A preconditioner maps the original system of equations onto a different system, say

$$\overline{A}\overline{x}=\overline{b}\text{,}$$

with, hopefully, better characteristics with respect to its speed of convergence: for example, the condition number of the matrix of the coefficients can be improved or eigenvalues in its spectrum can be made to coalesce. An orthogonal basis for the Krylov subspace $span\left\{{\overline{A}}^{\text{k}}{\overline{r}}_0\right\}$, for $\text{k}=0,1,\dots ,$, is generated and the solution proceeds as outlined above. The algorithms used are such that the solution and residual iterates of the original system are produced, not their preconditioned counterparts. Note that an unsuitable preconditioner or no preconditioning at all may result in a very slow rate, or lack, of convergence. However, preconditioning involves a trade-off between the reduction in the number of iterations required for convergence and the additional computational costs per iteration. Also, setting up a preconditioner may involve non-negligible overheads.

A preconditioner must be symmetric and positive definite, i.e., representable by $M=E{E}^T$, where $M$ is nonsingular, and such that $\overline{A}=E^{-1}A{E}^{-T}\sim I_n$ in (1), where $I_n$ is the identity matrix of order $n$. Also, we can define $\overline{r}=E^{-1}r$ and $\overline{x}=E^{T}x$. These are formal definitions, used only in the design of the algorithms; in practice, only the means to compute the matrix-vector products $v=Au$ and to solve the preconditioning equations $Mv=u$ are required, that is, explicit information about $M$, $E$ or their inverses is not required at any stage.

The first termination criterion

$${\parallel r_k\parallel }_p\le \tau ({\parallel b\parallel }_p+{\parallel A\parallel }_p\times {\parallel x_k\parallel }_p)$$

is available for both conjugate gradient and Lanczos (SYMMLQ) methods. In (2), $p=1,\infty$ or $2$ and $\tau$ denotes a user-specified tolerance subject to $max(10,\sqrt{n})ϵ\le \tau <1$, where $ϵ$ is the machine precision. Facilities are provided for the estimation of the norm of the matrix of the coefficients ${\parallel A\parallel }_1={\parallel A\parallel }_{\infty }$, when this is not known in advance, used in (2), by applying Higham’s method (see Higham (1988)). Note that ${\parallel A\parallel }_2$ cannot be estimated internally. This criterion uses an error bound derived from backward error analysis to ensure that the computed solution is the exact solution of a problem as close to the original as the termination tolerance requires. Termination criteria employing bounds derived from forward error analysis could be used, but any such criteria would require information about the condition number $\kappa \left(A\right)$ which is not easily obtainable.

The second termination criterion

$${\parallel {\overline{r}}_k\parallel }_2\le \tau max(1.0,{\parallel b\parallel }_2/{\parallel r_0\parallel }_2)({\parallel {\overline{r}}_0\parallel }_2+{\sigma }_1\left(\overline{A}\right)\times {\parallel \Delta {\overline{x}}_k\parallel }_2)$$

is available only for the Lanczos method (SYMMLQ). In (3), ${\sigma }_1\left(\overline{A}\right)={\Vert \overline{A}\Vert }_2$ is the largest singular value of the (preconditioned) iteration matrix $\overline{A}$. This termination criterion monitors the progress of the solution of the preconditioned system of equations and is less expensive to apply than criterion (2). When ${\sigma }_1\left(\overline{A}\right)$ is not supplied, facilities are provided for its estimation by ${\sigma }_1\left(\overline{A}\right)\sim {max}_k{\sigma }_1\left(T_k\right)$. The interlacing property ${\sigma }_1\left(T_{k-1}\right)\le {\sigma }_1\left(T_k\right)$ and Gerschgorin’s theorem provide lower and upper bounds from which ${\sigma }_1\left(T_k\right)$ can be easily computed by bisection. Alternatively, the less expensive estimate ${\sigma }_1\left(\overline{A}\right)\sim {max}_k{\parallel T_k\parallel }_1$ can be used, where ${\sigma }_1\left(\overline{A}\right)\le {\parallel T_k\parallel }_1$ by Gerschgorin’s theorem. Note that only order of magnitude estimates are required by the termination criterion.

Termination criterion (2) is the recommended choice, despite its (small) additional costs per iteration when using the Lanczos method (SYMMLQ). Also, if the norm of the initial estimate is much larger than the norm of the solution, that is, if $\parallel x_0\parallel \gg \parallel x\parallel$, a dramatic loss of significant digits could result in complete lack of convergence. The use of criterion (2) will enable the detection of such a situation, and the iteration will be restarted at a suitable point. No such restart facilities are provided for criterion (3).

Optionally, a vector $w$ of user-specified weights can be used in the computation of the vector norms in termination criterion (2), i.e., ${\parallel v\parallel }_p^{\left(w\right)}={\Vert v^{\left(w\right)}\Vert }_p$, where ${\left(v^{\left(w\right)}\right)}_{\text{i}}=w_{\text{i}}{v}_{\text{i}}$, for $\text{i}=1,2,\dots ,n$. Note that the use of weights increases the computational costs.

The MINRES algorithm terminates when the norm of the residual of the preconditioned system $F$, ${\parallel F\parallel }_2\le \tau \times {\Vert \overline{A}\Vert }_2\times {\parallel x_k\parallel }_2$, where $\overline{A}$ is the preconditioned matrix.

The termination criteria discussed are not robust in the presence of a non-trivial nullspace of $A$, i.e., when $A$ is singular. It is then possible for ${\parallel x_k\parallel }_p$ to grow without limit, spuriously satisfying the termination criterion. If singularity is suspected, more robust functions can be found in submodule opt.

The sequence of calls to the functions comprising the suite is enforced: first, the setup function real_symm_basic_setup must be called, followed by the solver real_symm_basic_solver(). The diagnostic function real_symm_basic_diag() can be called either when real_symm_basic_solver() is carrying out a monitoring step or after real_symm_basic_solver() has completed its tasks. Incorrect sequencing will raise an error condition.

References

Barrett, R, Berry, M, Chan, T F, Demmel, J, Donato, J, Dongarra, J, Eijkhout, V, Pozo, R, Romine, C and Van der Vorst, H, 1994, Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, SIAM, Philadelphia

Dias da Cunha, R and Hopkins, T, 1994, PIM 1.1 — the parallel iterative method package for systems of linear equations user’s guide — Fortran 77 version, Technical Report, Computing Laboratory, University of Kent at Canterbury, Kent, UK

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

Hestenes, M and Stiefel, E, 1952, Methods of conjugate gradients for solving linear systems, J. Res. Nat. Bur. Stand. (49), 409–436

Higham, N J, 1988, FORTRAN codes for estimating the one-norm of a real or complex matrix, with applications to condition estimation, ACM Trans. Math. Software (14), 381–396

Paige, C C and Saunders, M A, 1975, Solution of sparse indefinite systems of linear equations, SIAM J. Numer. Anal. (12), 617–629