U. Compute-e-s and V. =-d-s-v-?-?,

=. Scalarnumeratorcorrected, (. , V. , and S. , , vol.1

,. .. Do-let-c-x-i-=-scalarnumeratorcorrected, (. , V. , S. M-i-?-1-;-r, .. .. Becker et al., 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 References Alonso, vol.1, pp.1-15, 1996.

M. Bardet, J. C. Faugère, and B. Salvy, On the complexity of the F5 Gröbner basis algorithm, J. Symbolic Comput, vol.70, pp.49-70, 2015.

E. Becker, T. Mora, M. Marinari, and C. Traverso, The shape of the Shape Lemma, ISSAC'94, ACM, pp.129-133, 1994.

E. Becker and T. Wörmann, Radical computations of zero-dimensional ideals and real root counting, Mathematics and Computers in Simulation, vol.42, pp.561-569, 1996.

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.

W. Bosma, J. Cannon, and C. Playoust, The Magma algebra system. I. The user language, J. Symbolic Comput, vol.24, pp.235-265, 1997.

A. Bostan, P. Flajolet, B. Salvy, and ´. E. Schost, Fast computation of special resultants, J. Symbolic Comput, vol.41, pp.1-29, 2006.
URL : https://hal.archives-ouvertes.fr/inria-00000960

A. Bostan, B. Salvy, and ´. E. Schost, Fast algorithms for zero-dimensional polynomial systems using duality, Appl. Algebra Engrg. Comm. Comput, vol.14, pp.239-272, 2003.
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, pp.259-295, 1980.

D. Coppersmith, Solving homogeneous linear equations over GF(2) via block Wiedemann algorithm, Math. Comp, vol.62, pp.333-350, 1994.

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

J. C. 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, 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, J. Symbolic Comput, vol.16, pp.329-344, 1993.

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

J. C. Faugère, M. Safey-el-din, and P. J. Spaenlehauer, On the complexity of the generalized MinRank problem, J. Symbolic Comput, pp.30-58, 2013.

J. Von-zur-gathen, J. Gerhard, . Cambridge, P. Gianni, and T. Mora, Algebraic solution of systems of polynomial equations using Gröbner bases, pp.247-257, 1989.

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

P. Giorgi and R. Lebreton, Online order basis algorithm and its impact on the block Wiedemann algorithm, pp.202-209, 2014.
URL : https://hal.archives-ouvertes.fr/lirmm-01232873

G. Guennebaud and B. Jacob, 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, pp.777-806, 1995.

E. Kaltofen and G. Villard, On the complexity of computing determinants, pp.13-27, 2001.
URL : https://hal.archives-ouvertes.fr/hal-02102099

E. Kaltofen and G. Villard, On the complexity of computing determinants, Comput. Complexity, vol.13, pp.91-130, 2004.
URL : https://hal.archives-ouvertes.fr/hal-02102099

W. Keller-gehrig, Fast algorithms for the characteristic polynomial, Theoret. Comput. Sci, vol.36, pp.309-317, 1985.

B. A. Lamacchia and A. M. Odlyzko, Solving large sparse linear systems over finite fields, Adv. in Cryptography, Crypto '90, pp.109-133, 1990.

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, Trans. Amer. Math. Soc, vol.348, pp.3283-3321, 1996.

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.

B. Mourrain, Isolated points, duality and residues, Journal of Pure and Applied Algebra, vol.117, pp.469-493, 1997.
URL : https://hal.archives-ouvertes.fr/inria-00125278

V. ;. Neiger, H. Rahkooy, and ´. E. Schost, Bases of relations in one or several variables: fast algorithms and applications, vol.17, pp.313-328, 2016.
URL : https://hal.archives-ouvertes.fr/tel-01431413

A. Poteaux and E. Schost, On the complexity of computing with zero-dimensional triangular sets, J. Symbolic Comput, vol.50, pp.110-138, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00825847

F. Rouillier, Solving zero-dimensional systems through the Rational Univariate Representation, Appl. Algebra Engrg. Comm. Comput, vol.9, pp.433-461, 1999.
URL : https://hal.archives-ouvertes.fr/inria-00098872

S. Sakata, Extension of the Berlekamp-Massey algorithm to N dimensions, Information and Computation, vol.84, pp.207-239, 1990.

V. Shoup, Fast construction of irreducible polynomials over finite fields, J. Symbolic Comput, vol.17, pp.371-391, 1994.

V. Shoup, Efficient computation of minimal polynomials in algebraic extensions of finite fields, ISSAC'99, ACM, pp.53-58, 1999.

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

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

A. Storjohann, High-order lifting and integrality certification, J. Symbolic Comput, vol.36, pp.613-648, 2003.

F. The and . Group, FFLAS-FFPACK: Finite Field Linear Algebra Subroutines / Package, 2019.

, Linbox: Linear algebra over black-box matrices, 2018.

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

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.

G. Villard, Further analysis of Coppersmith's block Wiedemann algorithm for the solution of sparse linear systems, ISSAC'97, ACM, pp.32-39, 1997.

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

D. Wiedemann, Solving sparse linear equations over finite fields, IEEE Trans. Inf. Theory IT, vol.32, pp.54-62, 1986.

W. A. Wolovich, Linear Multivariable Systems, Applied Mathematical Sciences, vol.11, 1974.