Main Page | Modules | Namespace List | Class Hierarchy | Class List | File List | Namespace Members | Class Members | File Members | Related Pages

LinBox Namespace Reference


Detailed Description

linbox/field/ntl-lzz_pX.h Daniel Roche, August 2005


Classes

class  BlackboxBlockContainerBase
 A base class for BlackboxBlockContainer. The primary member function is begin(). More...

class  BlackboxContainerBase
 A base class for BlackboxContainer. The primary member function is begin(). More...

class  BlackboxContainerSymmetric
 See base class for doc. More...

class  BlackboxContainerSymmetrize
 Symmetrizing iterator (for rank computations). More...

class  BlackboxContainer
 Limited doc so far. More...

class  BlasMatrixDomainMulAdd
class  BlockLanczosSolver
 Block Lanczos iteration. More...

class  BlockMasseyDomain
 Compute the linear generator of a sequence of matrices. More...

class  DenseContainer
 Limited doc so far. More...

class  DiophantineSolver
 DiophantineSolver<QSolver> creates a diophantine solver using a QSolver to generate rational solutions. More...

class  Eliminator
class  GaussDomain
 Repository of functions for rank by elimination on sparse matrices. More...

class  LABlockLanczosSolver
class  LanczosSolver
 Solve a linear system using the conjugate Lanczos iteration. More...

class  LastInvariantFactor
 This is used in a Smith Form algorithm. More...

class  MasseyDomain
 Berlekamp/Massey algorithm. More...

class  MatrixRank
class  MGBlockLanczosSolver
 Block Lanczos iteration. More...

class  OneInvariantFactor
 Limited doc so far. More...

struct  RationalRemainder
 Chinese remainder of rationals. More...

class  RationalReconstruction
 Limited doc so far. Used, for instance, after LiftingContainer. More...

class  RationalSolver
 interface for the different specialization of p-adic lifting based solvers. More...

class  RationalSolver< Ring, Field, RandomPrime, WiedemannTraits >
 partial specialization of p-adic based solver with Wiedemann algorithm More...

class  RationalSolver< Ring, Field, RandomPrime, BlockWiedemannTraits >
 partial specialization of p-adic based solver with block Wiedemann algorithm More...

class  RationalSolver< Ring, Field, RandomPrime, DixonTraits >
 partial specialization of p-adic based solver with Dixon algorithm More...

class  RationalSolver< Ring, Field, RandomPrime, NumericalTraits >
 partial specialization of p-adic based solver with a hybrid Numeric/Symbolic computation More...

class  SmithFormBinary
 Compute Smith form. More...

class  SmithFormIliopoulos
 This is Iliopoulos' algorithm do diagonalize. More...

class  SmithFormLocal
 Smith normal form (invariant factors) of a matrix over a local ring. More...

class  PowerGaussDomain
 Repository of functions for rank modulo a prime power by elimination on sparse matrices. More...

class  VectorFraction
 VectorFraction<Domain> is a vector of rational elements with common reduced denominator. Here Domain is a ring supporting the gcd, eg NTL_ZZ or PID_integer For compatability with the return type of rationalSolver, it allows conversion from/to std::vector<std::pair<Domain::Element> >. All functions will return the fraction in reduced form, calling reduce() if necessary. More...

class  WiedemannSolver
 Linear system solvers based on Wiedemann's method. More...

class  BlackboxArchetype
 showing the member functions provided by all blackbox matrix classes. More...

class  BlackboxInterface
 This blackbox base class exists solely to aid documentation organization. More...

class  BlasBlackbox
 dense matrix representation for BLAS based elimination. More...

class  Butterfly
 Switching Network based BlackBox Matrix. A good preconditioner. More...

struct  Companion
 Companion matrix of a monic polynomial. More...

class  Compose
 General case. More...

class  Compose< _Blackbox, _Blackbox >
 specialization for _Blackbox1 = _Blackbox2 More...

class  ComposeTraits
 used in ..., for example More...

class  ComposeTraits< DenseMatrix< Field > >
 used in smith-binary, for example More...

class  DenseMatrix
 Blackbox interface to dense matrix representation. More...

class  DenseMatrixFactory
class  Diagonal
 Random diagonal matrices are used heavily as preconditioners. More...

class  Diagonal< _Field, VectorCategories::DenseVectorTag >
 Specialization of Diagonal for application to dense vectors. More...

class  Diagonal< Field, VectorCategories::SparseSequenceVectorTag >
 Specialization of Diagonal for application to sparse sequence vectors. More...

class  Diagonal< Field, VectorCategories::SparseAssociativeVectorTag >
 Specialization of Diagonal for application to sparse associative vectors. More...

class  Dif
 Blackbox of a difference: C := A - B, i.e. Cx = Ax - Bx. More...

class  DirectSum
 If C = DirectSum(A, B) and y = xA and z = wB, then (y,z) = (x,w)C. More...

class  BlackboxFactory
 A tool for computations with integer and rational matrices. More...

class  Frobenius
 template More...

class  Hilbert
 Example of a blackbox that is space efficient, though not time efficient. More...

class  Inverse
 A Blackbox for the inverse. Not efficient if many applications are used. More...

