linbox
Modules | Files | Functions
solutions

These are problem oriented drivers providing simple interfaces to the linear algebra algorithms. More...

Modules

 Characteristic polynomial
 NO DOC YET.
 
 Determinant
 NO DOC YET.
 
 Minimal polynomial
 NO DOC YET.
 
 Nullspace
 NO DOC YET.
 
 Rank
 NO DOC YET.
 
 Recuded forms
 NO DOC YET.
 
 System solving
 NO DOC YET.
 

Files

file  det.h
 NO DOC.
 
file  methods.h
 NO DOC.
 
file  solution-tags.h
 This allows files defining objects that have traits concerning several solutions to get the tags and traits with one inclusion.
 
file  solve.h
 System Solving.
 

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. More...
 
template<class Blackbox , class DetMethod , class DomainCategory >
Blackbox::Field::Element & det (typename Blackbox::Field::Element &d, const Blackbox &A, const DomainCategory &tag, const DetMethod &Meth)
 Compute the determinant of A. More...
 
template<class Field >
Field::Element & detin (typename Field::Element &d, BlasMatrix< Field > &A)
 Rank of Blackbox A. More...
 
template<class VecPoly , class Blackbox >
vector< Poly< Field > > & invariants (VecPol &S, const Blackbox< Field > &A, Method &M=Method::Hybrid)
 Compute the Frobenius form invariant factors of A. More...
 
template<class Blackbox , class Method , class DomainCategory >
unsigned long & rank (unsigned long &r, const Blackbox &A, const DomainCategory &tag, const Method &M)
 Compute the rank of a linear transform A over a field by selected method. More...
 
template<class Blackbox >
unsigned long & rank (unsigned long &r, const Blackbox &A)
 Compute the rank of a linear transform A over a field. More...
 
template<class Blackbox , class Method >
unsigned long & rank (unsigned long &r, const Blackbox &A, const Method &M)
 Compute the rank of a linear transform A over a field. More...
 
template<class Output , class Blackbox , class MyMethod >
Output & smithForm (Output &S, const Blackbox &A, const MyMethod &M)
 Compute the Smith form of A. More...
 
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. More...
 

Detailed Description

These are problem oriented drivers providing simple interfaces to the linear algebra algorithms.

The arguments to each are discussed in detail in the documentation of each function. The optional method parameter is discussed in general terms just below the list.

The algorithms are actively under development, and there is an algorithm choice to be made for each function. The choice is determined by an optional argument to the function which is a method object. The class of the method object determines the approach used and data in the object may help determine algorithm variants at run time. This makes it easy to try out and compare several approaches for a given matrix.

The first method classes to consider are the Blackbox, Elimination, and Hybrid classes. Blackbox and Elimination methods may be used for virtually every solution function.

Hybrid algorithms are under development and not in final form. The method used under the Hybrid designation may be a sophisticated hybrid algorithm, a very basic one, or simply our guess of the most widely useful of the available algorithms. The basic hybrid method is to use the elimination approach if the matrix is small or in a dense representation, and a blackbox method otherwise. A dense representation is one which inherits from DenseMatrix or BlasMatrix. Small means both row and column dimensions are less than 103. The threshold values can be changed in the hybrid method object. For instance

Hybrid h;
h.setSmallThreshold(5000);
rank(r, A, h) ;

Additional method classes exist to focus in greater detail on the method. For instance, in the Blackbox situation there are the Wiedemann, BlockWiedemann, Lanczos, and BlockLanczos approaches, to name a few. Actually, for each solution function, the Blackbox class simply chooses from among these the best one as currently implemented. They may be used specifically to override that default. Thus rank(r, A,Blackbox()) uses the Wiedemann method. But rank(r, A, BlockLanczos()) could be called as well.

Todo:
this may soon be reversed, in fact.

Also choice of preconditioner may be possible either at runtime by putting an indicator in the method object or at compile time by using a more special class of method such as BlockWiedemannButterfly.

Other method classes focus on algorithms attuned to specific matrix properties. For instance, there may be HybridSymmetric, EliminationSymmetric, and BlackboxSymmetric. Using these method choices, several functions are about twice as fast as those where the symmetry is unspecified. To get the same effect as a runtime choice, objects of the basic method classes may contain an indicator of symmetry,

Method::Elimination e;
e.setSymmetric();
rank(r, A, e);

Not every implemented algorithm is available through solution functions and their methods, but this is a good starting point. See algorithms for the other possibilities and LinBox::Method for available methods.

If the status parameter is given, it is used for output of side information. For instance the solve function will set it's isConsistent() property indicating whether or not the system was found to be consistent. Also an upper bound on the probability of error is given by errorBound(). In the future, it may even provide consistency certificates and cofactors for normal forms.

