. .. For-i-=-1,..-r and . Xn, D s ) 0?s<d B , (? s ) 0?s<d B ) 10. return ((R, C X 1 /C 1 mod mod R), X) Let us prove correctness. Since Q = Q A × Q B , we may assume without loss of generality that our multiplication matrices are block diagonal, with two blocks corresponding respectively to bases of Q A and Q B ; if not, apply a change of basis to reduce to this situation

E. Alonso, M. Becker, T. Roy, and . Wörmann, Zeroes, multiplicities and idempotents for zerodimensional systems, MEGA'94, pp.1-15, 1996.
DOI : 10.1007/978-3-0348-9104-2_1
URL : http://www.math.fsu.edu/~woermann/ABRW.ps

M. Bardet, J. Faugère, and B. Salvy, On the complexity of the <mml:math altimg="si1.gif" overflow="scroll" xmlns:xocs="http://www.elsevier.com/xml/xocs/dtd" xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns="http://www.elsevier.com/xml/ja/dtd" xmlns:ja="http://www.elsevier.com/xml/ja/dtd" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:tb="http://www.elsevier.com/xml/common/table/dtd" xmlns:sb="http://www.elsevier.com/xml/common/struct-bib/dtd" xmlns:ce="http://www.elsevier.com/xml/common/dtd" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:cals="http://www.elsevier.com/xml/common/cals/dtd" xmlns:sa="http://www.elsevier.com/xml/common/struct-aff/dtd"><mml:msub><mml:mrow><mml:mi>F</mml:mi></mml:mrow><mml:mrow><mml:mn>5</mml:mn></mml:mrow></mml:msub></mml:math> Gr??bner basis algorithm, Journal of Symbolic Computation, vol.70, pp.49-70, 2015.
DOI : 10.1016/j.jsc.2014.09.025

E. Becker, T. Mora, M. Marinari, and C. Traverso, The shape of the Shape Lemma, Proceedings of the international symposium on Symbolic and algebraic computation , ISSAC '94, pp.129-133, 1994.
DOI : 10.1145/190347.190382

E. Becker and T. Wörmann, Radical computations of zero-dimensional ideals and real root counting, Mathematics and Computers in Simulation, vol.42, issue.4-6, pp.561-569, 1996.
DOI : 10.1016/S0378-4754(96)00033-X

B. Beckermann and G. Labahn, A Uniform Approach for the Fast Computation of Matrix-Type Pad?? Approximants, SIAM Journal on Matrix Analysis and Applications, vol.15, issue.3, pp.804-823, 1994.
DOI : 10.1137/S0895479892230031

W. Bosma, J. Cannon, and C. Playoust, The Magma Algebra System I: The User Language, Journal of Symbolic Computation, vol.24, issue.3-4, pp.3-4235, 1997.
DOI : 10.1006/jsco.1996.0125

A. Bostan, P. Flajolet, B. Salvy, and . Schost, Fast computation of special resultants, Journal of Symbolic Computation, vol.41, issue.1, pp.1-29, 2006.
DOI : 10.1016/j.jsc.2005.07.001
URL : https://hal.archives-ouvertes.fr/inria-00000960

A. Bostan, B. Salvy, and . Schost, Fast Algorithms for Zero-Dimensional Polynomial Systems using Duality, Applicable Algebra in Engineering, Communication and Computing, vol.14, issue.4, pp.239-272, 2003.
DOI : 10.1007/s00200-003-0133-5
URL : https://hal.archives-ouvertes.fr/inria-00072296

R. P. Brent, F. G. Gustavson, and D. Y. Yun, Fast solution of toeplitz systems of equations and computation of Pad?? approximants, Journal of Algorithms, vol.1, issue.3, pp.259-295, 1980.
DOI : 10.1016/0196-6774(80)90013-9

D. Coppersmith, Solving Homogeneous Linear Equations Over GF(2) via Block Wiedemann Algorithm, Mathematics of Computation, vol.62, issue.205, pp.333-350, 1994.
DOI : 10.2307/2153413

J. Faugère, A new efficient algorithm for computing Gröbner bases without reductions to zero (F5), ISSAC'02, pp.75-83, 2002.

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

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

J. 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, issue.4, pp.329-344, 1993.
DOI : 10.1006/jsco.1993.1051

J. Faugère and C. Mou, Sparse FGLM algorithms, Journal of Symbolic Computation, vol.80, issue.8, pp.538-569, 2017.
DOI : 10.1016/j.jsc.2016.07.025

J. Faugère, M. Safey-el-din, and P. Spaenlehauer, On the complexity of the generalized MinRank problem, Journal of Symbolic Computation, vol.55, pp.30-58, 2013.
DOI : 10.1016/j.jsc.2013.03.004

J. Gathen and J. Gerhard, Modern Computer Algebra, 2013.

P. Gianni and T. Mora, Algebraic solution of systems of polynomial equations using Gröbner bases, AAECC'5, number 356 in Lecture Notes in Comput. Sci, pp.247-257, 1989.

C. Giorgi, G. Jeannerod, and . Villard, On the complexity of polynomial matrix computations, Proceedings of the 2003 international symposium on Symbolic and algebraic computation , ISSAC '03, pp.135-142, 2003.
DOI : 10.1145/860854.860889

P. Giorgi and R. Lebreton, Online order basis algorithm and its impact on the block Wiedemann algorithm, Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ISSAC '14, pp.202-209, 2014.
DOI : 10.1145/2608628.2608647
URL : https://hal.archives-ouvertes.fr/lirmm-01232873

L. The and . Group, Linbox: Linear algebra over black-box matrices, version 1.5.0, p.2017

G. Guennebaud and B. Jacob, Eigen v3, 2010.

