The matlingen
software package
The matlingen
software package
Here is the home of the matlingen
sotware package.
The matlingen
program computes generating polynomials for matrix
sequences. We take as an example the computation of a generating
polynomial for a sequence of
matrices of length
. Two algorithms are implemented:
bw-master
: Coppersmith's quadratic algorithm, of complexitybw-master2
: The subquadratic algorithm from the author, having complexity(complexity expression simplified under the assumption that
)
Note that there are also other algorithms suitable for this task, notably the Beckermann-Labahn approach, also providing subquadratic complexity.
For long, the sub-quadratic code has been only available for matrices defined over fields allowing the use of a polynomial FFT (possibly over a degree 2 extension). From version 20070614 and onwards, this requirement is being lifted, although bugs remain (see todo page).
Instructions for use are rather scarce, and provided in the README file contained in the distribution.
© 2005–2006 Emmanuel Thom\xE9 ; valid XHTML 1.0, valid CSS