#include <solvers.hpp>

Inheritance diagram for mfem::NNLSSolver:

Collaboration diagram for mfem::NNLSSolver:

Public Types
enum class	QRresidualMode { off , on , hybrid }
	Enumerated types of QRresidual mode. Options are 'off': the residual is calculated normally, 'on': the residual is calculated using the QR method, 'hybrid': the residual is calculated normally until we experience rounding errors, then the QR method is used. The default is 'hybrid', which should see the best performance. Recommend using 'hybrid' or 'off' only, since 'on' is computationally expensive. More...

Public Types inherited from mfem::Operator
enum	DiagonalPolicy { DIAG_ZERO , DIAG_ONE , DIAG_KEEP }
	Defines operator diagonal policy upon elimination of rows and/or columns. More...

enum	Type { ANY_TYPE , MFEM_SPARSEMAT , Hypre_ParCSR , PETSC_MATAIJ , PETSC_MATIS , PETSC_MATSHELL , PETSC_MATNEST , PETSC_MATHYPRE , PETSC_MATGENERIC , Complex_Operator , MFEM_ComplexSparseMat , Complex_Hypre_ParCSR , Complex_DenseMat , MFEM_Block_Matrix , MFEM_Block_Operator }
	Enumeration defining IDs for some classes derived from Operator. More...

Public Member Functions
	NNLSSolver ()

	~NNLSSolver ()

void	SetOperator (const Operator &op) override
	The operator must be a DenseMatrix.

void	Mult (const Vector &w, Vector &sol) const override
	Compute the non-negative least squares solution to the underdetermined system.

void	SetVerbosity (int v)
	Set verbosity. If set to 0: print nothing; if 1: just print results; if 2: print short update on every iteration; if 3: print longer update each iteration.

void	SetTolerance (real_t tol)
	Set the target absolute residual norm tolerance for convergence.

void	SetMinNNZ (int min_nnz)
	Set the minimum number of nonzeros required for the solution.

void	SetMaxNNZ (int max_nnz)
	Set the maximum number of nonzeros required for the solution, as an early termination condition.

void	SetResidualChangeTolerance (real_t tol)
	Set threshold on relative change in residual over nStallCheck_ iterations.

void	SetZeroTolerance (real_t tol)
	Set the magnitude of projected residual entries that are considered zero. Increasing this value relaxes solution constraints.

void	SetRHSDelta (real_t d)
	Set RHS vector constant shift, defining rhs_lb and rhs_ub in Solve().

void	SetOuterIterations (int n)
	Set the maximum number of outer iterations in Solve().

void	SetInnerIterations (int n)
	Set the maximum number of inner iterations in Solve().

void	SetStallCheck (int n)
	Set the number of iterations to use for stall checking.

void	SetNormalize (bool n)
	Set a flag to determine whether to call NormalizeConstraints().

void	SetQRResidualMode (const QRresidualMode qr_residual_mode)
	Set the residual calculation mode for the NNLS solver. See QRresidualMode enum above for details.

void	Solve (const Vector &rhs_lb, const Vector &rhs_ub, Vector &soln) const
	Solve the NNLS problem. Specifically, we find a vector soln, such that rhs_lb < mat*soln < rhs_ub is satisfied, where mat is the DenseMatrix input to SetOperator().

void	NormalizeConstraints (Vector &rhs_lb, Vector &rhs_ub) const
	Normalize the constraints such that the tolerances for each constraint (i.e. (UB - LB)/2) are equal. This seems to help the performance in most cases.

Public Member Functions inherited from mfem::Solver
	Solver (int s=0, bool iter_mode=false)
	Initialize a square Solver with size s.

	Solver (int h, int w, bool iter_mode=false)
	Initialize a Solver with height h and width w.

Public Member Functions inherited from mfem::Operator
void	InitTVectors (const Operator Po, const Operator Ri, const Operator *Pi, Vector &x, Vector &b, Vector &X, Vector &B) const
	Initializes memory for true vectors of linear system.

	Operator (int s=0)
	Construct a square Operator with given size s (default 0).

	Operator (int h, int w)
	Construct an Operator with the given height (output size) and width (input size).