class  MoorePenrose
 Generalized inverse of a blackbox. Efficiency concerns when many applications are used. More...

class  Hankel
 template More...

class  Sylvester
 template More...

class  NullMatrix
 This is a representation of the 0 by 0 empty matrix which does not occupy memory. It has it's uses! More...

class  Permutation
 size is n. More...

class  PolynomialBB
 represent the matrix P(A) where A is a blackbox and P a polynomial More...

class  ScalarMatrix
 Blackbox for aI. Use particularly for representing 0 and I. More...

class  SparseMatrix
 vector of sparse rows. More...

class  SparseMatrixFactory
class  Submatrix
class  Submatrix< Blackbox, VectorCategories::DenseVectorTag >
class  Submatrix< DenseMatrix< _Field >, VectorCategories::DenseVectorTag >
class  Sum
 blackbox of a matrix sum without copying. More...

class  Toeplitz
 This is the blackbox representation of a Toeplitz matrix. More...

class  Toeplitz< typename _PField::CoeffField, _PField >
class  Transpose
 transpose matrix without copying. More...

class  TriplesBB
 wrapper for NAG Sparse Matrix format. More...

class  ZeroOne
 Time and space efficient representation of sparse {0,1}-matrices. More...

class  ElementAbstract
 Abstract element base class, a technicality. More...

class  ElementArchetype
 Field and Ring element interface specification and archetypical instance class. More...

class  ElementEnvelope
 Adaptor from archetypical interface to abstract interface, a technicality. More...

class  GivPolynomial
 Polynomials over a domain. More...

class  GMPRationalElement
 elements of GMP_Rationals. More...

class  FFLAS
 BLAS for matrices over finite fields. More...

class  FFPACK
 Set of elimination based routines for dense linear algebra with matrices over finite prime field of characteristic less than 2^26. More...

class  FieldAbstract
 field base class. More...

class  FieldArchetype
 field specification and archetypical instance. More...

class  FieldEnvelope
 Derived class used to implement the field archetype. More...

class  FieldInterface
 This field base class exists solely to aid documentation organization. More...

struct  GivaroField
 give LinBox fields an allure of Givaro Fields More...

class  GivaroExtension
class  GivaroExtension< GivaroGfq >
class  GivaroGfq
class  GivaroMontg
 wrapper of Givaro's Montgomery<Std32>. More...

class  GivaroZpz
 wrapper of Givaro's ZpzDom. More...

class  NoHomError
 Error object for attempt to establish a Hom that cannot exist. More...

class  Hom
 map element of source ring(field) to target ring More...

class  LidiaGfq
 defines the Galois Field GF(pk). More...

struct  Local2_32
 Fast arithmetic mod 2^32, including gcd. More...

class  ModularBalance< int >
 template <> More...

class  Modular< int32 >
 template <> More...

class  Modular< int8 >
 Specialization of Modular to signed 8 bit element type with efficient dot product. More...

class  Modular< double >
 template <> More...

class  Modular< int16 >
 Specialization of Modular to short element type with efficient dot product. More...

class  Modular
 Prime fields of positive characteristic implemented directly in LinBox. More...

class  Modular< uint8 >
 Allows compact storage when the modulus is less than 2^8. More...

class  Modular< uint16 >
 Specialization of class Modular for uint16 element type. More...

class  Modular< uint32 >
 Specialization of class Modular for uint32 element type. More...

class  UnparametricRandIter< NTL::GF2E >
 template<> More...

struct  NTL_zz_p
 long ints modulo a positive integer. More...

class  NTL_zz_pX
struct  NTL_PID_zz_p
 extend Wrapper of zz_p from NTL. Add PID functions More...

class  NTL_ZZ_pX
class  ParamFuzzy
class  PIRModular< int >
 template <> More...

class  PIRModular< int32 >
 template <> More...

class  PIR_ntl_ZZ_p
 extend Wrapper of ZZ_p from NTL. Add PIR functions More...

struct  Rebind
 used in support of Hom, MatrixHom More...

class  MatrixArchetype
 Directly-represented matrix archetype. More...

class  indexDomain
class  DenseRowsMatrix
class  DenseSubmatrix
class  DenseMatrixBase
struct  MatrixCategories
 For specializing matrix arithmetic. More...

class  MVProductDomain
 Helper class to allow specializations of certain matrix-vector products. More...

class  MatrixDomain
 Class of matrix arithmetic functions. More...

class  InvalidMatrixInput
class  FieldIO
 Dummy field for conceptually unclear io. More...

class  SparseMatrixBase
class  TransposeMatrix
class  RandIterAbstract
class  RandIterArchetype
 Random field element generator archetype. More...

class  RandIterEnvelope
class  GF2RandIter
class  GmpRandomPrime
 generating random prime integers, using the gmp library. More...

class  ModularBalanceRandIter
class  ModularRandIter
class  NonzeroRandIter
class  ParamFuzzyRandIter
class  UnparametricRandIter
class  RingAbstract
 Abstract ring base class. More...

class  RingArchetype
 specification and archetypic instance for the ring interface More...

class  RingEnvelope
 implement the ring archetype to minimize code bloat. More...

class  GivPolynomialRing
 polynomials with coefficients modulo some power of two More...

