Belos Version of the Day
Belos::LSQRSolMgr< ScalarType, MV, OP > Class Template Reference

LSQR method (for linear systems and linear least-squares problems). More...

#include <BelosLSQRSolMgr.hpp>

Inheritance diagram for Belos::LSQRSolMgr< ScalarType, MV, OP >:
Inheritance graph
[legend]

List of all members.

Public Member Functions

Construct/Destroy
 LSQRSolMgr ()
 Empty constructor for LSQRSolMgr. This constructor takes no arguments and sets the default values for the solver. The linear problem must be passed in using setProblem() before solve() is called on this object. The solver values can be changed using setParameters().
 LSQRSolMgr (const Teuchos::RCP< LinearProblem< ScalarType, MV, OP > > &problem, const Teuchos::RCP< Teuchos::ParameterList > &pl)
 Basic constructor for LSQRSolMgr.
virtual ~LSQRSolMgr ()
 Destructor.
Accessor methods
const LinearProblem
< ScalarType, MV, OP > & 
getProblem () const
 Get current linear problem being solved for in this object.
Teuchos::RCP< const
Teuchos::ParameterList
getValidParameters () const
 Get a parameter list containing the valid parameters for this object.
Teuchos::RCP< const
Teuchos::ParameterList
getCurrentParameters () const
 Get a parameter list containing the current parameters for this object.
Teuchos::Array< Teuchos::RCP
< Teuchos::Time > > 
getTimers () const
 Return the timers for this object.
int getNumIters () const
 Iteration count from the last solve.
MagnitudeType getMatCondNum () const
 Estimated matrix condition number from the last solve.
MagnitudeType getMatNorm () const
 Estimated matrix Frobenius norm from the last solve.
MagnitudeType getResNorm () const
 Estimated residual norm from the last solve.
MagnitudeType getMatResNorm () const
 Estimate of $A^* r$ (residual vector $r$) from the last solve.
bool isLOADetected () const
 Whether a loss of accuracy was detected during the last solve.
Set methods
void setProblem (const Teuchos::RCP< LinearProblem< ScalarType, MV, OP > > &problem)
 Set the linear problem that needs to be solved.
void setParameters (const Teuchos::RCP< Teuchos::ParameterList > &params)
 Set the parameters the solver manager should use to solve the linear problem.
Reset methods
void reset (const ResetType type)
 reset the solver manager as specified by the ResetType, informs the solver manager that the solver should prepare for the next call to solve by resetting certain elements of the iterative solver strategy.
Solver application methods
ReturnType solve ()
 method that performs possibly repeated calls to the underlying linear solver's iterate() routine until the problem has been solved (as defined by the solver manager) or the solver manager decides to quit.
Overridden from Teuchos::Describable
std::string description () const
 Method to return description of the LSQR solver manager.

Detailed Description

template<class ScalarType, class MV, class OP>
class Belos::LSQRSolMgr< ScalarType, MV, OP >

LSQR method (for linear systems and linear least-squares problems).

Author:
Sarah Knepper and David Day
Template Parameters:
ScalarTypeThe type of entries in the right-hand side vector(s) $b$ and solution vector(s) $x$.
MVThe multivector type; the type of the solution vector(s) and right-hand side vector(s).
OPThe type of the matrix $A$ (and any preconditioner, if one is provided).
Warning:
Our LSQR implementation currently only compiles correctly for real-valued (not complex) ScalarType types. You may check whether ScalarType is complex using the following code:
   if (Teuchos::ScalarTraits<ScalarType>::isComplex) {
     // ScalarType is complex valued.
   } else {
     // ScalarType is real valued.
/  }
This may be fixed in future releases. It is not a limitation of the LSQR method itself, just of our current implementation. For now, you will not be able to compile any specialization of LSQRSolMgr for a complex-valued ScalarType type.

Algorithm

LSQR (Paige and Saunders; see References) is an iterative method for solving linear least-squares problems and linear systems. It can solve any of the following problems:

