10/8/2019

Ali M. Sahlodin
Department of Chemical Engineering
AmirKabir University of Technology
1397 S.H

 Sparsityand DAEs
 Index reduction and constraint stabilization

Copyright © Ali M. Sahlodin, Dept. of Chemical Engineering, AmirKabir Univ. of Tech. 2

1
 10/8/2019

 Differentiation destroys desirable DAE properties

(sparsity, physical relations, etc)
 How to minimize disruption of the original DAEs?
 Differentiate only a subset of the DAEs
 How to find the right subset(s)?
 Pantelides’ algorithm (1988)
 Uses DAE structure to determine the minimal subset of
equations that must be differentiated.

Copyright © Ali M. Sahlodin, Dept. of Chemical Engineering, AmirKabir Univ. of Tech. 3

Each connection represents an applicant’s interest in a particular job.

1 a

2 b

3 c

4 d

Applicant Job

Copyright © Ali M. Sahlodin, Dept. of Chemical Engineering, AmirKabir Univ. of Tech. 4

2
 10/8/2019

Job d is unassigned; Applicant 4 has no job!

1 a

2 b

3 c

4 d

Applicant Job

Copyright © Ali M. Sahlodin, Dept. of Chemical Engineering, AmirKabir Univ. of Tech. 5

Set of the edges where no two edges share an endpoint.

1 a

2 b

3 c

4 d

Applicant Job

Copyright © Ali M. Sahlodin, Dept. of Chemical Engineering, AmirKabir Univ. of Tech. 6

3
 10/8/2019

Matching is not possible here.

1 a

2 b

3 c

4 d

Applicant Job

Copyright © Ali M. Sahlodin, Dept. of Chemical Engineering, AmirKabir Univ. of Tech. 7

 Can we match equations with variables?

 Matrix is structurally full rank if all rows and
columns can be matched.
 Rows: functions
 Columns: variables

  
   
 
 
 
   

Copyright © Ali M. Sahlodin, Dept. of Chemical Engineering, AmirKabir Univ. of Tech. 8

4
 10/8/2019

 A DAE f ( x, x, y, t )  0 is at most index-1 if it can be

solved for the highest differentiated variables
 Sufficient condition
 We are interested in matching (pairing) of
equations with highest differentiated variables.

Copyright © Ali M. Sahlodin, Dept. of Chemical Engineering, AmirKabir Univ. of Tech. 9

 Given the DAE

f ( x, x, y, t )  0, f : R n  R n  R m  R  R 2 nm

 And a subset with k equations

f ( x , z , t )  0, x  R q , z  Rl

z  ( x, y ) Vector of highest differentiated variables

 Differentiate w.r.t. time

f x x  f z z  ft  0

Copyright © Ali M. Sahlodin, Dept. of Chemical Engineering, AmirKabir Univ. of Tech. 10

5
 10/8/2019

1. Differentiate subsets where k>l

 l is the number of highest differentiated variables in the subset.
 With k>l, the subset is structurally singular w.r.t. the highest
differentiated variables
2. Update the vector of differentiated variables
3. Repeat until no subset with k>l can be found
1. The resulting DAE is at most index 1.

Copyright © Ali M. Sahlodin, Dept. of Chemical Engineering, AmirKabir Univ. of Tech. 11

f1 : x  f ( x, y ) xdot ydot z
f1 X The last row is structurally
f 2 : y  g ( x, y, z ) singular
f2 X X
f 3 : 0  h( x )
f3 k=1>l=0

f1 : x  f ( x, y ) xdot ydot z The first and last rows are

structurally singular
f 2 : y  g ( x, y, z ) f1 X
dh k=2>l=1
f2 X X
f3 : 0  ( x)
dt f3 X

Copyright © Ali M. Sahlodin, Dept. of Chemical Engineering, AmirKabir Univ. of Tech. 12

6
 10/8/2019

df
x
f1 :  ( x, y )
dt xdotdot ydot z
f 2 : y  g ( x, y, z ) f1 X X
 d 2h f2 X X
f3 : 0  2
( x)
dt f3 X

No more singular subsets. This DAE is at most index 1.

Copyright © Ali M. Sahlodin, Dept. of Chemical Engineering, AmirKabir Univ. of Tech. 13

 let’s try this example: f1 : x1  x1  2 y1  3 y2

f 2  x1  y1  y2  1
f3  2 x1  y1  y2
 Candidate subset for differentiation
f 2  x1  y1  y2  1
f  ( f1, f 2 )
f3  2 x1  y1  y2
Highest differentiated variables in this subset: z=(y1,y2)

f 1 1

z 1 1
K=l=2

Algorithm stops and fails to detect the numerical singularity

Copyright © Ali M. Sahlodin, Dept. of Chemical Engineering, AmirKabir Univ. of Tech. 14

7
 10/8/2019

 Purely structural
 No need for arithmetic operations (efficient)
 No concern of rounding errors
 But unable to detect numerical singularity

How can this happen?

Remember the condition was sufficient, not necessary

Copyright © Ali M. Sahlodin, Dept. of Chemical Engineering, AmirKabir Univ. of Tech. 15

 Use Pantelides’ structural analysis to

 decide which equations to differentiate and how
many times
 Differentiate the equations
 keep the original eqs. too. (preserving algebraic
constraints).
 over-determined system!
 Replace some of the derivatives with
algebraic variables
 index-1 determined system

Copyright © Ali M. Sahlodin, Dept. of Chemical Engineering, AmirKabir Univ. of Tech. 16

8
 10/8/2019

Example x1  x2  a(t )

x1  x22  b(t )

Differentiate eq. 2, but keep it in the model:

x1  x2  a (t )
Over-determined (3
x  2 x x  b(t )
1 2 2 eqs, 2 unknowns
x1  x22  b(t )

Replace x1 with x1' Determined system

Copyright © Ali M. Sahlodin, Dept. of Chemical Engineering, AmirKabir Univ. of Tech. 17

 See your class notes for the solution

x  y
y  z
x  f (t )

Copyright © Ali M. Sahlodin, Dept. of Chemical Engineering, AmirKabir Univ. of Tech. 18