linbox
Public Member Functions
DixonSolver< Ring, Field, RandomPrime, Method::DenseElimination > Class Template Reference

partial specialization of p-adic based solver with Dixon algorithm. More...

#include <dixon-solver-dense.h>

+ Collaboration diagram for DixonSolver< Ring, Field, RandomPrime, Method::DenseElimination >:

Public Member Functions

 DixonSolver (const Ring &r=Ring(), const RandomPrime &rp=RandomPrime())
 Constructor.
 
 DixonSolver (const Prime &p, const Ring &r=Ring(), const RandomPrime &rp=RandomPrime())
 Constructor, trying the prime p first.
 
template<class IMatrix , class Vector1 , class Vector2 >
SolverReturnStatus solve (Vector1 &num, Integer &den, const IMatrix &A, const Vector2 &b, const bool s=false, const int maxPrimes=5, const SolverLevel level=SL_LASVEGAS)
 Solve a linear system Ax=b over quotient field of a ring.
 
template<class IMatrix , class Vector1 , class Vector2 >
SolverReturnStatus solve (Vector1 &num, Integer &den, const IMatrix &A, const Vector2 &b, const int maxPrimes, const SolverLevel level=SL_LASVEGAS)
 overload so that the bool 'oldMatrix' argument is not accidentally set to true
 
template<class IMatrix , class Vector1 , class Vector2 >
SolverReturnStatus solveNonsingular (Vector1 &num, Integer &den, const IMatrix &A, const Vector2 &b, bool s=false, int maxPrimes=5)
 Solve a nonsingular, square linear system Ax=b over quotient field of a ring.
 
template<class IMatrix , class Vector1 , class Vector2 >
SolverReturnStatus solveSingular (Vector1 &num, Integer &den, const IMatrix &A, const Vector2 &b, int maxPrimes=5, const SolverLevel level=SL_LASVEGAS)
 Solve a general rectangular linear system Ax=b over quotient field of a ring.
 
template<class IMatrix , class Vector1 , class Vector2 >
SolverReturnStatus findRandomSolution (Vector1 &num, Integer &den, const IMatrix &A, const Vector2 &b, int maxPrimes=5, const SolverLevel level=SL_LASVEGAS)
 Find a random solution of the general linear system Ax=b over quotient field of a ring.
 
template<class IMatrix , class Vector1 , class Vector2 >
SolverReturnStatus monolithicSolve (Vector1 &num, Integer &den, const IMatrix &A, const Vector2 &b, Method::Dixon method)
 Big solving routine to perform random solving and certificate generation.
 

Detailed Description

template<class Ring, class Field, class RandomPrime>
class LinBox::DixonSolver< Ring, Field, RandomPrime, Method::DenseElimination >

partial specialization of p-adic based solver with Dixon algorithm.

See the following reference for details on this algorithm:

Bibliography:
  • John D. Dixon Exact Solution of linear equations using p-adic expansions. Numerische Mathematik, volume 40, pages 137-141, 1982.

Constructor & Destructor Documentation

◆ DixonSolver() [1/2]

template<class Ring , class Field , class RandomPrime >
DixonSolver ( const Ring r = Ring(),
const RandomPrime &  rp = RandomPrime() 
)
inline

Constructor.

Parameters
ra Ring, set by default
rpa RandomPrime generator, set by default

◆ DixonSolver() [2/2]

template<class Ring , class Field , class RandomPrime >
DixonSolver ( const Prime &  p,
const Ring r = Ring(),
const RandomPrime &  rp = RandomPrime() 
)
inline

Constructor, trying the prime p first.

Parameters
pa Prime
ra Ring, set by default
rpa RandomPrime generator, set by default

Member Function Documentation

◆ solve()

template<class Ring , class Field , class RandomPrime >
template<class IMatrix , class Vector1 , class Vector2 >
SolverReturnStatus solve ( Vector1 &  num,
Integer &  den,
const IMatrix &  A,
const Vector2 &  b,
const bool  s = false,
const int  maxPrimes = 5,
const SolverLevel  level = SL_LASVEGAS 
)

Solve a linear system Ax=b over quotient field of a ring.