1. Solve $Ax=b$ for $x$ 2. Find $x$ that minimizes $\|Ax - b\|_2^2$ 3. Find $x$ that minimizes $\|Ax - b\|_2^2 + \lambda^2 \|x\|_2^2$

The third problem above is the most general and includes the previous two. This is the problem LSQR actually solves. Here, $\lambda$ is a user-provided positive real constant (the "damping parameter") which regularizes the problem so that it always has a bounded solution, even if $A$ does not have full rank.

In the words of Paige and Saunders: "The method is based on the Golub-Kahan bidiagonalization process. It is algebraically equivalent to applying MINRES to the normal equation[s] $(A^T A + \lambda 2I)x = A^T b$, but has better numerical properties, especially if $A$ is ill-conditioned."

LSQR has some special algorithmic properties:

1. It reduces $\|b - A x\|_2$ (the two-norm of the residual) monotonically. 2. LSQR also computes a monotonically increasing estimate of the two-norm condition number of the matrix $A$.

Property #2 makes LSQR useful for mixed-precision algorithms. If the matrix $A$ has condition number greater than the inverse of machine precision in the current working precision, one can reconstruct the problem to solve in the next higher precision and restart, possibly using the previous solution as an initial guess.

Preconditioning

If the linear problem to solve includes a preconditioner (in the LinearProblem object), then the least-squares problem is solved for the preconditioned linear system. Preconditioning changes the least-squares problem (in the sense of changing the norms), and the solution depends on the preconditioner in this sense. In the context of linear least-squares problems, "preconditioning" refers to the regularization matrix. In this solver, the regularization matrix is always a scalar multiple of the identity (standard form least squares).

A converged preconditioned residual norm suffices for convergence, but is not necessary. LSQR sometimes returns a larger relative residual norm than what would have been returned by a linear solver. For details on the stopping criteria, see the documentation of LSQRStatusTest, which implements the three-part stopping criterion recommended by Paige and Saunders.

Some Belos solvers implement detection of "loss of accuracy." That refers to the difference between convergence of the original linear system and convergence of the (left-)preconditioned linear system. LSQR does not implement detection of "loss of accuracy," because it is unclear what this means for linear least squares in general. This LSQR solves a possibly inconsistent system in a least-squares sense.

References

C. C. Paige and M. A. Saunders, LSQR: An algorithm for sparse linear equations and sparse least squares, TOMS 8(1), 43-71 (1982).

C. C. Paige and M. A. Saunders, Algorithm 583; LSQR: Sparse linear equations and least-squares problems, TOMS 8(2), 195-209 (1982).

See also the LSQR web page.

Definition at line 218 of file BelosLSQRSolMgr.hpp.


Constructor & Destructor Documentation

template<class ScalarType , class MV , class OP >
Belos::LSQRSolMgr< ScalarType, MV, OP >::LSQRSolMgr ( )

Empty constructor for LSQRSolMgr. This constructor takes no arguments and sets the default values for the solver. The linear problem must be passed in using setProblem() before solve() is called on this object. The solver values can be changed using setParameters().

Definition at line 458 of file BelosLSQRSolMgr.hpp.

template<class ScalarType , class MV , class OP >
Belos::LSQRSolMgr< ScalarType, MV, OP >::LSQRSolMgr ( const Teuchos::RCP< LinearProblem< ScalarType, MV, OP > > &  problem,
const Teuchos::RCP< Teuchos::ParameterList > &  pl 
)

Basic constructor for LSQRSolMgr.

