Computing Canonical Bases of Modules of Univariate Relations
share
We study the computation of canonical bases of sets of univariate relations (p_1,...,p_m) ∈K[x]^m such that p_1 f_1 + ... + p_m f_m = 0; here, the input elements f_1,...,f_m are from a quotient K[x]^n/M, where M is a K[x]-module of rank n given by a basis M∈K[x]^n× n in Hermite form. We exploit the triangular shape of 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 PFM. Our algorithm uses O(m^ω-1D + n^ω D/m) operations in K, where D = deg((M)) is the K-vector space dimension of K[x]^n/M, O(·) indicates that logarithmic factors are omitted, and ω is the exponent of matrix multiplication. This had previously only been achieved for a diagonal matrix 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.
READ FULL TEXT