Edit on GitHub

Equation Reduction

This section provides functions to reduce the dimensions of systems of equations.

Linear Integer Equations

Many equations of object-oriented models are linear Integer equations (such as all equations deduced from connections, or, say defining a potential difference) and can be pre-processed exactly to simplify the equations, for example elimination of alias variables, or variables that are identically to zero). Furthermore, (consistently) redundant or (consistently) overdetermined equations can be removed. Finally, hidden state constraints can be made explicit in order that a structural algorithm (such as the algorithm of Pantelides) can process state constraints.

ModiaBase.simplifyLinearIntegerEquations! — Function
(vEliminated, vProperty, nvArbitrary, redundantEquations) = 
    simplifyLinearIntegerEquations!(G, eInt, GcInt, Avar)

Remove singularities of the linear Integer equations of a DAE system and simplify these equations as much as possible.

The following singularities are fixed by this function:

  • Equations that are redundant are removed.

  • State constraint that are not structurally visible are transformed to a structurally visible form so that structural index reduction algorithms, such as the Pantelides algorithm, can handle these state constraints.

  • Variables that can have an arbitrary value and do not appear in the remaining set of equations (so must be solved from the linear Integer equations) are set to zero. The calling function should print a warning message in such a case (if nvArbitrary > 0).

The following simplifications are performed recursively (c is an arbitrary Integer literal):

  • An equation c*v1 = 0 is removed and v1 is replaced by zero in all occurrences of the linear Integer equations and all expressions with v1 are simplified.
  • An equation c*v2 + c*v3 = 0 or c*v2 - c*v3 = 0 is removed and v2 is replaced by v3 or by -v3 in all occurrences of the linear Integer equations and all expressions with v2 and v3 are simplified.

Note:

  • Input arguments G, eInt, GcInt are changed by a call of this function and represent the transformed linear Integer equations. The Abstract Syntax Tree (AST) of all these equations must be replaced by new AST equations defined by the returned arguments.
  • The number of operations in the transformed linear Integer equations is guaranteed to be not larger as the original equations - with exception of the structurally visible state constraints, where the number of operations could be larger.
  • Potential states (variables appearing differentiated) and derivatives of potential states are not eliminated by this function.

Input arguments

  • G: Bi-partite graph/incidence matrix of all equations. Typically: G::Vector{Vector{Int}} On entry, G is the original graph. On exit, the linear Integer equations of G are typically changed.

  • eInt::Vector{Int}: G[eInt] are the linear Integer equations of G. On exit, eInt is reordered. If length(G[eInt[i]]) = 0, then the corresponding equation is eliminated.

  • GcInt: GcInt[i] is the vector of Integer coefficients that are associated with the variables of G[eInt[i]]. Typically: GcInt::Vector{Vector{Int}}. On exit, GcInt is reordered according to eInt and typically most of the coefficients have been changed.

  • Avar::Vector{Int}: Defines the derivatives of the variables: A[i] = if der(v_i) == v_k then k else 0. This vector is not changed by simplifyLinearIntegerEquations!.

Output arguments

  • vEliminated::Vector{Int}: Variables that are eliminated.

  • vProperty::Vector{Int}: Defines the properties of the eliminated variables. These properties can be inquired with the following exported functions:

    o isNotEliminated(vProperty, v) - if variable v is not eliminated. o isEliminated(vProperty, v) - if variable v is eliminated. o isZero(vProperty,v) - if eliminated variable v is zero. o isAlias(vProperty,v) - if eliminated variable v is an alias variable v = valias o isNegAlias(vProperty,v) - if eliminated variable v is a negative alias variable v = -valias o alias(vProperty,v) - alias variable valias of eliminated variable v (v = valias). o negAlias(vProperty,v) - negated alias variable valias of eliminated variable v (v = -valias).

  • nvArbitrary::Int: Variables vEliminated[1:nvArbitrary] are variables that can be arbitrarily set and that have been set to zero.

  • redundantEquations::Vector{Int}: G[redundantEquations] are redundant equations that have been removed.

Algorithm

The algorithm to remove the singularities is sketched in the paper:

An error in this algorithm was fixed, the algorithm was improved to handle large equation systems and to simplify equations as much as possible.

Main developer

Martin Otter, DLR - Institute of System Dynamics and Control

source

Algebraic Systems

Algebraic equation systems are reduced by selecting a subset of the variables as iteration variables and computing the remaining variables in a forward sequence.

ModiaBase.TearingSetup — Type
ts = TearingSetup(G [,nv])

Generate a setup object ts from a bi-partite graph G to reduce one or more systems of equations that are present in G. The returned object ts holds internal auxiliary storage that is used in analysis with function tearEquations!.

