SymmLQ (Commons Math 3.0-SNAPSHOT API)

Overview

Package

Class

Use

Tree

Deprecated

Index

Help

PREV CLASS NEXT CLASS

FRAMES NO FRAMES

SUMMARY: NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

org.apache.commons.math.linear
Class SymmLQ

java.lang.Object
  org.apache.commons.math.linear.IterativeLinearSolver
      org.apache.commons.math.linear.PreconditionedIterativeLinearSolver
          org.apache.commons.math.linear.SymmLQ

public class SymmLQ
extends PreconditionedIterativeLinearSolver
extends PreconditionedIterativeLinearSolver

Implementation of the SYMMLQ iterative linear solver proposed by Paige and Saunders (1975). This implementation is largely based on the FORTRAN code by Pr. Michael A. Saunders, available here.

SYMMLQ is designed to solve the system of linear equations A · x = b where A is an n × n self-adjoint linear operator (defined as a RealLinearOperator), and b is a given vector. The operator A is not required to be positive definite. If A is known to be definite, the method of conjugate gradients might be preferred, since it will require about the same number of iterations as SYMMLQ but slightly less work per iteration.

SYMMLQ is designed to solve the system (A - shift · I) · x = b, where shift is a specified scalar value. If shift and b are suitably chosen, the computed vector x may approximate an (unnormalized) eigenvector of A, as in the methods of inverse iteration and/or Rayleigh-quotient iteration. Again, the linear operator (A - shift · I) need not be positive definite (but must be self-adjoint). The work per iteration is very slightly less if shift = 0.

Preconditioning

Preconditioning may reduce the number of iterations required. The solver may be provided with a positive definite preconditioner M = C · C^T that is known to approximate (A - shift · I) in some sense, where systems of the form M · y = x can be solved efficiently. Then SYMMLQ will implicitly solve the system of equations P · (A - shift · I) · P^T · xhat = P · b, i.e. Ahat · xhat = bhat, where P = C^-1, Ahat = P · (A - shift · I) · P^T, bhat = P · b, and return the solution x = P^T · xhat. The associated residual is rhat = bhat - Ahat · xhat = P · [b - (A - shift · I) · x] = P · r.

Default stopping criterion

A default stopping criterion is implemented. The iterations stop when || rhat || ≤ δ || Ahat || || xhat ||, where xhat is the current estimate of the solution of the transformed system, rhat the current estimate of the corresponding residual, and δ a user-specified tolerance.

Iteration count

In the present context, an iteration should be understood as one evaluation of the matrix-vector product A · x. The initialization phase therefore counts as one iteration. If the user requires checks on the symmetry of A, this entails one further matrix-vector product in the initial phase. This further product is not accounted for in the iteration count. In other words, the number of iterations required to reach convergence will be identical, whether checks have been required or not.

The present definition of the iteration count differs from that adopted in the original FOTRAN code, where the initialization phase was not taken into account.

Initial guess of the solution

The x parameter in

should not be considered as an initial guess, as it is set to zero in the initial phase. If x₀ is known to be a good approximation to x, one should compute r₀ = b - A · x, solve A · dx = r0, and set x = x₀ + dx.

Exception context

Besides standard DimensionMismatchException, this class might throw NonSelfAdjointOperatorException if the linear operator or the preconditioner are not symmetric. In this case, the ExceptionContext provides more information

key "operator" points to the offending linear operator, say L,
key "vector1" points to the first offending vector, say x,
key "vector2" points to the second offending vector, say y, such that x^T · L · y ≠ y^T · L · x (within a certain accuracy).

NonPositiveDefiniteOperatorException might also be thrown in case the preconditioner is not positive definite. The relevant keys to the ExceptionContext are

key "operator", which points to the offending linear operator, say L,
key "vector", which points to the offending vector, say x, such that x^T · L · x < 0.

References

Paige and Saunders (1975): C. C. Paige and M. A. Saunders, Solution of Sparse Indefinite Systems of Linear Equations, SIAM Journal on Numerical Analysis 12(4): 617-629, 1975

Since:: 3.0
Version:: $Id: SymmLQ.java 1188549 2011-10-25 07:37:08Z celestin $

Constructor Summary
`SymmLQ(int maxIterations, double delta, boolean check)` Creates a new instance of this class, with default stopping criterion.
`SymmLQ(IterationManager manager, double delta, boolean check)` Creates a new instance of this class, with default stopping criterion and custom iteration manager.

