Fast Computation of Shifted Popov Forms of Polynomial Matrices via Systems of Modular Polynomial Equations

Abstract

We give a Las Vegas algorithm which computes the shifted Popov form of an $m \times m$ nonsingular polynomial matrix of degree $d$ in expected $\widetilde{\mathcal{O}}(m^ωd)$ field operations, where $ω$ is the exponent of matrix multiplication and $\widetilde{\mathcal{O}}(\cdot)$ indicates that logarithmic factors are omitted. This is the first algorithm in $\widetilde{\mathcal{O}}(m^ωd)$ for shifted row reduction with arbitrary shifts. Using partial linearization, we reduce the problem to the case $d \le \lceil σ/m \rceil$ where $σ$ is the generic determinant bound, with $σ/ m$ bounded from above by both the average row degree and the average column degree of the matrix. The cost above becomes $\widetilde{\mathcal{O}}(m^ω\lceil σ/m \rceil)$, improving upon the cost of the fastest previously known algorithm for row reduction, which is deterministic. Our algorithm first builds a system of modular equations whose solution set is the row space of the input matrix, and then finds the basis in shifted Popov form of this set. We give a deterministic algorithm for this second step supporting arbitrary moduli in $\widetilde{\mathcal{O}}(m^{ω-1} σ)$ field operations, where $m$ is the number of unknowns and $σ$ is the sum of the degrees of the moduli. This extends previous results with the same cost bound in the specific cases of order basis computation and M-Padé approximation, in which the moduli are products of known linear factors.

8 pages, sig-alternate class, 5 figures (problems and algorithms)