Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 


Tractability index of hybrid equations for circuit simulation

Authors: Satoru Iwata, Mizuyo Takamatsu and Caren Tischendorf
Journal: Math. Comp. 81 (2012), 923-939
MSC (2010): Primary 34A09, 94C05; Secondary 65L80, 94C15
Published electronically: November 8, 2011
MathSciNet review: 2869043
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Modern modeling approaches for circuit simulation such as the modified nodal analysis (MNA) lead to differential-algebraic equations (DAEs). The index of a DAE is a measure of the degree of numerical difficulty. In general, the higher the index is, the more difficult it is to solve the DAE.

In this paper, we consider a broader class of analysis methods called the hybrid analysis. For nonlinear time-varying circuits with general dependent sources, we give a structural characterization of the tractability index of DAEs arising from the hybrid analysis. This enables us to determine the tractability index efficiently, which helps to avoid solving higher index DAEs in circuit simulation.

References [Enhancements On Off] (What's this?)

  • 1. S. Amari, Topological foundations of Kron's tearing of electric networks, RAAG Memoirs 3 (1962), 322-350.
  • 2. K. Balla and R. März, A unified approach to linear differential algebraic equations and their adjoints, Z. Anal. Anwendungen 21 (2002), no. 3, 783–802. MR 1929432, 10.4171/ZAA/1108
  • 3. Adi Ben-Israel and Thomas N. E. Greville, Generalized inverses, 2nd ed., CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, 15, Springer-Verlag, New York, 2003. Theory and applications. MR 1987382
  • 4. F. H. Branin, The relation between Kron's method and the classical methods of network analysis, The Matrix and Tensor Quarterly 12 (1962), 69-115.
  • 5. K. E. Brenan, S. L. Campbell, and L. R. Petzold, Numerical solution of initial-value problems in differential-algebraic equations, Classics in Applied Mathematics, vol. 14, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1996. Revised and corrected reprint of the 1989 original. MR 1363258
  • 6. P. R. Bryant, The order of complexity of electrical networks, Proceedings of the Institution of Electrical Engineers, Part C 106 (1959), 174-188.
  • 7. Stephen L. Campbell and C. William Gear, The index of general nonlinear DAEs, Numer. Math. 72 (1995), no. 2, 173–196. MR 1362259, 10.1007/s002110050165
  • 8. Leon O. Chua, Dynamic nonlinear networks: state-of-the-art, IEEE Trans. Circuits and Systems 27 (1980), no. 11, 1059–1087. MR 594151, 10.1109/TCS.1980.1084745
  • 9. D. Estévez Schwarz and C. Tischendorf, Structural analysis of electric circuits and consequences for MNA, International Journal of Circuit Theory and Applications 28 (2000), 131-162.
  • 10. W. Fischer, Equivalent circuit and gain of MOS field effect transistors, Solid-State Electronics 9 (1966), 71-81.
  • 11. Eberhard Griepentrog and Roswitha März, Differential-algebraic equations and their numerical treatment, Teubner-Texte zur Mathematik [Teubner Texts in Mathematics], vol. 88, BSB B. G. Teubner Verlagsgesellschaft, Leipzig, 1986. With German, French and Russian summaries. MR 881052
  • 12. M. Günther and P. Rentrop, The differential-algebraic index concept in electric circuit simulation, Zeitschrift für angewandte Mathematik und Mechanik 76, supplement 1 (1996), 91-94.
  • 13. E. Hairer and G. Wanner, Solving ordinary differential equations. II, 2nd ed., Springer Series in Computational Mathematics, vol. 14, Springer-Verlag, Berlin, 1996. Stiff and differential-algebraic problems. MR 1439506
  • 14. I. Higueras, R. März, and C. Tischendorf, Stability preserving integration of index-1 DAEs, Appl. Numer. Math. 45 (2003), no. 2-3, 175–200. MR 1967573, 10.1016/S0168-9274(02)00215-5
  • 15. Roger A. Horn and Charles R. Johnson, Matrix analysis, Cambridge University Press, Cambridge, 1985. MR 832183
  • 16. Masao Iri, A min-max theorem for the ranks and term-ranks of a class of matrices—An algebraic approach to the problem of the topological degrees of freedom of a network, Electron. Commun. Japan 51 (1968), no. 5, 18–25. MR 0258849
  • 17. M. Iri, Applications of matroid theory, Mathematical programming: the state of the art (Bonn, 1982) Springer, Berlin, 1983, pp. 158–201. MR 717401
  • 18. Satoru Iwata and Mizuyo Takamatsu, Index minimization of differential-algebraic equations in hybrid analysis for circuit simulation, Math. Program. 121 (2010), no. 1, Ser. A, 105–121. MR 2520408, 10.1007/s10107-008-0227-8
  • 19. S. Iwata, M. Takamatsu, and C. Tischendorf, Hybrid analysis of nonlinear time-varying circuits providing DAEs with index at most one, Scientific Computing in Electrical Engineering SCEE 2008 (J. Roos and L. R. J. Costa, eds.), Mathematics in Industry, vol. 14, Springer, 2010, pp. 151-158.
  • 20. Genya Kishi and Yoji Kajitani, Maximally distinct trees in a linear graph, Electron. Commun. Japan 51 (1968), no. 5, 35–42. MR 0252270
  • 21. G. Kron, Tensor Analysis of Networks, John Wiley and Sons, New York, 1939.
  • 22. Peter Kunkel and Volker Mehrmann, Canonical forms for linear differential-algebraic equations with variable coefficients, J. Comput. Appl. Math. 56 (1994), no. 3, 225–251. MR 1335565, 10.1016/0377-0427(94)90080-9
  • 23. Peter Kunkel and Volker Mehrmann, Index reduction for differential-algebraic equations by minimal extension, ZAMM Z. Angew. Math. Mech. 84 (2004), no. 9, 579–597. MR 2083283, 10.1002/zamm.200310127
  • 24. Roswitha März, Numerical methods for differential algebraic equations, Acta numerica, 1992, Acta Numer., Cambridge Univ. Press, Cambridge, 1992, pp. 141–198. MR 1165725
  • 25. -, Nonlinear differential-algebraic equations with properly formulated leading term, Tech. Report 01-3, Department of Mathematics, Humboldt-Universität zu Berlin, 2001,
  • 26. R. März, The index of linear differential algebraic equations with properly stated leading terms, Results Math. 42 (2002), no. 3-4, 308–338. MR 1946748, 10.1007/BF03322858
  • 27. Roswitha März and Ricardo Riaza, Linear differential-algebraic equations with properly stated leading term: regular points, J. Math. Anal. Appl. 323 (2006), no. 2, 1279–1299. MR 2260180, 10.1016/j.jmaa.2005.11.038
  • 28. Sven Erik Mattsson and Gustaf Söderlind, Index reduction in differential-algebraic equations using dummy derivatives, SIAM J. Sci. Comput. 14 (1993), no. 3, 677–692. MR 1214776, 10.1137/0914043
  • 29. H. Narayanan, Submodular functions and electrical networks, Annals of Discrete Mathematics, vol. 54, North-Holland Publishing Co., Amsterdam, 1997. MR 1453578
  • 30. Tatsuo Ohtsuki, Yasutoshi Ishizaki, and Hitoshi Watanabe, Network analysis and topological degrees of freedom, Electron. Commun. Japan 51 (1968), no. 6, 33–40. MR 0265068
  • 31. J. M. Rabaey, The spice page,
  • 32. A. Recski, Matroid Theory and Its Applications in Electric Network Theory and in Statics, Springer-Verlag, Berlin, 1989.
  • 33. G. Reißig, The index of the standard circuit equations of passive RLCTG-networks does not exceed 2, Proceedings of the 1998 IEEE International Symposium on Circuits and Systems (ISCAS '98) 3 (1998), 419-422.
  • 34. -, Extension of the normal tree method, International Journal of Circuit Theory and Applications 27 (1999), 241-265.
  • 35. Werner C. Rheinboldt, Differential-algebraic systems as differential equations on manifolds, Math. Comp. 43 (1984), no. 168, 473–482. MR 758195, 10.1090/S0025-5718-1984-0758195-5
  • 36. Ricardo Riaza, Differential-algebraic systems, World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2008. Analytical aspects and circuit applications. MR 2426820
  • 37. Ricardo Riaza and Roswitha März, Linear index-1 DAEs: regular and singular problems, Acta Appl. Math. 84 (2004), no. 1, 29–53. MR 2104183, 10.1023/B:ACAP.0000045308.01276.41
  • 38. M. Takamatsu and S. Iwata, Index characterization of differential-algebraic equations in hybrid analysis for circuit simulation, International Journal of Circuit Theory and Applications 38 (2010), 419-440.
  • 39. Caren Tischendorf, Topological index calculation of differential-algebraic equations in circuit simulation, Surveys Math. Indust. 8 (1999), no. 3-4, 187–199. MR 1737412

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 34A09, 94C05, 65L80, 94C15

Retrieve articles in all journals with MSC (2010): 34A09, 94C05, 65L80, 94C15

Additional Information

Satoru Iwata
Affiliation: Research Institute for Mathematical Sciences, Kyoto University, Kyoto 606-8502, Japan

Mizuyo Takamatsu
Affiliation: Department of Information and System Engineering, Chuo University, Tokyo 112-8551, Japan

Caren Tischendorf
Affiliation: Mathematical Institute, University of Cologne, Weyertal 86-90, 50931 Köln, Germany

Keywords: Differential-algebraic equations, index, circuit simulation, hybrid analysis
Received by editor(s): May 18, 2010
Received by editor(s) in revised form: February 23, 2011
Published electronically: November 8, 2011
Additional Notes: The first author was supported by a Grant-in-Aid for Scientific Research from the Japan Society for Promotion of Science.
The second author was supported by a Grant-in-Aid for Scientific Research from the Japan Society for Promotion of Science.
The third author was supported by the European Union within the framework of the project “Integrated Circuit/EM Simulation and design Technologies for Advanced Radio Systems-on-chip” (FP7/2008/ICT/214911).
Article copyright: © Copyright 2011 American Mathematical Society