Multiplier deux matrices à la main

Calcul matriciel et systèmes linéaires · Produit, transposition et commutation · niveau 3 (difficile)

Énoncé

Écrire une fonction Python produit(A, B) qui calcule le produit de deux matrices données comme listes de listes, sans utiliser numpy. Combien de multiplications effectue-t-elle pour deux matrices $n \times n$ ?

Corrigé


def produit(A, B):
    n, p, q = len(A), len(B), len(B[0])
    assert len(A[0]) == p, "dimensions incompatibles"
    C = [[0] * q for _ in range(n)]
    for i in range(n):
        for j in range(q):
            s = 0
            for k in range(p):
                s = s + A[i][k] * B[k][j]
            C[i][j] = s
    return C

Le compte. Les trois boucles imbriquées parcourent $n \times q \times p$ triplets, et chacun coûte exactement une multiplication. Pour deux matrices $n \times n$ , cela fait $n^{3}$ multiplications (et $n^{2} (n - 1)$ additions).

C'est une complexité cubique : doubler la taille multiplie le temps par huit. Sur $n = 1000$ , on est déjà à un milliard d'opérations — et c'est la raison pour laquelle on délègue ce calcul à numpy, dont les boucles sont compilées.

L'assert n'est pas décoratif : sans lui, un décalage de dimensions lèverait une erreur d'indice obscure au fond de la troisième boucle, au lieu de dire tout de suite ce qui ne va pas.

Énoncé

Corrigé

Exercices semblables