G is expected to be a vector of integer vectors (for example of type Vector{ Vector{Int} }). The optional argument nv is the largest integer number occuring in G (= number of variables). If nv is not provided, it is deduced from G.

TearingSetup is useful to reduce the amount of memory to be allocated, if function tearEquations! shall be called several times on equation systems from G.

source
ModiaBase.tearEquations! — Function
(eSolved, vSolved, eResidue, vTear) = tearEquations!(GorTs, isSolvable, es, vs; 
    eSolvedFixed=Int[], vSolvedFixed=Int[], check=true)

This function tears a system of equations consisting of equations es and eSolvedFixed that are functions of variables vs and vSolvedFixed. The optional arguments eSolvedFixed, vSolvedFixed define the starting Directed Acyclic Graph (solving equations eSolvedFixed[1] for variable vSolvedFixed[1], eSolvedFixed[2] for variable vSolvedFixed[2] etc.) starting at vSolvedFixed[1].

The function returns the teared equations so that if vTear are given, vSolved can be computed from eSolved in a forward sequence (so solving eSolved[1] for vSolved[1], eSolved[2] for vSolved[2], and so on). vTear must be selected, so that the equations eResidues are fulfilled. Equations eSolved and eResidue are the (reordered) union of es and eSolvedFixed. Variables vSolvedandvTearare the (reordered) union ofvsandvSolvedFixed`.

This means that an algebraic equation system 0 = g(w) (g are equations es and eSolvedFixed; w are unknowns vs and vSolvedFixed) is solved as much as possible explicitly for the unknowns resulting in

w_e := g_e(w_t)
  0  = g_r(w_t, w_e)

where

  • w (= vs and vSolvedFixed) consists of all elements of w_e, w_t;
  • equations g_e of g are explicitly solved for w_e;
  • equations g_r are the equations of g that cannot be explicitly solved (= residual equations).

Required arguments

  • GorTs: Either a bi-partite graph G::Vector{Vector{Int}} or ts::TearingSetup generated with constructor ts = TearingSetup(G). ts is re-initialized in tearEquations! for any call of the function. TearingSetup is useful to reduce the amount of memory to be allocated, if several equation systems shall be teared from G.

  • isSolvable(e,v): Function that returns true, if equation e can be solved for variable v without influencing the solution space (= rank preserving operation).

  • es::Vector{Int}: Vector of equations that shall be solved with respect to variables vs. es must be equations from G.

  • vs: Either of type Vector{Int} or of type Vector{Vector{Int}}. vs are the unknown variables that shall be solved from es. If vs::Vector{Vector{Int}}, it is first tried to solve es for vs[1], then for vs[2] etc. (so vs defines a priority to solve for variables).

Optional arguments

  • eSolvedFixed::Vector{Int}: Equations of G that are already defined to be solved for vSolvedFixed.
  • vSolvedFixed::Vector{Int]: Variables of G that are explicitly solved from eSolvedFixed.
  • check::Bool: = true, if various checks shall be performed, for example that eSolvedFixed/vSolvedFixed and eSolved/vSolved are a DAG respectively.

Return arguments

  • eSolved::Vector{Int}: Equations that are explicitly solved in the order eSolved[1], eSolved[2], ....
  • vSolved::Vector{Int}: Equation eSolved[i] is explicitly solved for variable vSolved[i].
  • eResdiue::Vector{Int}: Residual equations that are not explicitly solved.
  • vTear::Vector{Int}: Tearing variables, so variables that are assumed to be known, when solving equations eSolved.

Example

using ModiaBase

G = Vector{Int}[ [1,2,4],  # equation 1 depends on variables 1,2,4
                 [1,7],
                 [3,4],
                 [3,7],
                 [6,7],
                 [2] ]
    
es = [3,4,2,1]    # Solve equations 3,4,2,1                 
vs = [3,7,1,4]    # for variables 3,7,1,4 
isSolvable(e,v) = true  # Assume that every equation is solvable for its unknowns 
 
(eSolved,vSolved,eResidue,vTear) = tearEquations!(G, isSolvable, es, vs)

# eSolved  = [3,4,2]
# vSolved  = [3,7,1]
# eResidue = [1]
# vTear    = [4]

Algorithm

The algorithm used in this function is sketched in the paper:

The function uses several extensions of the described basic tearing algorithm that are important for transforming higher index Differential Algebraic Equations to index one form. Note, the traversals in Directed-Acyclic-Graphs - the core operation of the tearing algorithm - is not performed with recursive function calls but with while loops and an explicit stack, in order to avoid function stack overflow for large algebraic loops. Tests up to 1 million equations in 1 million unknowns have been performed.

For improving efficiency, algorithm N of the following paper is used as utility algorithm:

Main developer

Martin Otter, DLR - Institute of System Dynamics and Control

source