Fast computation of shifted Popov forms of polynomial matrices via systems of modular polynomial equations

1 ARIC - Arithmetic and Computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
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^\omega d)$ field operations, where $\omega$ 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^\omega d)$ for shifted row reduction with arbitrary shifts. Using partial linearization, we reduce the problem to the case $d \le \lceil \sigma/m \rceil$ where $\sigma$ is the generic determinant bound, with $\sigma / 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^\omega \lceil \sigma/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^{\omega-1} \sigma)$ field operations, where $m$ is the number of unknowns and $\sigma$ 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\'e approximation, in which the moduli are products of known linear factors.
Keywords :
Document type :
Conference papers

Cited literature [37 references]

https://hal.inria.fr/hal-01266014
Contributor : Vincent Neiger <>
Submitted on : Thursday, May 12, 2016 - 11:08:39 AM
Last modification on : Wednesday, November 20, 2019 - 3:27:16 AM
Long-term archiving on: : Wednesday, November 16, 2016 - 2:31:45 AM

File

fast_popov_form.pdf
Files produced by the author(s)

Citation

Vincent Neiger. Fast computation of shifted Popov forms of polynomial matrices via systems of modular polynomial equations. 41st International Symposium on Symbolic and Algebraic Computation, Jul 2016, Waterloo, ON, Canada. ⟨10.1145/2930889.2930936⟩. ⟨hal-01266014v2⟩

Record views