Ist das Sparsity-Muster eines linearen Systems für iterative (KSP) Löser wichtig?

So ziemlich die Frage. Wie wichtig ist bei einer allgemein spärlichen, nicht symmetrischen (sowohl numerisch als auch strukturell) Matrix das Sparsity-Muster (dh die Zeilen- / Spaltenpermutation von Matrix / Vektor) für iterative Löser? Ich kann sehen, dass es für Direktlöser (LU) oder Vorkonditionierer (ILU) wichtig wird, indem es die Anzahl der Füllungen direkt beeinflusst.

Für iterative Löser scheint es jedoch, dass der wichtigste Teil die MatVec-Operation ist, die sich nicht um das tatsächliche Matrixmuster zu kümmern scheint. Gibt es eine Komponente, die von dem Muster abhängen könnte, das ich hier nicht in Betracht ziehe?

Wie wäre es parallel? Ich vermute, dass das Muster für die Verteilung der Matrix und der Vektoren wichtig werden könnte und somit das Kommunikationsvolumen / den Overhead bestimmt, möchte aber andere Gedanken und Eingaben sehen.

Ich frage dies sowohl allgemein als auch in Bezug auf die KSP-Löser von PETSc.

linear-algebra petsc iterative-method mmirzadeh
quelle

Parallel dazu sollte es nur dann ein Problem geben, wenn eine Zeile oder Spalte eine sehr große Anzahl von Nicht-Nullen enthält. Eine Pfeilspitzenmatrix ist ein schönes Beispiel für einen solchen Fall (eine Diagonalmatrix plus eine dichte letzte Zeile und Spalte).

Jack Poulson

Ist "Sparsity Pattern" hier das richtige Wort? afaik, Sie fragen nach der Reihenfolge der Matrixeinträge, während sich der Begriff "Sparsity-Muster" beispielsweise auf Diagonale, Tridiagonale, Blockdiagonale usw.

bezieht

@Martin Beachten Sie, dass eine Eigenschaft wie "tridiagonal" immer noch von der Reihenfolge abhängt. Stellen Sie sich zum Beispiel ein 1D-Problem in zufälliger Reihenfolge vor.

Jed Brown

Antworten:

Die Bestellung ist nur für den Lastausgleich / die Kommunikation und die Eignung zur Vorkonditionierung von Bedeutung. Die Krylov-Methode kümmert sich nicht um die Reihenfolge oder sogar darum, ob die Matrixeinträge gespeichert sind.

In der Praxis erfordert eine schlechte Bestellung möglicherweise viel mehr Kommunikation als sonst erforderlich, wenn mit einer Matrix multipliziert wird. Ein Beispiel finden Sie im Abschnitt des PETSc-Benutzerhandbuchs zu "Natürliche Bestellung" im Vergleich zu "PETSc-Bestellung". Darüber hinaus kann eine Reihenfolge, die einer fehlerhaften parallelen Partition entspricht, die Vorkonditionierung der Domänenzerlegung weniger effektiv machen. Beachten Sie, dass es hier auf die Partition ankommt, obwohl eine Partition eine (Äquivalenzklasse von) Reihenfolge induziert.

Jed Brown
quelle