Name
Abstract | ||
|---|---|---|
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. Our algorithm uses O~(mω-1D + nω D/m) operations in K, where D = deg(det(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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1145/3087604.3087656 | ISSAC |
Keywords | DocType | Volume |
Polynomial matrix, shifted Popov form, division with remainder, univariate equations, syzygy module | Conference | abs/1705.10649 |
Citations | PageRank | References |
3 | 0.40 | 17 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vincent Neiger | 1 | 39 | 7.22 |
| Thi Xuan Vu | 2 | 3 | 0.40 |