Ein Algorithmus zur Spaltenapproximation mit minimalem Grad

Die spärliche Gaußsche Eliminierung mit partiellem Pivotieren berechnet die Faktorisierung PAQ = LU einer spärlichen Matrix A, wobei die Zeilenanordnung P während der Faktorisierung unter Verwendung des standardmäßigen partiellen Pivotierens mit Zeilenvertauschungen ausgewählt wird. Ziel ist es, eine Spaltenvorordnung Q auszuwählen, die ausschließlich auf dem Nicht-Null-Muster von A basiert und die schlimmstenfalls die Anzahl der Nicht-Null-Elemente in der Faktorisierung begrenzt. Die Auffüllung hängt ebenfalls von P ab, aber Q wird ausgewählt, um eine obere Schranke für die Auffüllung bei jeder nachfolgenden Wahl von P zu reduzieren. Die Wahl von Q kann einen dramatischen Einfluss auf die Anzahl der Nicht-Null-Elemente in L und U haben. Ein Verfahren zur Bestimmung einer günstigen Spaltenanordnung für A besteht darin, eine symmetrische Anordnung zu berechnen, die die Auffüllung in der Cholesky-Faktorisierung von A^T A reduziert. Ein konventioneller Algorithmus zur Anordnung mit minimalem Grad würde erfordern, dass die Sparsamkeitsstruktur von A^T A berechnet wird, was sowohl in Bezug auf den Speicher als auch auf die Zeit teuer sein kann, da A^T A möglicherweise viel dichter als A ist. Eine Alternative besteht darin, Q direkt aus der Sparsamkeitsstruktur von A zu berechnen; diese Strategie wird vom COLMMD-Vorordnungsalgorithmus von MATLAB verwendet. Ein neuer Anordnungsalgorithmus, COLAMD, wird vorgestellt. Er basiert auf derselben Strategie, verwendet jedoch eine bessere Anordnungsheuristik. COLAMD ist schneller und berechnet bessere Anordnungen mit weniger Nicht-Null-Elementen in den Faktoren der Matrix.