Verfahren zur Berechnung der
Exponentialmatrix
Konrad Waldherr
Verfahren zur Berechnung der Exponentialmatrix – p.1/14
Motivation
• In einem Quantensystem ist folgendes Produkt
von besonderer Bedeutung:
e−itM HM · . . . e−itk Hk · . . . e−it1 H1
Verfahren zur Berechnung der Exponentialmatrix – p.2/14
Motivation
• In einem Quantensystem ist folgendes Produkt
von besonderer Bedeutung:
e−itM HM · . . . e−itk Hk · . . . e−it1 H1
• Zur Berechnung dieses Produkts muss jeweils die
Exponentialfunktion einer Matrix berechnet
werden:
e−itM HM · . . . e−itk Hk · . . . e−it1 H1
Verfahren zur Berechnung der Exponentialmatrix – p.2/14
Motivation
• In einem Quantensystem ist folgendes Produkt
von besonderer Bedeutung:
e−itM HM · . . . e−itk Hk · . . . e−it1 H1
• Zur Berechnung dieses Produkts muss jeweils die
Exponentialfunktion einer Matrix berechnet
werden:
e−itM HM · . . . e−itk Hk · . . . e−it1 H1
• Frage: Wie berechnet man
e−itk Hk
Verfahren zur Berechnung der Exponentialmatrix – p.2/14
Definition der Exponentialmatrix
• Ausgangspunkt: Taylorreihe der e-Funktion
∞
X xk
ex =
k!
k=0
Verfahren zur Berechnung der Exponentialmatrix – p.3/14
Definition der Exponentialmatrix
• Ausgangspunkt: Taylorreihe der e-Funktion
∞
X xk
ex =
k!
k=0
• Definition der Exponentialfunktion einer Matrix A
∞
X Ak
exp(A) := eA :=
k!
k=0
Verfahren zur Berechnung der Exponentialmatrix – p.3/14
Definition der Exponentialmatrix
• Ausgangspunkt: Taylorreihe der e-Funktion
∞
X xk
ex =
k!
k=0
• Definition der Exponentialfunktion einer Matrix A
∞
X Ak
exp(A) := eA :=
k!
k=0
• 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:
n
X Ak
exp(A) ≈
k!
k=0
Verfahren zur Berechnung der Exponentialmatrix – p.4/14
Berechnung der Exponentialmatrix
• Naheliegend: Berechnung durch “abgeschnittene“
Taylor-Reihe:
n
X Ak
exp(A) ≈
k!
k=0
• Diese Reihe konvergiert allerdings sehr langsam:
n
Ak n+1
A
X kA k 1
ke − k≤ ≤δ
k! (n + 1)! 1− k A k /(n + 2)
k=0
Verfahren zur Berechnung der Exponentialmatrix – p.4/14
Berechnung der Exponentialmatrix
• Naheliegend: Berechnung durch “abgeschnittene“
Taylor-Reihe:
n
X Ak
exp(A) ≈
k!
k=0
• Diese Reihe konvergiert allerdings sehr langsam:
n
Ak n+1
A
X kA k 1
ke − k≤ ≤δ
k! (n + 1)! 1− k A k /(n + 2)
k=0
• Beispiel: k A k= 100 und δ = 10−6 liefert n = 284.
Verfahren zur Berechnung der Exponentialmatrix – p.4/14
Berechnung der Exponentialmatrix
• Naheliegend: Berechnung durch “abgeschnittene“
Taylor-Reihe:
n
X Ak
exp(A) ≈
k!
k=0
• Diese Reihe konvergiert allerdings sehr langsam:
n
Ak n+1
A
X kA k 1
ke − k≤ ≤δ
k! (n + 1)! 1− k A k /(n + 2)
k=0
• Beispiel: k A k= 100 und δ = 10−6 liefert n = 284.
• Weiteres Problem: Numerische Instabilität
Verfahren zur Berechnung der Exponentialmatrix – p.4/14
Weitere Verfahren zur Berechnung
von eA
• Scaling and Squaring
Verfahren zur Berechnung der Exponentialmatrix – p.5/14
Weitere Verfahren zur Berechnung
von eA
• Scaling and Squaring
m
− eA = eA/m
Verfahren zur Berechnung der Exponentialmatrix – p.5/14
Weitere Verfahren zur Berechnung
von eA
• Scaling and Squaring
m
− eA = eA/m
− Wähle m, so dass k A k /m ≤ 1
Verfahren zur Berechnung der Exponentialmatrix – p.5/14
Weitere Verfahren zur Berechnung
von eA
• Scaling and Squaring
m
− eA = eA/m
− Wähle m, so dass k A k /m ≤ 1
− Wähle m als Zweierpotenz: m = 2k
Verfahren zur Berechnung der Exponentialmatrix – p.5/14
Weitere Verfahren zur Berechnung
von eA
• Scaling and Squaring
m
− eA = eA/m
− Wähle m, so dass k A k /m ≤ 1
− Wähle m als Zweierpotenz: m = 2k
m
− eA/m durch wiederholtes Quadrieren
Verfahren zur Berechnung der Exponentialmatrix – p.5/14
Weitere Verfahren zur Berechnung
von eA
• Scaling and Squaring
m
− eA = eA/m
− Wähle m, so dass k A k /m ≤ 1
− Wähle m als Zweierpotenz: m = 2k
m
− eA/m durch wiederholtes Quadrieren
• Padé-Approximation:
Verfahren zur Berechnung der Exponentialmatrix – p.5/14
Weitere Verfahren zur Berechnung
von eA
• Scaling and Squaring
m
− eA = eA/m
− Wähle m, so dass k A k /m ≤ 1
− Wähle m als Zweierpotenz: m = 2k
m
− eA/m durch wiederholtes Quadrieren
• Padé-Approximation:
p(x)
− reelle Padé-Approximation: ex ≈ q(x)
Verfahren zur Berechnung der Exponentialmatrix – p.5/14
Weitere Verfahren zur Berechnung
von eA
• Scaling and Squaring
m
− eA = eA/m
− Wähle m, so dass k A k /m ≤ 1
− Wähle m als Zweierpotenz: m = 2k
m
− eA/m durch wiederholtes Quadrieren
• Padé-Approximation:
p(x)
− reelle Padé-Approximation: ex ≈ q(x)
− eA ≈ (q(A))−1 p(A)
Verfahren zur Berechnung der Exponentialmatrix – p.5/14
Weitere Verfahren zur Berechnung
von eA
• Scaling and Squaring
m
− eA = eA/m
− Wähle m, so dass k A k /m ≤ 1
− Wähle m als Zweierpotenz: m = 2k
m
− eA/m durch wiederholtes Quadrieren
• Padé-Approximation:
p(x)
− reelle Padé-Approximation: ex ≈ q(x)
− eA ≈ (q(A))−1 p(A)
− Kombination mit Scaling and Squaring
Verfahren zur Berechnung der Exponentialmatrix – p.5/14
Weitere Verfahren zur Berechnung
von eA
• Chebyshev-Approximation
Verfahren zur Berechnung der Exponentialmatrix – p.6/14
Weitere Verfahren zur Berechnung
von eA
• Chebyshev-Approximation
− Für −1 ≤ x ≤ 1 gilt die Entwicklung
∞
X
e−αx = 2I0 (α)T0 (αx) + 2 Tj (αx)Ij (α)(−1)j
j=1
Verfahren zur Berechnung der Exponentialmatrix – p.6/14
Weitere Verfahren zur Berechnung
von eA
• Chebyshev-Approximation
− Für −1 ≤ x ≤ 1 gilt die Entwicklung
∞
X
e−αx = 2I0 (α)T0 (αx) + 2 Tj (αx)Ij (α)(−1)j
j=1
− Tj : Chebyshev-Polynom 1. Art der Ordnung j
Verfahren zur Berechnung der Exponentialmatrix – p.6/14
Weitere Verfahren zur Berechnung
von eA
• Chebyshev-Approximation
− Für −1 ≤ x ≤ 1 gilt die Entwicklung
∞
X
e−αx = 2I0 (α)T0 (αx) + 2 Tj (αx)Ij (α)(−1)j
j=1
− Tj : Chebyshev-Polynom 1. Art der Ordnung j
− Ij : Besselfunktion der Ordnung j
Verfahren zur Berechnung der Exponentialmatrix – p.6/14
Weitere Verfahren zur Berechnung
von eA
• Chebyshev-Approximation
− Für −1 ≤ x ≤ 1 gilt die Entwicklung
∞
X
e−αx = 2I0 (α)T0 (αx) + 2 Tj (αx)Ij (α)(−1)j
j=1
− Tj : Chebyshev-Polynom 1. Art der Ordnung j
− Ij : Besselfunktion der Ordnung j
− Transfer auf Matrizen: r0 =k A k, A0 = A/r0
∞
X
eA = er0 A0 = 2I0 (−r0 )T0 (−A)+2 Tj (−A)Ij (−r0 )(−1)j
j=1
Verfahren zur Berechnung der Exponentialmatrix – p.6/14
Weitere Verfahren zur Berechnung
von eA
• Zugang über gewöhnliche Differentialgleichung:
Verfahren zur Berechnung der Exponentialmatrix – p.7/14
Weitere Verfahren zur Berechnung
von eA
• Zugang über gewöhnliche Differentialgleichung:
− Gegeben ist das AWP
y 0 = Ay, y(t0 ) = y0
Verfahren zur Berechnung der Exponentialmatrix – p.7/14
Weitere Verfahren zur Berechnung
von eA
• Zugang über gewöhnliche Differentialgleichung:
− Gegeben ist das AWP
y 0 = Ay, y(t0 ) = y0
− Die analytische Lösung lautet
y(t) = e(t−t0 )A y0
Verfahren zur Berechnung der Exponentialmatrix – p.7/14
Weitere Verfahren zur Berechnung
von eA
• Zugang über gewöhnliche Differentialgleichung:
− Gegeben ist das AWP
y 0 = Ay, y(t0 ) = y0
− Die analytische Lösung lautet
y(t) = e(t−t0 )A y0
− eA aus n Differentialgleichungen
0
y(i) = Ay(i) , y(i) (0) = ei
Verfahren zur Berechnung der Exponentialmatrix – p.7/14
Weitere Verfahren zur Berechnung
von eA
• Damit ergibt sich
eA = y1 (1) . . . yn (1)
Verfahren zur Berechnung der Exponentialmatrix – p.8/14
Weitere Verfahren zur Berechnung
von eA
• Damit ergibt sich
eA = y1 (1) . . . yn (1)
• Lösung der Differentialgleichungen:
Verfahren zur Berechnung der Exponentialmatrix – p.8/14
Weitere Verfahren zur Berechnung
von 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 Berechnung
von 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 Berechnung
von 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 Berechnung
von eA
• Zugang über Eigenwert-Zerlegung
Verfahren zur Berechnung der Exponentialmatrix – p.9/14
Weitere Verfahren zur Berechnung
von 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 Berechnung
von 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 Berechnung
von 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
eA V diag(λ 1 ,...,λn )V
= V ediag(λ1 ,...,λn ) V −1
−1
− Es folgt = e
Verfahren zur Berechnung der Exponentialmatrix – p.9/14
Weitere Verfahren zur Berechnung
von 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
eA V diag(λ 1 ,...,λn )V
= V ediag(λ1 ,...,λn ) V −1
−1
− Es folgt = e
− Es ergibt sich eA = V diag(eλ1 , . . . , eλn )V −1
Verfahren zur Berechnung der Exponentialmatrix – p.9/14
Weitere Verfahren zur Berechnung
von eA
• Splitting Methode
Verfahren zur Berechnung der Exponentialmatrix – p.10/14
Weitere Verfahren zur Berechnung
von eA
• Splitting Methode
− Ausgangspunkt: Zerlegung A = B + C
Verfahren zur Berechnung der Exponentialmatrix – p.10/14
Weitere Verfahren zur Berechnung
von eA
• Splitting Methode
− Ausgangspunkt: Zerlegung A = B + C
− Die Funktionalgleichung ex+y = ex ey gilt für
Matrizen im Allgemeinen nicht.
Verfahren zur Berechnung der Exponentialmatrix – p.10/14
Weitere Verfahren zur Berechnung
von eA
• Splitting Methode
− Ausgangspunkt: Zerlegung A = B + C
− Die Funktionalgleichung ex+y = ex ey gilt für
Matrizen im Allgemeinen nicht.
− Es gilt legiglich die folgende Äquivalenz:
eB+C = eB eC ⇐⇒ BC = CB
Verfahren zur Berechnung der Exponentialmatrix – p.10/14
Weitere Verfahren zur Berechnung
von eA
• Splitting Methode
− Ausgangspunkt: Zerlegung A = B + C
− Die Funktionalgleichung ex+y = ex ey gilt für
Matrizen im Allgemeinen nicht.
− Es gilt legiglich die folgende Äquivalenz:
eB+C = eB eC ⇐⇒ BC = CB
− Es gilt jedoch die Trotter-(Produkt-)Formel:
m
eB+C = lim eB/m eC/m
m→∞
Verfahren zur Berechnung der Exponentialmatrix – p.10/14
Inhalt der Diplomarbeit
Ziele der Diplomarbeit:
• Untersuchung und Implementierung der
verschiedenen Verfahren zur Berechnung von
n n
e −itH mit jeweils fester Matrix H ∈ C2 ×2
Verfahren zur Berechnung der Exponentialmatrix – p.11/14
Inhalt der Diplomarbeit
Ziele der Diplomarbeit:
• Untersuchung und Implementierung der
verschiedenen Verfahren zur Berechnung von
n n
e −itH mit jeweils fester Matrix H ∈ C2 ×2
• Folgende Aspekte sind zu berücksichtigen:
Verfahren zur Berechnung der Exponentialmatrix – p.11/14
Inhalt der Diplomarbeit
Ziele der Diplomarbeit:
• Untersuchung und Implementierung der
verschiedenen Verfahren zur Berechnung von
n n
e −itH mit jeweils fester Matrix H ∈ C2 ×2
• Folgende Aspekte sind zu berücksichtigen:
− Effizienz
Verfahren zur Berechnung der Exponentialmatrix – p.11/14
Inhalt der Diplomarbeit
Ziele der Diplomarbeit:
• Untersuchung und Implementierung der
verschiedenen Verfahren zur Berechnung von
n n
e −itH mit jeweils fester Matrix H ∈ C2 ×2
• 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 der
verschiedenen Verfahren zur Berechnung von
n n
e −itH mit jeweils fester Matrix H ∈ C2 ×2
• 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 der
verschiedenen Verfahren zur Berechnung von
n n
e −itH mit jeweils fester Matrix H ∈ C2 ×2
• 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
m
e−iHt = e−it(D+C) ≈ e−itD/m 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
m
e−iHt = e−it(D+C) ≈ e−itD/m e−itC/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
m
e−iHt = e−it(D+C) ≈ e−itD/m e−itC/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
m
e−iHt = e−it(D+C) ≈ e−itD/m e−itC/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
m
e−iHt = e−it(D+C) ≈ e−itD/m e−itC/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̃
!
A1 rE
H̃ =
rE A2
Verfahren zur Berechnung der Exponentialmatrix – p.13/14
Inhalt der Diplomarbeit
• Ausnutzung der Persymmetrie
• Transformation von H auf reelle Matrix H̃
!
A1 rE
H̃ =
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̃
!
A1 rE
H̃ =
rE A2
• H̃ ist ähnlich zur Matrix
!
A1 + A2 + 2rE 0
0 A1 + A2 − 2rE
• Reduktion des Problems der EW/EV-Zerlegung
auf 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 weiteren
Verfahren (ODE,Padé,...) ausgenutzt werden?
Verfahren zur Berechnung der Exponentialmatrix – p.14/14
Inhalt der Diplomarbeit
Offene Fragen
• Kann die Struktur von H auch bei weiteren
Verfahren (ODE,Padé,...) ausgenutzt werden?
• Wie pessimistisch sind die
Konvergenzabschätzungen in unserem Fall?
Verfahren zur Berechnung der Exponentialmatrix – p.14/14
Inhalt der Diplomarbeit
Offene Fragen
• Kann die Struktur von H auch bei weiteren
Verfahren (ODE,Padé,...) ausgenutzt werden?
• Wie pessimistisch sind die
Konvergenzabschätzungen in unserem Fall?
• Wie lässt sich die Matrix-Matrix Multiplikation
möglichst schnell berechnen?
Verfahren zur Berechnung der Exponentialmatrix – p.14/14