class  PowerOfTwoModular
 Ring of elements modulo some power of two. More...

struct  PowerOfTwoModular::RandIter
class  RingInterface
 This ring base class exists solely to aid documentation organization. More...

struct  Method
 Method specifiers for controlling algorithm choice. More...

struct  SolverTraits
class  SolveFailed
class  InconsistentSystem
class  BooleanSwitch
class  BooleanSwitchFactory
class  CekstvSwitch
class  CekstvSwitchFactory
class  ActivityState
 used by commentator More...

class  Commentator
 give information to user during runtime More...

class  MessageClass
class  LinboxError
class  FieldAXPY
class  MatrixStreamReader
class  PrimeStream
class  BaseTimer
 base for class RealTimer; class SysTimer; class UserTimer; More...

class  BitVector
class  ReverseVector
class  Sparse_Vector
 vector< Pair<T> > and actualsize More...

class  VectorStream
 Vector factory. More...

class  ConstantVectorStream
class  RandomDenseStream
class  RandomSparseStream
class  StandardBasisStream
class  Subiterator
 Subvector iterator class provides striding iterators. More...

class  Subvector
 Dense subvector. More...

struct  VectorCategories
 List of vector categories. More...

struct  VectorTraits
class  RawVector

Butterfly

Butterfly preconditioner and supporting function

std::vector< bool > setButterfly (const std::vector< bool > &x, size_t j=0)

class RR.

Rational number field. This field is provided as a convenience in a few places. Use with caution because expression swell.

This specialization allows the UnparametricField} template class to be used to wrap NTL's RR class as a LinBox field.

template<> NTL::RR & UnparametricField< NTL::RR >::init (NTL::RR &x, const integer &y) const
template<> integerUnparametricField< NTL::RR >::convert (integer &x, const NTL::RR &y) const
template<> NTL::RR & UnparametricField< NTL::RR >::inv (NTL::RR &x, const NTL::RR &y) const
template<> bool UnparametricField< NTL::RR >::isZero (const NTL::RR &x) const
template<> bool UnparametricField< NTL::RR >::isOne (const NTL::RR &x) const
template<> NTL::RR & UnparametricField< NTL::RR >::invin (NTL::RR &x) const
template<> std::ostream & UnparametricField< NTL::RR >::write (std::ostream &os) const
template<> NTL::RR & UnparametricRandIter< NTL::RR >::random (NTL::RR &elt) const

NTL_ZZ_p

Arbitrary precision integers modulus a positive integer.

While NTL allows any integer to serve as the modulus, only prime moduli yield fields. Therefore, while arthmetic operations may be valid for any modulus, only prime moduli are supported in this implementation. The primality of the modulus will not be checked, so it is the programmer's responsibility to supply a prime modulus. These specializations allow the UnparametricField} template class to be used to wrap NTL's { ZZ} class as a LinBox field.

template<>  UnparametricField< NTL::ZZ_p >::UnparametricField (integer q, size_t e)
template<> NTL::ZZ_p & UnparametricField< NTL::ZZ_p >::init (NTL::ZZ_p &x, const integer &y) const
 Initialization of field element from an integer. Behaves like C++ allocator construct. This function assumes the output field element x has already been constructed, but that it is not already initialized. This done by converting to a std::string : inefficient but correct.


[NOHEADER]

template<> integerUnparametricField< NTL::ZZ_p >::convert (integer &x, const NTL::ZZ_p &y) const
template<> integerUnparametricField< NTL::ZZ_p >::cardinality (integer &c) const
template<> integerUnparametricField< NTL::ZZ_p >::characteristic (integer &c) const
template<> NTL::ZZ_p & UnparametricField< NTL::ZZ_p >::inv (NTL::ZZ_p &x, const NTL::ZZ_p &y) const
template<> bool UnparametricField< NTL::ZZ_p >::isZero (const NTL::ZZ_p &x) const
template<> bool UnparametricField< NTL::ZZ_p >::isOne (const NTL::ZZ_p &x) const
template<> NTL::ZZ_p & UnparametricField< NTL::ZZ_p >::invin (NTL::ZZ_p &x) const
template<> std::ostream & UnparametricField< NTL::ZZ_p >::write (std::ostream &os) const
template<>  UnparametricRandIter< NTL::ZZ_p >::UnparametricRandIter (const UnparametricField< NTL::ZZ_p > &F, const integer &size, const integer &seed)
 Constructor for random field element generator.

template<> NTL::ZZ_p & UnparametricRandIter< NTL::ZZ_p >::random (NTL::ZZ_p &x) const
 Random field element creator.


Typedefs

