Rationales Multilevel Jacobi-Davidson Verfahren für ... · Gliederung I Einführung in die Kernfusion mit dem Tokamak I Eigenwertgleichung zur Beschreibung der Verluste I Lösen

Rationales Multilevel Jacobi-Davidson Verfahren fürEigenwertgleichungen in der Plasma Physik

Dominik Löchel

Betreuer: M. Hochbruck und M. Tokar; Kooperation mit D. Reiser

Graduiertenkolleg „Dynamik heißer Plasmen“

Mathematisches InstitutHeinrich-Heine-Universität Düsseldorf

Dezember 2009

Gliederung

I Einführung in die Kernfusion mit dem Tokamak

I Eigenwertgleichung zur Beschreibung der VerlusteI Lösen der EigenwertgleichungI Der Multilevel Jacobi-Davidson Algorithmus für rationale

EigenwertproblemeI Zusammenfassung

Energiegewinnung durch Kernfusion

I Fusion von Deuterium undTritium zu Helium

I Überwindung der CoulombBarriere→ starke Kernkraft

I hohe Temperatur undhohe Dichteausreichend lange Zeit

I PlasmaI magnetischer Einschluss















I Plasma

I magnetischer Einschluss






Tokamak

I toroidale Magnetfeldspulen

I magnetische Feldlinien in der FlussoberflächeI PrimärspuleI Transformator-Eisenkern

Tokamak

I toroidale MagnetfeldspulenI magnetische Feldlinien in der Flussoberfläche

I PrimärspuleI Transformator-Eisenkern

Tokamak



Tokamak

~v~E×~B←−∇B



Tokamak

I toroidale MagnetfeldspulenI magnetische Feldlinien in der FlussoberflächeI PrimärspuleI Transformator-Eisenkern

Drift Instabilitäten

I toroidale MagnetfeldspulenI magnetische Feldlinien in der FlussoberflächeI PrimärspuleI Transformator-Eisenkern

Drift Instabilitäten

← →↑

↓I toroidale MagnetfeldspulenI magnetische Feldlinien in der FlussoberflächeI PrimärspuleI Transformator-Eisenkern

Divertor und X-Punkt Geometrie

0 1 2 3 4 5−2

−1

0

1

2

Von der PDE zur Eigenwertgleichung

� �PDE

↓�� Separation: f = fmakroskopisch + fmikroskopisch

↓�� Linearisierung

↓��

��Welle φ̃(θ, t) =

∑kr , k⊥, ω φkr , k⊥(θ) · exp(ikr r + ik⊥y − iωt)

≈ φ(θ) · exp(ikr r + ik⊥y − iωt) einsetzen

↓�� Eigenwert-Differentialgleichung


� �PDE



↓��






� �PDE



↓��






� �PDE



↓��






� �PDE



↓��





Eigenwert-Differentialgleichung

Finde Eigenpaar (ω, φ), so dass(g2(θ)

∂2

∂θ2 + g1(θ)∂

∂θ+ g0(θ) +

Pn(ω, θ)

Pd(ω, θ)

)φ(θ) = 0,

φ 2π-periodisch und =(ω) maximal.

Pn(ω, θ) =n∑

j=0

ωjaj(θ)

Pd(ω, θ) =d∑

j=0

ωjbj(θ)

0 1 2 3 4 5−2

−1

0

1

2

Diskretisierung(g2(θ)

∂2

∂θ2 + g1(θ)∂

∂θ+ g0(θ) +

Pn(ω, θ)

Pd(ω, θ)

)φ(θ) = 0

