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

Vincent Neiger 1, 2
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.
Type de document :
Communication dans un congrès
41st International Symposium on Symbolic and Algebraic Computation, Jul 2016, Waterloo, ON, Canada. Proceedings of the 41st International Symposium on Symbolic and Algebraic Computation. 〈10.1145/2930889.2930936〉
Liste complète des métadonnées

Littérature citée [37 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01266014
Contributeur : Vincent Neiger <>
Soumis le : jeudi 12 mai 2016 - 11:08:39
Dernière modification le : vendredi 20 avril 2018 - 15:44:26
Document(s) archivé(s) le : mercredi 16 novembre 2016 - 02:31:45

Fichier

fast_popov_form.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

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. Proceedings of the 41st International Symposium on Symbolic and Algebraic Computation. 〈10.1145/2930889.2930936〉. 〈hal-01266014v2〉

Partager

Métriques

Consultations de la notice

238

Téléchargements de fichiers

100