, /N and the multiplication matrices M with respect to E. To build the matrix F ? K n×D , Step 2 uses O(nD) operations; precisely, each normal form of a coordinate vector in the Else statement costs at most D computations of the opposite of an element in K. By Proposition 3.14, Step 3 uses O(nD ??1 + rD ? log(D)) operations to compute the reduced ? 2 -Gröbner basis G 2 of Syz M (F). Hence the overall cost bound, Step 1 uses O(rD ? log(D)) operations in K and returns the ?-monomial basis E of

M. E. Alonso, M. G. Marinari, and T. Mora, The Big Mother of all Dualities: Möller Algorithm. Communications in Algebra 31, pp.783-818, 2003.

W. Auzinger and H. J. Stetter, An elimination algorithm for the computation of all zeros of a system of multivariate polynomial equations, Proceedings Numerical Mathematics, pp.11-30, 1988.

D. Bayer and M. Stillman, A theorem on refining division orders by the reverse lexicographic order, Duke Mathematical Journal, vol.55, pp.321-328, 1987.

B. Beckermann, A reliable method for computing M-Padé approximants on arbitrary staircases, J. Comput. Appl. Math, vol.40, pp.19-42, 1992.

B. Beckermann and G. Labahn, A uniform approach for the fast computation of matrix-type Padé approximants, SIAM J. Matrix Anal. Appl, vol.15, pp.804-823, 1994.

B. Beckermann and G. Labahn, Recursiveness in matrix rational interpolation problems, J. Comput. Appl. Math, vol.77, pp.5-34, 1997.

B. Beckermann and G. Labahn, Fraction-free computation of matrix rational interpolants and matrix gcds, SIAM J. Matrix Anal. Appl, vol.22, pp.114-144, 2000.

J. Berthomieu, B. Boyer, and J. C. Faugère, Linear algebra for computing gröbner bases of linear recursive multidimensional sequences, ISSAC'15, pp.61-68, 2015.

J. Berthomieu, B. Boyer, and J. C. Faugère, Linear Algebra for Computing Gröbner Bases of Linear Recursive Multidimensional Sequences, J. Symbolic Comput, vol.83, pp.36-67, 2017.

J. Berthomieu and J. C. Faugère, Guessing linear recurrence relations of sequence tuples and p-recursive sequences with linear algebra, ISSAC'16, pp.95-102, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01314266

J. Berthomieu and J. C. Faugère, A polynomial-division-based algorithm for computing linear recurrence relations, pp.79-86, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01935229

D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Comput, vol.9, pp.251-280, 1990.

D. Eisenbud, Commutative Algebra: with a View Toward Algebraic Geometry, Graduate Texts in Mathematics, 1995.

J. Faugère, P. Gaudry, L. Huot, and G. Renault, Polynomial systems solving by fast linear algebra, 2013.

J. C. Faugère, P. Gaudry, L. Huot, and G. Renault, Sub-cubic change of ordering for Gröbner basis: a probabilistic approach, vol.14, pp.170-177, 2014.

J. C. Faugère, P. Gianni, D. Lazard, and T. Mora, Efficient computation of zero-dimensional Gröbner bases by change of ordering, Journal of Symbolic Computation, vol.16, pp.329-344, 1993.

J. C. Faugère and C. Mou, Fast algorithm for change of ordering of zero-dimensional gröbner bases with sparse multiplication matrices, pp.115-122, 2011.

J. C. Faugère and C. Mou, Sparse FGLM algorithms, J. Symbolic Comput, vol.80, pp.538-569, 2017.

P. Fitzpatrick, Solving a Multivariable Congruence by Change of Term Order, J. Symbolic Comput, vol.24, pp.575-589, 1997.

A. Galligo, A propos du théorème de préparation de Weierstrass, Fonctions de Plusieurs Variables Complexes, pp.543-579, 1974.

P. Giorgi, C. P. Jeannerod, and G. Villard, On the complexity of polynomial matrix computations, ISSAC'03, ACM, pp.135-142, 2003.
URL : https://hal.archives-ouvertes.fr/hal-02101878

C. Hermite, Sur la généralisation des fractions continues algébriques, vol.21, pp.289-308, 1893.

