﻿MathNet.Numerics.LinearAlgebra.Sparse.Linear
 Math.NET Numerics v0.3

# MathNet.Numerics.LinearAlgebra.Sparse.Linear Namespace

Iterative linear solvers and preconditioners. Solves the linear problem
`A x = b`

with respect to `x`. A must be an `n*n` non-singular matrix, and `x` and `b` are `n`-vectors. Note that the value of `x` is used as an initial guess, and the convergence can be improved by using a good guess.

### Iterative linear solvers

The solvers are modified versions of the Templates versions. All the solvers implement the interface ILinearSolver, and its usage can be illustrated by an example:

```double[] Solver(Matrix A, Vector x, Vector b)
{
LinearSolver solver = new CGSolver();
try
{
x = solver.Solve(A, x, b);
}
catch (LinearNotConvergedException e)
{
Console.WriteLine("Linear solver did not converge");
Console.WriteLine("Final residual = " + e.Residual);
Console.WriteLine("Number of iterations = " + e.Iterations);
Console.WriteLine("Reason = ");
if (e.Reason == NotConvergedException.BREAKDOWN)
Console.WriteLine("breakdown");
else if (e.Reason == NotConvergedException.DIVERGENCE)
Console.WriteLine("divergence");
else if (e.getReason() == NotConvergedException.ITERATIONS)
Console.WriteLine("too many iterations");
}
return Blas.Default.GetArrayCopy(x);
}
```

In this example, the solver CGSolver was used. Other solvers include the following:

Solver SPD Transpose Notes
BiCGSolverYes
BiCGstabSolver
CGSolverYes
CGSSolver
ChebyshevSolverYes Needs extremal eigenvalues
GMRESSolverRestarted version
IRSolver
QMRSolverYes Uses left and right preconditioning

SPD means that the matrix must be symmetrical, positive definite, while transpose means that transpose matrix/vector multiplication and preconditioning is necessary.

### Convergence criteria

ILinearIterationMonitor monitors the iteration, and provides both convergence tracking and detection. There are two implementations of `ILinearIterationMonitor`:

• DefaultLinearIteration declares convergence when the current residual has decrease by a certain factor compared to the initial residual.
• MatrixLinearIteration a `DefaultLinearIteration`, but the matrix-norm to scale the initial residual.

The method Iteration is used to set a `ILinearIteration`.

Another use of the iteration objects is in the monitoring they can perform. By default, no monitoring is done, but the method Monitor allows one to attach a monitor. The following are available:

An easy way to attach a monitor without changing the iteration object is the following:

```LinearSolver solver = new CGSolver();
solver.Iteration.Monitor = new OutputLinearIterationMonitor();
```

### Preconditioning

To speed up convergence of the iterative solvers, preconditioners are often necessary. Use the method Preconditioner to set the preconditioner. Available preconditoners are:

PreconditionerNotes
GaussSeidelPreconditioner
ICCPreconditionerOptional fill-in and diagonal scaling.
ILUPreconditionerOptional fill-in and diagonal scaling.
PolynomialPreconditioner
SORPreconditioner
SSORPreconditioner
MultigridPreconditionerGeometrical variant.
CholeskyPreconditionerFor sub-problems only.
LUPreconditionerFor sub-problems only
QRPreconditionerFor sub-problems only
CompositePreconditionerApplies a sequence of preconditioners
IdentityPreconditionerDefault preconditioner, does nothing
IterativeSolverPreconditionerHas slack convergence criteria

For further details on the preconditioners, see the Templates page.

### Classes

