===== Komplexitäten =====

Editierhinweise: Zum Escapen zwei Prozentzeichen am Anfang und am Ende nutzen. Zwei Backslashes und Leerzeichen für eine Newline in der Tabelle.

^ Problem ^ Aufwand ^ Weitere Anmkerungen ^
| Matrix-Vektor|O(n²)|
| Matrix-Matrix|O(n³)|
| Matrix-Vektor, wenn Matrix Rang 1 hat und %%A = uv^T%% geg.|O(n)|
| LR-Zerlegung|O(n³)|
| QR-Zerlegung|O(n³)|
| QR mit Householder:|~doppelt so viel wie LR|
| QR mit Givens-Rotation:|~vier mal so viel wie LR|
| Cholesky: SPD Matrizen|~halb so groß wie LR|
| Rückwärts- & Vorwärtssubst. bei geg. LR:|O(n²)|
| Lösen bei geg. LR:|O(n²)||
| Lösen bei geg. QR:|O(n²)|
| A = LU, Determinante:|O(n)||
| A = P L U, Betrag der Determinante|O(n)|
| A = P L U, Determinante:|O(n³)|vllt. O(n²)\\ Siehe unten.|
| A = QR, Determinante|O(n³)|
| A = QR, Betrag der Determinante|O(n³)|
| LR m-diagonale Matrix:|O(m² * n)|
| Rückwärts- & Vorwärtssubst. bei geg. LR von m-diagonaler Matrix:|O(n*m)|
|||
| Interpolation Nearest Neighbor:|O(h)|
| Interpolation Linear:|O(h²)|
| Interpolation Catmull-Rom|O(h³)|
|||
| Newton (Aitken-Neville Pyramide):|O(n²)|
| De Casteljau:|O(n²)|
| Midpoint Subdivision Fehler:|%%O(1/(levelZahl^4))%%|
|||
| Ein Iterationsschritt Jacobi / GS / SOR|O(n²)|
| Anzahl Iterschritte bei Jacobi|O(n)|(Schätzwert)|
| Anzahl Iterschritte bei SOR|O(sqrt(n))|(Schätzwert)|
| Konvergenzordnung Jacobi / GS / SOR|rho = 1|Lineare Konvergenz, d. h. feste Anzahl an Iterationen nimmt der Fehler um einen __Faktor__ ab.|
|||
| Filter NxN Bildausschnitt (Rand vernachlässigbar), nicht sep. MxM Filter, insgesamte Anz. arithmetischer Ops:|2 N² M²|
| Filter NxN Bildausschnitt (Rand vernachlässigbar), sep. MxM Filter, insgesamte Anz. arithmetischer Ops:|4 N² M|

===== Algorithmen Details =====

==== A = PLU, det(A) bestimmen. ====

Beachte, dass nur |det(P)| = 1 gilt (mit Betrag!). Da P reell, kann also det(P) nur + 1 oder -1 sein.

P ist eine Permutationsmatrix, d. h. die Spalten sind e_1, e_2, e_3, ... nur umsortiert. Finde zuerst die erste 1 in der ersten Zeile (dies ist e_1), dann dies 'gedanklich' vortauschen. Pro Tauschschritt ändert sich die Determinante um den Faktor (-1). Dann finde die erste 1 in der zweiten Zeile usw. Das sind n^2 Schritte. Die finale Determinante ergibt sich zu: %%det(P) = (-1)^#Vertauschungen%%