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

#include <rational-solver.h>

Collaboration diagram for RationalSolver< Ring, Field, RandomPrime, DixonTraits >:

Public Member Functions
	RationalSolver (const Ring &r=Ring(), const RandomPrime &rp=RandomPrime(20))
	Constructor. More...

	RationalSolver (const Prime &p, const Ring &r=Ring(), const RandomPrime &rp=RandomPrime(20))
	Constructor, trying the prime p first. More...

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) const
	Solve a linear system `Ax=b` over quotient field of a ring. More...

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) const
	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) const
	Solve a nonsingular, square linear system `Ax=b` over quotient field of a ring. More...

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) const
	Solve a general rectangular linear system `Ax=b` over quotient field of a ring. More...

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) const
	Find a random solution of the general linear system `Ax=b` over quotient field of a ring. More...

template<class IMatrix , class Vector1 , class Vector2 >
SolverReturnStatus	monolithicSolve (Vector1 &num, Integer &den, const IMatrix &A, const Vector2 &b, bool makeMinDenomCert, bool randomSolution, int maxPrimes=5, const SolverLevel level=SL_LASVEGAS) const
	Big solving routine to perform random solving and certificate generation. More...

Detailed Description

template<class Ring, class Field, class RandomPrime>
class LinBox::RationalSolver< Ring, Field, RandomPrime, DixonTraits >

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

RationalSolver	(	const Ring &	r = `Ring()`,
		const RandomPrime &	rp = `RandomPrime( 20 )`
	)

inline

Constructor.

Parameters

r	a Ring, set by default
rp	a RandomPrime generator, set by default

RationalSolver	(	const Prime &	p,
		const Ring &	r = `Ring()`,
		const RandomPrime &	rp = `RandomPrime( 20 )`
	)

inline

Constructor, trying the prime p first.

Parameters

p	a Prime
r	a Ring, set by default
rp	a RandomPrime generator, set by default

Member Function Documentation

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`
	)		const

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

Parameters

num	Vector of numerators of the solution
den	The common denominator. 1/den * num is the rational solution of `Ax=b`.
A	Matrix of linear system
b	Right-hand side of system
s
maxPrimes	maximum number of moduli to try
level	level 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)

SolverReturnStatus solveNonsingular	(	Vector1 &	num,
		Integer &	den,
		const IMatrix &	A,
		const Vector2 &	b,
		bool	s = `false`,
		int	maxPrimes = `5`
	)		const

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

Parameters

num	Vector of numerators of the solution
den	The common denominator. `1/den * num` is the rational solution of `Ax = b`
A	Matrix of linear system (it must be square)
b	Right-hand side of system
s	unused
maxPrimes	maximum 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.

SolverReturnStatus solveSingular	(	Vector1 &	num,
		Integer &	den,
		const IMatrix &	A,
		const Vector2 &	b,
		int	maxPrimes = `5`,
		const SolverLevel	level = `SL_LASVEGAS`
	)		const

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

num	Vector of numerators of the solution
den	The common denominator. `1/den * num` is the rational solution of `Ax = b`
A	Matrix of linear system
b	Right-hand side of system
maxPrimes	maximum number of moduli to try
level	level 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)

SolverReturnStatus findRandomSolution	(	Vector1 &	num,
		Integer &	den,
		const IMatrix &	A,
		const Vector2 &	b,
		int	maxPrimes = `5`,
		const SolverLevel	level = `SL_LASVEGAS`
	)		const

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

Parameters

num	Vector of numerators of the solution
den	The common denominator. `1/den * num` is the rational solution of `Ax = b`.
A	Matrix of linear system
b	Right-hand side of system
maxPrimes	maximum number of moduli to try
level	level 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)

SolverReturnStatus monolithicSolve	(	Vector1 &	num,
		Integer &	den,
		const IMatrix &	A,
		const Vector2 &	b,
		bool	makeMinDenomCert,
		bool	randomSolution,
		int	maxPrimes = `5`,
		const SolverLevel	level = `SL_LASVEGAS`
	)		const

Big solving routine to perform random solving and certificate generation.

Same arguments and return as findRandomSolution, except

Parameters

num	Vector of numerators of the solution
den	The common denominator. `1/den * num` is the rational solution of `Ax = b`
A
b
randomSolution	parameter to determine whether to randomize or not (since solveSingular calls this function as well)
makeMinDenomCert	determines 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:

rational-solver.h
rational-solver.inl

Public Member Functions

Detailed Description

template<class Ring, class Field, class RandomPrime> class LinBox::RationalSolver< Ring, Field, RandomPrime, DixonTraits >

Constructor & Destructor Documentation

Member Function Documentation

template<class Ring, class Field, class RandomPrime>
class LinBox::RationalSolver< Ring, Field, RandomPrime, DixonTraits >