produit de deux matrices

Le but de cet exercice est d’implémenter le calcul du produit de deux matrices creuses $C = A B$ en utilisant la classe de matrice creuse au format COO basée sur une std::map que vous avez écrite en cours.

Si l’on se place pour simplifier dans le cas de matrices carrées de taille $N$ et en supposant que l’on a $O(1)$ éléments par ligne, l’algorithme que vous écrirez devra avoir une complexité en $O(N \log(N))$.

Vous pourrez par exemple tester votre algorithme pour le calcul du carré $A A$ de la matrice tridiagonale ci-dessous :

$$ \begin{equation} A = \begin{pmatrix} 2 & -1 & 0 & 0 & \dots & 0 & 0 \\\ -1 & 2 & -1& 0 & \dots & 0 & 0 \\\ 0 & -1 & 2 & -1& \dots & 0 & 0 \\\ \vdots & \ddots & \ddots & \ddots & \dots & \vdots & \vdots \\\ 0 & 0 & 0 & 0 & \dots & -1 & 2 \\ \end{pmatrix} \end{equation} $$

Vous pourrez illustrer la complexité de l’algorithme en reportant les temps de calcul (vous pourrez utiliser clock()) lorsque $N$ varie, comme dans la figure ci-dessous :