typedef UnparametricField<
integer
GMP_Integers
typedef NTL_ZZRandIter RandIter
 the integer ring. class NTL_ZZ {

typedef Integer integer
 This is a representation of arbitrary integers.

typedef signed __LINBOX_INT32 int32
typedef unsigned __LINBOX_INT32 uint32

Enumerations

enum  SolverReturnStatus
 define the different return status of the p-adic based solver's computation. More...

enum  SolverLevel
 define the different strategy which can be used in the p-adic based solver. More...

enum  FileFormatTag
 tags for SparseMatrixBase::read() and write()


Functions

template<class Blackbox, class MyMethod> Blackbox::Field::Element & lif_cra_det (typename Blackbox::Field::Element &d, const Blackbox &A, const RingCategories::IntegerTag &tag, const MyMethod &M)
 Compute the determinant of A over the integers.

template<class Ring, class ItMatrix> void SpecialBound (const Ring &R, typename Ring::Element &H_col_sqr, typename Ring::Element &short_col_sqr, const ItMatrix &A)
template<class Ring, class ItMatrix> void ApplyBound (const Ring &R, typename Ring::Element &bound_A, const ItMatrix &A)
template<class Domain> void reduceIn (Domain &D, std::pair< typename Domain::Element, typename Domain::Element > &frac)
template<class Domain, class Vector> void vectorGcdIn (typename Domain::Element &result, Domain &D, Vector &v)
template<class Domain, class Vector> Domain::Element vectorGcd (Domain &D, Vector &v)
template<class Domain, class IMatrix> void create_MatrixQadic (const Domain &D, const IMatrix &M, double *chunks, size_t num_chunks, const integer &shift=0)
 split an integer matrix into a padic chunk representation

template<class Domain, class Vector> void create_VectorQadic (const Domain &D, const Vector &V, double *chunks, size_t num_chunks)
 split an integer vector into a padic chunk representation

template<class Domain, class Vector> void create_VectorQadic_32 (const Domain &D, const Vector &V, double *chunks, size_t num_chunks)
 split an integer vector into a padic chunk representation

template<> NTL::zz_p & UnparametricField< NTL::zz_p >::init (NTL::zz_p &x, const integer &y) const
template<> integerUnparametricField< NTL::zz_p >::convert (integer &x, const NTL::zz_p &y) const
template<> integerUnparametricField< NTL::zz_p >::cardinality (integer &c) const
template<> integerUnparametricField< NTL::zz_p >::characteristic (integer &c) const
template<> NTL::zz_p & UnparametricField< NTL::zz_p >::inv (NTL::zz_p &x, const NTL::zz_p &y) const
template<> bool UnparametricField< NTL::zz_p >::isZero (const NTL::zz_p &x) const
template<> bool UnparametricField< NTL::zz_p >::isOne (const NTL::zz_p &x) const
template<> NTL::zz_p & UnparametricField< NTL::zz_p >::invin (NTL::zz_p &x) const
template<> std::ostream & UnparametricField< NTL::zz_p >::write (std::ostream &os) const
template<>  UnparametricRandIter< NTL::zz_p >::UnparametricRandIter (const UnparametricField< NTL::zz_p > &F, const integer &size, const integer &seed)
 Constructor for random field element generator.

template<> NTL::zz_p & UnparametricRandIter< NTL::zz_p >::random (NTL::zz_p &x) const
 Random field element creator.

template<> std::ostream & UnparametricField< NTL::zz_pX >::write (std::ostream &os) const
template<class Element2> Element & init (Element &x, const Element2 &y) const
 Init x from y.

Element & init (Element &x, const Element &y) const
 Init from a NTL::ZZ.

Element & init (Element &x, const int64 &y) const
 Init from an int64.

Element & init (Element &x, const uint64 &y) const
 Init from a uint64.

Element & init (Element &x, const integer &y) const
 I don't know how to init from integer efficiently.

Element & assign (Element &x, const Element &y) const
 x = y.

bool areEqual (const Element &x,const Element &y) const
 Test if x == y.

bool isZero (const Element &x) const
 Test if x == 0.

bool isOne (const Element &x) const
 Test if x == 1.

Element & add (Element &x, const Element &y, const Element &z) const
 return x = y + z

Element & sub (Element &x, const Element &y, const Element &z) const
 return x = y - z

template<class Int> Element & mul (Element &x, const Element &y, const Int &z) const
 return x = y * z

Element & div (Element &x, const Element &y, const Element &z) const
 If z divides y, return x = y / z, otherwise, throw an exception.

Element & inv (Element &x, const Element &y) const
 If y is a unit, return x = 1 / y, otherwsie, throw an exception.

Element & neg (Element &x, const Element &y) const
 return x = -y;

template<class Int> Element & axpy (Element &r, const Element &a, const Int &x, const Element &y) const
 return r = a x + y

Element & addin (Element &x, const Element &y) const
 return x += y;

Element & subin (Element &x, const Element &y) const
 return x -= y;

template<class Int> Element & mulin (Element &x, const Int &y) const
 return x *= y;

Element & divin (Element &x, const Element &y) const
 If y divides x, return x /= y, otherwise throw an exception.

Element & invin (Element &x)
 If x is a unit, x = 1 / x, otherwise, throw an exception.

Element & negin (Element &x) const
 return x = -x;

template<class Int> Element & axpyin (Element &r, const Element &a, const Int &x) const
 return r += a x

std::ostream & write (std::ostream &out, const Element &y) const
 out << y;

std::istream & read (std::istream &in, Element &x) const
 read x from istream in

bool isUnit (const Element &x) const
 Test if x is a unit.

Element & gcd (Element &g, const Element &a, const Element &b) const
 return g = gcd (a, b)

Element & gcdin (Element &g, const Element &b) const
 return g = gcd (g, b)

Element & xgcd (Element &g, Element &s, Element &t, const Element &a, const Element &b) const
 g = gcd(a, b) = a*s + b*t. The coefficients s and t are defined according to the standard Euclidean algorithm applied to |a| and |b|, with the signs then adjusted according to the signs of a and b.

Element & lcm (Element &c, const Element &a, const Element &b) const
 c = lcm (a, b)

Element & lcmin (Element &l, const Element &b) const
 l = lcm (l, b)

Element & sqrt (Element &x, const Element &y) const
 x = floor ( sqrt(y)).

long reconstructRational (Element &a, Element &b, const Element &x, const Element &m, const Element &a_bound, const Element &b_bound) const
 Requires 0 <= x < m, m > 2 * a_bound * b_bound, a_bound >= 0, b_bound > 0 This routine either returns 0, leaving a and b unchanged, or returns 1 and sets a and b so that (1) a = b x (mod m), (2) |a| <= a_bound, 0 < b <= b_bound, and (3) gcd(m, b) = gcd(a, b).

Element & quo (Element &q, const Element &a, const Element &b) const
 q = floor (x/y);

Element & rem (Element &r, const Element &a, const Element &b) const
 r = remindar of a / b

Element & quoin (Element &a, const Element &b) const
 a = quotient (a, b)

Element & remin (Element &x, const Element &y) const
 a = quotient (a, b)

void quoRem (Element &q, Element &r, const Element &a, const Element &b) const
 q = [a/b], r = a - b*q |r| < |b|, and if r != 0, sign(r) = sign(b)

bool isDivisor (const Element &a, const Element &b) const
 Test if b | a.

long compare (const Element &a, const Element &b) const
Element & abs (Element &x, const Element &a) const
template<> std::ostream & UnparametricField< NTL::ZZ_pX >::write (std::ostream &os) const
template<class Blackbox, class Polynomial, class MyMethod> Polynomial & charpoly (Polynomial &P, const Blackbox &A, const MyMethod &M)
 ...using an optional Method parameter

template<class Blackbox, class Polynomial> Polynomial & charpoly (Polynomial &P, const Blackbox &A)
 ...using default method

template<class Polynomial, class Blackbox> Polynomial & charpoly (Polynomial &P, const Blackbox &A, const RingCategories::ModularTag &tag, const Method::BlasElimination &M)
 Compute the characteristic polynomial over Zp.

template<class Polynomial, class Blackbox> Polynomial & charpoly (Polynomial &P, const Blackbox &A, const RingCategories::ModularTag &tag, const Method::Blackbox &M)
template<class Blackbox, class MyMethod> Blackbox::Field::Element & det (typename Blackbox::Field::Element &d, const Blackbox &A, const MyMethod &M)
 Compute the determinant of A.

template<class Field> Field::Element & detin (typename Field::Element &d, BlasBlackbox< Field > &A)
 A will be modified.

template<class BB> BB::Field::Element & getEntry (typename BB::Field::Element &x, const BB &A, const size_t i, const size_t j)
 Getting the i,j entry of the blackbox.

template<class BB> BB::Field::Element & getEntry (typename BB::Field::Element &x, const BB &A, const size_t i, const size_t j, const Method::Hybrid &m)
 our best guess

template<class BB> BB::Field::Element & getEntry (typename BB::Field::Element &x, const BB &A, const size_t i, const size_t j, const Method::Elimination &m)
 our elimination (a fake in this case)

template<class Blackbox> Blackbox::Field::Element & getEntry (typename Blackbox::Field::Element &res, const Blackbox &A, const size_t i, const size_t j, const Method::Blackbox &m)
template<class Blackbox, class MyMethod> bool isPositiveDefinite (const Blackbox &A, const MyMethod &M)
template<class Blackbox, class MyMethod> bool isPositiveSemiDefinite (const Blackbox &A, const MyMethod &M)
template<class Field> void LU (DenseMatrix< Field > &M)
template<class Blackbox, class Polynomial, class MyMethod> Polynomial & minpoly (Polynomial &P, const Blackbox &A, const MyMethod &M)
 ...using an optional Method parameter

template<class Polynomial, class Blackbox> Polynomial & minpoly (Polynomial &P, const Blackbox &A)
 ...using default Method

template<class Blackbox, class Method, class DomainCategory> unsigned long & rank (unsigned long &r, const Blackbox &A, const DomainCategory &tag, const Method &M)
template<class Blackbox> unsigned long & rank (unsigned long &r, const Blackbox &A)
template<class Matrix> unsigned long & rankin (unsigned long &r, Matrix &A)
template<class Blackbox, class Method> unsigned long & rank (unsigned long &r, const Blackbox &A, const Method &M)
template<class Blackbox> unsigned long & rank (unsigned long &res, const Blackbox &A, const RingCategories::ModularTag &tag, const Method::Wiedemann &M)
 M may be Method::Wiedemann().

template<class Field> unsigned long & rank (unsigned long &r, const SparseMatrix< Field, typename LinBox::Vector< Field >::SparseSeq > &A, const RingCategories::ModularTag &tag, const Method::SparseElimination &M)
 M may be Method::SparseElimination().

template<class Field> unsigned long & rankin (unsigned long &r, BlasBlackbox< Field > &A, const RingCategories::ModularTag &tag, const Method::BlasElimination &M)
 A is modified.

template<class Output, class Blackbox, class MyMethod> Output & smithForm (Output &S, const Blackbox &A, const MyMethod &M)
template<class Vector, class Blackbox, class SolveMethod> Vector & solve (Vector &x, const Blackbox &A, const Vector &b, const SolveMethod &M)
 Solve Ax = b, for x.

template<class Vector, class Ring> Vector & solve (Vector &x, typename Ring::Element &d, const BlasBlackbox< Ring > &A, const Vector &b, const RingCategories::IntegerTag tag, Method::Dixon &m)
 solver specialization with the 2nd API and DixonTraits over integer (no copying)

template<class Vector, class Ring> Vector & solve (Vector &x, typename Ring::Element &d, const DenseMatrix< Ring > &A, const Vector &b, const RingCategories::IntegerTag tag, const Method::Dixon &m)
 solver specialization with the 2nd API and DixonTraits over integer (no copying)

template<class BB> BB::Field::Element & trace (typename BB::Field::Element &t, const BB &A)
 sum of eigenvalues

template<class BB> BB::Field::Element & trace (typename BB::Field::Element &t, const BB &A, const Method::Hybrid &m)
 our best guess

template<class BB> BB::Field::Element & trace (typename BB::Field::Element &t, const BB &A, const Method::Elimination &m)
 our elimination (a fake in this case)

template<class Blackbox> Blackbox::Field::Element & trace (typename Blackbox::Field::Element &res, const Blackbox &A, const Method::Blackbox &m)
template<class Blackbox, class MyMethod> Blackbox::Field::Element & valence (typename Blackbox::Field::Element &v, const Blackbox &A, const MyMethod &M)
 Compute the valence of A.

template<class Field, class Vector> Vector randomVector (Field &F, size_t n, typename Field::RandIter &r)


Typedef Documentation

typedef signed __LINBOX_INT32 int32
 

This is a representation of 32 bit ints, usually equivalent to `int'.

The use of `int32' ensures you are working with 32 bit signed ints, [-2^31..2^31). Similarly, int8, int16, and int64 are defined.

typedef unsigned __LINBOX_INT32 uint32
 

This is a representation of 32 bit unsigned ints, usually equivalent to `unsigned int'.

The use of `uint32' ensures you are working with 32 bit unsigned ints, [0..2^32). Similarly, uint8, uint16, and uint64 are defined.


Function Documentation

void SpecialBound const Ring &  R,
typename Ring::Element &  H_col_sqr,
typename Ring::Element &  short_col_sqr,
const ItMatrix &  A
 

BoundBlackbox: Sets H_col_sqr <- H_col(A)^2, short_col_sqr <- short_col(A)^2 where H_col(A) is prod_j sqrt(sum_i a_ij^2) ('Hadamard column bound') short_col(A) is min_j sqrt(sum_i a_ij^2) ('shortest column')

note: H_col is not actually a norm! but it is what we need for lifting bound computation

void ApplyBound const Ring &  R,
typename Ring::Element &  bound_A,
const ItMatrix &  A
 

ApplyBound: computes bound_A <- max_i(max(sum_{j|a_ij > 0} a_ij, sum_{j|a_ij < 0} |a_ij|)) this is useful because for all u, v >= 0: [b has all entries in -u..v] => [each entry of A.b is at most (u+v)*bound_A in absolute value]

void reduceIn Domain &  D,
std::pair< typename Domain::Element, typename Domain::Element > &  frac
 

utility function to reduce a rational pair to lowest form

void vectorGcdIn typename Domain::Element &  result,
Domain &  D,
Vector &  v
 

utility function to gcd-in a vector of elements over a domain

Domain::Element vectorGcd Domain &  D,
Vector &  v
 

utility function, returns gcd of a vector of elements over a domain

void create_MatrixQadic const Domain &  D,
const IMatrix &  M,
double *  chunks,
size_t  num_chunks,
const integer shift = 0
 

split an integer matrix into a padic chunk representation

void create_VectorQadic const Domain &  D,
const Vector &  V,
double *  chunks,
size_t  num_chunks
 

split an integer vector into a padic chunk representation

void create_VectorQadic_32 const Domain &  D,
const Vector &  V,
double *  chunks,
size_t  num_chunks
 

split an integer vector into a padic chunk representation

std::vector<bool> setButterfly const std::vector< bool > &  x,
size_t  j = 0
 

A function used with Butterfly Blackbox Matrices. This function takes an STL vector x of booleans, and returns a vector y of booleans such that setting the switches marked by true flags in y to be on (or to swap elements) the true elements x will be switched to a given contiguous block through the use of a Butterfly switching network. The integer parameter j marks where this block is to begin. If x has r true elements, the Butterfly switching network will place these elements in a contiguous block starting at j and ending at j + r - 1. Wrap around shall be considered to preserve contiguity. The value of j is defaulted to be zero, and it is only allowed to be non-zero is the size of x is a power of 2.

Returns:
vector of booleans for setting switches
Parameters:
x vector of booleans marking elements to switch into contiguous block
j offset of contiguous block
log reference to ostream for logging

NTL::zz_p& UnparametricField< NTL::zz_p >::init NTL::zz_p &  x,
const integer y
const
 

Initialization of field element from an integer. This Uses NTL's to_zz_p function.

Returns:
reference to field element.
Parameters:
x field element to contain output (reference returned).
y integer.

integer& UnparametricField< NTL::zz_p >::convert integer x,
const NTL::zz_p &  y
const
 

Conversion of field element to an integer. This function assumes the output field element x has already been constructed, but that it is not already initialized. For now, this is done by converting the element type to a C++ long and then to the integer type through the use of static cast and NTL's to_long function. This, of course, assumes such static casts are possible. This function should be changed in the future to avoid using long.

Returns:
reference to integer.
Parameters:
x reference to integer to contain output (reference returned).
y constant reference to field element.

integer& UnparametricField< NTL::zz_p >::cardinality integer c  )  const
 