int	Height () const
	Get the height (size of output) of the Operator. Synonym with NumRows().

int	NumRows () const
	Get the number of rows (size of output) of the Operator. Synonym with Height().

int	Width () const
	Get the width (size of input) of the Operator. Synonym with NumCols().

int	NumCols () const
	Get the number of columns (size of input) of the Operator. Synonym with Width().

virtual MemoryClass	GetMemoryClass () const
	Return the MemoryClass preferred by the Operator.

virtual void	MultTranspose (const Vector &x, Vector &y) const
	Action of the transpose operator: `y=A^t(x)`. The default behavior in class Operator is to generate an error.

virtual void	AddMult (const Vector &x, Vector &y, const real_t a=1.0) const
	Operator application: `y+=A(x)` (default) or `y+=a*A(x)`.

virtual void	AddMultTranspose (const Vector &x, Vector &y, const real_t a=1.0) const
	Operator transpose application: `y+=A^t(x)` (default) or `y+=a*A^t(x)`.

virtual void	ArrayMult (const Array< const Vector * > &X, Array< Vector * > &Y) const
	Operator application on a matrix: `Y=A(X)`.

virtual void	ArrayMultTranspose (const Array< const Vector * > &X, Array< Vector * > &Y) const
	Action of the transpose operator on a matrix: `Y=A^t(X)`.

virtual void	ArrayAddMult (const Array< const Vector * > &X, Array< Vector * > &Y, const real_t a=1.0) const
	Operator application on a matrix: `Y+=A(X)` (default) or `Y+=a*A(X)`.

virtual void	ArrayAddMultTranspose (const Array< const Vector * > &X, Array< Vector * > &Y, const real_t a=1.0) const
	Operator transpose application on a matrix: `Y+=A^t(X)` (default) or `Y+=a*A^t(X)`.

virtual Operator &	GetGradient (const Vector &x) const
	Evaluate the gradient operator at the point x. The default behavior in class Operator is to generate an error.

virtual void	AssembleDiagonal (Vector &diag) const
	Computes the diagonal entries into diag. Typically, this operation only makes sense for linear Operators. In some cases, only an approximation of the diagonal is computed.

virtual const Operator *	GetProlongation () const
	Prolongation operator from linear algebra (linear system) vectors, to input vectors for the operator. `NULL` means identity.

virtual const Operator *	GetRestriction () const
	Restriction operator from input vectors for the operator to linear algebra (linear system) vectors. `NULL` means identity.

virtual const Operator *	GetOutputProlongation () const
	Prolongation operator from linear algebra (linear system) vectors, to output vectors for the operator. `NULL` means identity.

virtual const Operator *	GetOutputRestrictionTranspose () const
	Transpose of GetOutputRestriction, directly available in this form to facilitate matrix-free RAP-type operators.

virtual const Operator *	GetOutputRestriction () const
	Restriction operator from output vectors for the operator to linear algebra (linear system) vectors. `NULL` means identity.

void	FormLinearSystem (const Array< int > &ess_tdof_list, Vector &x, Vector &b, Operator *&A, Vector &X, Vector &B, int copy_interior=0)
	Form a constrained linear system using a matrix-free approach.

void	FormRectangularLinearSystem (const Array< int > &trial_tdof_list, const Array< int > &test_tdof_list, Vector &x, Vector &b, Operator *&A, Vector &X, Vector &B)
	Form a column-constrained linear system using a matrix-free approach.

virtual void	RecoverFEMSolution (const Vector &X, const Vector &b, Vector &x)
	Reconstruct a solution vector x (e.g. a GridFunction) from the solution X of a constrained linear system obtained from Operator::FormLinearSystem() or Operator::FormRectangularLinearSystem().

void	FormSystemOperator (const Array< int > &ess_tdof_list, Operator *&A)
	Return in A a parallel (on truedofs) version of this square operator.