Parameters
numVector of numerators of the solution
denThe common denominator. 1/den * num is the rational solution of Ax=b.
AMatrix of linear system
bRight-hand side of system
s
maxPrimesmaximum number of moduli to try
levellevel of certification to be used
Returns
status of solution. if (return != SS_FAILED), and (level >= SL_LASVEGAS), solution is guaranteed correct. SS_FAILED - all primes used were bad SS_OK - solution found. SS_INCONSISTENT - system appreared inconsistent. certificate is in lastCertificate if (level >= SL_CERTIFIED)

◆ solveNonsingular()

template<class Ring , class Field , class RandomPrime >
template<class IMatrix , class Vector1 , class Vector2 >
SolverReturnStatus solveNonsingular ( Vector1 &  num,
Integer &  den,
const IMatrix &  A,
const Vector2 &  b,
bool  s = false,
int  maxPrimes = 5 
)

Solve a nonsingular, square linear system Ax=b over quotient field of a ring.

Parameters
numVector of numerators of the solution
denThe common denominator. 1/den * num is the rational solution of Ax = b
AMatrix of linear system (it must be square)
bRight-hand side of system
sunused
maxPrimesmaximum number of moduli to try
Returns
status of solution :
  • SS_FAILED all primes used were bad;
  • SS_OK solution found, guaranteed correct;
  • SS_SINGULAR system appreared singular mod all primes.

◆ solveSingular()

template<class Ring , class Field , class RandomPrime >
template<class IMatrix , class Vector1 , class Vector2 >
SolverReturnStatus solveSingular ( Vector1 &  num,
Integer &  den,
const IMatrix &  A,
const Vector2 &  b,
int  maxPrimes = 5,
const SolverLevel  level = SL_LASVEGAS 
)

Solve a general rectangular linear system Ax=b over quotient field of a ring.

If A is known to be square and nonsingular, calling solveNonsingular is more efficient.

Parameters
numVector of numerators of the solution
denThe common denominator. 1/den * num is the rational solution of Ax = b
AMatrix of linear system
bRight-hand side of system
maxPrimesmaximum number of moduli to try
levellevel of certification to be used
Returns
status of solution. if (return != SS_FAILED), and (level >= SL_LASVEGAS), solution is guaranteed correct.
  • SS_FAILED all primes used were bad
  • SS_OK solution found.
  • SS_INCONSISTENT system appeared inconsistent. certificate is in lastCertificate if (level >= SL_CERTIFIED)

◆ findRandomSolution()

template<class Ring , class Field , class RandomPrime >
template<class IMatrix , class Vector1 , class Vector2 >
SolverReturnStatus findRandomSolution ( Vector1 &  num,
Integer &  den,
const IMatrix &  A,
const Vector2 &  b,
int  maxPrimes = 5,
const SolverLevel  level = SL_LASVEGAS 
)

Find a random solution of the general linear system Ax=b over quotient field of a ring.

Parameters
numVector of numerators of the solution
denThe common denominator. 1/den * num is the rational solution of Ax = b.
AMatrix of linear system
bRight-hand side of system
maxPrimesmaximum number of moduli to try
levellevel of certification to be used
Returns
status of solution. if (return != SS_FAILED), and (level >= SL_LASVEGAS), solution is guaranteed correct.
  • SS_FAILED all primes used were bad
  • SS_OK solution found.
  • SS_INCONSISTENT system appreared inconsistent. certificate is in lastCertificate if (level >= SL_CERTIFIED)

◆ monolithicSolve()

template<class Ring , class Field , class RandomPrime >
template<class IMatrix , class Vector1 , class Vector2 >
SolverReturnStatus monolithicSolve ( Vector1 &  num,
Integer &  den,
const IMatrix &  A,
const Vector2 &  b,
Method::Dixon  method 
)

Big solving routine to perform random solving and certificate generation.

Same arguments and return as findRandomSolution, except

Parameters
numVector of numerators of the solution
denThe common denominator. 1/den * num is the rational solution of Ax = b
A
b
randomSolutionparameter to determine whether to randomize or not (since solveSingular calls this function as well)
makeMinDenomCertdetermines whether a partial certificate for the minimal denominator of a rational solution is made
maxPrimes
level

When (randomSolution == true && makeMinDenomCert == true),

  • If (level == SL_MONTECARLO) this function has the same effect as calling findRandomSolution.
  • If (level >= SL_LASVEGAS && return == SS_OK), lastCertifiedDenFactor contains a certified factor of the min-solution's denominator.
  • If (level >= SL_CERTIFIED && return == SS_OK), lastZBNumer and lastCertificate are updated as well.

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