Week of 7/28 Update

This week I've started looking into an alternative way of computing the modulus for the polynomial ring used by SmithFormIliopolus. The problem with PolyDet is that it's painfully slow, mostly due to its heavy use of arithmetic over field extensions. The new approach would avoid the use of extensions and is based on a paper by Dixon (Exact Solutions of Linear Equations Using P-Adic Expansions (1982)). The difference is that here we're working with polynomial, not p-adic representations of integers. The goal is to compute the largest invariant factor of a matrix A. For our purposes, this is actually better than the determinant since it keeps our intermediate polynomials smaller. Here's the algorithm:

• Choose a random polynomial vector $\vec{b}$ over the ground field $\mathbb{F}$
• The degree of $\vec{b}$ (defined as the maximum of the degrees of the elements of $\vec{b}$) should be large enough to sample the range of $A$, but how big exactly remains unclear. 
• Choose $\alpha$ to make $A(-\alpha)$ non-singular then let $A\leftarrow{}A(x-\alpha)$
• Solve $A\vec{x}=\vec{b}$ for the first $2n$ terms of a power series solution for $\vec{x}$ for $n$ the sum of the degrees of each row of $A$
• Perform a rational reconstruction to solve $\vec{x}=\frac{\vec{n}}{d}$ for $d$
• Take a few random linear combinations of the elements of $\vec{x}$
• For each linear combination find $f$ and $g$ of minimal degree such that $g\vec{x}\equiv{}f$ (mod $x^{2n}$)
• Take the least common multiple of the various $g$'s
• Return the polynomial $d$

Asymptotically this algorithm require about the same number of field operations as PolyDet. However, because it only works over the ground field I'm hoping it will be much faster. I'm working on a Sage example of this algorithm now to work out the details. Hopefully I'll then be able to get a Linbox implementation up and working to compare against PolyDet.