Diskretisiere die Gleichung auf einem N-Punkt Gitter:I [0,2π[→ ~θ

I g(θ)→ Diag(g(~θ)), Pn(ω) =n∑

j=0

ωjDiag(aj(~θ))

I∂k

∂θk → Dk finite Differenzen oder Spektral-Methode

∂k f∂θk (θ0) ≈

m∑j=0

〈ψj , f 〉∂kψj

∂θk (θ0)

(G2D2 + G1D1 + G0 +

Pn(ω)

Pd(ω)

)~φ = 0


∂2

∂θ2 + g1(θ)∂

∂θ+ g0(θ) +

Pn(ω, θ)

Pd(ω, θ)

)φ(θ) = 0

Diskretisiere die Gleichung auf einem N-Punkt Gitter:

I [0,2π[→ ~θ


j=0

ωjDiag(aj(~θ))

I∂k


∂k f∂θk (θ0) ≈

m∑j=0


∂θk (θ0)

(G2D2 + G1D1 + G0 +

Pn(ω)

Pd(ω)

)~φ = 0


∂2

∂θ2 + g1(θ)∂

∂θ+ g0(θ) +

Pn(ω, θ)

Pd(ω, θ)

)φ(θ) = 0



j=0

ωjDiag(aj(~θ))

I∂k


∂k f∂θk (θ0) ≈

m∑j=0


∂θk (θ0)

(G2D2 + G1D1 + G0 +

Pn(ω)

Pd(ω)

)~φ = 0


∂2

∂θ2 + g1(θ)∂

∂θ+ g0(θ) +

Pn(ω, θ)

Pd(ω, θ)

)φ(θ) = 0



j=0

ωjDiag(aj(~θ))

I∂k


∂k f∂θk (θ0) ≈

m∑j=0


∂θk (θ0)

(G2D2 + G1D1 + G0 +

Pn(ω)

Pd(ω)

)~φ = 0


∂2

∂θ2 + g1(θ)∂

∂θ+ g0(θ) +

Pn(ω, θ)

Pd(ω, θ)

)φ(θ) = 0



j=0

ωjDiag(aj(~θ))

I∂k


∂k f∂θk (θ0) ≈

m∑j=0


∂θk (θ0)

(G2D2 + G1D1 + G0 +

Pn(ω)

Pd(ω)

)~φ = 0


∂2

∂θ2 + g1(θ)∂

∂θ+ g0(θ) +

Pn(ω, θ)

Pd(ω, θ)

)φ(θ) = 0



j=0

ωjDiag(aj(~θ))

I∂k


∂k f∂θk (θ0) ≈

m∑j=0


∂θk (θ0)

(G2D2 + G1D1 + G0 +

Pn(ω)

Pd(ω)

)~φ = 0

Lösen des diskreten Eigenwertproblems

diskrete Eigenwertgleichung(G2D2 + G1D1 + G0 +

Pn(ω)

Pd(ω)

)~φ = 0

Bisher:(Pd(ω) · [G2D2 + G1D1 + G0] + Pn(ω))~φ = 0

⇐⇒ (M0 + M1ω + M2ω

2 + M3ω3)~φ = 0

Rechnung

(Pd(ω) · [G2D2 + G1D1 + G0] + Pn(ω))~φ = 0

Standardlöser

0 1 2 3 4

−2

−1

0

1

2

Z /m

R/mω1024 = −46.794 + 3.019i

richtig

1 2 3 4

−2

−1

0

1

2

Z /m

R/mω1024 = −54.415 + 4.043iω64 = −56.759 + 18.008i

Rechnung

(Pd(ω) · [G2D2 + G1D1 + G0] + Pn(ω))~φ = 0

Standardlöser

0 1 2 3 4

−2

−1

0

1

2

Z /m

R/mω1024 = −46.794 + 3.019iω64 = −56.759 + 18.008i

richtig

1 2 3 4

−2

−1

0

1

2

Z /m

R/mω1024 = −54.415 + 4.043iω64 = −56.759 + 18.008i

Rechnung

(Pd(ω) · [G2D2 + G1D1 + G0] + Pn(ω))~φ = 0

Standardlöser

0 1 2 3 4

−2

−1

0

1

2

Z /m

R/mω1024 = −46.794 + 3.019iω64 = −56.759 + 18.008i

richtig

1 2 3 4

−2

−1

0

1

2

Z /m

R/mω1024 = −54.415 + 4.043iω64 = −56.759 + 18.008i

Kondition der Eigenwertgleichung

(- -) (Pd(ω) · [G2D2 + G1D1 + G0] + Pn(ω))~φ = 0

(—)(

G2D2 + G1D1 + G0 +Pn(ω)

Pd(ω)

)~φ = 0

6 7 8 9 10 11 12

105

1010

log2(N)

c

c = limε→0

{|∆ω||εω|

∣∣∣∣ ω + ∆ω löst die

mit ε gestörteEigenwertgleichung }