Cardinality. Return integer representing cardinality of the field. Returns the modulus of the field, which should be prime.

Returns:
integer representing cardinality of the field

integer& UnparametricField< NTL::zz_p >::characteristic integer c  )  const
 

Characteristic. Return integer representing characteristic of the field. Returns the modulus of the field, which should be prime.

Returns:
integer representing characteristic of the field.

NTL::zz_p& UnparametricField< NTL::zz_p >::inv NTL::zz_p &  x,
const NTL::zz_p &  y
const
 

Multiplicative Inverse. x = 1 / y This function assumes both field elements have already been constructed and initialized.

Returns:
reference to x.
Parameters:
x field element (reference returned).
y field element.

bool UnparametricField< NTL::zz_p >::isZero const NTL::zz_p &  x  )  const
 

Zero equality. Test if field element is equal to zero. This function assumes the field element has already been constructed and initialized. In this specialization, NTL's IsZero function is called.

Returns:
boolean true if equals zero, false if not.
Parameters:
x field element.

bool UnparametricField< NTL::zz_p >::isOne const NTL::zz_p &  x  )  const
 

One equality. Test if field element is equal to one. This function assumes the field element has already been constructed and initialized. In this specialization, NTL's IsOne function is called.

Returns:
boolean true if equals one, false if not.
Parameters:
x field element.

