Projekt 1: Konjugierte Gradienten

21.06.2019 / B. Leder

Wissenschaftliches Rechnen III / CP III

Ziele

  1. Konjugierte Gradienten (CG) [1] für den diskreten Laplace-Operator [2] auf der GPU implementieren.

  2. Mixed-precision CG: Nutzen Sie preconditioning (siehe Kapitel 12 in [1]), um den Großteil der Berechnungen auf der GPU in einfacher Genauigkeit durchzuführen, und doch das Ergebnis auf der CPU in doppelter Genauigkeit zu erhalten.

  3. Potenzmethode (power methode/power iteration) in Verbindung mit CG anwenden, um den kleinsten und größten Eigenwert (\(\lambda_{min}\), \(\lambda_{max}\)) zu bestimmen (siehe z.B. [4]) \[\begin{align} & q^{(0)} \mathrm{beliebig} \nonumber \\ & \mathrm{for} \; k=1,2,... \nonumber \\ & \quad z^{(k)}=A q^{(k-1)} \nonumber \\ & \quad q^{(k)}=z^{(k)}/||z^{(k)}|| \nonumber \\ & \quad \lambda^{(k)}={q^{(k)}}^{T} q^{(k)} \nonumber \\ & \mathrm{end} \nonumber \end{align}\] mit \(|\lambda_{max} - \lambda^{(k)}|\to 0\).

  4. Bestimmung der benötigten CG-Iterationen für eine feste Genauigkeit (Reduktion der Residuumsnorm) und Vergleich mit dem erwarteten Konvergenzverhalten in Abhängigkeit von der Konditionszahl \(\kappa=\lambda_{max}/\lambda_{min}\).

Anforderungen / Hinweise:

[1] Jonathan Richard Shewchuk, “An Introduction to the Conjugate Gradient Method Without the Agonizing Pain” http://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf

[2] Endliche Differenzen-Diskretisierung der Laplace-Gleichung mit Randbedingungen (Englisch) http://people.physik.hu-berlin.de/~leder/cp3/laplace.pdf

[3] Vorgegebene CPU-Version http://people.physik.hu-berlin.de/~leder/cp3/uebung5.zip

[4] Gene H. Golub, Charles F. Van Loan “Matrix Computations”, Johns Hopkins University Press, 1989