Method Summary
`boolean`	`getCheck()` Returns `true` if symmetry of the matrix, and symmetry as well as positive definiteness of the preconditioner should be checked.
`RealVector`	`solve(RealLinearOperator a, InvertibleRealLinearOperator m, RealVector b)` Returns an estimate of the solution to the linear system A · x = b.
`RealVector`	`solve(RealLinearOperator a, InvertibleRealLinearOperator m, RealVector b, boolean goodb, double shift)` Returns an estimate of the solution to the linear system (A - shift · I) · x = b.
`RealVector`	`solve(RealLinearOperator a, InvertibleRealLinearOperator m, RealVector b, RealVector x)` Returns an estimate of the solution to the linear system A · x = b.
`RealVector`	`solve(RealLinearOperator a, RealVector b)` Returns an estimate of the solution to the linear system A · x = b.
`RealVector`	`solve(RealLinearOperator a, RealVector b, boolean goodb, double shift)` Returns the solution to the system (A - shift · I) · x = b.
`RealVector`	`solve(RealLinearOperator a, RealVector b, RealVector x)` Returns an estimate of the solution to the linear system A · x = b.
`RealVector`	`solveInPlace(RealLinearOperator a, InvertibleRealLinearOperator m, RealVector b, RealVector x)` Returns an estimate of the solution to the linear system A · x = b.
`RealVector`	`solveInPlace(RealLinearOperator a, InvertibleRealLinearOperator m, RealVector b, RealVector x, boolean goodb, double shift)` Returns an estimate of the solution to the linear system (A - shift · I) · x = b.
`RealVector`	`solveInPlace(RealLinearOperator a, RealVector b, RealVector x)` Returns an estimate of the solution to the linear system A · x = b.

Methods inherited from class org.apache.commons.math.linear.PreconditionedIterativeLinearSolver
`checkParameters`

Methods inherited from class org.apache.commons.math.linear.IterativeLinearSolver
`checkParameters, getIterationManager`

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Constructor Detail

SymmLQ

public SymmLQ(int maxIterations,
              double delta,
              boolean check)

Creates a new instance of this class, with default stopping criterion.

Parameters:: maxIterations - Maximum number of iterations.; delta - δ parameter for the default stopping criterion.; check - true if self-adjointedness of both matrix and preconditioner should be checked. This entails an extra matrix-vector product in the initial phase.

SymmLQ

public SymmLQ(IterationManager manager,
              double delta,
              boolean check)

Creates a new instance of this class, with default stopping criterion and custom iteration manager.

Parameters:: manager - Custom iteration manager.; delta - δ parameter for the default stopping criterion.; check - true if self-adjointedness of both matrix and preconditioner should be checked. This entails an extra matrix-vector product in the initial phase.

Method Detail

getCheck

public final boolean getCheck()

Returns true if symmetry of the matrix, and symmetry as well as positive definiteness of the preconditioner should be checked.

Returns:: true if the tests are to be performed.

solve

public RealVector solve(RealLinearOperator a,
                        InvertibleRealLinearOperator m,
                        RealVector b)
                 throws NullArgumentException,
                        NonSquareOperatorException,
                        DimensionMismatchException,
                        NonSelfAdjointOperatorException,
                        NonPositiveDefiniteOperatorException,
                        IllConditionedOperatorException,
                        MaxCountExceededException

Returns an estimate of the solution to the linear system A · x = b.

Overrides:: solve in class PreconditionedIterativeLinearSolver

Parameters:: a - Linear operator A of the system.; m - Preconditioner (can be null).; b - Right-hand side vector.
Returns:: A new vector containing the solution.
Throws:: NullArgumentException - if one of the parameters is null.; NonSquareOperatorException - if a or m is not square.; DimensionMismatchException - if m, b or x have dimensions inconsistent with a.; NonSelfAdjointOperatorException - if getCheck() is true, and a or m is not self-adjoint.; NonPositiveDefiniteOperatorException - if m is not positive definite.; IllConditionedOperatorException - if a is ill-conditioned.; MaxCountExceededException - at exhaustion of the iteration count, unless a custom callback has been set at construction.

solve

public RealVector solve(RealLinearOperator a,
                        InvertibleRealLinearOperator m,
                        RealVector b,
                        boolean goodb,
                        double shift)
                 throws NullArgumentException,
                        NonSquareOperatorException,
                        DimensionMismatchException,
                        NonSelfAdjointOperatorException,
                        NonPositiveDefiniteOperatorException,
                        IllConditionedOperatorException,
                        MaxCountExceededException

Returns an estimate of the solution to the linear system (A - shift · I) · x = b.

If the solution x is expected to contain a large multiple of b (as in Rayleigh-quotient iteration), then better precision may be achieved with goodb set to true; this however requires an extra call to the preconditioner.

shift should be zero if the system A · x = b is to be solved. Otherwise, it could be an approximation to an eigenvalue of A, such as the Rayleigh quotient b^T · A · b / (b^T · b) corresponding to the vector b. If b is sufficiently like an eigenvector corresponding to an eigenvalue near shift, then the computed x may have very large components. When normalized, x may be closer to an eigenvector than b.