NTL::zz_p& UnparametricField< NTL::zz_p >::invin NTL::zz_p &  x  )  const
 

Inplace Multiplicative Inverse. x = 1 / x This function assumes both field elements have already been constructed and initialized.

Returns:
reference to x.
Parameters:
x field element (reference returned).

std::ostream& UnparametricField< NTL::zz_p >::write std::ostream &  os  )  const
 

Print field.

Returns:
output stream to which field is written.
Parameters:
os output stream to which field is written.

std::ostream& UnparametricField< NTL::zz_pX >::write std::ostream &  os  )  const
 

Write a description of the field

long compare const Element &  a,
const Element &  b
const [inline]
 

compare two elements, a and b return 1, if a > b return 0, if a = b; return -1. if a < b

Element& abs Element &  x,
const Element &  a
const [inline]
 

return the absolute value x = abs (a);

integer& UnparametricField< NTL::ZZ_p >::convert integer x,
const NTL::ZZ_p &  y
const
 

Conversion of field element to an integer. This function assumes the output field element x has already been constructed, but that it is not already initialized. This done by converting to a std::string : inefficient but correct.

Returns:
reference to integer.
Parameters:
x reference to integer to contain output (reference returned).
y constant reference to field element.

integer& UnparametricField< NTL::ZZ_p >::cardinality integer c  )  const
 

