Neues Reordering‑Netzwerk minimiert Fill‑Ins bei spärlichen Matrizen

In der linearen Algebra entstehen bei der LU‑Faktorisierung sogenannte Fill‑Ins – neue Nicht‑Null‑Elemente, die die Speicher‑ und Rechenkosten stark erhöhen. Für große, spärliche Matrizen ist die Suche nach einer optimalen Zeilen‑ oder Spaltenanordnung, die diese Fill‑Ins minimiert, ein NP‑schweres Problem. Traditionelle Heuristiken liefern zwar praktikable Permutationen, garantieren jedoch keine Nähe zum wahren Optimum.

Die neue Methode nutzt ein neuronales Reordering‑Netzwerk, das die Zeilen‑ bzw. Spaltenreihenfolge anhand eines Graphencoders vorhersagt. Anstatt die Fill‑Ins direkt zu zählen, minimiert das Netzwerk die l1-Norm der oberen und unteren Dreiecksfaktoren der neu geordneten Matrix – ein indirekter, aber effektiver Schätzer für die tatsächliche Anzahl der Fill‑Ins. Durch zwei neu entwickelte Reparameterisierungstechniken wird aus den vorhergesagten Knotenscores eine Permutationsmatrix abgeleitet, die die Matrix anschließend umsortiert.

Der Optimierungsprozess integriert die Faktorisierung selbst in die Zielfunktion. Mit einer Kombination aus dem Alternating‑Direction‑Method‑of‑Multipliers (ADMM) und proximalem Gradientenabstieg wird die Gesamtfunktion effizient angepasst. Auf einer Reihe von Benchmark‑Datensätzen spärlicher Matrizen zeigte die Methode signifikante Reduktionen der Fill‑Ins und damit verbundener Speicher‑ und Laufzeitkosten, ohne dabei die Genauigkeit der Faktorisierung zu beeinträchtigen.

Diese Arbeit liefert damit einen wichtigen Schritt in Richtung automatisierter, theoretisch fundierter Matrixreordering‑Algorithmen, die sowohl in wissenschaftlichen Berechnungen als auch in industriellen Anwendungen von großem Nutzen sein können.