Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4945909 | Journal of Symbolic Computation | 2017 | 43 Pages |
Abstract
In the mentioned references, the problem is solved using iterative algorithms based on recurrence relations. Here, we discuss a fast, divide-and-conquer version of this recurrence, taking advantage of fast matrix computations over the scalars and over the polynomials. This new algorithm is deterministic, and for computing shifted minimal bases of relations between m vectors of size Ï it uses OË(mÏâ1(Ï+|s|)) field operations, where Ï is the exponent of matrix multiplication, and |s| is the sum of the entries of the input shift s, with minâ¡(s)=0. This complexity bound improves in particular on earlier algorithms in the case of bivariate interpolation for soft decoding, while matching fastest existing algorithms for simultaneous Hermite-Padé approximation.
Related Topics
Physical Sciences and Engineering
Computer Science
Artificial Intelligence
Authors
Claude-Pierre Jeannerod, Vincent Neiger, Ãric Schost, Gilles Villard,