void	FormRectangularSystemOperator (const Array< int > &trial_tdof_list, const Array< int > &test_tdof_list, Operator *&A)
	Return in A a parallel (on truedofs) version of this rectangular operator (including constraints).

void	FormDiscreteOperator (Operator *&A)
	Return in A a parallel (on truedofs) version of this rectangular operator.

void	PrintMatlab (std::ostream &out, int n, int m=0) const
	Prints operator with input size n and output size m in Matlab format.

virtual void	PrintMatlab (std::ostream &out) const
	Prints operator in Matlab format.

virtual	~Operator ()
	Virtual destructor.

Type	GetType () const
	Return the type ID of the Operator class.

Additional Inherited Members
Public Attributes inherited from mfem::Solver
bool	iterative_mode
	If true, use the second argument of Mult() as an initial guess.

Protected Member Functions inherited from mfem::Operator
void	FormConstrainedSystemOperator (const Array< int > &ess_tdof_list, ConstrainedOperator *&Aout)
	see FormSystemOperator()

void	FormRectangularConstrainedSystemOperator (const Array< int > &trial_tdof_list, const Array< int > &test_tdof_list, RectangularConstrainedOperator *&Aout)
	see FormRectangularSystemOperator()

Operator *	SetupRAP (const Operator Pi, const Operator Po)
	Returns RAP Operator of this, using input/output Prolongation matrices Pi corresponds to "P", Po corresponds to "Rt".

Protected Attributes inherited from mfem::Operator
int	height
	Dimension of the output / number of rows in the matrix.

int	width
	Dimension of the input / number of columns in the matrix.

Detailed Description

Non-negative least squares (NNLS) solver class, for computing a vector with non-negative entries approximately satisfying an under-determined linear system.

Definition at line 1290 of file solvers.hpp.

Member Enumeration Documentation

◆ QRresidualMode

enum class mfem::NNLSSolver::QRresidualMode

strong

Enumerated types of QRresidual mode. Options are 'off': the residual is calculated normally, 'on': the residual is calculated using the QR method, 'hybrid': the residual is calculated normally until we experience rounding errors, then the QR method is used. The default is 'hybrid', which should see the best performance. Recommend using 'hybrid' or 'off' only, since 'on' is computationally expensive.

Enumerator
off
on
hybrid

Definition at line 1353 of file solvers.hpp.

Constructor & Destructor Documentation

◆ NNLSSolver()

mfem::NNLSSolver::NNLSSolver ( )

Definition at line 3579 of file solvers.cpp.

◆ ~NNLSSolver()

mfem::NNLSSolver::~NNLSSolver ( )

inline

Definition at line 1295 of file solvers.hpp.

Member Function Documentation

◆ Mult()

void mfem::NNLSSolver::Mult	(	const Vector &	w,
		Vector &	sol ) const

overridevirtual

Compute the non-negative least squares solution to the underdetermined system.

Implements mfem::Operator.

Definition at line 3641 of file solvers.cpp.

◆ NormalizeConstraints()

void mfem::NNLSSolver::NormalizeConstraints	(	Vector &	rhs_lb,
		Vector &	rhs_ub ) const

Normalize the constraints such that the tolerances for each constraint (i.e. (UB - LB)/2) are equal. This seems to help the performance in most cases.

Definition at line 3609 of file solvers.cpp.

◆ SetInnerIterations()

void mfem::NNLSSolver::SetInnerIterations ( int n )

inline

Set the maximum number of inner iterations in Solve().

Definition at line 1337 of file solvers.hpp.

◆ SetMaxNNZ()

void mfem::NNLSSolver::SetMaxNNZ ( int max_nnz )

inline

Set the maximum number of nonzeros required for the solution, as an early termination condition.

Definition at line 1319 of file solvers.hpp.

◆ SetMinNNZ()

void mfem::NNLSSolver::SetMinNNZ ( int min_nnz )

inline

Set the minimum number of nonzeros required for the solution.

Definition at line 1315 of file solvers.hpp.