ClassDescription
AbstractLinearIteration Partial implementation of a linear iteration object.
AbstractLinearSolver Partial implementation of LinearSolver
AbstractPreconditioner Partial implementation of Preconditioner
ArrayLinearIterationMonitor Stores all the residuals in an array, which the user can retrieve afterwards.
BiCGSolver BiCG solver. BiCG solves the unsymmetric linear system `Ax = b` using the Preconditioned BiConjugate Gradient method.
BiCGstabSolver BiCG stablized solver. BiCGstab solves the unsymmetric linear system
`Ax = b`
using the Preconditioned BiConjugate Gradient Stabilized method
CGSolver Conjugate Gradients solver. CG solves the symmetric positive definite linear system `Ax=b` using the Conjugate Gradient method.
CGSSolver Conjugate Gradients squared solver. CGS solves the unsymmetric linear system `Ax = b` using the Conjugate Gradient Squared method.
ChebyshevSolver Chebyshev solver. Solves the symmetric positive definite linear system `Ax = b` using the Preconditioned Chebyshev Method. Chebyshev requires an acurate estimate on the bounds of the spectrum of the matrix.
CholeskyPreconditioner Complete Choleksy preconditioner. It should only be used to precondition blocks of the matrix, as for instance in the BlockDiagonalPreconditioner.
CompositePreconditioner Composite preconditioner. Applies several preconditioners in sequence serially. If the preconditioners have already been set up, it is not necessary to call the setup method in this class, as it simply calls setup() on every preconditioner.
DecompositionPreconditioner Partial preconditioner for decomposition based methods. Contains some methods to make incomplete decomposition based preconditioners easier to implement, such as ILU and ICC.
DefaultLinearIteration Default linear iteration object. This tester checks declares convergence if the absolute value of the residual norm is sufficiently small, or if the relative decrease is small. Divergence is decleared if too many iterations are spent, or the residual has grown too much. NaNs will also cause divergence to be flagged.
GaussSeidelPreconditioner Gauss-Seidel preconditioner. Applies one sweep of Gauss-Seidel to the system matrix. Does not perform transpose operations.
GMRESSolver GMRES solver. GMRES solves the unsymmetric linear system `Ax = b` using the Generalized Minimum Residual method. The GMRES iteration is restarted after a given number of iterations. By default it is restarted after 30 iterations.
ICCPreconditioner An ICC preconditioner. Uses an incomplete Cholesky decomposition as preconditioner. Applicable to symmetrical, positive definite problems.
IdentityPreconditioner Identity preconditioner. A dummy preconditioner. Useful as a placeholder.
ILUPreconditioner ILU preconditioner. Performs an incomplete LU decomposition as a preconditioner. Applicable to unsymmetrical problems.
IRSolver Iterative Refinement. IR solves the unsymmetric linear system `Ax = b` using Iterative Refinement (preconditioned Richardson iteration).
IterativeSolverPreconditioner Applies an iterative linear solver as preconditioner. Only for transpose-free problems. The convergence criteria for the preconditioner should not be too stringent as that can defeat the purpose of the preconditioner.

Note that if the solver doesn't converge, the exceptions are caught and promptly ignored.

LinearNotConvergedException Exception for lack of convergence in a linear problem. Contains the final computed residual.
LUPreconditioner Complete LU factorization as preconditioner. It should only be used to precondition blocks of the matrix, as for instance in the BlockDiagonalPreconditioner. Transpose operation is not supported.
MatrixLinearIteration Linear iteration object based on matrix norms. Extends the default linear iteration object to compare with the norm of the system matrix and the right hand side. Can often be a better convergence criteria than the default, but requires the computation of the matrix norm.
MultigridPreconditioner Multigrid preconditioner. Uses a geometric multigrid, thus the user needs to create matrix operators and restriction operators. The preconditioner supports different kinds of cycles (V, W etc), and the smoothers can be chosen by the user.
NullLinearIterationMonitor An iteration monitor which does nothing.
OutputLinearIterationMonitor Outputs iteration information to an output stream.
PolynomialPreconditioner Neumann series preconditioner. Expands the inverse of the matrix into a Neumann series, ie. `A-1=I + (I-A) + (I-A)2 + ...`. This series only converge if the norm of A is less than 1. If the norm is greater, a scaling factor may be supplied.
QMRSolver Quasi-Minimal Residual method. QMR solves the unsymmetric linear system `Ax = b` using the Quasi-Minimal Residual method. QMR uses two preconditioners, and by default these are the same preconditioner.
QRPreconditioner Complete QR factorization as preconditioner. It should only be used to precondition blocks of the matrix, as for instance in the BlockDiagonalPreconditioner. Transpose operations are not supported.
SORPreconditioner SOR preconditioner. Applies one sweep of SOR to the system matrix. Sequential. For best performance, a good choice of the overrelaxation parameter omega must be made (0 < omega < 2). Does not perform transpose operations.
SSORPreconditioner SSOR preconditioner. Uses a symmetrical SOR as a preconditioner. Meant for symmetrical matrices. For best performance, omega must be carefully chosen (between 0 and 2).

### Interfaces

InterfaceDescription
ILinearIteration Iteration for a linear system
ILinearIterationMonitor Monitors the iteration of a solver.
ILinearSolver Krylov subspace linear solver. Interface to a generic iterative Krylov based system solver. It solves the linear problem
`Ax=b`
for x, using preconditioning and convergence monitoring.
IPreconditioner Preconditioner interface. Preconditioners are approximate solvers to some problem. They may be used in iterative solution procedures to speed up convergence.

The only method the user needs to call from this interface is setup. Before using the preconditioner in a LinearSolver, setup must have been called. The advantage of this is that the same internal structure of the preconditioner can be reused for repeated solves with the same matrix. This is particularly important for complicated preconditioners such as ILU or BlockDiagonalPreconditioner.