Parameters:: a - Linear operator A of the system.; m - Preconditioner (can be null).; b - Right-hand side vector.; goodb - Usually false, except if x is expected to contain a large multiple of b.; shift - The amount to be subtracted to all diagonal elements of A.
Returns:: A reference to x (shallow copy).
Throws:: NullArgumentException - if one of the parameters is null.; NonSquareOperatorException - if a or m is not square.; DimensionMismatchException - if m or b have dimensions inconsistent with a.; NonSelfAdjointOperatorException - if getCheck() is true, and a or m is not self-adjoint.; NonPositiveDefiniteOperatorException - if m is not positive definite.; IllConditionedOperatorException - if a is ill-conditioned.; MaxCountExceededException - at exhaustion of the iteration count, unless a custom callback has been set at construction.

solve

public RealVector solve(RealLinearOperator a,
                        InvertibleRealLinearOperator m,
                        RealVector b,
                        RealVector x)
                 throws NullArgumentException,
                        NonSquareOperatorException,
                        DimensionMismatchException,
                        NonSelfAdjointOperatorException,
                        NonPositiveDefiniteOperatorException,
                        IllConditionedOperatorException,
                        MaxCountExceededException

Returns an estimate of the solution to the linear system A · x = b.

Overrides:: solve in class PreconditionedIterativeLinearSolver

Parameters:: a - Linear operator A of the system.; m - Preconditioner (can be null).; b - Right-hand side vector.; x - Not meaningful in this implementation. Should not be considered as an initial guess (more).
Returns:: A new vector containing the solution.
Throws:: NullArgumentException - if one of the parameters is null.; NonSquareOperatorException - if a or m is not square.; DimensionMismatchException - if m, b or x have dimensions inconsistent with a.; NonSelfAdjointOperatorException - if getCheck() is true, and a or m is not self-adjoint.; NonPositiveDefiniteOperatorException - if m is not positive definite.; IllConditionedOperatorException - if a is ill-conditioned.; MaxCountExceededException - at exhaustion of the iteration count, unless a custom callback has been set at construction.

solve

public RealVector solve(RealLinearOperator a,
                        RealVector b)
                 throws NullArgumentException,
                        NonSquareOperatorException,
                        DimensionMismatchException,
                        NonSelfAdjointOperatorException,
                        IllConditionedOperatorException,
                        MaxCountExceededException

Returns an estimate of the solution to the linear system A · x = b.

Overrides:: solve in class PreconditionedIterativeLinearSolver

Parameters:: a - Linear operator A of the system.; b - Right-hand side vector.
Returns:: A new vector containing the solution.
Throws:: NullArgumentException - if one of the parameters is null.; NonSquareOperatorException - if a is not square.; DimensionMismatchException - if b has dimensions inconsistent with a.; NonSelfAdjointOperatorException - if getCheck() is true, and a is not self-adjoint.; IllConditionedOperatorException - if a is ill-conditioned.; MaxCountExceededException - at exhaustion of the iteration count, unless a custom callback has been set at construction.

solve

public RealVector solve(RealLinearOperator a,
                        RealVector b,
                        boolean goodb,
                        double shift)
                 throws NullArgumentException,
                        NonSquareOperatorException,
                        DimensionMismatchException,
                        NonSelfAdjointOperatorException,
                        IllConditionedOperatorException,
                        MaxCountExceededException

Returns the solution to the system (A - shift · I) · x = b.

If the solution x is expected to contain a large multiple of b (as in Rayleigh-quotient iteration), then better precision may be achieved with goodb set to true.

Parameters:: a - Linear operator A of the system.; b - Right-hand side vector.; goodb - Usually false, except if x is expected to contain a large multiple of b.; shift - The amount to be subtracted to all diagonal elements of A.
Returns:: a reference to x.
Throws:: NullArgumentException - if one of the parameters is null.; NonSquareOperatorException - if a is not square.; DimensionMismatchException - if b has dimensions inconsistent with a.; NonSelfAdjointOperatorException - if getCheck() is true, and a is not self-adjoint.; IllConditionedOperatorException - if a is ill-conditioned.; MaxCountExceededException - at exhaustion of the iteration count, unless a custom callback has been set at construction.

solve

public RealVector solve(RealLinearOperator a,
                        RealVector b,
                        RealVector x)
                 throws NullArgumentException,
                        NonSquareOperatorException,
                        DimensionMismatchException,
                        NonSelfAdjointOperatorException,
                        IllConditionedOperatorException,
                        MaxCountExceededException

Returns an estimate of the solution to the linear system A · x = b.

Overrides:: solve in class PreconditionedIterativeLinearSolver

