, 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

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

B. Beckermann, G. Labahn, and G. Villard, Normal forms for general polynomial matrices, Research report LIP 2002-1, 2002.

T. Beelen and P. M. Van-dooren, 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.

T. Beelen and P. M. Van-dooren, 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.

R. R. Bitmead, S. Y. Kung, B. D. Anderson, and T. Kailath, Greatest common divisors via generalized Sylvester and Bezout matrices, IEEE Trans. Automat. Control, vol.23, issue.6, pp.1043-1047, 1978.

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

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

P. Bürgisser, M. Clausen, and M. A. Shokrollahi, Algebraic Complexity Theory, Grundlehren der mathematischen Wissenschaften, vol.315, 1997.

D. G. Cantor and E. Kaltofen, On fast multiplication of polynomials over arbitrary algebras, Acta Informatica, vol.28, issue.7, pp.693-701, 1991.

L. Chen, W. Eberly, E. Kaltofen, B. D. Saunders, W. J. Turner et al., Efficient matrix preconditioners for black box linear algebra, Linear Algebra and its Applications, pp.119-146, 2002.

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

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

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

J. Zur-gathen and J. Gerhard, Modern Computer Algebra, 1999.

P. Giorgi, C. Jeannerod, and G. Villard, On the complexity of polynomial matrix computations, Proc. International Symposium on Symbolic and Algebraic Computation, pp.135-142, 2003.

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

T. Kailath, Linear systems, 1980.

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

E. Kaltofen, M. S. Krishnamoorthy, and B. D. Saunders, Parallel algorithms for matrix normal forms, Linear Algebra and its Applications, vol.136, pp.189-208, 1990.

E. Kaltofen and B. D. Saunders, On Wiedemann's method of solving sparse linear systems, Proc. AAECC-9, vol.539, pp.29-38, 1991.

E. Kaltofen and G. Villard, On the complexity of computing determinants, Computational Complexity, vol.13, pp.91-130, 2004.

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

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

P. Misra, P. Van-dooren, and A. Varga, Computation of structural invariants of generalized state-space systems, Automatica, vol.30, pp.1921-1936, 1994.

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

C. Oar?aoar?a and P. Van-dooren, 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.

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

A. Schönhage, Schnelle Berechnung von Kettenbruchenwicklungen, Acta Informatica, vol.1, pp.139-144, 1971.

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

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

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

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

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

G. Villard, 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.

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