Computing Canonical Bases of Modules of Univariate Relations
Vincent Neiger, Vu Thi Xuan · 2017
We study the computation of canonical bases of sets of univariate relations (p1,...,pm) ∈ K[x]m such that p1 f1 + ⋯ + pm fm = 0; here, the input elements f1,...,fm 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 x 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 P F mod M.