Parameters:: a - Linear operator A of the system.; b - Right-hand side vector.; x - Not meaningful in this implementation. Should not be considered as an initial guess (more).
Returns:: A new vector containing the solution.
Throws:: NullArgumentException - if one of the parameters is null.; NonSquareOperatorException - if a is not square.; DimensionMismatchException - if b or x have dimensions inconsistent with a.; NonSelfAdjointOperatorException - if getCheck() is true, and a is not self-adjoint.; IllConditionedOperatorException - if a is ill-conditioned.; MaxCountExceededException - at exhaustion of the iteration count, unless a custom callback has been set at construction.

solveInPlace

public RealVector solveInPlace(RealLinearOperator a,
                               InvertibleRealLinearOperator m,
                               RealVector b,
                               RealVector x)
                        throws NullArgumentException,
                               NonSquareOperatorException,
                               DimensionMismatchException,
                               NonSelfAdjointOperatorException,
                               NonPositiveDefiniteOperatorException,
                               IllConditionedOperatorException,
                               MaxCountExceededException

Returns an estimate of the solution to the linear system A · x = b. The solution is computed in-place.

Specified by:: solveInPlace in class PreconditionedIterativeLinearSolver

Parameters:: a - Linear operator A of the system.; m - Preconditioner (can be null).; b - Right-hand side vector.; x - Vector to be updated with the solution. x should not be considered as an initial guess (more).
Returns:: A reference to x (shallow copy) updated with the solution.
Throws:: NullArgumentException - if one of the parameters is null.; NonSquareOperatorException - if a or m is not square.; DimensionMismatchException - if m, b or x have dimensions inconsistent with a.; NonSelfAdjointOperatorException - if getCheck() is true, and a or m is not self-adjoint.; NonPositiveDefiniteOperatorException - if m is not positive definite.; IllConditionedOperatorException - if a is ill-conditioned.; MaxCountExceededException - at exhaustion of the iteration count, unless a custom callback has been set at construction.

solveInPlace

public RealVector solveInPlace(RealLinearOperator a,
                               InvertibleRealLinearOperator m,
                               RealVector b,
                               RealVector x,
                               boolean goodb,
                               double shift)
                        throws NullArgumentException,
                               NonSquareOperatorException,
                               DimensionMismatchException,
                               NonSelfAdjointOperatorException,
                               NonPositiveDefiniteOperatorException,
                               IllConditionedOperatorException,
                               MaxCountExceededException

Returns an estimate of the solution to the linear system (A - shift · I) · x = b. The solution is computed in-place.

Parameters:: a - Linear operator A of the system.; m - Preconditioner (can be null).; b - Right-hand side vector.; x - Vector to be updated with the solution. x should not be considered as an initial guess (more).; goodb - Usually false, except if x is expected to contain a large multiple of b.; shift - The amount to be subtracted to all diagonal elements of A.
Returns:: A reference to x (shallow copy).
Throws:: NullArgumentException - if one of the parameters is null.; NonSquareOperatorException - if a or m is not square.; DimensionMismatchException - if m, b or x have dimensions inconsistent with a.; NonSelfAdjointOperatorException - if getCheck() is true, and a or m is not self-adjoint.; NonPositiveDefiniteOperatorException - if m is not positive definite.; IllConditionedOperatorException - if a is ill-conditioned.; MaxCountExceededException - at exhaustion of the iteration count, unless a custom callback has been set at construction.

solveInPlace

public RealVector solveInPlace(RealLinearOperator a,
                               RealVector b,
                               RealVector x)
                        throws NullArgumentException,
                               NonSquareOperatorException,
                               DimensionMismatchException,
                               NonSelfAdjointOperatorException,
                               IllConditionedOperatorException,
                               MaxCountExceededException

Returns an estimate of the solution to the linear system A · x = b. The solution is computed in-place.

Overrides:: solveInPlace in class PreconditionedIterativeLinearSolver

Parameters:: a - Linear operator A of the system.; b - Right-hand side vector.; x - Vector to be updated with the solution. x should not be considered as an initial guess (more).
Returns:: A reference to x (shallow copy) updated with the solution.
Throws:: NullArgumentException - if one of the parameters is null.; NonSquareOperatorException - if a or m is not square.; DimensionMismatchException - if m, b or x have dimensions inconsistent with a.; NonSelfAdjointOperatorException - if getCheck() is true, and a or m is not self-adjoint.; IllConditionedOperatorException - if a is ill-conditioned.; MaxCountExceededException - at exhaustion of the iteration count, unless a custom callback has been set at construction.

Overview

Package

Class

Use

Tree

Deprecated

Index

Help

PREV CLASS NEXT CLASS

FRAMES NO FRAMES

SUMMARY: NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

org.apache.commons.math.linear Class SymmLQ

Preconditioning

Default stopping criterion

Iteration count

Initial guess of the solution

Exception context

References

SymmLQ

SymmLQ

getCheck

solve

solve

solve

solve

solve

solve

solveInPlace

solveInPlace

solveInPlace

org.apache.commons.math.linear
Class SymmLQ