, remark that ad hoc successive index choices for constructing the submatrices?Msubmatrices? submatrices?M (k) 's will lead to m ? 2r o linearly independent vectors (see Proposition 7.1 and its proof)

, We do not further detail the proof of the algorithm which relies on similar techniques than those used for the proof of Proposition 7.1. The m ? r o computed vectors at Step (c) and Step (d) are in the nullspaces of full rank submatrices with r o columns of?Mof? of?M, Again, we ensure independency by ad hoc row index choices

, O(nmMM(r, d)/r 2 + (m/r + log r)(MM(r, d) log(rd) + r 2 B(d) log r + rM

, The final check at Step (e) is done in q + 1 multiplications using the special form of the intermediate results of Step (c) and Step (d). For one output of Nullspace minimal vectors at Step (c), the check is done in O(n/r)MM(r, d) operations, therefore q calls lead to a check in O((nm)MM(r, d)/r 2 ). As done in Corollary 6.5 for computing ?, the check involving the output of Algorithm Nullspace 2n is done by splitting the large degrees in the N i 's, and by forming an (min{m, The cost for computing?Mcomputing? computing?M using Lemma 7.3 is bounded by O(nmMM(r, d)/r 2 ). The top r o × r o matrix is made non-singular by pre-multiplication by a random constant matrix Q ? K m×m (see Algorithm Nullspace 2n ) in O(MM(n, d))

, For m r, since the sum of the Kronecker indices is no more than rd, we see that the bound we propose in Theorem 7.4 is within a factor asymptotically m/r from the optimal. A more accurate "tri-parameter" analysis-with respect to n, m and r-remains to be done. It may first require slight modifications of the ?-basis algorithm of [1, 15] that we use for computing minimal vectors, and a corresponding cost analysis especially with respect to r when m r. We conclude with a simplified expression of the cost for n = m and using r ? n. The polynomial matrix multiplication has, For m ? 2r we have already commented after Proposition 7.1 the quality of the degree sum bound rdlog 2 r

A uniform approach for the fast computation of matrixtype Padé approximants, SIAM J. Matrix Anal. Appl, vol.15, issue.3, pp.804-823, 1994. ,

Normal forms for general polynomial matrices, Research report LIP 2002-1, 2002. ,

URL : https://hal.archives-ouvertes.fr/hal-02101933

An improved algorithm for the computation of Kronecker's canonical form of a singular pencil, Linear Algebra and its Applications, vol.105, pp.9-65, 1988. ,

A pencil approach for embedding a polynomial matrix into a unimodular matrix, SIAM J. Matrix Anal. Appl, vol.9, issue.1, pp.77-89, 1988. ,

Greatest common divisors via generalized Sylvester and Bezout matrices, IEEE Trans. Automat. Control, vol.23, issue.6, pp.1043-1047, 1978. ,

Algorithmique efficace pour des opérations de base en calcul formel, 2003. ,

Polynomial evaluation and interpolation on special sets of points, Laboratoire STIX, ´ Ecole Polytechnique, 2004. ,

Algebraic Complexity Theory, Grundlehren der mathematischen Wissenschaften, vol.315, 1997. ,

On fast multiplication of polynomials over arbitrary algebras, Acta Informatica, vol.28, issue.7, pp.693-701, 1991. ,

Efficient matrix preconditioners for black box linear algebra, Linear Algebra and its Applications, pp.119-146, 2002. ,

URL : https://hal.archives-ouvertes.fr/hal-02101893

Matrix multiplication via arithmetic progressions, J. of Symbolic Computations, vol.9, issue.3, pp.251-280, 1990. ,

A probabilistic remark on algebraic program testing, Information Process. Letters, vol.7, issue.4, pp.193-195, 1978. ,

Minimal bases of rational vector spaces, with applications to multivariable linear systems, SIAM J. Control, vol.13, pp.493-520, 1975. ,

Modern Computer Algebra, 1999. ,

On the complexity of polynomial matrix computations, Proc. International Symposium on Symbolic and Algebraic Computation, pp.135-142, 2003. ,

URL : https://hal.archives-ouvertes.fr/hal-02101878

Essentially optimal computation of the inverse of generic polynomial matrices, Journal of Complexity, vol.21, issue.1, pp.72-86, 2005. ,

Linear systems, 1980. ,

On computing determinants without divisions, International Symposium on Symbolic and Algebraic Computation, pp.342-349, 1992. ,

Parallel algorithms for matrix normal forms, Linear Algebra and its Applications, vol.136, pp.189-208, 1990. ,

On Wiedemann's method of solving sparse linear systems, Proc. AAECC-9, vol.539, pp.29-38, 1991. ,

On the complexity of computing determinants, Computational Complexity, vol.13, pp.91-130, 2004. ,

URL : https://hal.archives-ouvertes.fr/hal-02102099

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

The analysis of algorithms, Proc. International Congress of Mathematicians, vol.3, pp.269-274, 1970. ,

Computation of structural invariants of generalized state-space systems, Automatica, vol.30, pp.1921-1936, 1994. ,

On lattice reduction for polynomial matrices, Journal of Symbolic Computation, vol.35, issue.4, pp.377-401, 2003. ,

An improved algorithm for the computation of structural invariants of a system pencil and related geometric aspects, Systems and Control Letters, vol.30, pp.38-48, 1997. ,

Some properties of control systems with irreducible matrix transfer functions, Lecture Notes in Mathematics, vol.144, pp.169-180, 1970. ,

Schnelle Berechnung von Kettenbruchenwicklungen, Acta Informatica, vol.1, pp.139-144, 1971. ,

Fast probabilistic algorithms for verification of polynomial identities, J. ACM, vol.27, pp.701-717, 1980. ,

Algorithms for Matrix Canonical Forms, 2000. ,

High-Order Lifting (Extended Abstract), Proc. International Symposium on Symbolic and Algebraic Computation, pp.246-254, 2002. ,

High-order lifting and integrality certification, Special issue International Symposium on Symbolic and Algebraic Computation, vol.36, pp.613-648, 2002. ,

A study of Coppersmith's block Wiedemann algorithm using matrix polynomials, RR 975-I-M IMAG, 1997. ,

Further analysis of Coppersmith's block Wiedemann algorithm for the solution of sparse linear systems, International Symposium on Symbolic and Algebraic Computation, pp.32-39, 1997. ,

Probabilistic algorithms for sparse polynomials, Proc. EUROSAM, vol.72, pp.216-226, 1979. ,