Function Documentation

Blackbox::Field::Element& LinBox::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.

The determinant of a linear operator A, represented as a black box, is computed over the integers.

This variant is a hybrid between Last Invariant Factor and Chinese Remaindering It performs several determinants mod primes Then switches to the LIF method, producing a factor of det. It then comes back to the CRA if necessary to compute the remaining (usually small) factor of the determinant.

Parameters
dField element into which to store the result
ABlack box of which to compute the determinant
tagexplicit over the integers
Mmay be a Method::BlasElimination (default) or a Method::Wiedemann.
Blackbox::Field::Element& LinBox::det ( typename Blackbox::Field::Element &  d,
const Blackbox &  A,
const DomainCategory &  tag,
const DetMethod &  Meth 
)

Compute the determinant of A.

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

Parameters
dField element into which to store the result
ABlack box of which to compute the determinant
tagoptional tag. Specifies Integer, Rational or modular ring/field
Moptional method. The default is Method::Hybrid(), Other options include Blackbox, Elimination, Wiedemann, BlasElimination and SparseElimination. Sometimes it helps to indicate properties of the matrix in the method object (for instance symmetry). See class Method for details.
Examples:
examples/det.C, examples/doubledet.C, and examples/sparseelimdet.C.
Field::Element& LinBox::detin ( typename Field::Element &  d,
BlasMatrix< Field > &  A 
)

Rank of Blackbox A.

A will be modified.

Parameters
[out]ddeterminant of A.
Athis BlasMatrix matrix will be modified in place in the process.
Returns
d
vector<Poly<Field> >& LinBox::invariants ( VecPol &  S,
const Blackbox< Field > &  A,
Method &  M = Method::Hybrid 
)

Compute the Frobenius form invariant factors of A.

The first of them is the minimal polynomial, each divides the previous, and the product is the characteristic polynomial of A.

Parameters
[out]Sa vector of the invariant factors.
ASquare matrix over a field.
MThe default method is Hybrid. For sparse and structured matrices, a block blackbox method is used For dense matrices the approach is Krylov style.
unsigned long& LinBox::rank ( unsigned long &  r,
const Blackbox &  A,
const DomainCategory &  tag,
const Method &  M 
)
inline

Compute the rank of a linear transform A over a field by selected method.

For very large and/or very sparse matrices the Wiedemann method will be faster (and it is memory efficient). For some sparse matrices SparseElimination may outperform Wiedemann. For small or dense matrices BlasElimination will be faster.

Parameters
[out]routput rank of A.
[in]Alinear transform, member of any blackbox class.
[in]Mmay be a Method::Hybrid (the default), a Method::Wiedemann, a Method::BlasElimination, or a Method::SparseElimination..
tagUNDOC
Returns
a reference to r.
Examples:
examples/grid_reduce.C, examples/omp_block_rank.C, examples/rank.C, and examples/sparseelimrank.C.
unsigned long& LinBox::rank ( unsigned long &  r,
const Blackbox &  A 
)
inline

Compute the rank of a linear transform A over a field.

The default method is Wiedemann(), using diagonal preconditioning and the minpoly. For small or dense matrices BlasElimination will be faster.

Parameters
Alinear transform, member of any blackbox class.
[out]rrank of A
Returns
r rank of A.
unsigned long& LinBox::rank ( unsigned long &  r,
const Blackbox &  A,
const Method &  M 
)
inline

Compute the rank of a linear transform A over a field.

The default method is Wiedemann(), using diagonal preconditioning and the minpoly. For small or dense matrices BlasElimination will be faster.

Returns
r rank of A.
Parameters
Alinear transform, member of any blackbox class.
[out]rrank of A
Mmethod (see ???)
Output& LinBox::smithForm ( Output &  S,
const Blackbox &  A,
const MyMethod &  M 
)

Compute the Smith form of A.

The Smith form of a linear operator A, represented as a black box, is computed over a representation of $Z$ or $Z_m$.

Parameters
[out]Sa list of invariant/repcount pairs.
AMatrix of which to compute the Smith form
Mmay be a Method::Hybrid (default), which uses the algorithms/smith-form-adaptive.
Todo:
Other methods will be provided later. For now see the examples/smith.C for ways to call other smith form algorithms.
Examples:
examples/smith.C.
Blackbox::Field::Element& LinBox::valence ( typename Blackbox::Field::Element &  v,
const Blackbox &  A,
const MyMethod &  M 
)

Compute the valence of A.

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

Parameters
vField element into which to store the result
ABlack box of which to compute the determinant
Mmay is a Method.