Die Matrixmultiplikation ist assoziativ. Das bedeutet, dass sich bei Produkten aus mehr als zwei Matrizen die Klammerung der Multiplikationen nicht auf das Ergebnis auswirkt. Allerdings wirkt sich die Klammerung auf den Rechenaufwand aus.

Der beste Algorithmus für das Finden der optimalen Klammerung benutzt das Verfahren der sogenannten dynamischen Programmierung. Anstatt dessen wird hier ein einfacherer Algorithmus verwendet, der in die Klasse der "gierigen" (engl. greedy) Verfahren fällt.

Für jedes benachbarte Paar von Matrizen A mit Abmessungen m x n und B im Format n x p wird die durch die Multiplikation erreichte Abnahme der Elementanzahl bestimmet: vorher haben beide Matrixen zusammen m * n + n * p Elemente, nachher ist die Zahl m * p.

Durch die Funktion find-minimum-pair wird das Paar von Matrixen gesucht, bei dem die größte Abnahme eintritt. Haben zwei Paare die gleiche Reduktion, wird noch die Zahl der Multiplikationen m * n * p zum Vergleich herangezogen. Niedrige Zahlen werden bevorzugt.

Die Funktion replace-matrix-pair ersetzt die Matrixen aus dem besten Paar durch ihr Produkt. Das Verfahren beginnt von vorne, solange noch mindestens zwei Matrizen übrig sind.

(defproc chain-product (matrixes)
  (if
    (single? matrixes)
    (first matrixes)
    (let
      ((pair (find-minimum-pair matrixes)))
      (chain-product
        (replace-matrix-pair
          (first pair)
          (* (first pair) (second pair))
          matrixes)))))

(defproc find-minimum-pair (matrixes)
  (first
    (sort
      (zip-with
        (lambda (left right)
          (list
            left
            right
            (element-count-reduction left right)
            (multiplication-count left right)))
        (butlast matrixes)
        (rest matrixes))
      (lambda (e1 e2)
        (or
          (> (third e1) (third e2))
          (and
            (= (third e1) (third e2))
            (< (fourth e1) (fourth e2))))))))

(defproc element-count-reduction (left right)
  (-
    (+ (get-element-count left)
       (get-element-count right))
    (* (. left rows)
       (. right columns))))

(defproc multiplication-count (left right)
  (* (. left rows)
     (. left columns)
     (. right columns)))

(defproc replace-matrix-pair (left product matrixes)
  (cond
    ((null? matrixes)
      nil)
    ((= left (first matrixes))
      (cons
        product
        (rest (rest matrixes))))
    (t
      (cons
        (first matrixes)
        (replace-matrix-pair left product (rest matrixes))))))