Probability-One Homotopy for Robust Initialization of Differential-Algebraic Equations

Michael Sielemann
Deutsches Zentrum für Luft- und Raumfahrt, Robotics and Mechatronics Center, System Dynamics and Control, Germany

Ladda ner artikelhttp://dx.doi.org/10.3384/ecp12076223

Ingår i: Proceedings of the 9th International MODELICA Conference; September 3-5; 2012; Munich; Germany

Linköping Electronic Conference Proceedings 76:22, s. 223-236

Visa mer +

Publicerad: 2012-11-19

ISBN: 978-91-7519-826-2

ISSN: 1650-3686 (tryckt), 1650-3740 (online)


An evolution of the recently introduced operator homotopy() is proposed; which further improves the solution of difficult initialization problems. The background and motivation for this approach are discussed and it is demonstrated how to apply it for electrical and fluid systems. The key difference to the earlier approach is the supporting theory; which guarantees that the method converges globally with probability one.


Initialization; DAE; homotopy; nonlinear equations


[1] F. Casella; L. Savoldelli; and M. Sielemann. Steady-state initialization of object-oriented thermo-fluid models by homotopy methods. In Proceedings of Eighth International Modelica Conference; Dresden; Germany; March 2011.

[2] J. E. Dennis and R. B. Schnabel. Numerical methods for unconstrained optimization and nonlinear equations. SIAM Classics in Applied Mathematics; 1996. doi: 10.1137/1.9781611971200.

[3] P. Deuflhard. Newton Methods for Nonlinear Problems. Affine Invariance and Adaptive Algorithms. Springer Verlag; 2004.

[4] P. Dimo. Nodal analysis of power systems. Taylor & Francis; 1975.

[5] R. Duffin. Nonlinear networks lIa. B. Am. Math. Soc.; 53:963–971; 1947. doi: 10.1090/S0002-9904-1947-08917-5.

[6] H. Elmqvist. A Structured Model Language for Large Continuous Systems. PhD thesis; Lund University; Department of Automatic Control; Sweden; May 1978.

[7] M. Green and R. Melville. Sufficient conditions for finding multiple operating points of dc circuits using continuation methods. In IEEE International Symposium on Circuits and Systems; pages 117–120; Seattle; 1995.

[8] M. A. Heroux; R. A. Bartlett; V. E. Howle; R. J. Hoekstra; J. J. Hu; T. G. Kolda; R. B. Lehoucq; K. R. Long; R. P. Pawlowski; E. T. Phipps; A. G. Salinger; H. K. Thornquist; R. S. Tuminaro; J. M. Willenbring; A. Williams; and K. S. Stanley. An overview of the Trilinos project. Acm. T. Math. Software.; 31(3):397–423; 2005. doi: 10.1145/1089014.1089021.

[9] Y. Inoue. A practical algorithm for DC operatingpoint analysis of large-scale circuits. Electronics and Communications in Japan (Part III: Fundamental Electronic Science); 77(10):49–62; 1994. doi: 10.1002/ecjc.4430771005.

[10] C. T. Kelley. Solving nonlinear equations with Newton’s method. SIAM Classics in Applied Mathematics; 2003. doi: 10.1137/1.9780898718898.

[11] W. Mathis; L. Trajkovic; M. Koch; and U. Feldmann. Parameter embedding methods for finding DC operating points of transistor circuits. In Third international specialist workshop on Nonlinear Dynamics of Electronic Systems; NDES 1995; pages 147–150; Dublin; Ireland; July 1995.

[12] S. Mattsson; H. Elmqvist; M. Otter; and H. Olsson. Initialization of hybrid differential-algebraic equations in Modelica 2.0. In Proceedings of the Second International Modelica Conference; 2002.

[13] R. Melville; S. Moinian; P. Feldmann; and L. Watson. Sframe: An efficient system for detailed DC simulation of bipolar analog integrated circuits using continuation methods. Analog. Integr. Circ. S.; 3(3):163–180; 1993. doi: 10.1007/BF01239359.

[14] R. C. Melville; L. Trajkovic; S.-C. Fang; and L. T. Watson. Artificial parameter homotopy methods for the DC operating point problem. IEEE T. Comput. Aid. D.; 12(6):861–877; June 1993. doi: 10.1109/43.229761.

[15] J. J. Moré; B. S. Garbow; and K. E. Hillstrom. User guide for MINPACK-1. Technical Report ANL-80-74; Argonne National Laboratory; 1980.

[16] J. Roychowdhury and R. Melville. Delivering global DC convergence for large mixedsignal circuits via homotopy/continuation methods. IEEE T. Comput. Aid. D.; 25(1):66–78; January 2006. doi: 10.1109/TCAD.2005.852461.

[17] J. S. Roychowdhury and R. C. Melville. Homotopy techniques for obtaining a DC solution of large-scale mos circuits. In Proceedings of the 33rd Design Automation Conference; pages 286–291; 1996.

[18] M. Sielemann. Device-Oriented Modeling and Simulation in Aircraft Energy Systems Design. PhD thesis; Technical University of Hamburg-Harburg; Institute of Thermo-Fluid Dynamics; 2012.

[19] M. Sielemann; F. Casella; M. Otter; C. Clauss; J. Eborn; S. Mattsson; and H. Olsson. Robust initialization of differential-algebraic equations using homotopy. In Proceedings of Eighth International Modelica Conference; Dresden; Germany; March 2011.

[20] M. Sielemann and G. Schmitz. A quantitative metric for robustness of nonlinear algebraic equation solvers. Math. Comput. Simulat.; 81(12):2673–2687; 2011. doi: 10.1016/j.matcom.2011.05.010.

[21] R. Tarjan. Depth-first search and linear graph algorithms. SIAM J. Comput.; 1:146–160; 1972. doi: 10.1137/0201010.

[22] L. Trajkovic and W. Mathis. Parameter embedding methods for finding DC operating points: formulation and implementation. In 1995 International Symposium on Nonlinear Theory and its Applications; NOLTA 1995; pages 1159–1164; Las Vegas NE; USA; December 1995.

[23] L. Trajkovic; R. Melville; and S.-C. Fang. Passivity and no-gain properties establish global convergence of a homotopy method for DC operating points. In IEEE International Symposium on Circuits and Systems; volume 2; pages 914–917; May 1990. doi: 10.1109/ISCAS.1990.112242.

[24] L. Trajkovic; R. C. Melville; and S.-C. Fang. Finding DC operating points of transistor circuits using homotopy methods. In Proc. IEEE Int Circuits and Systems Sympoisum; pages 758–761; 1991.

[25] L. Trajkovic; R. C. Melville; and S.-C. Fang. Improving DC convergence in a circuit simulator using a homotopy method. In Proc. Custom Integrated Circuits Conf. the IEEE 1991; 1991.

[26] L. T. Watson. Globally convergent homotopy methods: A tutorial. Appl. Math. Comput.; 31:369–396; May 1989. doi: 10.1016/0096-3003(89)90129-X.

[27] L. T. Watson. Probability-one homotopies in computational science. J. Comput. Appl. Math.; 140:785–807; 2002. doi: 10.1016/S0377-0427(01)00473-3.

[28] A. N. Willson Jr. The no-gain property for networks containing three-terminal elements. IEEE T. Circuits. Syst.; 22(8):678–687; August 1975. doi: 10.1109/TCS.1975.1084110.

[29] K. Yamamura; T. Sekiguchi; and Y. Inoue. A fixed-point homotopy method for solving modified nodal equations. Circuits and Systems I: Fundamental Theory and Applications; IEEE Transactions on; 46(6):654–665; 1999.

Citeringar i Crossref