Heuristik von Curtis, Powell und Reid

Die Heuristik von Curtis, Powell und Reid (im Folgenden auch CPR-Heuristik) ist eine Methode zum Auffinden der Spalten (bzw. Zeilen) einer dünnbesetzten Matrix, die linear kombiniert werden können.

Problem

Sei J eine dünnbesetzte $m\times n$-Matrix. Finde eine binäre $n\times p$-Matrix S mit minimalem p, so dass alle von Null verschiedenen Elemente von J in dem Produkt $\tilde{J}=J\cdot S$ (der komprimierten Version von J) auftauchen.

Strukturelle Orthogonalität

Zwei Vektoren einer Matrix heißen strukturell orthogonal, wenn es keine Zeile gibt, in denen sie beide Elemente verschieden von Null besitzen. Daraus folgert, dass das Skalarprodukt dieser beiden Vektoren null ist, was eine notwendige, aber keine hinreichende Bedingung ist.

Aufstellen einer Partition

Gruppen von strukturell orthogonalen Spalten werden durch eine Partition beschrieben.

$P: i \rightarrow \{1,2, \dots ,p\}$

$P(i)=k\Leftrightarrow$ i-te Spalte ist in k-ter Gruppe von strukturell orthogonalen Spalten.

Die Nummer einer Gruppe wird auch Farbe genannt.

Es werden zum Aufstellen der Partition alle Spalten durchgegangen bis die Farben zugeordnet sind. Dabei wird jeweils die Farbe mit der niedrigsten Nummer zugewiesen, falls die aktuell betrachtete Spalte zu einer oder mehreren Spalten strukturell orthogonal ist. Ist die Spalte zu keiner Spalte strukturell orthogonal, dann erhält sie eine neue Farbe mit der nächsthöheren Nummer.

Aufstellen der Saat-Matrix

Aus der Partition P kann die Saat-Matrix S wie folgt bestimmt werden: Der Eintrag S_i,j = 1, falls Spalte i die Farbe k hat und ansonsten S_i,j = 0.

Bemerkung: Da S im Allgemeinen nicht invertierbar ist benötigt man das Dünnbesetztheits-Muster um von der komprimierten Version $\tilde{J}$ wieder auf die unkomprimierte Version J zu kommen.