WiedemannSolver Class Template Reference

#include <wiedemann.h>

---

Detailed Description

template<class Field, class Vector>
class LinBox::WiedemannSolver< Field, Vector >

Linear system solvers based on Wiedemann's method. This class encapsulates all of the functionality for linear system solving with Wiedemann's algorithm. It includes the random solution and random nullspace element of Kaltofen and Saunders (1991), as well as the certificate of inconsistency of Giesbrecht, Lobo, and Saunders (1998).

Public Types
enum	ReturnStatus {   OK, FAILED, SINGULAR, INCONSISTENT,   BAD_PRECONDITIONER }
	{ OK, FAILED, SINGULAR, INCONSISTENT, BAD_PRECONDITIONER } More...
Public Member Functions
	WiedemannSolver (const Field &F, const SolverTraits< WiedemannTraits > &traits)
	WiedemannSolver (const Field &F, const SolverTraits< WiedemannTraits > &traits, typename Field::RandIter r)
ReturnStatus	solve (const BlackboxArchetype &A, Vector &x, const Vector &b, Vector &u)
ReturnStatus	solveNonsingular (const BlackboxArchetype &A, Vector &x, const Vector &b, bool useRandIter=false)
ReturnStatus	solveSingular (const BlackboxArchetype &A, Vector &x, const Vector &b, Vector &u, unsigned long r)
ReturnStatus	findRandomSolution (const BlackboxArchetype &A, Vector &x, const Vector &b, size_t r, const BlackboxArchetype *P=NULL, const BlackboxArchetype *Q=NULL)
ReturnStatus	findNullspaceElement (Vector &x, const BlackboxArchetype &A)
bool	certifyInconsistency (Vector &u, const BlackboxArchetype &A, const Vector &b)
const BlackboxArchetype *	precondition (const BlackboxArchetype &A, BlackboxArchetype *&PAQ, BlackboxArchetype *&P, BlackboxArchetype *&Q)

---

Member Enumeration Documentation

enum ReturnStatus

{ OK, FAILED, SINGULAR, INCONSISTENT, BAD_PRECONDITIONER } Enumeration values: OK  FAILED  SINGULAR  INCONSISTENT  BAD_PRECONDITIONER

---

Constructor & Destructor Documentation

WiedemannSolver (  const Field &  F, const SolverTraits< WiedemannTraits > &  traits )  [inline]

Constructor Parameters: F  Field over which to operate traits  SolverTraits} structure describing user options for the solver

WiedemannSolver (  const Field &  F, const SolverTraits< WiedemannTraits > &  traits, typename Field::RandIter  r )  [inline]

Constructor with a random iterator Parameters: F  Field over which to operate traits  SolverTraits} structure describing user options for the solver r  Random iterator to use for randomization

---

Member Function Documentation

ReturnStatus solve (  const BlackboxArchetype &  A, Vector &  x, const Vector &  b, Vector &  u )

Solve a system Ax=b, giving a random solution if the system is singular and consistent, and a certificate of inconsistency (if specified in traits parameter at construction time) otherwise. Parameters: A  Black box of linear system x  Vector in which to store solution b  Right-hand side of system u  Vector in which to store certificate of inconsistency Returns: Reference to solution vector

ReturnStatus solveNonsingular (  const BlackboxArchetype &  A, Vector &  x, const Vector &  b, bool  useRandIter = false )

Solve a nonsingular system Ax=b. This is a "Las Vegas" method, which makes use of randomization. It attempts to certify that the system solution is correct. It will only make one attempt to solve the system before giving up. Parameters: A  Black box of linear system x  Vector in which to store solution b  Right-hand side of system useRandIter  true if solveNonsingular should use a random iterator for the Krylov sequence computation; false if it should use the right-hand side Returns: Reference to solution vector

ReturnStatus solveSingular (  const BlackboxArchetype &  A, Vector &  x, const Vector &  b, Vector &  u, unsigned long  r )

Solve a general singular linear system. Parameters: A  Black box of linear system x  Vector in which to store solution b  Right-hand side of system u  Vector into which certificate of inconsistency will be stored r  Rank of A Returns: Return status

ReturnStatus findRandomSolution (  const BlackboxArchetype &  A, Vector &  x, const Vector &  b, size_t  r, const BlackboxArchetype *  P = NULL, const BlackboxArchetype *  Q = NULL )

Get a random solution to a singular system Ax=b of rank r with generic rank profile. Parameters: A  Black box of linear system x  Vector in which to store solution b  Right-hand side of system r  Rank of A P  Left preconditioner (NULL if none needed) Q  Right preconditioner (NULL if none needed) Returns: Return status

ReturnStatus findNullspaceElement (  Vector &  x, const BlackboxArchetype &  A )

Get a random element of the right nullspace of A. Parameters: x  Vector in which to store nullspace element A  Black box of which to find nullspace element r  Rank of A P  Left preconditioner, if applicable Q  Right preconditioner, if applicable

bool certifyInconsistency (  Vector &  u, const BlackboxArchetype &  A, const Vector &  b )

Get a certificate u that the given system Ax=b is inconsistent, if one can be found. Parameters: u  Vector in which to store certificate A  Black box for the linear system b  Right-hand side for the linear system r  Rank of A P  Left preconditioner, if applicable Returns: true if a certificate can be found in one iteration; u is filled in with that certificate; and false otherwise

const BlackboxArchetype* precondition (  const BlackboxArchetype &  A, BlackboxArchetype *&  PAQ, BlackboxArchetype *&  P, BlackboxArchetype *&  Q )

Given a blackbox archetype A, construct preconditioners P and Q of the type requested in the constructor and return the preconditioned matrix PAQ. Returns a pointer to A and leaves P and Q untouched if no preconditioning was requested. Parameters: A  Black box to precondition PAQ  Pointer to preconditioned matrix P  Pointer to left preconditioner Q  Pointer to right preconditioner

---