Equation Sorting

function matching(G, M, vActive=fill(true, M))

Find maximum matching in bipartite graph

• G: bipartite graph
• M: number of V-nodes
• vActive: set to false has the same effect as deleting V-node and corresponding edges
• return assign: assign[j] contains the E-node to which V-node j is assigned or 0 if V-node j not assigned

Reference: Pantelides, C.: The consistent initialization of differential-algebraic systems. SIAM Journal of Scientific and Statistical Computing, 9(2), pp. 213–231 (1988).

function BLT(G, assign)

Find Block Lower Triangular structure for a bipartite graph G with assignment assign

• G: bipartite graph
• assign: assign[j] contains the E-node to which V-node j is assigned or 0 if V-node j not assigned
• return components: cell array of components. Each component is a list of indices to E-nodes

function invertDer(A)

Invert derivative relationships for variables and equations

• A: A[j] = if V[k] = der(V[j]) then k else 0 (or correspondingly for E-nodes)
• return orgIndex: index of original variable or equation
• return derOrder: derivative order

Note that invertDer can be used to invert from list of E-nodes to list of V-nodes as well.

Example: julia> BLTandPantelidesUtilities.invertDer([5,6,7,8,10,11,0,0,0,0,0]) ([1,2,3,4,1,2,3,4,9,1,2],[0,0,0,0,1,1,1,1,0,2,2])

invertAssign(assign, n=length(assign))

Invert assignment relationships for variables and equations.

• assign: assign[j] contains the E-node to which V-node j is assigned or 0 if V-node j not assigned
• n: number of E-nodes
• return invAssign: invAssign[i] contains the V-node to which E-node i is assigned or 0 if E-node i not assigned
• return unAssigned: unassigned V-nodes

Note that invertAssign can be used to invert from list of E-nodes to list of V-nodes as well.

Example: julia> inv=BLTandPantelidesUtilities.invertAssign([0,0,0,0,1,2,7,4,3,9,8]) ([5,6,9,8,0,0,7,11,10,0,0],[1,2,3,4])

julia> BLTandPantelides.invertAssign(inv[1]) ([0,0,0,0,1,2,7,4,3,9,8],[5,6,10,11])

function buildExtendedSystem(A)

Extend a system according to Pantelides equation (15), i.e. return the incidence for function h(x, der(x)).

• A: A[j] = if V[k] = der(V[j]) then k else 0
• return G: bipartite graph

Example: julia> BLTandPantelidesUtilities.buildExtendedSystem([5,6,7,8,0,0,0,0,0]) 4-element Array{Any,1}: [1,5] [2,6] [3,7] [4,8]

buildFullIncidence(n,m)

Build a bipartite graph with full incidence, i.e. all of the n E-nodes refer to all of the m V-nodes.

• n: number of E-nodes
• m: number of V-nodes
• return G: bipartite graph

Example: julia> BLTandPantelidesUtilities.buildFullIncidence(2,3) 2-element Array{Any,1}: [1,2,3] [1,2,3]

function createNames(infixes, A)

Creates names.

• infixes: infix strings for original variable
• A: A[j] = if V[k] = der(V[j]) then k else 0

Example: julia> BLTandPantelidesUtilities.createNames(["x", "y", "w", "z", "", "", "", "", "T"], [5,6,7,8,10,11,0,0,0,0,0]) x, y, w, z, der(x), der(y), der(w), der(z), T, der2(x), der2(y)

function printList(infixes, indices, A, vertical=false)

Print list of variables or equations.

• infixes: infix strings for original variable or equation
• indices: indices for the variables or equations to be printed
• A: A[j] = if V[k] = der(V[j]) then k else 0 (or correspondingly for E-nodes)
• vertical: if vertical then new line separation else comma separation

Example: julia> BLTandPantelidesUtilities.printList(["x", "y", "w", "z", "", "", "", "", "T"], 1:11, [5,6,7,8,10,11,0,0,0,0,0]) x, y, w, z, der(x), der(y), der(w), der(z), T, der2(x), der2(y)

printAssignedEquations(equations, variables, indices, assign, A, B)

Print assigned equations.

• equations: infix string for original equations
• variables: infix string for original variables
• indices: indices for the equations to be printed
• assign: assign[j] contains the E-node to which V-node j is assigned or 0 if V-node j not assigned
• A: A[j] = if V[k] = der(V[j]) then k else 0
• B: B[i] = if E[l] = der(E[l]) then l else 0

Example: See testBLTandPantelides.testPendulum

printSortedEquations(equations, variables, components, assign, A, B)

Print sorted equations.

• equations: infix string for original equations
• variables: infix string for original variables
• components: cell array of components. Each component is a list of indices to E-nodes
• assign: assign[j] contains the E-node to which V-node j is assigned or 0 if V-node j not assigned
• A: A[j] = if V[k] = der(V[j]) then k else 0
• B: B[i] = if E[l] = der(E[l]) then l else 0

Example: See testBLTandPantelides.testPendulum

printUnassigned(equations, variables, components, assign, A, B)

Print unassigned variables and equations.

• equations: infix string for original equations
• variables: infix string for original variables
• assign: assign[j] contains the E-node to which V-node j is assigned or 0 if V-node j not assigned
• A: A[j] = if V[k] = der(V[j]) then k else 0
• B: B[i] = if E[l] = der(E[l]) then l else 0

Example: See testBLTandPantelides.testPendulum