Pantelides Algorithm in PHP

The following describes an implementation of Pantelides algorithm in PHP that was used to identify index problems in a differential-algebraic equation system that I have been working on. You might be interested to use this software if you are having trouble understanding how this algorithm works, or if you are having trouble formulating a system of equations in a form which is reliably solvable. It's licensed under GPL.

What is Pantelides Algorithm?

[figure: graph of the exothermic reactor example]

Pantelides algorithm is an iterative procedure which reduces the index of a system of non-linear differential equations, such that it can be solved by conventional ODE tools. For full details on the algorithm, see the original paper or try the following lecture overheads by Francois Cellier.

Pantelides Algorithm uses some graph theory to establish a minimum set of equations which must be differentiated in order to remove a structural singularity. Each time equations are differentiated, a 'path augmentation' process is applied to the bi-partite graph of equations and variables to attempt to find a mapping which uniquely assigns all of the unknown variables in the system to an equation which can be used to calculate that variable. The algorithm will go on differentiating the system of equations until a complete assignment has been found.

A PHP implementation

PHP is a simple scripting language (a bit like Python, which, to be honest, is much more appropriate for scientific computing) that I am familiar with. I used it to knock up a quick visual guide to how the algorithm works. It was helpful to me in coming to understand the algorithm. Even though the code here is fairly messy, it does work, so perhaps it will be useful to someone else. It would be nice to translate it to a more object-oriented form, but that will have to wait.

Please download pantelides-0.1.tar.bz2 (version 0.1, 5k) if you would like to use the code.


The following examples from the Pantelides paper have been implemented. Click to view the output (source files are in the archive above. To create a graphic like that shown on this page, use the function 'printsystemdot' and then post-process that output with the GraphViz 'dot' tool.

Pantlides in Practice

Pantelides' algorithm is used in various simulation software: EMSO and Modelica, among others.

Rafael de Pelegrini Soares (developer of EMSO) is working on a modified version of Pantelides Algorithm which does not suffer from the infinite loop problem that the original version has, to be published soon.

US Patent 7415395 by M Khan, of Caterpillar Inc., seems to refer to this page! Cool, huh?

John Pye
Last modified: 8 Nov 2011