Upload
vokien
View
244
Download
0
Embed Size (px)
Citation preview
Verfahren zur Berechnung derExponentialmatrix
Konrad Waldherr
Verfahren zur Berechnung der Exponentialmatrix – p.1/14
Motivation
• In einem Quantensystem ist folgendes Produktvon besonderer Bedeutung:
e−itMHM · . . . e−itkHk · . . . e−it1H1
Verfahren zur Berechnung der Exponentialmatrix – p.2/14
Motivation
• In einem Quantensystem ist folgendes Produktvon besonderer Bedeutung:
e−itMHM · . . . e−itkHk · . . . e−it1H1
• Zur Berechnung dieses Produkts muss jeweils dieExponentialfunktion einer Matrix berechnetwerden:
e−itMHM · . . . e−itkHk · . . . e−it1H1
Verfahren zur Berechnung der Exponentialmatrix – p.2/14
Motivation
• In einem Quantensystem ist folgendes Produktvon besonderer Bedeutung:
e−itMHM · . . . e−itkHk · . . . e−it1H1
• Zur Berechnung dieses Produkts muss jeweils dieExponentialfunktion einer Matrix berechnetwerden:
e−itMHM · . . . e−itkHk · . . . e−it1H1
• Frage: Wie berechnet man
e−itkHk
Verfahren zur Berechnung der Exponentialmatrix – p.2/14
Definition der Exponentialmatrix
• Ausgangspunkt: Taylorreihe der e-Funktion
ex =∞∑
k=0
xk
k!
Verfahren zur Berechnung der Exponentialmatrix – p.3/14
Definition der Exponentialmatrix
• Ausgangspunkt: Taylorreihe der e-Funktion
ex =∞∑
k=0
xk
k!
• Definition der Exponentialfunktion einer Matrix A
exp(A) := eA :=
∞∑
k=0
Ak
k!
Verfahren zur Berechnung der Exponentialmatrix – p.3/14
Definition der Exponentialmatrix
• Ausgangspunkt: Taylorreihe der e-Funktion
ex =∞∑
k=0
xk
k!
• Definition der Exponentialfunktion einer Matrix A
exp(A) := eA :=
∞∑
k=0
Ak
k!
• Für eine Diagonalmatrix D = diag(d1, . . . , dn) gilt
eD = diag(ed1 , . . . , edn)Verfahren zur Berechnung der Exponentialmatrix – p.3/14
Berechnung der Exponentialmatrix
• Naheliegend: Berechnung durch “abgeschnittene“Taylor-Reihe:
exp(A) ≈
n∑
k=0
Ak
k!
Verfahren zur Berechnung der Exponentialmatrix – p.4/14
Berechnung der Exponentialmatrix
• Naheliegend: Berechnung durch “abgeschnittene“Taylor-Reihe:
exp(A) ≈
n∑
k=0
Ak
k!
• Diese Reihe konvergiert allerdings sehr langsam:
‖ eA−
n∑
k=0
Ak
k!‖≤
(
‖ A ‖n+1
(n + 1)!
)(
1
1− ‖ A ‖ /(n + 2)
)
≤ δ
Verfahren zur Berechnung der Exponentialmatrix – p.4/14
Berechnung der Exponentialmatrix
• Naheliegend: Berechnung durch “abgeschnittene“Taylor-Reihe:
exp(A) ≈
n∑
k=0
Ak
k!
• Diese Reihe konvergiert allerdings sehr langsam:
‖ eA−
n∑
k=0
Ak
k!‖≤
(
‖ A ‖n+1
(n + 1)!
)(
1
1− ‖ A ‖ /(n + 2)
)
≤ δ
• Beispiel: ‖ A ‖= 100 und δ = 10−6 liefert n = 284.
Verfahren zur Berechnung der Exponentialmatrix – p.4/14
Berechnung der Exponentialmatrix
• Naheliegend: Berechnung durch “abgeschnittene“Taylor-Reihe:
exp(A) ≈
n∑
k=0
Ak
k!
• Diese Reihe konvergiert allerdings sehr langsam:
‖ eA−
n∑
k=0
Ak
k!‖≤
(
‖ A ‖n+1
(n + 1)!
)(
1
1− ‖ A ‖ /(n + 2)
)
≤ δ
• Beispiel: ‖ A ‖= 100 und δ = 10−6 liefert n = 284.
• Weiteres Problem: Numerische InstabilitätVerfahren zur Berechnung der Exponentialmatrix – p.4/14
Weitere Verfahren zur Berechnungvon eA
• Scaling and Squaring
Verfahren zur Berechnung der Exponentialmatrix – p.5/14
Weitere Verfahren zur Berechnungvon eA
• Scaling and Squaring
− eA =(
eA/m)m
Verfahren zur Berechnung der Exponentialmatrix – p.5/14
Weitere Verfahren zur Berechnungvon eA
• Scaling and Squaring
− eA =(
eA/m)m
− Wähle m, so dass ‖ A ‖ /m ≤ 1
Verfahren zur Berechnung der Exponentialmatrix – p.5/14
Weitere Verfahren zur Berechnungvon eA
• Scaling and Squaring
− eA =(
eA/m)m
− Wähle m, so dass ‖ A ‖ /m ≤ 1
− Wähle m als Zweierpotenz: m = 2k
Verfahren zur Berechnung der Exponentialmatrix – p.5/14
Weitere Verfahren zur Berechnungvon eA
• Scaling and Squaring
− eA =(
eA/m)m
− Wähle m, so dass ‖ A ‖ /m ≤ 1
− Wähle m als Zweierpotenz: m = 2k
−(
eA/m)m
durch wiederholtes Quadrieren
Verfahren zur Berechnung der Exponentialmatrix – p.5/14
Weitere Verfahren zur Berechnungvon eA
• Scaling and Squaring
− eA =(
eA/m)m
− Wähle m, so dass ‖ A ‖ /m ≤ 1
− Wähle m als Zweierpotenz: m = 2k
−(
eA/m)m
durch wiederholtes Quadrieren
• Padé-Approximation:
Verfahren zur Berechnung der Exponentialmatrix – p.5/14
Weitere Verfahren zur Berechnungvon eA
• Scaling and Squaring
− eA =(
eA/m)m
− Wähle m, so dass ‖ A ‖ /m ≤ 1
− Wähle m als Zweierpotenz: m = 2k
−(
eA/m)m
durch wiederholtes Quadrieren
• Padé-Approximation:
− reelle Padé-Approximation: ex ≈ p(x)q(x)
Verfahren zur Berechnung der Exponentialmatrix – p.5/14
Weitere Verfahren zur Berechnungvon eA
• Scaling and Squaring
− eA =(
eA/m)m
− Wähle m, so dass ‖ A ‖ /m ≤ 1
− Wähle m als Zweierpotenz: m = 2k
−(
eA/m)m
durch wiederholtes Quadrieren
• Padé-Approximation:
− reelle Padé-Approximation: ex ≈ p(x)q(x)
− eA ≈ (q(A))−1p(A)
Verfahren zur Berechnung der Exponentialmatrix – p.5/14
Weitere Verfahren zur Berechnungvon eA
• Scaling and Squaring
− eA =(
eA/m)m
− Wähle m, so dass ‖ A ‖ /m ≤ 1
− Wähle m als Zweierpotenz: m = 2k
−(
eA/m)m
durch wiederholtes Quadrieren
• Padé-Approximation:
− reelle Padé-Approximation: ex ≈ p(x)q(x)
− eA ≈ (q(A))−1p(A)
− Kombination mit Scaling and Squaring
Verfahren zur Berechnung der Exponentialmatrix – p.5/14
Weitere Verfahren zur Berechnungvon eA
• Chebyshev-Approximation
Verfahren zur Berechnung der Exponentialmatrix – p.6/14
Weitere Verfahren zur Berechnungvon eA
• Chebyshev-Approximation− Für −1 ≤ x ≤ 1 gilt die Entwicklung
e−αx = 2I0(α)T0(αx) + 2∞∑
j=1
Tj(αx)Ij(α)(−1)j
Verfahren zur Berechnung der Exponentialmatrix – p.6/14
Weitere Verfahren zur Berechnungvon eA
• Chebyshev-Approximation− Für −1 ≤ x ≤ 1 gilt die Entwicklung
e−αx = 2I0(α)T0(αx) + 2∞∑
j=1
Tj(αx)Ij(α)(−1)j
− Tj: Chebyshev-Polynom 1. Art der Ordnung j
Verfahren zur Berechnung der Exponentialmatrix – p.6/14
Weitere Verfahren zur Berechnungvon eA
• Chebyshev-Approximation− Für −1 ≤ x ≤ 1 gilt die Entwicklung
e−αx = 2I0(α)T0(αx) + 2∞∑
j=1
Tj(αx)Ij(α)(−1)j
− Tj: Chebyshev-Polynom 1. Art der Ordnung j
− Ij: Besselfunktion der Ordnung j
Verfahren zur Berechnung der Exponentialmatrix – p.6/14
Weitere Verfahren zur Berechnungvon eA
• Chebyshev-Approximation− Für −1 ≤ x ≤ 1 gilt die Entwicklung
e−αx = 2I0(α)T0(αx) + 2∞∑
j=1
Tj(αx)Ij(α)(−1)j
− Tj: Chebyshev-Polynom 1. Art der Ordnung j
− Ij: Besselfunktion der Ordnung j
− Transfer auf Matrizen: r0 =‖ A ‖, A0 = A/r0
eA = er0A0 = 2I0(−r0)T0(−A)+2∞∑
j=1
Tj(−A)Ij(−r0)(−1)j
Verfahren zur Berechnung der Exponentialmatrix – p.6/14
Weitere Verfahren zur Berechnungvon eA
• Zugang über gewöhnliche Differentialgleichung:
Verfahren zur Berechnung der Exponentialmatrix – p.7/14
Weitere Verfahren zur Berechnungvon eA
• Zugang über gewöhnliche Differentialgleichung:− Gegeben ist das AWP
y′ = Ay, y(t0) = y0
Verfahren zur Berechnung der Exponentialmatrix – p.7/14
Weitere Verfahren zur Berechnungvon eA
• Zugang über gewöhnliche Differentialgleichung:− Gegeben ist das AWP
y′ = Ay, y(t0) = y0
− Die analytische Lösung lautet
y(t) = e(t−t0)Ay0
Verfahren zur Berechnung der Exponentialmatrix – p.7/14
Weitere Verfahren zur Berechnungvon eA
• Zugang über gewöhnliche Differentialgleichung:− Gegeben ist das AWP
y′ = Ay, y(t0) = y0
− Die analytische Lösung lautet
y(t) = e(t−t0)Ay0
− eA aus n Differentialgleichungen
y′(i) = Ay(i), y(i)(0) = ei
Verfahren zur Berechnung der Exponentialmatrix – p.7/14
Weitere Verfahren zur Berechnungvon eA
• Damit ergibt sich
eA =(
y1(1) . . . yn(1))
Verfahren zur Berechnung der Exponentialmatrix – p.8/14
Weitere Verfahren zur Berechnungvon eA
• Damit ergibt sich
eA =(
y1(1) . . . yn(1))
• Lösung der Differentialgleichungen:
Verfahren zur Berechnung der Exponentialmatrix – p.8/14
Weitere Verfahren zur Berechnungvon eA
• Damit ergibt sich
eA =(
y1(1) . . . yn(1))
• Lösung der Differentialgleichungen:− Einschrittverfahren (z.B. Runge-Kutta-Verfahren
mit fester Schrittweite)
Verfahren zur Berechnung der Exponentialmatrix – p.8/14
Weitere Verfahren zur Berechnungvon eA
• Damit ergibt sich
eA =(
y1(1) . . . yn(1))
• Lösung der Differentialgleichungen:− Einschrittverfahren (z.B. Runge-Kutta-Verfahren
mit fester Schrittweite)− Mehrschrittverfahren
Verfahren zur Berechnung der Exponentialmatrix – p.8/14
Weitere Verfahren zur Berechnungvon eA
• Damit ergibt sich
eA =(
y1(1) . . . yn(1))
• Lösung der Differentialgleichungen:− Einschrittverfahren (z.B. Runge-Kutta-Verfahren
mit fester Schrittweite)− Mehrschrittverfahren− allgemeiner ODE-Solver
Verfahren zur Berechnung der Exponentialmatrix – p.8/14
Weitere Verfahren zur Berechnungvon eA
• Zugang über Eigenwert-Zerlegung
Verfahren zur Berechnung der Exponentialmatrix – p.9/14
Weitere Verfahren zur Berechnungvon eA
• Zugang über Eigenwert-Zerlegung− Seien v1, . . . , vn die Eigenvektoren von A zu den
Eigenwerten λ1, . . . , λn
Verfahren zur Berechnung der Exponentialmatrix – p.9/14
Weitere Verfahren zur Berechnungvon eA
• Zugang über Eigenwert-Zerlegung− Seien v1, . . . , vn die Eigenvektoren von A zu den
Eigenwerten λ1, . . . , λn
− Dann gilt A = V diag(λ1, . . . , λn)V −1
Verfahren zur Berechnung der Exponentialmatrix – p.9/14
Weitere Verfahren zur Berechnungvon eA
• Zugang über Eigenwert-Zerlegung− Seien v1, . . . , vn die Eigenvektoren von A zu den
Eigenwerten λ1, . . . , λn
− Dann gilt A = V diag(λ1, . . . , λn)V −1
− Es folgt eA = eV diag(λ1,...,λn)V −1
= V ediag(λ1,...,λn)V −1
Verfahren zur Berechnung der Exponentialmatrix – p.9/14
Weitere Verfahren zur Berechnungvon eA
• Zugang über Eigenwert-Zerlegung− Seien v1, . . . , vn die Eigenvektoren von A zu den
Eigenwerten λ1, . . . , λn
− Dann gilt A = V diag(λ1, . . . , λn)V −1
− Es folgt eA = eV diag(λ1,...,λn)V −1
= V ediag(λ1,...,λn)V −1
− Es ergibt sich eA = V diag(eλ1 , . . . , eλn)V −1
Verfahren zur Berechnung der Exponentialmatrix – p.9/14
Weitere Verfahren zur Berechnungvon eA
• Splitting Methode
Verfahren zur Berechnung der Exponentialmatrix – p.10/14
Weitere Verfahren zur Berechnungvon eA
• Splitting Methode− Ausgangspunkt: Zerlegung A = B + C
Verfahren zur Berechnung der Exponentialmatrix – p.10/14
Weitere Verfahren zur Berechnungvon eA
• Splitting Methode− Ausgangspunkt: Zerlegung A = B + C
− Die Funktionalgleichung ex+y = exey gilt fürMatrizen im Allgemeinen nicht.
Verfahren zur Berechnung der Exponentialmatrix – p.10/14
Weitere Verfahren zur Berechnungvon eA
• Splitting Methode− Ausgangspunkt: Zerlegung A = B + C
− Die Funktionalgleichung ex+y = exey gilt fürMatrizen im Allgemeinen nicht.
− Es gilt legiglich die folgende Äquivalenz:
eB+C = eBeC ⇐⇒ BC = CB
Verfahren zur Berechnung der Exponentialmatrix – p.10/14
Weitere Verfahren zur Berechnungvon eA
• Splitting Methode− Ausgangspunkt: Zerlegung A = B + C
− Die Funktionalgleichung ex+y = exey gilt fürMatrizen im Allgemeinen nicht.
− Es gilt legiglich die folgende Äquivalenz:
eB+C = eBeC ⇐⇒ BC = CB
− Es gilt jedoch die Trotter-(Produkt-)Formel:
eB+C = limm→∞
(
eB/meC/m)m
Verfahren zur Berechnung der Exponentialmatrix – p.10/14
Inhalt der Diplomarbeit
Ziele der Diplomarbeit:
• Untersuchung und Implementierung derverschiedenen Verfahren zur Berechnung vone−itH mit jeweils fester Matrix H ∈ C
2n×2n
Verfahren zur Berechnung der Exponentialmatrix – p.11/14
Inhalt der Diplomarbeit
Ziele der Diplomarbeit:
• Untersuchung und Implementierung derverschiedenen Verfahren zur Berechnung vone−itH mit jeweils fester Matrix H ∈ C
2n×2n
• Folgende Aspekte sind zu berücksichtigen:
Verfahren zur Berechnung der Exponentialmatrix – p.11/14
Inhalt der Diplomarbeit
Ziele der Diplomarbeit:
• Untersuchung und Implementierung derverschiedenen Verfahren zur Berechnung vone−itH mit jeweils fester Matrix H ∈ C
2n×2n
• Folgende Aspekte sind zu berücksichtigen:− Effizienz
Verfahren zur Berechnung der Exponentialmatrix – p.11/14
Inhalt der Diplomarbeit
Ziele der Diplomarbeit:
• Untersuchung und Implementierung derverschiedenen Verfahren zur Berechnung vone−itH mit jeweils fester Matrix H ∈ C
2n×2n
• Folgende Aspekte sind zu berücksichtigen:− Effizienz− Numerische Stabilität
Verfahren zur Berechnung der Exponentialmatrix – p.11/14
Inhalt der Diplomarbeit
Ziele der Diplomarbeit:
• Untersuchung und Implementierung derverschiedenen Verfahren zur Berechnung vone−itH mit jeweils fester Matrix H ∈ C
2n×2n
• Folgende Aspekte sind zu berücksichtigen:− Effizienz− Numerische Stabilität− Parallelisierbarkeit
Verfahren zur Berechnung der Exponentialmatrix – p.11/14
Inhalt der Diplomarbeit
Ziele der Diplomarbeit:
• Untersuchung und Implementierung derverschiedenen Verfahren zur Berechnung vone−itH mit jeweils fester Matrix H ∈ C
2n×2n
• Folgende Aspekte sind zu berücksichtigen:− Effizienz− Numerische Stabilität− Parallelisierbarkeit− Ausnutzen der speziellen Struktur von H
H = D + C = diag(d1, . . . , dN ) + C1 ⊗ · · · ⊗ Cn
Verfahren zur Berechnung der Exponentialmatrix – p.11/14
Inhalt der Diplomarbeit
Wie kann man die Struktur von H ausnutzen?
• H = D + C
Verfahren zur Berechnung der Exponentialmatrix – p.12/14
Inhalt der Diplomarbeit
Wie kann man die Struktur von H ausnutzen?
• H = D + C
• Anwendung der Splitting-Methode
e−iHt = e−it(D+C) ≈(
e−itD/me−itC/m)m
Verfahren zur Berechnung der Exponentialmatrix – p.12/14
Inhalt der Diplomarbeit
Wie kann man die Struktur von H ausnutzen?
• H = D + C
• Anwendung der Splitting-Methode
e−iHt = e−it(D+C) ≈(
e−itD/me−itC/m)m
• Direkte Berechnung von e−itD/m und e−itC/m
Verfahren zur Berechnung der Exponentialmatrix – p.12/14
Inhalt der Diplomarbeit
Wie kann man die Struktur von H ausnutzen?
• H = D + C
• Anwendung der Splitting-Methode
e−iHt = e−it(D+C) ≈(
e−itD/me−itC/m)m
• Direkte Berechnung von e−itD/m und e−itC/m
− D ist Diagonalmatrix
Verfahren zur Berechnung der Exponentialmatrix – p.12/14
Inhalt der Diplomarbeit
Wie kann man die Struktur von H ausnutzen?
• H = D + C
• Anwendung der Splitting-Methode
e−iHt = e−it(D+C) ≈(
e−itD/me−itC/m)m
• Direkte Berechnung von e−itD/m und e−itC/m
− D ist Diagonalmatrix− Die Eigenvektoren von C sind gerade die
Spalten von F2 ⊗ · · · ⊗ F2
Verfahren zur Berechnung der Exponentialmatrix – p.12/14
Inhalt der Diplomarbeit
Wie kann man die Struktur von H ausnutzen?
• H = D + C
• Anwendung der Splitting-Methode
e−iHt = e−it(D+C) ≈(
e−itD/me−itC/m)m
• Direkte Berechnung von e−itD/m und e−itC/m
− D ist Diagonalmatrix− Die Eigenvektoren von C sind gerade die
Spalten von F2 ⊗ · · · ⊗ F2
• Wiederholtes Quadrieren für m = 2k
Verfahren zur Berechnung der Exponentialmatrix – p.12/14
Inhalt der Diplomarbeit
• Ausnutzung der Persymmetrie
Verfahren zur Berechnung der Exponentialmatrix – p.13/14
Inhalt der Diplomarbeit
• Ausnutzung der Persymmetrie
• Transformation von H auf reelle Matrix H̃
H̃ =
(
A1 rE
rE A2
)
Verfahren zur Berechnung der Exponentialmatrix – p.13/14
Inhalt der Diplomarbeit
• Ausnutzung der Persymmetrie
• Transformation von H auf reelle Matrix H̃
H̃ =
(
A1 rE
rE A2
)
• H̃ ist ähnlich zur Matrix(
A1 + A2 + 2rE 0
0 A1 + A2 − 2rE
)
Verfahren zur Berechnung der Exponentialmatrix – p.13/14
Inhalt der Diplomarbeit
• Ausnutzung der Persymmetrie
• Transformation von H auf reelle Matrix H̃
H̃ =
(
A1 rE
rE A2
)
• H̃ ist ähnlich zur Matrix(
A1 + A2 + 2rE 0
0 A1 + A2 − 2rE
)
• Reduktion des Problems der EW/EV-Zerlegungauf zwei Matrizen halber Größe
Verfahren zur Berechnung der Exponentialmatrix – p.13/14
Inhalt der Diplomarbeit
Offene Fragen
• Kann die Struktur von H auch bei weiterenVerfahren (ODE,Padé,...) ausgenutzt werden?
Verfahren zur Berechnung der Exponentialmatrix – p.14/14
Inhalt der Diplomarbeit
Offene Fragen
• Kann die Struktur von H auch bei weiterenVerfahren (ODE,Padé,...) ausgenutzt werden?
• Wie pessimistisch sind dieKonvergenzabschätzungen in unserem Fall?
Verfahren zur Berechnung der Exponentialmatrix – p.14/14
Inhalt der Diplomarbeit
Offene Fragen
• Kann die Struktur von H auch bei weiterenVerfahren (ODE,Padé,...) ausgenutzt werden?
• Wie pessimistisch sind dieKonvergenzabschätzungen in unserem Fall?
• Wie lässt sich die Matrix-Matrix Multiplikationmöglichst schnell berechnen?
Verfahren zur Berechnung der Exponentialmatrix – p.14/14