Dieses Papier stellt eine Reihe exakter Overlays für die 4x4-Matrixmultiplikation vor, die die gezählte Anzahl der Multiplikationen reduzieren, ohne die zugrundeliegende bilineare Komplexität des Basisalgorithmus, wie beispielsweise Strassens 49-Multiplikationsalgorithmus oder den optimalen 48-Multiplikationsalgorithmus, zu verändern. Wir präsentieren mehrere wertbewusste Techniken, die die numerischen Eigenschaften der Eingabematrizen ausnutzen. Die Hauptbeiträge umfassen die 'Peeler'-Methode, eine Subtraktionstechnik pro Blattmodus mit einem nachweislich engen Kostenmodell; 'Value-Aware Collapse', ein Zählmodell, das Multiplikationen mit -1, 0 oder 1 als kostenfrei behandelt; und einen 'Block Peeler' für optimale Algorithmen. Um die Wirksamkeit dieser Methoden weiter zu verstärken, führen wir strukturelle Änderungen mit null-arithmetischen Kosten ein, darunter 'Permutation Clustering' und 'Inner Sign-Perm Reindexing'. Zusätzlich schlagen wir einen 'Bit-Sliced GEMM'-Pfad für Ganzzahl- und Festkommamatrizen vor, der skalare Multiplikationen vollständig eliminiert und durch effiziente bitweise Operationen ersetzt. Wir leiten geschlossene Formeln für die erwarteten Rechenzeiteinsparungen bei verschiedenen diskreten Eingangsverteilungen her und validieren unsere Ergebnisse mit einem umfassenden experimentellen Protokoll. Die vorgeschlagenen Overlays bewahren die Worst-Case-Leistung der Basisalgorithmen und ermöglichen gleichzeitig erhebliche Rechenzugwinne bei strukturierten, quantisierten oder spärlichen Daten, was einen praktischen Weg zur Beschleunigung der Matrixmultiplikation in verschiedenen realen Anwendungen bietet.
Michael Rey (Fr,) untersuchte diese Frage.