C. Jeannerod, V. Neiger, ´. E. Schost, and G. Villard, Fast Computation of Minimal Interpolation Bases in Popov Form for Arbitrary Shifts, Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC '16, pp.295-302
DOI : 10.1016/j.jsc.2011.12.009
URL : https://hal.archives-ouvertes.fr/hal-01265983

T. Kailath, Linear Systems, 1980.

E. Kaltofen, Analysis of Coppersmith's block Wiedemann algorithm for the parallel solution of sparse linear systems, Mathematics of Computation, vol.64, issue.210, pp.777-806, 1995.

E. Kaltofen and G. Villard, On the complexity of computing determinants, ISSAC'01, pp.13-27, 2001.

E. Kaltofen and G. Villard, On the complexity of computing determinants, computational complexity, vol.13, issue.3-4, pp.91-130, 2004.
DOI : 10.1007/s00037-004-0185-3

W. Keller-gehrig, Fast algorithms for the characteristics polynomial, Theoretical Computer Science, vol.36, issue.2-3, pp.309-317, 1985.
DOI : 10.1016/0304-3975(85)90049-0
URL : https://doi.org/10.1016/0304-3975(85)90049-0

B. A. Lamacchia and A. M. Odlyzko, Solving Large Sparse Linear Systems Over Finite Fields, Adv. in Cryptography, Crypto '90, number 537 in Lectures Notes in Computer Science, pp.109-133, 1990.
DOI : 10.1007/3-540-38424-3_8

F. S. Macaulay, The Algebraic Theory of Modular Systems, 1916.

M. G. Marinari, H. M. Möller, and T. Mora, On multiplicities in polynomial system solving, Transactions of the American Mathematical Society, vol.348, issue.08, pp.3283-3321, 1996.
DOI : 10.1090/S0002-9947-96-01671-6
URL : ftp://ftp.disi.unige.it/person/MoraF/Mult_ISSAC.ps.gz

G. Moreno-socías, Autour de la fonction de Hilbert-Samuel (escaliers d'idéaux polynomiaux ), 1991.

A. Morgan, Solving Polynominal Systems Using Continuation for Engineering and Scientific Problems, 1988.
DOI : 10.1137/1.9780898719031

B. Mourrain, Isolated points, duality and residues, Journal of Pure and Applied Algebra, vol.117, issue.118, pp.469-493, 1997.
DOI : 10.1016/S0022-4049(97)00023-6
URL : https://hal.archives-ouvertes.fr/inria-00125278

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, H. Rahkooy, and . Schost, Algorithms for Zero-Dimensional Ideals Using Linear Recurrent Sequences, CASC'17, pp.313-328, 2017.
DOI : 10.1006/jsco.1995.1055
URL : https://hal.archives-ouvertes.fr/hal-01558042

V. M. Popov, Invariant Description of Linear, Time-Invariant Controllable Systems, SIAM Journal on Control, vol.10, issue.2, pp.252-264, 1972.
DOI : 10.1137/0310020

A. Poteaux and . Schost, On the complexity of computing with zero-dimensional triangular sets, Journal of Symbolic Computation, vol.50, pp.110-138, 2013.
DOI : 10.1016/j.jsc.2012.05.008
URL : https://hal.archives-ouvertes.fr/hal-00825847

F. Rouillier, Solving Zero-Dimensional Systems Through the Rational Univariate Representation, Applicable Algebra in Engineering, Communication and Computing, vol.9, issue.5, pp.433-461, 1999.
DOI : 10.1007/s002000050114
URL : https://hal.archives-ouvertes.fr/inria-00098872

S. Sakata, Extension of the Berlekamp-Massey algorithm to N dimensions, Information and Computation, vol.84, issue.2, pp.207-239, 1990.
DOI : 10.1016/0890-5401(90)90039-K

V. Shoup, NTL: A library for doing number theory

V. Shoup, Fast Construction of Irreducible Polynomials over Finite Fields, Journal of Symbolic Computation, vol.17, issue.5, pp.371-391, 1994.
DOI : 10.1006/jsco.1994.1025

V. Shoup, Efficient computation of minimal polynomials in algebraic extensions of finite fields, Proceedings of the 1999 international symposium on Symbolic and algebraic computation , ISSAC '99, pp.53-58, 1999.
DOI : 10.1145/309831.309859

A. Steel, Direct solution of the8)-MinRank problem by the block Wiedemann algorithm in Magma with a Tesla GPU, PASCO'15, pp.2-6, 2015.

A. Storjohann, High-order lifting and integrality certification, Journal of Symbolic Computation, vol.36, issue.3-4, pp.613-648, 2003.
DOI : 10.1016/S0747-7171(03)00097-X
URL : https://doi.org/10.1016/s0747-7171(03)00097-x

W. J. Turner, Black box linear algebra with the LINBOX library, 2002.

M. , V. 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.

G. Villard, Further analysis of Coppersmith's block Wiedemann algorithm for the solution of sparse linear systems (extended abstract), Proceedings of the 1997 international symposium on Symbolic and algebraic computation , ISSAC '97, pp.32-39, 1997.
DOI : 10.1145/258726.258742

G. Villard, A study of Coppersmith's block Wiedemann algorithm using matrix polynomials, LMC-IMAG, 1997.

W. A. Wolovich, Linear Multivariable Systems, of Applied Mathematical Sciences, 1974.
DOI : 10.1007/978-1-4612-6392-0

W. Zhou and G. Labahn, Efficient algorithms for order basis computation, Journal of Symbolic Computation, vol.47, issue.7, pp.793-819, 2012.
DOI : 10.1016/j.jsc.2011.12.009
URL : https://doi.org/10.1016/j.jsc.2011.12.009