Computing Canonical Bases of Modules of Univariate Relations

Vincent Neiger 1 Thi Xuan Vu 2
2 ARIC - Arithmetic and Computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : We study the computation of canonical bases of sets of univariate relations $(p_1,\ldots,p_m) \in \mathbb{K}[x]^{m}$ such that $p_1 f_1 + \cdots + p_m f_m = 0$; here, the input elements $f_1,\ldots,f_m$ are from a quotient $\mathbb{K}[x]^n/\mathcal{M}$, where $\mathcal{M}$ is a $\mathbb{K}[x]$-module of rank $n$ given by a basis $\mathbf{M}\in\mathbb{K}[x]^{n\times n}$ in Hermite form. We exploit the triangular shape of $\mathbf{M}$ to generalize a divide-and-conquer approach which originates from fast minimal approximant basis algorithms. Besides recent techniques for this approach, we rely on high-order lifting to perform fast modular products of polynomial matrices of the form $\mathbf{P}\mathbf{F} \bmod \mathbf{M}$. Our algorithm uses $O\tilde{~}(m^{\omega-1}D + n^{\omega} D/m)$ operations in $\mathbb{K}$, where $D = \deg(\det(\mathbf{M}))$ is the $\mathbb{K}$-vector space dimension of $\mathbb{K}[x]^n/\mathcal{M}$, $O\tilde{~}(\cdot)$ indicates that logarithmic factors are omitted, and $\omega$ is the exponent of matrix multiplication. This had previously only been achieved for a diagonal matrix $\mathbf{M}$. Furthermore, our algorithm can be used to compute the shifted Popov form of a nonsingular matrix within the same cost bound, up to logarithmic factors, as the previously fastest known algorithm, which is randomized.
Type de document :
Communication dans un congrès
ISSAC '17 - 42nd International Symposium on Symbolic and Algebraic Computation, Jul 2017, Kaiserslautern, Germany. pp.8, 〈http://www.issac-conference.org/2017/〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01457979
Contributeur : Vincent Neiger <>
Soumis le : mardi 30 mai 2017 - 16:02:52
Dernière modification le : vendredi 20 avril 2018 - 15:44:26
Document(s) archivé(s) le : mercredi 6 septembre 2017 - 14:18:59

Fichier

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

Identifiants

  • HAL Id : hal-01457979, version 2
  • ARXIV : 1705.10649

Citation

Vincent Neiger, Thi Xuan Vu. Computing Canonical Bases of Modules of Univariate Relations. ISSAC '17 - 42nd International Symposium on Symbolic and Algebraic Computation, Jul 2017, Kaiserslautern, Germany. pp.8, 〈http://www.issac-conference.org/2017/〉. 〈hal-01457979v2〉

Partager

Métriques

Consultations de la notice

203

Téléchargements de fichiers

144