Conversion Methods for Improving Structural Analysis of Differential-Algebraic Equation Systems

Abstract

Systems of differential-algebraic equations (DAEs) arise in many areas including chemical engineering, electrical circuit simulation, and robotics. Such systems are routinely generated by simulation and modeling environments, like MapleSim, Matlab/Simulink, and those based on the Modelica language. Before a simulation starts and a numerical solution method is applied, some kind of structural analysis (SA) is performed to determine the structure and the index of a DAE system. Structural analysis methods serve as a necessary preprocessing stage, and among them, Pantelides's graph-theory-based algorithm is widely used in industry. Recently, Pryce's Σ-method is becoming increasingly popular, owing to its straightforward approach and capability of analyzing high-order systems. Both methods are equivalent in the sense that (a) when one succeeds, producing a nonsingular Jacobian, the other also succeeds, and that (b) the two give the same structural index in the case of either success or failure. When SA succeeds, the structural results can be used to perform an index reduction process, or to devise a stage-by-stage solution scheme for computing derivatives or Taylor coefficients up to some order. Although such a success occurs on fairly many problems of interest, SA can fail on some simple, solvable DAEs with an identically singular Jacobian, and give incorrect structural information that usually includes the index. In this thesis, we focus on the Σ-method and investigate its failures. Aiming at making this SA more reliable, we develop two conversion methods for fixing SA failures. These methods reformulate a DAE on which the Σ-method fails into an equivalent problem on which SA is more likely to succeed with a nonsingular Jacobian. The implementation of our methods requires symbolic computations. We also combine our conversion methods with block triangularization of a DAE. Using a block triangular form of a Jacobian sparsity pattern, we identify which diagonal block(s) of the Jacobian is identically singular, and then perform a conversion on each singular block. This approach can reduce the computational cost and improve the efficiency of finding a suitable conversion for fixing SA's failures.