MathNet.Numerics.LinearAlgebra.Sparse.Linear

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
BiCGSolver		Yes
BiCGstabSolver
CGSolver	Yes
CGSSolver
ChebyshevSolver	Yes		Needs extremal eigenvalues
GMRESSolver			Restarted version
IRSolver
QMRSolver		Yes	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:

ArrayLinearIterationMonitor stores the iteration progress in an array.
OutputLinearIterationMonitor outputs the information to a stream, by default System.Console.Err.

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:

Preconditioner	Notes
GaussSeidelPreconditioner
ICCPreconditioner	Optional fill-in and diagonal scaling.
ILUPreconditioner	Optional fill-in and diagonal scaling.
PolynomialPreconditioner
SORPreconditioner
SSORPreconditioner
MultigridPreconditioner	Geometrical variant.
CholeskyPreconditioner	For sub-problems only.
LUPreconditioner	For sub-problems only
QRPreconditioner	For sub-problems only
CompositePreconditioner	Applies a sequence of preconditioners
IdentityPreconditioner	Default preconditioner, does nothing
IterativeSolverPreconditioner	Has slack convergence criteria

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

Classes

Class	Description
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)² + ...`. 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

Interface	Description
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.

MathNet.Numerics.LinearAlgebra.Sparse.Linear Namespace

Iterative linear solvers

Convergence criteria

Preconditioning

Classes

Interfaces