Cardinality. Return integer representing cardinality of the field. Returns the modulus of the field, which should be prime.

Returns:
integer representing cardinality of the field

integer& UnparametricField< NTL::ZZ_p >::characteristic integer c  )  const
 

Characteristic. Return integer representing characteristic of the field. Returns the modulus of the field, which should be prime.

Returns:
integer representing characteristic of the field.

NTL::ZZ_p& UnparametricField< NTL::ZZ_p >::inv NTL::ZZ_p &  x,
const NTL::ZZ_p &  y
const
 

Multiplicative Inverse. x = 1 / y This function assumes both field elements have already been constructed and initialized.

Returns:
reference to x.
Parameters:
x field element (reference returned).
y field element.

bool UnparametricField< NTL::ZZ_p >::isZero const NTL::ZZ_p &  x  )  const
 

Zero equality. Test if field element is equal to zero. This function assumes the field element has already been constructed and initialized. In this specialization, NTL's IsZero function is called.

Returns:
boolean true if equals zero, false if not.
Parameters:
x field element.

bool UnparametricField< NTL::ZZ_p >::isOne const NTL::ZZ_p &  x  )  const
 

One equality. Test if field element is equal to one. This function assumes the field element has already been constructed and initialized. In this specialization, NTL's IsOne function is called.

Returns:
boolean true if equals one, false if not.
Parameters:
x field element.

NTL::ZZ_p& UnparametricField< NTL::ZZ_p >::invin NTL::ZZ_p &  x  )  const
 

Inplace Multiplicative Inverse. x = 1 / x This function assumes both field elements have already been constructed and initialized.

Returns:
reference to x.
Parameters:
x field element (reference returned).

std::ostream& UnparametricField< NTL::ZZ_p >::write std::ostream &  os  )  const
 