This constructor accepts the LinearProblem to be solved in addition to a parameter list of options for the solver manager. Blocks of size > 1 are not implemented. The options are otherwise the BlockGmres options.

  • "Maximum Iterations" - the maximum number of iterations the LSQR solver is allowed to perform. Default: 1000
  • "Condition Limit" - a MagnitudeType specifying the upper limit of the estimate of the norm of Abar to decide convergence. Default: 0.
  • "Term Iter Max" - the number of consecutive successful iterations required before convergence is declared. Default: 1.
  • "Rel RHS Err" - an estimate of the error in the data defining the RHS. Default: 10*sqrt(eps).
  • "Rel Mat Err" - an estimate of the error in the data defining the matrix. Default: 10*sqrt(eps).
  • "Orthogonalization" - a string specifying the desired orthogonalization method. Default: "DGKS". See OrthoManagerFactory for a list of the available orthogonalization methods.
  • "Verbosity" - a sum of MsgType specifying the verbosity. Default: Belos::Errors
  • "Output Style" - a OutputType specifying the style of output. Default: Belos::General
  • "Lambda" - a MagnitudeType that specifies the regularization parameter.

Definition at line 467 of file BelosLSQRSolMgr.hpp.

template<class ScalarType , class MV , class OP >
virtual Belos::LSQRSolMgr< ScalarType, MV, OP >::~LSQRSolMgr ( ) [inline, virtual]

Destructor.

Definition at line 271 of file BelosLSQRSolMgr.hpp.


Member Function Documentation

template<class ScalarType , class MV , class OP >
const LinearProblem<ScalarType,MV,OP>& Belos::LSQRSolMgr< ScalarType, MV, OP >::getProblem ( ) const [inline, virtual]

Get current linear problem being solved for in this object.

Implements Belos::SolverManager< ScalarType, MV, OP >.

Definition at line 279 of file BelosLSQRSolMgr.hpp.

template<class ScalarType , class MV , class OP >
Teuchos::RCP< const Teuchos::ParameterList > Belos::LSQRSolMgr< ScalarType, MV, OP >::getValidParameters ( ) const [virtual]

Get a parameter list containing the valid parameters for this object.

Implements Belos::SolverManager< ScalarType, MV, OP >.

Definition at line 488 of file BelosLSQRSolMgr.hpp.

template<class ScalarType , class MV , class OP >
Teuchos::RCP<const Teuchos::ParameterList> Belos::LSQRSolMgr< ScalarType, MV, OP >::getCurrentParameters ( ) const [inline, virtual]

Get a parameter list containing the current parameters for this object.

Implements Belos::SolverManager< ScalarType, MV, OP >.

Definition at line 289 of file BelosLSQRSolMgr.hpp.

template<class ScalarType , class MV , class OP >
Teuchos::Array<Teuchos::RCP<Teuchos::Time> > Belos::LSQRSolMgr< ScalarType, MV, OP >::getTimers ( ) const [inline]

Return the timers for this object.

The timers are ordered as follows:

Definition at line 296 of file BelosLSQRSolMgr.hpp.

template<class ScalarType , class MV , class OP >
int Belos::LSQRSolMgr< ScalarType, MV, OP >::getNumIters ( ) const [inline, virtual]

Iteration count from the last solve.

Implements Belos::SolverManager< ScalarType, MV, OP >.

Definition at line 301 of file BelosLSQRSolMgr.hpp.

template<class ScalarType , class MV , class OP >
MagnitudeType Belos::LSQRSolMgr< ScalarType, MV, OP >::getMatCondNum ( ) const [inline]

Estimated matrix condition number from the last solve.

LSQR computes a running condition number estimate of the (preconditioned, if applicable) operator.

Definition at line 309 of file BelosLSQRSolMgr.hpp.

template<class ScalarType , class MV , class OP >
MagnitudeType Belos::LSQRSolMgr< ScalarType, MV, OP >::getMatNorm ( ) const [inline]

Estimated matrix Frobenius norm from the last solve.

LSQR computes a running Frobenius norm estimate of the (preconditioned, if applicable) operator.

Definition at line 317 of file BelosLSQRSolMgr.hpp.

template<class ScalarType , class MV , class OP >
MagnitudeType Belos::LSQRSolMgr< ScalarType, MV, OP >::getResNorm ( ) const [inline]

