Fast matrix multiplication

In this thesis, we tackle the problem of matrix multiplication complexity. Matrix multiplication, which is a bilinear map, can henceforth be represented by a third-order tensor. Decompositions of the associated tensor as a sum of $F$ rank-$1$ tensors provide algorithms to compute the product of $\left(n,p\right)$ by $\left(p,n\right)$ matrices with $F$ ``active multiplications''. The minimal number of rank-$1$ terms necessary to decompose a tensor is its rank. Although the problem is quite old (it was initiated in 1969 by V. Strassen), only partial results are known so far. For example, we know that the rank of the tensor associated to the multiplication of $\left(3,3\right)$ matrices is between $19$ and $23$ but its exact value is still not determined. However, recent developments in numerical multi-linear algebra open the door for further improvements. The emergence of numerical algorithms for the decomposition of tensors induced a paradigm shift in the estimation of matrix multiplication complexity. In a first time, we are interested in practical algorithms to efficiently compute matrix multiplication, i.e. with less ``active multiplications'' than the ``straightforward'' algorithm. Practical algorithms require that the rank-$1$ terms are sparse and contain only entries in $\left\lbrace -1,0,+1 \right\rbrace$ or $\left\lbrace -1,-1/2,0,+1/2,+1 \right\rbrace$ for example. We present a method for decomposing small tensors into the sum of sparse rank-$1$ tensors with entries in $\left\lbrace -1,0,+1 \right\rbrace$. Applying the method on matrix multiplication tensors, we propose efficient algorithms for computing the product of $\left(3,2\right)$ by $\left(2,3\right)$ matrices or $\left(3,3\right)$ by $\left(3,3\right)$ matrices for example and using only scalar additions, subtractions and multiplications. In a second time, we concentrate on the relations between decompositions. Invariant transformations define a class of transformations acting on the decompositions of a matrix multiplication tensor but leaving the result unchanged, i.e. the transformed decomposition is still a decomposition of the same tensor. We introduce the concept of characteristic polynomials of a decomposition. Thanks to that, we provide a necessary condition for a decomposition to be ``discretizable'', i.e. be joinable (via invariant transformations) to a decomposition with rank-$1$ terms containing only $\pm 1$ or $0$ entries. Finally, we propose an algorithm for deciding whether two decompositions are equivalent through invariant transformations. The algorithm uses linear algebra and a novel strategy to get rid of the ``permutation equivalence'' that might exist between the two decompositions. With it, we analyze the distribution of the equivalence classes of decompositions through invariant transformations: ``is there a unique decomposition up to invariant transformations?'' or ``picking two decompositions of a same matrix multiplication tensor, is there any chance that they are equivalent through invariant transformations?''. For the different cases we discuss, namely multiplication of matrices with sizes between $\left(1,2\right)$ by $\left(2,1\right)$ and $\left(3,3\right)$ by $\left(3,3\right)$, it seems that only two different situations occur: either there is one and only one equivalence class of decompositions or the equivalence classes are so numerous that two ``randomly picked'' decompositions are equivalent with probability zero.