I Erklärung: Nenner mit Pn(ω) ≈ ω multipliziertI Fazit nicht mit Nenner multiplizierenI Auf niedriger Aufloesung (N = 64) kubische Gleichung anwendbar,

Kandidat ermitteln


(- -) (Pd(ω) · [G2D2 + G1D1 + G0] + Pn(ω))~φ = 0

(—)(

G2D2 + G1D1 + G0 +Pn(ω)

Pd(ω)

)~φ = 0

6 7 8 9 10 11 12

105

1010

log2(N)

c c = limε→0

{|∆ω||εω|




Kandidat ermitteln


(- -) (Pd(ω) · [G2D2 + G1D1 + G0] + Pn(ω))~φ = 0

(—)(

G2D2 + G1D1 + G0 +Pn(ω)

Pd(ω)

)~φ = 0

6 7 8 9 10 11 12

105

1010

log2(N)

c c = limε→0

{|∆ω||εω|



I Erklärung: Nenner mit Pn(ω) ≈ ω multipliziert

I Fazit nicht mit Nenner multiplizierenI Auf niedriger Aufloesung (N = 64) kubische Gleichung anwendbar,

Kandidat ermitteln


(- -) (Pd(ω) · [G2D2 + G1D1 + G0] + Pn(ω))~φ = 0

(—)(

G2D2 + G1D1 + G0 +Pn(ω)

Pd(ω)

)~φ = 0

6 7 8 9 10 11 12

105

1010

log2(N)

c c = limε→0

{|∆ω||εω|



I Erklärung: Nenner mit Pn(ω) ≈ ω multipliziertI Fazit nicht mit Nenner multiplizieren

I Auf niedriger Aufloesung (N = 64) kubische Gleichung anwendbar,Kandidat ermitteln


(- -) (Pd(ω) · [G2D2 + G1D1 + G0] + Pn(ω))~φ = 0

(—)(

G2D2 + G1D1 + G0 +Pn(ω)

Pd(ω)

)~φ = 0

6 7 8 9 10 11 12

105

1010

log2(N)

c c = limε→0

{|∆ω||εω|




Kandidat ermitteln

Lösung des rationalen Eigenwertproblems

R(ω)~φ :=

(G2D2 + G1D1 + G0 +

Pn(ω)

Pd(ω)

)~φ = 0

Newtonschritt

DF (ωj , ~φj)

[∆ω~∆φ

]= F (ωj , ~φj), ∆ω = ωj+1 − ωj , ~∆φ = ~φj+1 − ~φj

R′(ωj)~φj∆ω + R(ω) ~∆φ = R(ωj), 2~φHj~∆φ = ~φH

j~φj − 1,

Update des Eigenvektors

~φj+1 = ∆ωR−1(ωj)R′(ωj)~φj .

Update des Eigenwertes

f (ω) := ~φHR(ω)~φ Newton: ωj+1 = ωj −~φHR(ωj)~φ

~φHR′(ω)~φ.


R(ω)~φ :=

(G2D2 + G1D1 + G0 +

Pn(ω)

Pd(ω)

)~φ = 0

F (ω,~φ) :=

[R(ω)~φ

]= 0, DF (ω,~φ) =

[R′(ω)~φ R(ω)

].

Newtonschritt

DF (ωj , ~φj)

[∆ω~∆φ



j~φj − 1,

Update des Eigenvektors~φj+1 = ∆ωR−1(ωj)R′(ωj)~φj .



~φHR′(ω)~φ.


R(ω)~φ :=

(G2D2 + G1D1 + G0 +

Pn(ω)

Pd(ω)

)~φ = 0

F (ω,~φ) :=

[R(ω)~φ~φH~φ− 1

]= 0, DF (ω,~φ) =

[R′(ω)~φ R(ω)

0 2~φH

].

Newtonschritt

DF (ωj , ~φj)

[∆ω~∆φ



j~φj − 1,




~φHR′(ω)~φ.


R(ω)~φ :=

(G2D2 + G1D1 + G0 +

Pn(ω)

Pd(ω)

)~φ = 0

F (ω,~φ) :=


]= 0, DF (ω,~φ) =

[R′(ω)~φ R(ω)

0 2~φH

].

Newtonschritt

DF (ωj , ~φj)

[∆ω~∆φ



j~φj − 1,




~φHR′(ω)~φ.


R(ω)~φ :=

(G2D2 + G1D1 + G0 +

Pn(ω)

Pd(ω)

)~φ = 0

F (ω,~φ) :=


]= 0, DF (ω,~φ) =

[R′(ω)~φ R(ω)

0 2~φH

].

Newtonschritt

DF (ωj , ~φj)

[∆ω~∆φ



j~φj − 1,




~φHR′(ω)~φ.


R(ω)~φ :=

(G2D2 + G1D1 + G0 +

Pn(ω)

Pd(ω)

)~φ = 0

F (ω,~φ) :=


]= 0, DF (ω,~φ) =

[R′(ω)~φ R(ω)

0 2~φH

].

Newtonschritt

DF (ωj , ~φj)

[∆ω~∆φ



j~φj − 1,




~φHR′(ω)~φ.

Inverse IterationLöse R(ω)~φ = 0

(0.) Wähle Startpaar (ω0, ~φ0)

for j = 0,1,2, . . . do(1.) ~φj+1 := R−1(ωj)R′(ωj)~φj // Update des Eigenvektors

(2.) ~φj+1 := ~φj+1/‖~φj+1‖ // Normierung

(3.) ~rj+1 = R(ωj)~φj+1 // Residuumif ‖~rj+1‖ klein genug do Stopp end if

(4.) ωj+1 := ωj −~φH

j+1~rj+1

~φHj+1R′(ω)~φj+1

// Update des Eigenwertes

end for

I Spezialfall R(ω)~φ = (ωI − A)~φ = 0: Rayleighquotienten-IterationI (1.) ist teuer, i.A. O(N3)

I Newtonverfahren kann zu anderem Eigenpaar springen

Inverse IterationLöse R(ω)~φ = 0

(0.) Wähle Startpaar (ω0, ~φ0)

for j = 0,1,2, . . . do(1.) ~φj+1 := R−1(ωj)R′(ωj)~φj // Update des Eigenvektors

(2.) ~φj+1 := ~φj+1/‖~φj+1‖ // Normierung

(3.) ~rj+1 = R(ωj)~φj+1 // Residuumif ‖~rj+1‖ klein genug do Stopp end if

(4.) ωj+1 := ωj −~φH

j+1~rj+1

~φHj+1R′(ω)~φj+1


end for

I Spezialfall R(ω)~φ = (ωI − A)~φ = 0: Rayleighquotienten-IterationI (1.) ist teuer, i.A. O(N3)

I Newtonverfahren kann zu anderem Eigenpaar springen

Inverse Iteration im Unterraum

Löse R(ω)~φ = 0, wobei ~φ ∈ span(V ), V ∈ CN×k , k � N

(0.) Wähle Suchraum V und Startpaar (ω0, ~φ0= V~x0)

for j = 0,1,2, . . . do(1.) ~x j+1 := (V HR(ωj)V )−1V HR′(ωj)V~x j // Update des Eigenvektors(2.) ~x j+1 := ~x j+1/‖~x j+1‖ // Normierung(3.) ~rj+1 = V HR(ωj)V~x j+1 // Residuumif ‖~rj+1‖ klein genug do Stopp end if

(4.) ωj+1 := ωj −~xH

j+1~rj+1

~xHj+1V HR′(ω)V~x j+1


end for

I (1.) ist preiswert, i.A. O(k2)

I Newtonverfahren kann nur innerhalb von V springenI Differentialoperatoren mit FFT in R(ω)V

Rationaler Jacobi-Davidson Algorithmus

(0.) Wähle Startpaar (ω0, ~φ0) und Suchraum V := [~φ0]

loop(1.) Orthonormalisiere V(2.) Berechne Eigenpaar (ν, ~u) in V mit inverser Iteration(4.) Berechne Residuum ~r := R(ν)~u. Es gilt ~r ⊥ V .if ‖~r‖ klein genug do Stopp end if(5.) Löse (näherungsweise)(

I −~w~uH

~uH ~w

)R(ν)(I − ~u~uH)~t = −~r , ~t ⊥ ~u, ~w := R′(ν)~u.

(6.) Erweitere den Suchraum zu [V ,~t ].end loop



loop(1.) Orthonormalisiere V

(2.) Berechne Eigenpaar (ν, ~u) in V mit inverser Iteration(4.) Berechne Residuum ~r := R(ν)~u. Es gilt ~r ⊥ V .if ‖~r‖ klein genug do Stopp end if(5.) Löse (näherungsweise)(

I −~w~uH

~uH ~w

)R(ν)(I − ~u~uH)~t = −~r , ~t ⊥ ~u, ~w := R′(ν)~u.

(6.) Erweitere den Suchraum zu [V ,~t ].

end loop



loop(1.) Orthonormalisiere V(2.) Berechne Eigenpaar (ν, ~u) in V mit inverser Iteration

(4.) Berechne Residuum ~r := R(ν)~u. Es gilt ~r ⊥ V .if ‖~r‖ klein genug do Stopp end if(5.) Löse (näherungsweise)(

I −~w~uH

~uH ~w

)R(ν)(I − ~u~uH)~t = −~r , ~t ⊥ ~u, ~w := R′(ν)~u.


end loop



loop(1.) Orthonormalisiere V(2.) Berechne Eigenpaar (ν, ~u) in V mit inverser Iteration(4.) Berechne Residuum ~r := R(ν)~u. Es gilt ~r ⊥ V .

if ‖~r‖ klein genug do Stopp end if(5.) Löse (näherungsweise)(

I −~w~uH

~uH ~w

)R(ν)(I − ~u~uH)~t = −~r , ~t ⊥ ~u, ~w := R′(ν)~u.


end loop



loop(1.) Orthonormalisiere V(2.) Berechne Eigenpaar (ν, ~u) in V mit inverser Iteration(4.) Berechne Residuum ~r := R(ν)~u. Es gilt ~r ⊥ V .if ‖~r‖ klein genug do Stopp end if

(5.) Löse (näherungsweise)(I −

~w~uH

~uH ~w

)R(ν)(I − ~u~uH)~t = −~r , ~t ⊥ ~u, ~w := R′(ν)~u.


end loop



loop(1.) Orthonormalisiere V(2.) Berechne Eigenpaar (ν, ~u) in V mit inverser Iteration(4.) Berechne Residuum ~r := R(ν)~u. Es gilt ~r ⊥ V .if ‖~r‖ klein genug do Stopp end if(5.) Löse (näherungsweise)(

I −~w~uH

~uH ~w

)R(ν)(I − ~u~uH)~t = −~r , ~t ⊥ ~u, ~w := R′(ν)~u.

(6.) Erweitere den Suchraum zu [V ,~t ].end loop

Die Korrekturgleichung (5.)Gegeben: Näherung (ν, ~u) der Eigenwertaufgabe

R(ω)~φ =

(G2D2 + G1D1 + G0 +

Pn(ω)

Pd(ω)

)~φ = 0

Jetzt Suchraum V → [V ,~t ] erweitern mit Newton Schritt (inverse Iteration)

~s = R−1(ν)R′(ν)~u, zusätzlich ~t = α~s − ~u, so dass ~t ⊥ ~u

~t =~uH~u~uH~s

~s − ~u,

Q−1(ν)~r = ~z ⇔ Q(ν)~z = ~r ,

R−1(ν)R′(ν)~u = ~s ⇔ R(ν)~s = R′(ν)~u

Dj Spektralmethode R(ν) = = O(N3)

Dj finite Differenzen Q(ν) = = O(N)

Die Korrekturgleichung (5.)Gegeben: Näherung (ν, ~u) der Eigenwertaufgabe

R(ω)~φ =

(G2D2 + G1D1 + G0 +

Pn(ω)

Pd(ω)

)~φ = 0

Jetzt Suchraum V → [V ,~t ] erweitern mit Newton Schritt (inverse Iteration)

~s = R−1(ν)R′(ν)~u, zusätzlich ~t = α~s − ~u, so dass ~t ⊥ ~u

~t =~uH~z~uH~s

~s − ~z, Q(ν) ≈ R(ν)

Q−1(ν)~r = ~z ⇔ Q(ν)~z = ~r , Q−1(ν)R′(ν)~u = ~s ⇔ Q(ν)~s = R′(ν)~u

Dj Spektralmethode R(ν) = = O(N3)

Dj finite Differenzen Q(ν) = = O(N)

Multilevel Jacobi-Davidson für Rationales Eig.��

��

Grobgitterlösung (ωN0 ,~φN0) bei N0 = 64 mit

P(ω)~φ = (M3ω3 + M2ω

2 + M1ω + M0)~φ = 0

↓��

��V = [~φN0 ], Jacobi-Davidson mit inverser Iteration bei N0

↓��

��Feineres Gitter N1 = 2N0, Eigenvektor interpolieren⇒ ~φN1

↓��

��V = [~φN1 ], Jacobi-Davidson mit inverser Iteration bei N0...�� (ω,~φ) auf Nfinal

Jacobi-Davidson-Verfahren

I Korrekturvektor~t ∈ V (→Abbruch)I Neustart mit skaliertem Eigenwertproblem 0 = R̃(ω)Φ = SR(ω)SΦ,

wobei S ≈ diag(~φ)

I Orthogonalisierung bzgl. 〈., .〉S−2 , d.h. V HV = I → V HS−2V = II Konvergenzrate (inverse Iteration): lokal quadratischI Zweiseitige inverse Iteration: lokal kubische Konvergenz

R(ω)~φ = 0 und ~ψHR(ω) = 0,

~φj+1 := R−1(ωj)R′(ωj)~φj Update des rechten Eigenvektors~ψH

j+1 := ~ψHj R′(ωj)R−1(ωj) Update des linken Eigenvektors

ωj+1 := ωj −~ψH

j+1R(ω)~φj+1

~ψHj+1R′(ω)~φj+1


I Linker Vl und rechter Vr Suchraum: V Hl R(ω)Vr

Beispiel SkalierungI links ohne Skalierung, rechts mit SkalierungI Beschränkung: maximal (4) Durchläufe mit dim V ≤ 16, ef ≤ 10−9

N EP 1 EP 2 EP 3 EP 44096 64(4) 5(1) 8(1) 5(1) 64(4) 7(1) 14(1) 8(1)2048 64(4) 5(1) 7(1) 4(1) 19(2) 6(1) 12(1) 9(1)1024 9(1) 6(1) 9(1) 6(1) 14(1) 30(2) 14(1) 12(1)

512 12(1) 7(1) 8(1) 6(1) 24(2) 64(4) 55(4) 25(2)256 12(1) 9(1) 11(1) 9(1) 64(4) 64(4) 64(4) 64(4)128 16(1) 13(1) 14(1) 13(1) 64(4) 64(4) 64(4) 64(4)

64 11(1) 22(2) 10(1) 10(1) 22(2) 25(2) 27(2) 45(3)

1 2 3 4−2

−1

0

1

2

1 2 3 4−2

−1

0

1

2

1 2 3 4

−2

−1

0

1

2

1 2 3 4

−2

−1

0

1

2

Parameterstudie

0 10 20 30 40 500

1

2

3

4

=(ω) Ep 2

Ep 1

k (Wellenzahl)1 2 3 4

0

0.05

0.1

0.15

0.2

0.25

0.3

0.35

=(ω)

k (Wellenzahl)

N = 4096, 410 k-Werte, Toleranz 10−9:Rechenzeit: durchschnittlich 6 Sekunden je Eigenpaar

Zusammenfassung

I Eigenwertgleichung zur Beschreibung der Drift-Instabilitäten imTokamak

I In X-Punkt-Geometrie: kubische Eigenwertgleichungs-Formulierungunbrauchbar

I Lösung der Rationalen Eigenwertgleichung: Newton, InverseIteration, Unterraumiteration

I Jacobi-Davidson Verfahren: präzise Bestimmung des Eigenwertesüber Spektral-Diskretisierung, Korrekturgleichung preiswert über finiteDifferenzen

I Multilevel Jacobi-Davidson Verfahren mit Skalierung und Restarts:schnell, preiswert, präzise

I Parameterstudien: Restart mit neuem Parameter auf wenigen Levelngröber

I physikalische Interpretation

Fragen?

Documents

Rationales Multilevel Jacobi-Davidson Verfahren für ... · Gliederung I Einführung in die Kernfusion mit dem Tokamak I Eigenwertgleichung zur Beschreibung der Verluste I Lösen