rank(r, A[, method]) r gets rank of A determinant(d, A[, method]) d gets determinant of A solve(x, A, b[, method[, status]]) get x such that Ax = b, random solution if sigular and consistent, x = 0 if inconsistent (also inconsistency is indicated in the status). The method parameter may include specifications that can make the computation faster. These include symmetry, nonsingularity, and that an arbitrary solution is acceptable rather than a random sample. minpoly(m, A[, method, status]) m gets minimal polynomial of A charpoly(c, A[, method, status]) c gets characteristic polynomial of A smithForm(S, A[, method]) S gets Smith Normal Form of A. Smith form is unitarily equivalent to A and is diag(s1 .. sn) such that si | si+1. primary form? Relative primary form of A? Primary form is similar to A and finest which is a direct sum of companion matrices Cfi such that, for all i, j, gcd(fi, fj) = 1 or fi or fj. Relative primary form is coarsest such decomposition.
this may soon be reversed, in fact.
frobeniusForm(F, A, method, status) F gets Frobenius (Rational) normal form of A. Frobenius form is similar to A and is a direct sum of companion matrices Cfi such that, fi divides fi+1.
signature(s, A, method) bool isPositiveDefinite(A, method_symm) bool isPositiveSemidefinite(A, method_symm) 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.
The Elimination class provides access to algorithms based on dense or sparse elimination and the algorithms take advantage of the numeric BLAS routines when the underlying field or ring is the integers or a prime field of appropriate cardinality.
The Blackbox class provides functions which are space efficient and are particularly effective for very large and very sparse systems. They are also fast and useful for structured systems such as Toeplitz, Hankel, Vandermonde, etc. Currently in LinBox the superfast methods for structured matrices are not implemented.
The Hybrid class chooses Blackbox, Elimination, or a mix of them based on matrix properties checked at runtime. It is the default method. Thus for each problem (e.g. rank) the function call without a method, rank(r, A), is equivalent to a call using the default Hybrid object, rank(r, A, Method::Hybrid()).
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.
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 linbox/algorithms for the other possibilities.
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.
Functions | |
| template<class Blackbox, class MyMethod> Blackbox::Field::Element & | det (typename Blackbox::Field::Element &d, const Blackbox &A, const MyMethod &M) |
| template<class Field> Field::Element & | detin (typename Field::Element &d, BlasBlackbox< Field > &A) |
| A will be modified. | |
| template<class Blackbox> unsigned long & | rank (unsigned long &r, const Blackbox &A) |
| template<class Blackbox, class Method> unsigned long & | rank (unsigned long &r, const Blackbox &A, const Method &M) |
| template<class Blackbox, class MyMethod> BOUTPUT & | SOLUTION (BOUTPUT &r, const Blackbox &A, const MyMethod &M) |
|
||||||||||||||||
|
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.
|
|
||||||||||||
|
A will be modified.
|
|
||||||||||||||||
|
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.
|
|
||||||||||||
|
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.
|
|
||||||||||||||||
|
Compute the SOLUTION of A The SOLUTION of a linear operator A, represented as a black box, is computed over the ring or field of A.
|
1.2.18