Computing Canonical Bases of Modules of Univariate Relations

Abstract

We study the computation of canonical bases of sets of univariate relations $(p_1,\dots ,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,\dots ,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{PF}\mathrm{mod}\mathbf{M}$. Our algorithm uses $O\stackrel{~}{}(m^{\omega -1}D+n^{\omega }D/m)$ operations in $\mathbb{K}$, where $D=\mathrm{deg}(\det (\mathbf{M}))$ is the $\mathbb{K}$-vector space dimension of $\mathbb{K}[x{]}^n/\mathcal{M}$, $O\stackrel{~}{}(\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.

arXiv comment8 pages, uses acmart sigconf

References in corpus (4)

• Powers of Tensors and Fast Matrix Multiplication
• Fast Computation of Minimal Interpolation Bases in Popov Form for Arbitrary Shifts
• Algorithms for Simultaneous Padé Approximations
• Fast Computation of Shifted Popov Forms of Polynomial Matrices via Systems of Modular Polynomial Equations

Cited by in corpus (3)

• Generic bivariate multi-point evaluation, interpolation and modular composition with precomputation
• Faster List Decoding of AG Codes
• Rank-Sensitive Computation of the Rank Profile of a Polynomial Matrix