Complexité et jeux combinatoires sur les graphes

English

Séminaire Modèles et Algorithmes Déterministes: CASYS

10/04/2014 - 09:45 Mr Pascal Giorgi (Université de Montpellier) Salle 1 - Tour IRMA

Matrix multiplication is an important tool for scientific computing, especially in computer algebra. In the latter case, the matrix entries are not floating point numbers but can be integers, finite field elements, polynomials or even more complex algebraic structure. Since nowadays processors do not provide a native supports to all these structures one need to handle carefully the underlying arithmetic to get efficient matrix multiplication. In this talk, I will report on some recent development to get efficient matrix multiplication for multi-precision integers or polynomials. In particular, I will discuss the use of matrix multiplication with small entries (e.g. floating point number) combined with algebraic decomposition such as Chinese remainder theorem or discrete Fourier transform.