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 $m\times n$ matrices of length $d$ . Two algorithms are implemented:

bw-master: Coppersmith's quadratic algorithm, of complexity $O((m+n)n^2d^2)$
bw-master2: The subquadratic algorithm from the author, having complexity $O((m+n)^2d\log^2d)$ (complexity expression simplified under the assumption that $m,n\in O(\log k)$ )

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.

The matlingen software package

The matlingen software package

The `matlingen` software package

The `matlingen` software package