⬇ Download Markdown · ⬇ Download LaTeX · ⬇ original · view original
Stability Analysis of Latency Insertion Method (LIM) Zhichao Deng and I. E. Schutt-Aine Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign Urbana, IL 61801, USA (2 17)333-0503, (21 7 )244-7279 email: [email protected], [email protected] Abstract In this work, the stability of the latency insertion method (LIM) for the time-domain simulation of networks is analyred in order to determine the optimal difference scheme for various formulations. The Von Neumann method is used and the stability conditions are given by the limitations on the time step according to R, L , and C. Introduction The latency insertion method (LIM) was recently developed to simulate the high-frequency response of large networks in the time domain [ 11. The method uses a finite difference formulation to update branch currents and node voltages in a leapfrog manner similar to the Yee algorithm used in the finite-difference time-domain (FDTD) method [Z]. As a result, LIM has linear computational complexity and is thus substantially faster than the tra ditional matrix-vector product based methods such as SPICE. The LIM formulation is enabled through the insertion of small inductors and capacitors throughout the network, which generate the latency at each node and branch and also impose conditions on the time step size and stability of the solution. In this paper, the stability of the LIM algorithm is investigated in a manner analogous to the traditional FDTD schemes 131-[4]. Several difference approaches are analyzed based on the Von Neumann (Fourier series) method. Different stability conditions are given for each approach. r Fig. 1. Linear branch and node Stability Analysis of Linear and Nonlinear Elements to the following relations. In standard LIM algorithm [I], the linear elements in a branch linked to a node (Fig. 1 . ) are discretized according The nonlinear elements of a branch linked to a node (Fig. 2) are discretized as below: In order to analyze the stability ofthese solutions, various difference approaches need to be compared. In [I], the stability condition is given for the lossless case, where Rij and Gi are both zeros and correspond to the same condition obtained for FDTD: At<& (5) 0-7803-667-1/04/$20.00 0 2004 IEEE 167
In the linear case, [ I ] uses the forward and backward Euler schemes respectively. When nonlinear elements are present, it uses the backward Euler scheme. Without loss of generality, the independent sources are neglected. First, the stability analysis assumes a homogeneously loaded grid with identical R, L, and G, C~values in all branches and nodes. In addition, only two branches connected to each node. which corresoonds I I to a unidirectional network. And the direction is x. This places the LIM algorithm in the same difference scheme category as the one-dimensional . FDTD in [3]. Two simplified differential equations for linear branch and node are respectively given Fig. 2. Nonlinear branch and node Next, from (6)-(7), we use the stability criterion based on Von Neumann method for FDTD [3]-[4] to obtain similar stability constraints for several difference formulations. Further details about the Von Neumann method can be found in [SI. LIM uses a central difference formulation for dv/dt and dUdt according to (l)-(2). However, the resistive drop term, RI and GV can take an explicit, semi-implicit or fully implicit form. The three cases will be discussed later. If the current of the branches are in x-direction, the discretized form of (6) and (7) i s The resistorlconductance term can have several elements. For an arbitrary nonlinear device the resistorlconductance term can he expressed by a linear combination of the currentlvoltage at previous time steps. RI=-( c ,P +c ol" + c,I"-' +. . . + CJO) At I I 3 I C At GV = -(d-,Vnf +'d,V'-' +d,V'? +...+ d,,.,Vi) Here c,and d, ,i = -1,O,l...n are the coefficients represent the linearized currentlvoltage model of any nonlinear devices. For different scheme, the coefficients are different. It will be illustrated in the following subsections. To perform stability analysis of this system, the Von Neumann method used in [3]-[4] is applied. In order to insure stability, the magnitudes of all eigenvalues of the amplification matrix for the difference scheme have to be less than one. This leads to the following stability conditions for different difference schemes. A. Explicit (Forward Euler) In the explicit case, the resistor term RI is given by RI" and the conductance term GV is given by GV". Then RAf GAf L c C, = - do = - ,dj &c,-= 0,; # 0. T his is a first-order accurate scheme. Hence, the Courant number y = AI / ( ~ x f i ) , (AX = I ) satisfies 1 2 y < -&I - 2( RAt I L + GAt / C) + RGA12 I LC 168
This inequality is used to solve for the time step leading to the following stability condition r If RG > 8 , K, 2 1 ; the time step can be larger than the unloaded FDTD case. For other cases, K, can be any value. A special condition when G = 0, the stability condition becomes y < l / q z 2 At < J - - R C / 4 = [[T-(R7) (15) When R is increased, the time step is decreased. B. Semi-Implicit (Luap Fro@ In the semi-implicit case, the resistor term RI is expressed by R(I" + 1"+')/2 and the conductance term GYis given by G(Y'i+'/2 + V"-'l2 ) / 2 . This is a second-order accurate scheme. So we have GAt d., = do = - , d, &ei = 0,i # 0,-1, Then the Courant number y satisfies the condition: RAt c-l = = 21, 2c 1 1 + d-, , dD- (16) 1 ac+bd+abcd+l 1 Y S - j Y ' , aOl-c,, b D l - d o , CO- 2 I+c-, There are three cases, when the inequality of (16) can be correct. alc > l&lbld < 1 alc < 1 & Ibld > 1 I) a and b ~(0,1] 2) ab < O and lbld < l 3) a and b < O and abcd <1 and Then the time step AI is limited by 1 At K2m, K --,/(I -c0)(2+d., + d o ) + ( l+c-,)(2+ d -, -do) 2-2 For a special case where c-, = co,d_, & do = 0, the stability condition is (17) This is the same limit as in the lossless case. The time step Al is not related to the value of the resistor. C. Fully Implicit (Backward Euler) In the fully implicit case, the resistor term RI is given by RI"" and the conductance term GV is given by . Then we have c_, = - d-, = - ,d, &, = 0,i f -1. This has a first-order accuracy. And the Courant GV"+l/2 RAt GAt L C number y satisfies the condition: For the case c-, f O,d., = 0, the stability condition becomes 169
y l - 4 +2- 2 ‘ d ‘r This stability limit is larger than that of the lossless case, because the factor a + M , ( M = Jc/L. R / 4 ) is always greater than one. A similar result can be derived for the case where G # 0 and R=O. This analysis also shows that for larger time steps, the backward Euler scheme is faster. Thus, for more accurate results, the semi-implicit scheme is the most appropriate. At each time step, the nonlinear function can be linearized; in fact, the stability analysis becomes more complex due to the time dependent parameters. For a branch diode, the equivalent local resistance Req = V, l(I + Is) is used in the above stability analysis. For inhomogeneous cases, where the L and C are not the same over the overall domain but R and G are the same, the smallest product of L and C, which are connected to the same node, determines the whole system’s stability. For inhomogeneous cases, where the R, G, L and C are all different over the overall domain, there is no analytical stability condition. But for linear system, the stability condition can be limited by the smallest product of L and C connected to the same node for fully implicit difference scheme. For multi-dimensional case, where n pairs of branches connected to a node i and the LjI and C, are the inductance ofthe kth branch and capacitance of node i, respectively. Then the stability condition becomes (22) A t < P. m i n ( J L l k C I ) / f i , ( k = 1 ,... , 2 n ) Ik i,k Here P,k represents the coefficient from a given difference scheme (i.e. P,r = 6 + M for Backward Euler). Thus for inhomogeneous medium, the stability condition will vary from one location to another, the overall stability condition is limited to the smallest LC, which greatly affects the speed of LIM. Then some automatic partitioning algorithm will be needed to divide the whole network into many sub networks, which have different time step limitations. Conclusions This paper presented a stability analysis of LIM for explicit, semi-explicit and fully implicit difference schemes. It was shown that with the proper constraints, the largest possible time step could optimize the algorithm. Speedup techniques can be found to further improve the efficiency of the algorithm; for example, automatic partitioning of the network according to the level of latency can help reduce the simulation time for blocks associated with large time steps. The nonlinear simulation capability of LIM will be addressed in another paper. References [l] Jose E. Schun-AinQ “Latency insertion method(L1M) for the fast transient simulation of large networks,” IEEE Trum. Circuits Syst., vol. 48 (Jan. 2001) pp. 81-89. [2] K. S. Yee, “Numerical solution of initial boundary value problems involving Maxwell’s equation in isotropic media”, IEEE Trans. Antennas Propagat., vol. AP-14 (May 1966) pp. 302-307. [3] Werner Thiel and Linda P. B. Katehi, “Some aspects of stability and numerical dissipation of the fmite- difference time-domain (FDTD) technique including passive and active lumped elements,” IEEE Trans Microwave Theory Tech., v ol. 50, No. 9 (September 2002) pp. 2159-2165. [4] Jose A. Pereda, Oscar Garcia, Angel Vegas, and Andres Prieto, “Numerical dispersion and stability analysis of the FDTD technique in lossy dielectrics,” IEEE Microwave and Guided Wave Letters, vol. 8, No. 7 (July 1998) pp. 245-241. [ 5 ] J. W. Thomas, Numerical Partial Differential Eauations. Finite Difference Methods, Springer-Verlag (New York, 1995). 170