]. J. Abbott, M. Bronstein, and T. Mulders, Fast deterministic computation of determinants of dense matrices, Proceedings of the 1999 international symposium on Symbolic and algebraic computation , ISSAC '99, pp.197-204, 1999.
DOI : 10.1145/309831.309934

M. , V. Barel, and A. Bultheel, A general module theoretic framework for vector M-Padé and matrix rational interpolation, Numerical Algorithms, vol.3, pp.451-462, 1992.

M. Barkatou, C. Bacha, G. Labahn, and E. Pflügel, On simultaneous row and column reduction of higher-order linear differential systems, Journal of Symbolic Computation, vol.49, issue.1, pp.45-64, 2013.
DOI : 10.1016/j.jsc.2011.12.016
URL : https://hal.archives-ouvertes.fr/hal-00913462

B. Beckermann, A reliable method for computing M-Pad?? approximants on arbitrary staircases, Journal of Computational and Applied Mathematics, vol.40, issue.1, pp.19-42, 1992.
DOI : 10.1016/0377-0427(92)90039-Z
URL : http://doi.org/10.1016/0377-0427(92)90039-z

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

B. Beckermann and G. Labahn, Fraction-Free Computation of Matrix Rational Interpolants and Matrix GCDs, SIAM Journal on Matrix Analysis and Applications, vol.22, issue.1, pp.114-144, 2000.
DOI : 10.1137/S0895479897326912
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.1668

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
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.25.5965

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 : http://doi.org/10.1016/j.jsc.2006.02.001

J. Bunch and J. Hopcroft, Triangular factorization and inversion by fast matrix multiplication, Mathematics of Computation, vol.28, issue.125, pp.231-236, 1974.
DOI : 10.1090/S0025-5718-1974-0331751-8

D. S. Dummit and R. M. Foote, Abstract Algebra, 2004.

W. Eberly, M. Giesbrecht, and G. Villard, On computing the determinant and Smith normal form of an integer matrix, Proceedings of 41st IEEE Symposium on Foundations of Computer Science (FOCS'2000), pp.675-687, 2000.

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, 2011.
DOI : 10.1145/1993886.1993913

S. Gupta, S. Sarkar, A. Storjohann, and J. Valeriote, Triangular <mml:math altimg="si1.gif" display="inline" 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"><mml:mi>x</mml:mi></mml:math>-basis decompositions and derandomization of linear algebra algorithms over <mml:math altimg="si2.gif" display="inline" 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"><mml:mstyle mathvariant="sans-serif"><mml:mi>K</mml:mi></mml:mstyle><mml:mrow><mml:mo>[</mml:mo><mml:mi>x</mml:mi><mml:mo>]</mml:mo></mml:mrow></mml:math>, Journal of Symbolic Computation, vol.47, issue.4, pp.422-453, 2012.
DOI : 10.1016/j.jsc.2011.09.006

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

J. Hafner and K. Mccurley, Asymptotically Fast Triangularization of Matrices over Rings, SIAM Journal on Computing, vol.20, issue.6, pp.1068-1083, 1991.
DOI : 10.1137/0220067

C. Hermite, Sur l'introduction des variables continues dans la théorie des nombres, Journal für die reine und angewandte Mathematik, pp.191-216, 1851.
DOI : 10.1017/cbo9780511702754.015
URL : http://www.digizeitschriften.de/download/PPN243919689_0041/PPN243919689_0041___log16.pdf

C. Iliopoulos, Worst-Case Complexity Bounds on Algorithms for Computing the Canonical Structure of Finite Abelian Groups and the Hermite and Smith Normal Forms of an Integer Matrix, SIAM Journal on Computing, vol.18, issue.4, pp.658-669, 1986.
DOI : 10.1137/0218045

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, 2016.
DOI : 10.1145/2930889.2930928
URL : https://hal.archives-ouvertes.fr/hal-01265983

T. Kailath, Linear Systems, 1980.

E. Kaltofen, On computing determinants of matrices without divisions, Papers from the international symposium on Symbolic and algebraic computation , ISSAC '92, pp.342-349, 1992.
DOI : 10.1145/143242.143350

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

R. Kannan, Solving systems of linear equations over polynomials, Theoretical Computer Science, vol.39, pp.69-88, 1985.
DOI : 10.1016/0304-3975(85)90131-8
URL : http://doi.org/10.1016/0304-3975(85)90131-8

S. E. Labhalla, H. Lombardi, and R. Marlin, Algorithmes de calcul de la réduction d'Hermite d'une matricè a coefficients polynmiaux, Comptes-Rendus de MEGA92, 1992.
DOI : 10.1016/0304-3975(95)00090-9
URL : http://doi.org/10.1016/0304-3975(95)00090-9

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 : http://doi.org/10.1016/s0747-7171(02)00139-6

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.1145/2930889.2930936
URL : https://hal.archives-ouvertes.fr/hal-01266014

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

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

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 : http://doi.org/10.1016/s0747-7171(03)00097-x

A. Storjohann, Notes on computing minimal approximant bases, Dagstuhl Seminar Proceedings, pp.1862-4405, 2006.

A. Storjohann, On the complexity of inverting integer and polynomial matrices, computational complexity, vol.66, issue.4, p.777, 2015.
DOI : 10.1007/s00037-015-0106-7

A. Storjohann and G. Labahn, Asymptotically fast computation of Hermite normal forms of integer matrices, Proceedings of the 1996 international symposium on Symbolic and algebraic computation , ISSAC '96, pp.259-266, 1996.
DOI : 10.1145/236869.237083

A. Storjohann and G. Villard, Computing the rank and a small nullspace basis of a polynomial matrix, Proceedings of the 2005 international symposium on Symbolic and algebraic computation , ISSAC '05, pp.309-316, 2005.
DOI : 10.1145/1073884.1073927
URL : https://hal.archives-ouvertes.fr/hal-00004832

G. Villard, Computing Popov and Hermite forms of polynomial matrices, Proceedings of the 1996 international symposium on Symbolic and algebraic computation , ISSAC '96, pp.250-258, 1996.
DOI : 10.1145/236869.237082
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.160.9885

W. Zhou, Fast order basis and kernel basis computation and related problems, 2012.

W. Zhou and G. Labahn, Efficient computation of order bases, Proceedings of the 2009 international symposium on Symbolic and algebraic computation, ISSAC '09, pp.375-382, 2009.
DOI : 10.1145/1576702.1576753

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 : http://dx.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-387, 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.375-382, 2012.
DOI : 10.1145/2442829.2442881
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.410.3917

W. Zhou, G. Labahn, and A. Storjohann, A deterministic algorithm for inverting a polynomial matrix, Journal of Complexity, vol.31, issue.2, pp.162-173, 2015.
DOI : 10.1016/j.jco.2014.09.004

. Indeed, U mod x) = 0, determining the diagonal entries of a triangular form of U allows us to deduce its determinant as explained in Remark 4.1. Thus, we obtain det(A) in O(n ? deg(A)) field operations