linbox
Data Structures | Enumerations
p-adic lifting for linear system solutions.

interface for solving linear system by p-adic lifting technique over the quotient field of a ring. More...

Data Structures

class  RationalSolver< Ring, Field, RandomPrime, MethodTraits >
 Interface for the different specialization of p-adic lifting based solvers. More...
 

Enumerations

enum  SolverReturnStatus
 define the different return status of the p-adic based solver's computation.
 
enum  SolverLevel
 Define the different strategy which can be used in the p-adic based solver. More...
 

Detailed Description

interface for solving linear system by p-adic lifting technique over the quotient field of a ring.

i.e. solution over the rational for an integer linear system.

Headers
#include "linbox/algorithms/rational-solver.h>

See the following reference for details on this algorithm:

Bibliography:
  • Robert T. Moenck and John H. Carter Approximate algorithms to derive exact solutions to system of linear equations. In Proc. EUROSAM'79, volume 72 of Lectures Note in Computer Science, pages 65-72, Berlin-Heidelberger-New York, 1979. Springer-Verlag.
  • John D. Dixon Exact Solution of linear equations using p-adic expansions. Numerische Mathematik, volume 40, pages 137-141, 1982.

Enumeration Type Documentation

enum SolverLevel

Define the different strategy which can be used in the p-adic based solver.

Used to determine what level of solving should be done:

  • Monte Carlo: Try to solve if possible, but result is not guaranteed. In any case a 0 denominator should not be returned.
  • Las Vegas : Result should be guaranteed correct.
  • Certified : Additionally, provide certificates that the result returned is correct.
    • if the return value is SS_INCONSISTENT, this means lastCertificate satisfies $lC \cdot A = 0$ and $lC \cdot b \neq 0 $
    • if diophantine solving was called and the return value is SS_OK, this means lastCertificate satisfies $ \mathrm{den}(lC \cdot A) = 1, \mathrm{den}(lC \cdot b) = \mathrm{den}(answer) $