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

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://hal.archives-ouvertes.fr/hal-02101933

D. A. Bini and V. , Pan. Polynomial and Matrix Computations. Progress in Theoretical Computer Science. Birkhäuser Basel, 1994.

A. Bostan and É. Schost, Polynomial evaluation and interpolation on special sets of points, Journal of Complexity, vol.21, issue.4, pp.420-446, 2005.
DOI : 10.1016/j.jco.2004.09.009

N. Bourbaki, Commutative Algebra, Elements of Mathematics, pp.40-43, 1972.

, Preprint dated, 2018.

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

D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, vol.9, issue.3, pp.251-280, 1990.
DOI : 10.1016/S0747-7171(08)80013-2

C. Costello, C. Fournet, J. Howell, M. Kohlweiss, B. Kreuter et al., Geppetto: Versatile Verifiable Computation, 2015 IEEE Symposium on Security and Privacy, pp.253-270, 2015.
DOI : 10.1109/SP.2015.23

R. A. Demillo and R. J. Lipton, A probabilistic remark on algebraic program testing, Information Processing Letters, vol.7, issue.4, pp.193-195, 1978.
DOI : 10.1016/0020-0190(78)90067-4

J. D. Dixon, Exact solution of linear equations usingP-adic expansions, Numerische Mathematik, vol.82, issue.1, pp.137-141, 1982.
DOI : 10.1007/BF01459082

J. Dumas and E. Kaltofen, Essentially optimal interactive certificates in linear algebra, Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ISSAC '14, pp.146-153
DOI : 10.1145/2608628.2608644
URL : https://hal.archives-ouvertes.fr/hal-00932846

J. Dumas, E. Kaltofen, E. Thomé, and G. Villard, Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix, Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC '16, pp.199-206
DOI : 10.1007/3-540-09519-5_73
URL : https://hal.archives-ouvertes.fr/hal-01266041

J. Dumas, D. Lucas, and C. Pernet, Certificates for Triangular Equivalence and Rank Profiles, Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation , ISSAC '17, pp.133-140
DOI : 10.1145/2755996.2756672
URL : https://hal.archives-ouvertes.fr/hal-01466093

A. Fiat and A. Shamir, How To Prove Yourself: Practical Solutions to Identification and Signature Problems, CRYPTO '86, pp.186-194, 1987.
DOI : 10.1007/3-540-47721-7_12

R. Freivalds, Fast probabilistic algorithms, Mathematical Foundations of Computer Science, pp.57-69, 1979.
DOI : 10.1007/3-540-09526-8_5

F. R. Gantmacher, The Theory of Matrices, 1959.

J. Zur-gathen and J. Gerhard, Modern Computer Algebra, 2003.
DOI : 10.1017/CBO9781139856065

P. Giorgi and V. Neiger, Certification of Minimal Approximant Bases, Proceedings of the 2018 ACM on International Symposium on Symbolic and Algebraic Computation , ISSAC '18, 2018.
DOI : 10.1007/3-540-09519-5_73
URL : https://hal.archives-ouvertes.fr/hal-01701861

, Preprint dated, 2018.

C. Giorgi, G. Jeannerod, and . 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
URL : https://hal.archives-ouvertes.fr/hal-02101878

S. Goldwasser, Y. T. Kalai, and G. N. Rothblum, Delegating computation: Interactive proofs for muggles, STOC '08, pp.113-122, 2008.

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
DOI : 10.1016/j.jsc.2011.09.006

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.

C. Jeannerod, C. Pernet, and A. Storjohann, Rank-profile revealing Gaussian elimination and the CUP matrix decomposition, Journal of Symbolic Computation, vol.56, pp.46-68, 2013.
DOI : 10.1016/j.jsc.2013.04.004
URL : https://hal.archives-ouvertes.fr/hal-00841300

T. Kailath, Linear Systems, 1980.

E. L. Kaltofen, M. Nehring, and B. D. Saunders, Quadratic-time certificates in linear algebra, Proceedings of the 36th international symposium on Symbolic and algebraic computation, ISSAC '11, pp.171-176, 2011.
DOI : 10.1145/1993886.1993915
URL : http://www.math.ncsu.edu/%7Ekaltofen/bibliography/11/KNS11.pdf

E. L. Kaltofen, B. Li, Z. Yang, and L. Zhi, Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients, Journal of Symbolic Computation, vol.47, issue.1, pp.1-15
DOI : 10.1016/j.jsc.2011.08.002

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, pp.44-71, 2017.
DOI : 10.1016/j.jco.2017.03.003
URL : https://hal.archives-ouvertes.fr/hal-01345627

L. Gall, Powers of tensors and fast matrix multiplication, Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ISSAC '14, pp.296-303
DOI : 10.1145/2608628.2608664

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

T. Mulders and A. Storjohann, Certified dense linear system solving, Journal of Symbolic Computation, vol.37, issue.4, pp.485-510, 2004.
DOI : 10.1016/j.jsc.2003.07.004
URL : https://doi.org/10.1016/j.jsc.2003.07.004

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, pp.357-364
DOI : 10.1109/TAC.1983.1103203
URL : https://hal.archives-ouvertes.fr/hal-01457979

V. Neiger, J. Rosenkilde, and G. Solomatov, Computing Popov and Hermite Forms of Rectangular Polynomial Matrices, Proceedings of the 2018 ACM on International Symposium on Symbolic and Algebraic Computation , ISSAC '18, 2018.
DOI : 10.1145/2442829.2442881
URL : https://hal.archives-ouvertes.fr/hal-01701867

, Preprint dated, 2018.

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

C. Pernet and W. Stein, Fast computation of Hermite normal forms of random integer matrices, Journal of Number Theory, vol.130, issue.7, pp.1675-1683, 2010.
DOI : 10.1016/j.jnt.2010.01.017
URL : https://hal.archives-ouvertes.fr/hal-00798442

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

J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM, vol.27, issue.4, pp.701-717, 1980.
DOI : 10.1145/322217.322225

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

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

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.

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://perso.ens-lyon.fr/gilles.villard/BIBLIOGRAPHIE/PDF/issac96.pdf

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

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
DOI : 10.1145/2465506.2465947
URL : http://dl.acm.org/ft_gateway.cfm?id=2465947&type=pdf

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, A deterministic algorithm for inverting a polynomial matrix, Journal of Complexity, vol.31, issue.2, pp.162-173
DOI : 10.1016/j.jco.2014.09.004

R. , Probabilistic algorithms for sparse polynomials, EUROSAM'79, pp.216-226, 1979.
DOI : 10.1007/3-540-09519-5_73