C. P. Jeannerod, V. Neiger, E. Schost, and G. Villard, Fast computation of minimal interpolation bases in Popov form for arbitrary shifts, pp.295-302, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01265983

C. P. Jeannerod, V. Neiger, E. Schost, and G. Villard, Computing minimal interpolation bases, J. Symbolic Comput, vol.83, pp.272-314, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01241781

C. P. Jeannerod, V. Neiger, and G. Villard, Fast computation of approximant bases in canonical form, J. Symbolic Comput. In press, 2019.
URL : https://hal.archives-ouvertes.fr/hal-01683632

T. Kailath, Linear Systems, 1980.

A. Kehrein, M. Kreuzer, and L. Robbiano, An algebraist's view on border bases, Solving Polynomial Equations: Foundations, Algorithms, and Applications, pp.169-202, 2005.

W. Keller-gehrig, Fast algorithms for the characteristic polynomial, Theoretical Computer Science, vol.36, pp.309-317, 1985.

C. Kojima, P. Rapisarda, and K. Takaba, Canonical forms for polynomial and quadratic differential operators, Systems and Control Letters, vol.56, pp.678-684, 2007.

L. Gall and F. , Powers of tensors and fast matrix multiplication, pp.296-303, 2014.

F. S. Macaulay, Some formulae in elimination, Proceedings of the London Mathematical Society s1-35, pp.3-27, 1902.

F. S. Macaulay, The Algebraic Theory of Modular Systems, Cambridge Tracts in Mathematics and Mathematical Physics, 1916.

K. Mahler, Perfect systems, Composit. Math, vol.19, pp.95-166, 1968.

M. G. Marinari, H. M. Möller, and T. Mora, Gröbner bases of ideals given by dual bases, ISSAC'91, pp.55-63, 1991.

M. G. Marinari, H. M. Möller, and T. Mora, Gröbner bases of ideals defined by functionals with an application to ideals of projective points, Appl. Algebra Engrg. Comm. Comput, vol.4, pp.103-145, 1993.

H. M. Möller and B. Buchberger, The construction of multivariate polynomials with preassigned zeros, EUROCAM'82, pp.24-31, 1982.

B. Mourrain, A new criterion for normal form algorithms, in: Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, pp.430-442, 1999.

V. Neiger, Bases of relations in one or several variables: fast algorithms and applications, 2016.
URL : https://hal.archives-ouvertes.fr/tel-01431413

H. O'keeffe and P. Fitzpatrick, Gröbner basis solutions of constrained interpolation problems, Linear Algebra Appl, vol.351, pp.533-551, 2002.

H. Padé, Sur la généralisation des fractions continues algébriques, Journal de Mathématiques Pures et Appliquées, pp.291-330, 1894.

K. Pardue, Nonstandard Borel-Fixed Ideals, 1994.

S. Paszkowski, Recurrence relations in Padé-Hermite approximation, J. Comput. Appl. Math, vol.19, pp.99-107, 1987.

V. M. Popov, Invariant description of linear, time-invariant controllable systems, SIAM Journal on Control, vol.10, pp.252-264, 1972.

S. Sakata, Extension of the berlekamp-massey algorithm to n dimensions, Inform. and Comput, vol.84, pp.207-239, 1990.

A. V. Sergeyev, A recursive algorithm for Padé-Hermite approximations, USSR Comput. Math. Math. Phys, vol.26, pp.17-22, 1987.

A. Storjohann, Algorithms for Matrix Canonical Forms, 2000.

J. J. Sylvester, On a Theory of the Syzygetic Relations of Two Rational Integral Functions, Comprising an Application to the Theory of Sturm's Functions, and That of the Greatest Algebraical Common Measure. Philosophical Transactions of the, Royal Society of London, vol.143, pp.407-548, 1853.

M. Van-barel and A. Bultheel, The computation of non-perfect Padé-Hermite approximants, Numer. Algorithms, vol.1, pp.285-304, 1991.

M. Van-barel and A. Bultheel, A general module theoretic framework for vector M-Padé and matrix rational interpolation, Numer. Algorithms, vol.3, pp.451-462, 1992.