General Linear Methods for Integrated Circuit Design
My PhD thesis was published by Logos Verlag Berlin.
Brief summary
Modelling electrical circuits leads to differential algebraic equations (DAEs) having a properly stated leading term. These equations need to be solved numerically, e.g. in case of a transient analysis of the given circuit.
Classical methods such as linear multistep methods or Runge-Kutta schemes suffer from disadvantages that can be overcome by studying general linear schemes. Both Runge-Kutta methods and linear multistep schemes belong to this class as special cases, but there is plenty of room for new methods with improved properties.
This work presents both a detailed study of DAEs in the framework of integrated circuit design and a thorough analysis of general linear methods for these kind of equations. The construction and implementation of general linear methods for DAEs is discussed in detail.
Original project description
Duration: | August 2003 - May 2006 |
Group Leader: |
Prof. Dr. Caren Tischendorf Technical University Berlin Department of Mathematics Strasse des 17. Juni 136 10623 Berlin Germany |
Collaborator: | Steffen Voigtmann |
Cooperation: | Infineon Technologies AG, München |
Today's microchips are mainly produced in CMOS (complementary metal-oxide semiconductor) technology. The main reason for this is that such circuits use almost no power when it is not needed. Combining negatively and positively charged transistors, they only draw power when switching polarity. This is in particular important for mobile devices including laptops, PDAs, and phones. Furthermore, advanced CMOS technology is expected to dominate also in the future since it allows to manufacture transistors in the nanoscale regime.
The further miniaturization drives simulation methods into their limits. Due to the reduced signal/noise ratio, stability and robustness of the methods become more and more important. The mathematical modeling based on the modified nodal analysis leads to differential-algebraic systems. Regarding the switching tasks of circuits, it becomes clear that input functions and solutions often have steep gradients. Consequently, implicit methods of low order are preferable. A combination of low order BDF methods and the trapezoidal rule has been proven to be a very successful and effective approach. Considering the damping properties of BDF methods and the stability behavior of the trapezoidal rule, the latter one is better suited for oscillating circuits. However, solving the system by the trapezoidal rule, the numerical solution drifts away from the manifold given by inherent constraints. On the other hand, BDF methods provide solutions satisfying at least the explicit (index-1) constraints. Therefore, the commonly used strategy is the following. Start the integration with the BDF method. After a few successful steps continue with the trapezoidal rule until convergence problems arise or a breakpoint (switching point) is reached. Use again the BDF method for a few steps followed by trapezoidal steps etc. Obviously, the frequent change of the methods causes problems for an efficient error estimation and stepsize selection.
The concept of general linear methods [1] treats multistep methods and Runge-Kutta methods within one framework. It enables the construction of new methods with different convergence and stability properties. This huge class of methods contains certain subclasses which are of interest for the solution of circuit systems. In particular, certain Diagonally Implicit MultiStage Integration Methods (DIMSIMs) are promising. On the one hand, they can be efficiently implemented because of their diagonal structure. On the other hand, some of them are A-stable and stiffly accurate [10] for ordinary differential equations. Since stiffly accurate Runge-Kutta methods applied to circuit DAEs provide solutions satisfying the index-1 constraints [8,9], we expect the same behavior also for stiffly accurate general linear methods.
The goal is now to find a cheap low order general linear method for index-1 DAEs which has a similar stability region as the trapezoidal rule and provides solutions satisfying the constraints. Following the approach for error estimations presented in [2], a validated stepsize control based on estimations for nodal potentials and currents should be possible. For circuit DAEs of index 2, the method probably needs to be modified in critical parts of the DAE in order to maintain stability properties (cf. [5]). For general DAEs, we cannot expect to identify all critical parts (causing hidden constraints) in advance. But it is possible for circuit DAEs if we exploit their special structure [3,4].
Research program.
The aims of the project can be summarized as follows.
- Development of general linear methods having low order and being stiffly accurate as well as diagonally implicit.
- Investigation of their stability properties for differential algebraic equations. If necessary, modification for index-2 DAEs.
- Development of an error estimator to be the basis for a stepsize control.
- Implementation of a suited method. Use of Nordsieck vectors for easy stepsize change.
- Comparison of the results with existing methods with respect to their accuracy, reliability and computational effort.
Cooperation.
Our industrial partners are Dr. Diana Estévez Schwarz and Dr. Uwe Feldmann from Infineon Technologies in Munich. Furthermore, we closely cooperate with Prof. John Butcher (University of Auckland, New Zealand) and Prof. Claus Führer (Lund University, Sweden).
Literatur.
[1] | J.C. Butcher. Numerical Methods for Ordinary Differential Equations, Second Edition. John Wiley & Sons, 2003. |
[2] | J.C. Butcher and Z. Jackiewicz. A new approach to error estimation for general linear methods. To appear in Numer. Math., 2003. |
[3] | D. Estévez Schwarz, U. Feldmann, R. März, S. Sturtzel, and C. Tischendorf. Finding beneficial DAE structures in circuit simulation. In W. Jäger and H.-J. Krebs, editors, Mathematics - Key Technology for the Future: Joint Projects Between Universities and Industry, pages 413--428. Springer, Berlin, 2003. |
[4] | D. Estévez Schwarz and C. Tischendorf. Structural analysis of electric circuits and consequences for {MNA}. Int. J. Circ. Theor. Appl., 28:131--162, 2000. |
[5] | C. Führer and C. Tischendorf. Stabilization of multistep methods for electric networks. In preparation. |
[6] | M. Günther. Ladungsorientierte Rosenbrock-Wanner-Methoden zur numerischen Simulation digitaler Schaltungen. PhD thesis, Techn. Univ. München, 1995. Fortschritt-Berichte VDI Reihe 20 Nr. 168. VDI-Verlag Düsseldorf. |
[7] | M. Günther and M. Hoschek. ROW methods adapted to electric circuit simulation packages. Journal of Computational and Applied Mathematics, 82:159--170, 1997. |
[8] | I. Higueras, R. März, and C. Tischendorf. Stability preserving integeration of index-1 DAEs. APNUM, 45:175--200, 2003. |
[9] | I. Higueras, R. März, and C.Tischendorf. Stability preserving integeration of index-2 DAEs. APNUM, 45:201--229, 2003. |
[10] | W. Wright. General linear methods with inherent Runge-Kutta stability. PhD thesis, University of Auckland, 2003. |