Estimated residual norm from the last solve.

LSQR computes the current residual norm. LSQR can solve inconsistent linear systems in a least-squares sense, so the residual norm may not necessarily be small, even if LSQR converges. (LSQR defines "convergence" to allow for possibly inconsistent systems. See the documentation of LSQRStatusTest for details.)

Definition at line 329 of file BelosLSQRSolMgr.hpp.

template<class ScalarType , class MV , class OP >
MagnitudeType Belos::LSQRSolMgr< ScalarType, MV, OP >::getMatResNorm ( ) const [inline]

Estimate of $A^* r$ (residual vector $r$) from the last solve.

Definition at line 334 of file BelosLSQRSolMgr.hpp.

template<class ScalarType , class MV , class OP >
bool Belos::LSQRSolMgr< ScalarType, MV, OP >::isLOADetected ( ) const [inline, virtual]

Whether a loss of accuracy was detected during the last solve.

The "loss of accuracy" concept is not yet implemented here, becuase it is unclear what this means for linear least squares. LSQR solves a possibly inconsistent linear system in a least-squares sense. "Loss of accuracy" would correspond to the difference between the preconditioned residual and the unpreconditioned residual.

Implements Belos::SolverManager< ScalarType, MV, OP >.

Definition at line 346 of file BelosLSQRSolMgr.hpp.

template<class ScalarType , class MV , class OP >
void Belos::LSQRSolMgr< ScalarType, MV, OP >::setProblem ( const Teuchos::RCP< LinearProblem< ScalarType, MV, OP > > &  problem) [inline, virtual]

Set the linear problem that needs to be solved.

Implements Belos::SolverManager< ScalarType, MV, OP >.

Definition at line 354 of file BelosLSQRSolMgr.hpp.

template<class ScalarType , class MV , class OP >
void Belos::LSQRSolMgr< ScalarType, MV, OP >::setParameters ( const Teuchos::RCP< Teuchos::ParameterList > &  params) [virtual]

Set the parameters the solver manager should use to solve the linear problem.

Implements Belos::SolverManager< ScalarType, MV, OP >.

Definition at line 575 of file BelosLSQRSolMgr.hpp.

template<class ScalarType , class MV , class OP >
void Belos::LSQRSolMgr< ScalarType, MV, OP >::reset ( const ResetType  type) [inline, virtual]

reset the solver manager as specified by the ResetType, informs the solver manager that the solver should prepare for the next call to solve by resetting certain elements of the iterative solver strategy.

Implements Belos::SolverManager< ScalarType, MV, OP >.

Definition at line 367 of file BelosLSQRSolMgr.hpp.

template<class ScalarType , class MV , class OP >
Belos::ReturnType Belos::LSQRSolMgr< ScalarType, MV, OP >::solve ( ) [virtual]

method that performs possibly repeated calls to the underlying linear solver's iterate() routine until the problem has been solved (as defined by the solver manager) or the solver manager decides to quit.

This method calls LSQRIter::iterate(), which will return either because a specially constructed status test evaluates to Passed or an std::exception is thrown.

A return from LSQRIter::iterate() signifies that either

  • the maximum number of iterations has been exceeded ... "return ::Unconverged".
  • ... or convergence ... "solver manager will return ::Converged" In either case the current solution is in the linear problem
Returns:
ReturnType specifying:
  • Converged: the linear problem was solved to the specification required by the solver manager.
  • Unconverged: the linear problem was not solved to the specification desired by the solver manager.

Implements Belos::SolverManager< ScalarType, MV, OP >.

Definition at line 881 of file BelosLSQRSolMgr.hpp.

template<class ScalarType , class MV , class OP >
std::string Belos::LSQRSolMgr< ScalarType, MV, OP >::description ( ) const [virtual]

Method to return description of the LSQR solver manager.

Reimplemented from Teuchos::Describable.

Definition at line 1024 of file BelosLSQRSolMgr.hpp.


The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines