Week of 6/30 Update

This week I finished implementing the PolyDet class which computes the determinant of a matrix over a polynomial ring. The basic steps of the algorithm are:

• Given: $F=GF(p)$, $A\in{}F^{n*n}[x]$
• Let $d=\sum_{i=1}^{i=m}\max_{j\in\{1..n\}}\deg(A_{i,j})$
• (Choose $d$ to be the sum of the maximum row degrees)
• Let $d\leftarrow{}\min\left\{k|2^{k}>d+1\right\}$
• (Add 1 to $d$ and round up to the nearest power of 2)
• Let $EF=GF(p^{e})$ where $p^{e}=\min{\left\{k|\geq{}d\right\}}$
• Map the elements of $A$ to $EF$ homomorphicaly
• Choose d distinct points $p_{i}$ in $EF$
• Compute $\forall{}i\in\left\{1..d\right\}:v_{i}=det(A(p_{i}))$
• Interpolate the polynomial $P(x)$ of minimal degree that fits the points $v_{i}$
• Map the coefficients of $P(x)$ back to the ground field and return

This was a real bear to get working primarily because it involved working so much with extension fields. I used the GivaroExtension class for this and it turns out that it's still fairly buggy. A lot of algorithms in Linbox don't work for extension fields because of subtle differences in how the interfaces work. In addition, currently you can't construct an extension of an extension using GivaroExtension, you need a different extension class such as GivaroZpz which has some limitations of its own. I'm hoping to clean up some of these issues in the near future.

Having gotten polynomial determinants working the next step is to adapt the Smith Normal Form code to use this functionality. My plan is to implement a ring class that will automatically perform operations mod the determinant polynomial $P(x)$. The SmithFormIliopolus code was intended to work in a similar manner, albeit over the integers. With luck I'll be able to reuse the field extension code which already does everything mod a polynomial, and just tell it to use an arbitrary polynomial instead.

I'm also looking into using chinese remaindering to compute the invariant factors of integer matrices. With luck this should be as simple as wrapping the existing finite field code with a call to the existing CRADomain code, and performing a quick verification step. It should also provide more opportunities for parallelism since this step is embarrassingly parallel.