Advanced Circuit Simulation Using Matrix Exponential Operators
Circuit Simulation via Matrix
Exponential Operators
CK Cheng
UC San Diego
1
Outline
•
General Matrix Exponential
•
Krylov Space and Arnoldi Orthogonalization
•
Matrix Exponential Method
–
Krylov Subspace Approximation
–
Invert Krylov Subspace Approximation
–
Rational Krylov Subspace Approximation
2
General Matrix Exponential
3
Krylov Space and Arnoldi
Orthonormalization
Input A and v
1
=x
0
/|x
0
|
Output AV=VH+h
m+1
v
m+1
e
m
T
For i=1, …, m
•
T
i+1
=Av
i
•
For j=1, …, I
–
h
ji
=<T
i+1
,v
j
>
–
T
i+1
=T
i+1
-h
ji
v
j
•
End For
•
h
i+1,i
=|T
i+1
|
•
v
i+1
=1/h
i+1
T
i+1
End For
4
Standard Krylov Space
Generate: AV=VH+h
m+1
v
m+1
e
m
T
Thus, we have e
Ah
v
1
≈
Ve
Hh
e
1
Residual r=Cdx/dt-Gx=-h
m+1
Cv
m+1
e
m
T
e
Hh
e
1
Derivation:
Cdx/dt-Gx=CVHe
Hh
e
1
-GVe
Hh
e
1
=(CVH-GV)e
Hh
e
1
= C(VH-C
-1
GV)e
Hh
e
1
=C(VH-VH-h
m+1
v
m+1
e
m
T
)e
Hh
e
1
=-h
m+1
Cv
m+1
e
m
T
e
Hh
e
1
5
Standard Mexp
Error trend
6
sweep
m
and
h
Invert Krylov Space
Generate: A
-1
V=VH+h
m+1
v
m+1
e
m
T
Let
H
=H
-1
, we have e
Ah
v
1
≈
Ve
H
h
e
1
Residual r=Cdx/dt-Gx=h
m+1
Gv
m+1
e
m
T
H
e
H
h
e
1
Derivation:
Cdx/dt-Gx=CV
H
e
H
h
e
1
-GVe
H
h
e
1
=(CV
H
-GV)e
H
h
e
1
= G(G
-1
CV
H
-V)e
H
h
e
1
=G(A
-1
V
H
-V)e
H
h
e
1
=h
m+1
Gv
m+1
e
m
T
H
e
H
h
e
1
7
•
large step size with less dimension
Invert
Matrix Exponential
8
sweep
m
and
h
Rational Krylov Space
Generate: (1-rA)
-1
V=VH+h
m+1
v
m+1
e
m
T
Let
H
=1/r (I-H
-1
) we have e
Ah
v
1
≈
Ve
H
h
e
1
Residual r=Cdx/dt-Gx=-h
m+1
(C/r-G)v
m+1
e
m
T
H
-1
e
H
h
e
1
Derivation:
Cdx/dt-Gx=CV
H
e
H
h
e
1
-GVe
H
h
e
1
=(CV
H
-GV)e
H
h
e
1
= (1/r CV(I-H
-1
)-GV)e
H
h
e
1
=(1/rCV(H-1)-GVH)H
-1
e
H
h
e
1
=((1/rC-G)VH-1/rCV)H
-1
e
H
h
e
1
=-h
m+1
(C/r-G)v
m+1
e
m
T
H
-1
e
H
h
e
1
9
•
large step size with less dimension
Rational
Matrix Exponential
10
fix
,
sweep
m
and
h
Different
11
Different
12
Spectral Transformation –
= 10f
•
Small RC mesh, 100 by 100
•
Different h for Krylov subspace
•
Different
for rational Krylov subspace
13
Spectral Transformation–
= 1p
•
Small RC mesh, 100 by 100
•
Different h for Krylov subspace
•
Different
for rational Krylov subspace
14
Spectral Transformation–
= 100p
•
Small RC mesh, 100 by 100
•
Different h for Krylov subspace
•
Different
for rational Krylov subspace
15
Sweep
for Large Range
16
Sweep
for Large Range
17
Difference Between Inverted and
Rational
18
Fixed
= 1p, sweep time step h
19
Fixed
= 1n, sweep time step h
20
Fixed
= 1u, sweep time step h
21
Fixed
= 1m, sweep time step h
22
Fixed
= 1, sweep time step h
23
Fixed
= 1k, sweep time step h
24
Fixed
= 1M, sweep time step h
25
Krylov Space Residual
Generate: AV=VH+h
m+1
v
m+1
e
m
T
Thus, we have e
Ah
v
1
≈
Ve
Hh
e
1
Residual r=Cdx/dt-Gx=-h
m+1
Cv
m+1
e
m
T
e
Hh
e
1
Derivation:
1. Set Y=[e
1
He
1
H
2
e
1
… H
m-1
e
1
]
2. We have YC=HY where C=
z
m
+c
m-1
z
m-1
+…+c
1
z+c
0
=0
has roots
𝞴
1,
𝞴
2,…
𝞴
m
26
Krylov Space Residual
27
Invert Krylov Space Residual
28
Explore the innovative approach of circuit simulation via matrix exponential operators as proposed by CK Cheng from UC San Diego. The method involves utilizing general matrix exponentials, Krylov spaces, Arnoldi orthonormalization, and inverting Krylov subspaces for accurate simulations. These techniques provide a deeper understanding of circuit behavior and allow for efficient analysis in complex systems.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Circuit Simulation via Matrix Exponential Operators CK Cheng UC San Diego 1
Outline General Matrix Exponential Krylov Space and Arnoldi Orthogonalization Matrix Exponential Method Krylov Subspace Approximation Invert Krylov Subspace Approximation Rational Krylov Subspace Approximation 2
General Matrix Exponential ?0(At)= eAt ?1(At)= 0 ?2(At)= 0 ?eA(t ?) d?=A-1(eAt-I) ?eA(t ?) ?d?=A-2(eAt-A-I) ?k(At) = 0 ???(? ?)?k/k!d?=A k(eAt Ak 1/(k 1)! A I) Exercise: Expand the right hand side expression to remove the inverse operation. 3
Krylov Space and Arnoldi Orthonormalization Input A and v1=x0/|x0| Output AV=VH+hm+1vm+1emT For i=1, , m Ti+1=Avi For j=1, , I hji=<Ti+1,vj> Ti+1=Ti+1-hjivj End For hi+1,i=|Ti+1| vi+1=1/hi+1 Ti+1 End For In other words, ? Avi- ?=1 hjivj =hi+1,ivi+1 4
Standard Krylov Space Generate: AV=VH+hm+1vm+1emT Thus, we have eAhv1 VeHhe1 Residual r=Cdx/dt-Gx=-hm+1Cvm+1emTeHhe1 Derivation: Cdx/dt-Gx=CVHeHhe1-GVeHhe1 =(CVH-GV)eHhe1 = C(VH-C-1GV)eHhe1 =C(VH-VH-hm+1vm+1emT)eHhe1 =-hm+1Cvm+1emTeHhe1 5
Standard Mexp = H A h h v v V Error e e e m m 1 2 Error trend sweep m and h 6
Invert Krylov Space Generate: A-1V=VH+hm+1vm+1emT Let H=H-1, we have eAhv1 VeHhe1 Residual r=Cdx/dt-Gx=hm+1Gvm+1emTHeHhe1 Derivation: Cdx/dt-Gx=CVHeHhe1-GVeHhe1 =(CVH-GV)eHhe1 = G(G-1CVH-V)eHhe1 =G(A-1VH-V)eHhe1 =hm+1Gvm+1emTHeHhe1 7
Invert Matrix Exponential large step size with less dimension h m 1 H = A h v v V error e e e sweep m and h m 1 2 8
Rational Krylov Space Generate: (1-rA)-1V=VH+hm+1vm+1emT Let H=1/r (I-H-1) we have eAhv1 VeHhe1 Residual r=Cdx/dt-Gx=-hm+1(C/r-G)vm+1emTH-1eHhe1 Derivation: Cdx/dt-Gx=CVHeHhe1-GVeHhe1 =(CVH-GV)eHhe1 = (1/r CV(I-H-1)-GV)eHhe1 =(1/rCV(H-1)-GVH)H-1eHhe1 =((1/rC-G)VH-1/rCV)H-1eHhe1 =-hm+1(C/r-G)vm+1emTH-1eHhe1 9
Rational Matrix Exponential large step size with less dimension h ~ H m = A fix , sweep m and h h v v V Error e e e m 1 2 10
Different needs large m 11
Different 12
Spectral Transformation = 10f Small RC mesh, 100 by 100 Different h for Krylov subspace Different for rational Krylov subspace 13
Spectral Transformation = 1p Small RC mesh, 100 by 100 Different h for Krylov subspace Different for rational Krylov subspace 14
Spectral Transformation = 100p Small RC mesh, 100 by 100 Different h for Krylov subspace Different for rational Krylov subspace 15
Difference Between Inverted and Rational 18
Krylov Space Residual Generate: AV=VH+hm+1vm+1emT Thus, we have eAhv1 VeHhe1 Residual r=Cdx/dt-Gx=-hm+1Cvm+1emTeHhe1 Derivation: 1. Set Y=[e1 He1 H2e1 Hm-1e1] 2. We have YC=HY where C= zm+cm-1zm-1+ +c1z+c0=0 has roots ?1,?2, ?m 0 -c0 -c1 -c2 1 0 1 0 1 0 -cm-2 -cm-1 1 26
Krylov Space Residual Residual r=Cdx/dt-Gx=-hm+1Cvm+1emTeHhe1 3. C=V-1DV (VC=DV), V= D=Diag(?1,?2, ?m) 4. H=YCY-1=YV-1DVY-1 5. eH=YV-1eDVY-1 6. emTeHhe1 =emTYV-1eDhVY-1e1 =emTYV-1eDh1, 1=[1,1, 1]T =emTYV-1[e?1h, e?2h, ,e?mh]T ?=1 ?1m-1 ?2m-1 . ?1 ?2 . 1 . 1 . . . . . . . . . . ?mm-1 ?m 1 . ? 1hi+1,ihm-1/(m-1)! 27
Invert Krylov Space Residual Generate: A-1V=VH+hm+1vm+1emT Thus, we have eAhv1 VeHhe1 Residual r=Cdx/dt-Gx=-hm+1Cvm+1emTeHhe1 Derivation: 6. Exercise to derive: emTH-1eHhe1 ? 28