◆ SetNormalize()

void mfem::NNLSSolver::SetNormalize ( bool n )

inline

Set a flag to determine whether to call NormalizeConstraints().

Definition at line 1343 of file solvers.hpp.

◆ SetOperator()

void mfem::NNLSSolver::SetOperator ( const Operator & op )

overridevirtual

The operator must be a DenseMatrix.

Implements mfem::Solver.

Definition at line 3587 of file solvers.cpp.

◆ SetOuterIterations()

void mfem::NNLSSolver::SetOuterIterations ( int n )

inline

Set the maximum number of outer iterations in Solve().

Definition at line 1334 of file solvers.hpp.

◆ SetQRResidualMode()

void mfem::NNLSSolver::SetQRResidualMode ( const QRresidualMode qr_residual_mode )

Set the residual calculation mode for the NNLS solver. See QRresidualMode enum above for details.

Definition at line 3600 of file solvers.cpp.

◆ SetResidualChangeTolerance()

void mfem::NNLSSolver::SetResidualChangeTolerance ( real_t tol )

inline

Set threshold on relative change in residual over nStallCheck_ iterations.

Definition at line 1323 of file solvers.hpp.

◆ SetRHSDelta()

void mfem::NNLSSolver::SetRHSDelta ( real_t d )

inline

Set RHS vector constant shift, defining rhs_lb and rhs_ub in Solve().

Definition at line 1331 of file solvers.hpp.

◆ SetStallCheck()

void mfem::NNLSSolver::SetStallCheck ( int n )

inline

Set the number of iterations to use for stall checking.

Definition at line 1340 of file solvers.hpp.

◆ SetTolerance()

void mfem::NNLSSolver::SetTolerance ( real_t tol )

inline

Set the target absolute residual norm tolerance for convergence.

Definition at line 1312 of file solvers.hpp.

◆ SetVerbosity()

void mfem::NNLSSolver::SetVerbosity ( int v )

inline

Set verbosity. If set to 0: print nothing; if 1: just print results; if 2: print short update on every iteration; if 3: print longer update each iteration.

Definition at line 1309 of file solvers.hpp.

◆ SetZeroTolerance()

void mfem::NNLSSolver::SetZeroTolerance ( real_t tol )

inline

Set the magnitude of projected residual entries that are considered zero. Increasing this value relaxes solution constraints.

Definition at line 1328 of file solvers.hpp.

◆ Solve()

void mfem::NNLSSolver::Solve	(	const Vector &	rhs_lb,
		const Vector &	rhs_ub,
		Vector &	soln ) const

Solve the NNLS problem. Specifically, we find a vector soln, such that rhs_lb < mat*soln < rhs_ub is satisfied, where mat is the DenseMatrix input to SetOperator().

The method by which we find the solution is the active-set method developed by Lawson and Hanson (1974) using lapack. To decrease rounding errors in the case of very tight tolerances, we have the option to compute the residual using the QR factorization of A, by res = b - Q*Q^T*b. This residual calculation results in less rounding error, but is more computationally expensive. To select whether to use the QR residual method or not, see set_qrresidual_mode above.

Definition at line 3689 of file solvers.cpp.

The documentation for this class was generated from the following files:

linalg/solvers.hpp
linalg/solvers.cpp

Public Types

Public Member Functions

Additional Inherited Members

Detailed Description

Member Enumeration Documentation

◆ QRresidualMode

Constructor & Destructor Documentation

◆ NNLSSolver()

◆ ~NNLSSolver()

Member Function Documentation

◆ Mult()

◆ NormalizeConstraints()

◆ SetInnerIterations()

◆ SetMaxNNZ()

◆ SetMinNNZ()

◆ SetNormalize()

◆ SetOperator()

◆ SetOuterIterations()

◆ SetQRResidualMode()

◆ SetResidualChangeTolerance()

◆ SetRHSDelta()

◆ SetStallCheck()

◆ SetTolerance()

◆ SetVerbosity()

◆ SetZeroTolerance()

◆ Solve()