Algèbre linéaire

Analyse de complexité

V. Pan a découvert en 1978 une méthode pour multiplier:

: Quelle est la complexité d’un algorithme diviser pour régner utilisant ces formules? Comparer avec la complexité de l’algorithme de Strassen.

Arithmétique naïve des matrices

Ce TD est à développer de préférence dans un notebook Jupyter.

Nous allons enrichir la classe Matrice, créée au TD précédent, avec les méthodes pour les opérations arithmétiques de base : addition, négation, multiplication.

Nous avons déjà appris à définir la méthode spéciale __repr__ pour contrôler l’affichage d’un objet Python. D’autres méthodes spéciales permettent de définir un comportement lorsque un objet est combiné avec un opérateur arithmétique. Par exemple, le code suivant permet de définir un comportement pour l’addition :

>>> class MaxPlus:
...     def __init__(self, val):
...         self.val = val
... 
...     def __repr__(self):
...         return str(self.val)
... 
...     def __add__(self, other):
...         return MaxPlus(max(self.val, other.val))
... 
>>> MaxPlus(10) + MaxPlus(2)
10

Voici une liste des méthodes spéciales qui nous intéressent pour les matrices :

Méthode spéciale opération opérateur
__add__(self, other) addition a+b
__sub__(self, other) soustraction a-b
__mul__(self, other) mulitplication a*b
__truediv__(self, other) division exacte a/b
__neg__(self) négation unaire -a
__invert__(self) inverse ~a
__eq__(self, other) test d’égalité a==b

À l’exception de __neg__ et __invert__, qui représentent des opérations unaires, toutes les méthodes prennent deux paramètres : le premier est l’opérande gauche, le deuxième l’opérande droit.1 À l’exception de __eq__, qui donne une valeur booléene, toutes les autes méthodes doivent donner un objet en retour, typiquement un nouvel objet appartenant à la même classe et représentant le résultat de l’opération.

: Implanter la méthode __eq__ pour la classe Matrice. Deux matrices sont égales si et seulement si toutes leurs entrées sont égales.

: Implanter les méthodes __add__, __neg__ et __sub__ pour la classe Matrice.

: Implanter la méthode __mul__ pour la classe Matrice, en utilisant l’algorithme de multiplication naïf.

Algorithme de multiplication de Strassen

On rappelle les formules de Strassen. Étant données deux matrices et , à coefficients dans un anneau non-commutatif, le produit se calcule comme suit :

: Ajouter une méthode strassen à la classe Matrice, qui calcule le produit de deux matrices carrées en utilisant la méthode de Strassen récursive.

Note : Pour simplifier, on pourra se limiter à implanter une méthode qui multiplie des matrices de taille une puissance de 2.

Comparer les performances

Nous voulons maintenant comparer les performances des méthodes naïve et de Strassen, afin de mesurer la taille à partir de laquelle la deuxième devient intéressante.

Avec Jupyter

Le notebook Jupyter nous permet de faire ces mesures aisément. La clef magique %time permet de mesurer le temps d’exécution d’une instruction Python. Par exemple

%time A.strassen(X)

affichera plusieurs informations sur le temps d’exécution de la méthode strassen. La clef magique %timeit fait des mesures plus précises en exécutant plusieurs fois la même instruction, et en prenant une moyenne.

Sans Jupyter

Nous pouvons aussi utiliser le module timeit en python.

Avec python ≥ 3.6, on utilise:

print(timeit.autorange('A.strassen(X)', globals=globals()))

Avec python ≥ 3.5:

print(timeit.repeat('A.strassen(X)', globals=globals()))

: Déterminer le point où l’algorithme de Strassen croise l’algorithme naïf.

: Optimiser la méthode de Strassen en arrêtant la récursion en dessous d’un seuil déterminé expérimentalement.

Solution de systèmes

: Implanter une méthode solve qui prend en entrée un vecteur , et qui calcule une solution au système par la méthode de Gauss.

: Implanter la méthode __invert__ pour inverser une matrice carrée (suggestion : vous pouvez utiliser la méthode solve de façon répétée).

  1. C’est toujours la méthode de la classe de l’opérande gauche qui est appelée. Python ne donne aucune garantie sur la classe de l’opérande droit, c’est la responsabilité du développeur de vérifier que l’opérande droit peut bien être combiné avec l’opérande gauche.