. N-=-?x-d-,-y-e-?-×-·-·-·-×-?x-d-,-y-e-?-?-r-n, let F ? R m×n with deg X (F ) < d and deg Y (F ) < e, and let ? be a monomial order on R m . Algorithm 4 computes a minimal ?-Gröbner basis of Syz N (F ) using O?((M ??1 + Mn)(M + n)de) operations in K, where M =

, It follows that all matrices Q i , Q 1 , Q 2 , Q in the algorithm have at most M rows and at most M columns, and that the matrices G, have at most M rows and exactly n columns. Besides, by Kronecker substitution [7, Chap. 1 Sec. 8], multiplying two bivariate matrices of dimensions M × M (resp. M × n) and bidegree at most (d, e) costs O?(M ? de) (resp. O?(M ? (1 + n/M)de)) operations in K. Let C(m, n, d, e) denote the number of field operations used by Algorithm 4; we have C(m, n, d, e) ? C(M, n, d, e). First

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

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, issue.96, pp.120-123, 1997.

C. Berkesch and F. Schreyer, Syzygies, finite length modules, and random curves, Commutative Algebra and Noncommutative Algebraic Geometry. Mathematical Sciences Research Institute Publications, vol.67, pp.25-52, 2015.

J. Berthomieu and J. Faugère, A Polynomial-Division-Based Algorithm for Computing Linear Recurrence Relations, Proceedings ISSAC 2018. 79-86, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01784369

D. Bini and V. Y. Pan, Fundamental Algorithms, vol.1, 1994.

D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Comput, vol.9, issue.08, pp.80013-80015, 1990.

D. A. Cox, J. Little, and D. O'shea, Using Algebraic Geometry, 2005.

D. A. Cox, J. Little, and D. O'shea, Ideals, Varieties, and Algorithms, 2007.

D. Eisenbud, Commutative Algebra: with a View Toward Algebraic Geometry, 1995.

J. B. Farr and S. Gao, Computing Gröbner bases for vanishing ideals of finite sets of points, International Symposium on Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes, pp.118-127, 2006.

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

P. Fitzpatrick and J. Flynn, A Gröbner basis technique for Padé approximation, J. Symbolic Comput, vol.13, issue.08, pp.80087-80096, 1992.

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

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

C. Jeannerod, V. Neiger, É. 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. Jeannerod, V. Neiger, and G. Villard, Fast computation of approximant bases in canonical form, J. Symbolic Comput, vol.98, pp.192-224, 2020.
URL : https://hal.archives-ouvertes.fr/hal-01683632

F. and L. Gall, Powers of Tensors and Fast Matrix Multiplication, ISSAC'14, pp.296-303, 2014.

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, vol.144, pp.24-31, 1982.

T. Mora-;-cryptography, M. Sala, S. Sakata, T. Mora, and C. , The FGLM Problem and Möller's Algorithm on Zero-dimensional Ideals, Gröbner Bases, Coding, and, pp.27-45, 2009.

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

V. Neiger and É. Schost, Computing syzygies in finite dimension using fast linear algebra, 2019.
URL : https://hal.archives-ouvertes.fr/hal-02392488

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

F. Schreyer, Die Berechnung von Syzygien mit dem verallgemeinerten Weierstraßschen Divisionssatz, 1980.

A. Storjohann, Notes on computing minimal approximant bases, Challenges in Symbolic Computation Software (Dagstuhl Seminar Proceedings, 2006.

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.

W. Zhou and G. Labahn, Efficient Algorithms for Order Basis Computation, J. Symbolic Comput, vol.47, pp.793-819, 2012.