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

URL : http://www.scg.uwaterloo.ca/~glabahn/berndgeorge2.ps

B. Beckermann and G. Labahn, Recursiveness in matrix rational interpolation problems, Journal of Computational and Applied Mathematics, vol.77, issue.1-2, pp.1-2, 1997.
DOI : 10.1016/S0377-0427(96)00120-3

URL : https://doi.org/10.1016/s0377-0427(96)00120-3

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

D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Comput, vol.9, pp.3-251, 1990.
DOI : 10.1016/s0747-7171(08)80013-2

URL : https://doi.org/10.1016/s0747-7171(08)80013-2

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

URL : http://www.dtic.mil/cgi-bin/GetTRDoc?AD=ADA050745&Location=U2&doc=GetTRDoc.pdf

J. Dumas, P. Giorgi, and C. Pernet, Dense Linear Algebra over Word-Size Prime Fields, ACM Transactions on Mathematical Software, vol.35, issue.3, p.19, 2008.
DOI : 10.1145/1391989.1391992

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

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, 2014.
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, 2016.
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, 2017.
DOI : 10.1145/2755996.2756672

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

J. Farkas, Theorie der einfachen Ungleichungen, J. Reine Angew. Math, vol.124, pp.1-27, 1902.

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

P. Giorgi, Certification of Polynomial Middle Product Available at https, 2017.

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

URL : http://www.lirmm.fr/~giorgi/issac03.pdf

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.

E. 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-1, 2012.
DOI : 10.1016/j.jsc.2011.08.002

E. 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

T. Kimbrel and R. K. Sinha, A probabilistic algorithm for verifying matrix products using O(n2) time and log2n + O(1) random bits, Information Processing Letters, vol.45, issue.2, pp.107-110, 1993.
DOI : 10.1016/0020-0190(93)90224-W

T. Kleinjung, C. Diem, A. K. Lenstra, C. Priplata, and C. Stahlke, Computation of a 768-Bit Prime Field Discrete Logarithm, Eurocrypt 2017, pp.185-201, 2017.
DOI : 10.1109/TIT.1986.1057137

F. and 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, 2014.
DOI : 10.1145/2608628.2608664

R. Motwani and P. Raghavan, Randomized Algorithms, 1995.

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

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

URL : http://rjlipton.files.wordpress.com/2009/11/schwartz.pdf

A. Storjohann, Notes on computing minimal approximant bases, Challenges in Symbolic Computation Software (Dagstuhl Seminar Proceedings), 2006.

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 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