K. M×m-is-invertible, the truncated inverse of U is computed by Newton iteration in time O?(m ? ? ); then, the truncated product uses O?(m ? ?(n ? m)/m?? ) operations

B. Beckermann, G. Labahn, and G. Villard, Shifted normal forms of polynomial matrices, Proceedings of the 1999 international symposium on Symbolic and algebraic computation , ISSAC '99, pp.189-196, 1999.
DOI : 10.1145/309831.309929

B. Beckermann, G. Labahn, and G. Villard, Normal forms for general polynomial matrices, Journal of Symbolic Computation, vol.41, issue.6, pp.708-737, 2006.
DOI : 10.1016/j.jsc.2006.02.001
URL : https://doi.org/10.1016/j.jsc.2006.02.001

D. G. Cantor and E. Kaltofen, On fast multiplication of polynomials over arbitrary algebras, Acta Informatica, vol.7, issue.7, pp.7-693, 1991.
DOI : 10.1007/BF01178683

G. D. Forney and J. , Minimal Bases of Rational Vector Spaces, with Applications to Multivariable Linear Systems, SIAM Journal on Control, vol.13, issue.3, pp.493-520, 1975.
DOI : 10.1137/0313029

P. Giorgi, C. Jeannerod, and G. 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

S. Gupta, Hermite forms of polynomial matrices. Master's thesis, 2011.
DOI : 10.1145/1993886.1993913

S. Gupta, S. Sarkar, A. Storjohann, and J. Valeriote, Triangular x -basis decompositions and derandomization of linear algebra algorithms over K [x ], J. Symbolic Comput, vol.47, pp.4-2012, 2012.

S. Gupta and A. Storjohann, Computing hermite forms of polynomial matrices, Proceedings of the 36th international symposium on Symbolic and algebraic computation, ISSAC '11, pp.155-162, 2011.
DOI : 10.1145/1993886.1993913

C. Hermite, Sur l'introduction des variables continues dans la théorie des nombres, Journal für die reine und angewandte Mathematik, vol.41, pp.191-216, 1851.
DOI : 10.1017/cbo9780511702754.015

C. Jeannerod, V. Neiger, É. 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, 2016.
DOI : 10.1016/j.jsc.2011.12.009
URL : https://hal.archives-ouvertes.fr/hal-01265983

T. Kailath, Linear Systems, 1980.

G. Labahn, V. Neiger, and W. Zhou, Fast, deterministic computation of the Hermite normal form and determinant of a polynomial matrix, Journal of Complexity, vol.42, 2017.
DOI : 10.1016/j.jco.2017.03.003
URL : https://hal.archives-ouvertes.fr/hal-01345627

C. C. Macduffee, The Theory of Matrices, pp.978-981, 1933.

T. Mulders and A. Storjohann, On lattice reduction for polynomial matrices, Journal of Symbolic Computation, vol.35, issue.4, pp.377-401, 2003.
DOI : 10.1016/S0747-7171(02)00139-6
URL : https://doi.org/10.1016/s0747-7171(02)00139-6

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, Fast Computation of Shifted Popov Forms of Polynomial Matrices via Systems of Modular Polynomial Equations, Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC '16, pp.365-372, 2016.
DOI : 10.1016/j.jco.2014.09.004
URL : https://hal.archives-ouvertes.fr/hal-01266014

V. Neiger and T. X. Vu, Computing Canonical Bases of Modules of Univariate Relations, Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation , ISSAC '17, 2017.
DOI : 10.1109/TAC.1983.1103203
URL : https://hal.archives-ouvertes.fr/hal-01457979

M. Newman, Integral Matrices. Number v. 45 in Integral matrices, 1972.

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

S. Sarkar, Computing Popov Forms of Polynomial Matrices. Master's thesis, 2011.

S. Sarkar and A. Storjohann, Normalization of row reduced matrices, Proceedings of the 36th international symposium on Symbolic and algebraic computation, ISSAC '11, pp.297-304, 2011.
DOI : 10.1145/1993886.1993931

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.

W. Zhou, Fast Order Basis and Kernel Basis Computation and Related Problems, 2012.

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

W. Zhou and G. Labahn, Computing column bases of polynomial matrices, Proceedings of the 38th international symposium on International symposium on symbolic and algebraic computation, ISSAC '13, pp.379-386, 2013.
DOI : 10.1145/2465506.2465947

W. Zhou and G. Labahn, Unimodular completion of polynomial matrices, Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ISSAC '14, pp.413-420, 2014.
DOI : 10.1145/2608628.2608640

W. Zhou, G. Labahn, and A. Storjohann, Computing minimal nullspace bases, Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation, ISSAC '12, pp.366-373, 2012.
DOI : 10.1145/2442829.2442881