Computing canonical bases of modules of univariate relations

DOI10.1145/3087604.3087656MaRDI QIDQ5119962zbMATH OpenOpenAlexFDO

Authors Vincent Neiger

Publication date 9 September 2020

Published in Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.10649, https://hal.inria.fr/hal-01457979v2/file/univariate_relation_bases.pdf

zbMATH Keywords

division with remainderpolynomial matrixshifted Popov formsyzygy moduleunivariate equations

Mathematics Subject Classification ID

Structure, classification theorems for modules and ideals in commutative rings (13C05) Symbolic computation and algebraic computation (68W30)

Abstract: We study the computation of canonical bases of sets of univariate relations $(p_1,ldots,p_m)inmathbbK[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 $mathbbK[x{]}^n/mathcalM$, where $mathcalM$ is a $mathbbK[x]$-module of rank $n$ given by a basis $mathbfMinmathbbK[x{]}^{nimesn}$ in Hermite form. We exploit the triangular shape of $mathbfM$ 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 $$. Our algorithm uses $Oilde(m^{omega-1}D+n^{omega}D/m)$ operations in $mathbbK$, where $D=mathrmdeg(det(mathbfM))$ is the $mathbbK$-vector space dimension of $mathbbK[x{]}^n/mathcalM$, $Oilde(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 $mathbfM$. 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.

Recommendations

• Fast computation of shifted Popov forms of polynomial matrices via systems of modular polynomial equations
• Fast computation of approximant bases in canonical form
• Computing column bases of polynomial matrices
• Computing Popov and Hermite forms of rectangular polynomial matrices
• Computing the rank and a small nullspace basis of a polynomial matrix

Cited in

(4)

• Verification protocols with sub-linear communication for polynomial matrix operations
• Deterministic computation of the characteristic polynomial in the time of matrix multiplication
• scientific article; zbMATH DE number 939805 (Why is no real title available?)
• Computing Krylov iterates in the time of matrix multiplication

This page was built for publication: Computing canonical bases of modules of univariate relations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5119962)