Print field.

Returns:
output stream to which field is written.
Parameters:
os output stream to which field is written.

std::ostream& UnparametricField< NTL::ZZ_pX >::write std::ostream &  os  )  const
 

Write a description of the field

Polynomial& charpoly Polynomial &  P,
const Blackbox &  A,
const MyMethod &  M
 

...using an optional Method parameter

Parameters:
P - the output characteristic polynomial. If the polynomial is of degree d, this random access container has size d+1, the 0-th entry is the constant coefficient and the d-th is 1 since the charpoly is monic.
A - a blackbox matrix Optional
M - the method object. Generally, the default object suffices and the algorithm used is determined by the class of M. Basic methods are Method::Blackbox, Method::Elimination, and Method::Hybrid (the default). See methods.h for more options.
Returns:
a reference to P.

Polynomial& charpoly Polynomial &  P,
const Blackbox &  A,
const RingCategories::ModularTag &  tag,
const Method::BlasElimination &  M
 

Compute the characteristic polynomial over Zp.

Compute the characteristic polynomial of a matrix using dense elimination methods

Parameters:
P Polynomial where to store the result
A Blackbox representing the matrix

Polynomial& charpoly Polynomial &  P,
const Blackbox &  A,
const RingCategories::ModularTag &  tag,
const Method::Blackbox &  M
 

Compute the characteristic polynomial over Zp.

Compute the characteristic polynomial of a matrix, represented via a blackBox.

Parameters:
P Polynomial where to store the result
A Blackbox representing the matrix

BB::Field::Element& getEntry typename BB::Field::Element &  x,
const BB &  A,
const size_t  i,
const size_t  j,
const Method::Hybrid &  m
 

our best guess

Hybrid method will choose based on matrix size and type

BB::Field::Element& getEntry typename BB::Field::Element &  x,
const BB &  A,
const size_t  i,
const size_t  j,
const Method::Elimination &  m
 

our elimination (a fake in this case)

Elimination method will go to blackbox.

Blackbox::Field::Element& getEntry typename Blackbox::Field::Element &  res,
const Blackbox &  A,
const size_t  i,
const size_t  j,
const Method::Blackbox &  m
 

Compute the getEntry of a linear operator A, represented as a black box. This class is parameterized by the black box type so that it can be specialized for different black boxes.

bool isPositiveDefinite const Blackbox &  A,
const MyMethod &  M
 

Compute the isPositiveDefinite of A

The isPositiveDefinite of a linear operator A, represented as a black box, is computed over the ring or field of A.

Parameters:
r OUTPUT instance into which to store the result r
A Black box of which to compute the isPositiveDefinite
M may be a Method::Hybrid (default), Method::Blackbox, Method::Elimination, or of other method type.

bool isPositiveSemiDefinite const Blackbox &  A,
const MyMethod &  M
 

Compute the isPositiveSemiDefinite of A

The isPositiveSemiDefinite of a linear operator A, represented as a black box, is computed over the ring or field of A.

Parameters:
r OUTPUT instance into which to store the result r
A Black box of which to compute the isPositiveSemiDefinite
M may be a Method::Hybrid (SemiDefault), Method::Blackbox, Method::Elimination, or of other method type.

void LU DenseMatrix< Field > &  M  ) 
 

M <-- the LU decomposition of M.

Parameters:
M is a dense matrix on input. require all principle minor are non-singular. Every leading principal minor must be nonzero. M is modified to represent the LU decomposition of the original M. L is unit lower triangular and occupies the strictly lower triangular part of M. The diagonal one's are implicit. U is upper triangular and occupies the rest of M.

Polynomial& minpoly Polynomial &  P,
const Blackbox &  A,
const MyMethod &  M
 

...using an optional Method parameter

Parameters:
P - the output minimal polynomial. If the polynomial is of degree d, this random access container has size d+1, the 0-th entry is the constant coefficient and the d-th is 1 since the minpoly is monic.
A - a blackbox matrix Optional
M - the method object. Generally, the default object suffices and the algorithm used is determined by the class of M. Basic methods are Method::Blackbox, Method::Elimination, and Method::Hybrid (the default). See methods.h for more options.
Returns:
a reference to P.

unsigned long& rankin unsigned long &  r,
Matrix &  A
 

A may be modified

BB::Field::Element& trace typename BB::Field::Element &  t,
const BB &  A
 

sum of eigenvalues

Also sum of diagonal entries. This is the generic one.

testing multiple doc comments.

BB::Field::Element& trace typename BB::Field::Element &  t,
const BB &  A,
const Method::Hybrid &  m
 

our best guess

Hybrid method will choose based on matrix size and type

BB::Field::Element& trace typename BB::Field::Element &  t,
const BB &  A,
const Method::Elimination &  m
 

our elimination (a fake in this case)

Elimination method will go to blackbox.

Blackbox::Field::Element& trace typename Blackbox::Field::Element &  res,
const Blackbox &  A,
const Method::Blackbox &  m
 

Compute the trace of a linear operator A, represented as a black box. This class is parameterized by the black box type so that it can be specialized for different black boxes.


Generated on Thu Feb 8 22:32:56 2007 for linbox by doxygen 1.3.4