Belos Version of the Day

LSQR method (for linear systems and linear leastsquares problems). More...
#include <BelosLSQRSolMgr.hpp>
Public Member Functions  
LSQRSolMgr ()  
LSQRSolMgr (const Teuchos::RCP< LinearProblem< ScalarType, MV, OP > > &problem, const Teuchos::RCP< Teuchos::ParameterList > &pl)  
virtual  ~LSQRSolMgr () 
LSQR method (for linear systems and linear leastsquares problems).
ScalarType  The type of entries in the righthand side vector(s) and solution vector(s) . 
MV  The multivector type; the type of the solution vector(s) and righthand side vector(s). 
OP  The type of the matrix (and any preconditioner, if one is provided). 
LSQR (Paige and Saunders; see References) is an iterative method for solving linear leastsquares problems and linear systems. It can solve any of the following problems:
1. Solve for 2. Find that minimizes 3. Find that minimizes
The third problem above is the most general and includes the previous two. This is the problem LSQR actually solves. Here, is a userprovided positive real constant (the "damping parameter") which regularizes the problem so that it always has a bounded solution, even if does not have full rank.
In the words of Paige and Saunders: "The method is based on the GolubKahan bidiagonalization process. It is algebraically equivalent to applying MINRES to the normal equation[s] , but has better numerical properties, especially if is illconditioned."
LSQR has some special algorithmic properties:
1. It reduces (the twonorm of the residual) monotonically. 2. LSQR also computes a monotonically increasing estimate of the twonorm condition number of the matrix .
Property #2 makes LSQR useful for mixedprecision algorithms. If the matrix 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.
This LSQR implementation currently only supports realvalued (not complexvalued) 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 is not a limitation of the LSQR method itself, just of the current implementation. If there is sufficient interest, we can remedy this deficiency. For now, if you attempt to invoke the constructor when ScalarType
is complex, the constructor will throw an exception. This is why this class inherits from Details::RealSolverManager. LSQRSolMgr can still compile if ScalarType
is complex, but you will not be able to construct a LSQRSolMgr instance in that case, due to the aforementioned runtime error that the constructor raises. We do this so that the class will still compile, whether ScalarType is real or complex. This helps make SolverFactory valid to compile, whether ScalarType is real or complex.
If the linear problem to solve includes a preconditioner (in the LinearProblem object), then the leastsquares problem is solved for the preconditioned linear system. Preconditioning changes the leastsquares problem (in the sense of changing the norms), and the solution depends on the preconditioner in this sense. In the context of linear leastsquares 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 threepart 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 leastsquares sense.
C. C. Paige and M. A. Saunders, LSQR: An algorithm for sparse linear equations and sparse least squares, TOMS 8(1), 4371 (1982).
C. C. Paige and M. A. Saunders, Algorithm 583; LSQR: Sparse linear equations and leastsquares problems, TOMS 8(2), 195209 (1982).
See also the LSQR web page.
Definition at line 235 of file BelosLSQRSolMgr.hpp.
Belos::LSQRSolMgr< ScalarType, MV, OP, scalarTypeIsComplex >::LSQRSolMgr  (  )  [inline] 
Definition at line 243 of file BelosLSQRSolMgr.hpp.
Belos::LSQRSolMgr< ScalarType, MV, OP, scalarTypeIsComplex >::LSQRSolMgr  (  const Teuchos::RCP< LinearProblem< ScalarType, MV, OP > > &  problem, 
const Teuchos::RCP< Teuchos::ParameterList > &  pl  
)  [inline] 
Definition at line 246 of file BelosLSQRSolMgr.hpp.
virtual Belos::LSQRSolMgr< ScalarType, MV, OP, scalarTypeIsComplex >::~LSQRSolMgr  (  )  [inline, virtual] 
Definition at line 250 of file BelosLSQRSolMgr.hpp.