Loading [MathJax]/extensions/TeX/boldsymbol.js

Modular Equations

AVICPS Workshop, Vancouver 2013-12-3

Outline


  • Motivation: 3 Missing Features in Modelica

  • The Common Cause: Index Reduction

  • The Solution: Automatic Differentiation

1Modular equations - christoph.hoeger@tu-berlin.de

Feature I: Separate Compilation


Compile models (i.e. especially equations) once and simulate them afterwards without having to resort to runtime symbolic algebra or numeric differentiation.

Build a semantic analysis upon this foundation. Distinguish between compile-time, link-time and run-time checks.

2Modular equations - christoph.hoeger@tu-berlin.de

Feature II: Structural Dynamics


Allow many different modes during simulation.

Allow a model to compute the next mode.

3Modular equations - christoph.hoeger@tu-berlin.de

Feature III: Implementation Agnostic Integration


model Pendulum Real x(start=0.1),y(start=0.9, fixed=true),vx,vy,F; equation x^2 + y^2 = 1; vx = der(x); vy = der(y); der(vx) = F*x; der(vy) = F*y - 9.81; end Pendulum;

model Pendulum function f input Real x; input Real y; output Real r; algorithm r := x^2 + y^2 - 1; end f; Real x(start=0.1),y(start=0.9, fixed=true),vx,vy,F; equation f(x,y) = 0; vx = der(x); vy = der(y); der(vx) = F*x; der(vy) = F*y - 9.81; end Pendulum;

model Pendulum function f input Real x; input Real y; output Real r; algorithm if (x <> 0) then r := x^2 + y^2 - 1; else if (y <> 0) then r := y^2 - 1; else r := -1; end if; end if; end f; Real x(start=0.1),y(start=0.9, fixed=true),vx,vy,F; equation f(x,y) = 0; vx = der(x); vy = der(y); der(vx) = F*x; der(vy) = F*y - 9.81; end Pendulum;

4Modular equations - christoph.hoeger@tu-berlin.de

The Reason: Index Reduction

Index Reduction: Basics


Consider the ideal representation of the cartesian Pendulum:

Sorting equations:

(Maximizing the dots on the left-hand side)

Problem: x occurs two times derived, but is computed directly.

5Modular equations - christoph.hoeger@tu-berlin.de

Pryce' Method


The dual Problem (in LP sense) to the assignment problem introduces slack variables \bar{c}, \bar{d} and a consistency condition:

where \sigma_{ij} is the highest derivative of variable j in equation i

The interpretation of c_i is the "index" of equation i, i.e. the number of times it needs to be derived, d_j is the (maximal) degree of derivation of variable j in the model.

The dual goal is to minimize:

6Modular equations - christoph.hoeger@tu-berlin.de

Applied to Pendulum:


Incidence matrix:

Solution:

7Modular equations - christoph.hoeger@tu-berlin.de

Apply the Result


Sorting derived equations:

Note, that \ddot{y}, \ddot{x}, F form a connected component

8Modular equations - christoph.hoeger@tu-berlin.de

n-times Differentiable Terms

Syntax


We start with a small term language t

\tau \in t, \phi is one of a set of primitive functions, \unk{n}{d} are unknowns, n, d \in \mathbb{N}

(obviously not turing-complete)

9Modular equations - christoph.hoeger@tu-berlin.de

Semantics


Let \mathbb{D} \subseteq \mathbb{R} be an open interval, \bar{x} = (x_1 \ldots x_p) \in \xdomain be a vector containing n-times differentiable real valued functions on that interval.

Strict evaluation relation: \env \tau \reduce\ r indicates that \tau evaluates to r under \envonly, where v \in\mathbb{D} is the independent variable.

10Modular equations - christoph.hoeger@tu-berlin.de

Computing Functions:


Let f : \xdomain \times \mathbb{D} \rightarrow \mathbb{R} an n-times differentiable function, then:

(\tau computes f)

11Modular equations - christoph.hoeger@tu-berlin.de

Automatic Differentiation


To include AD, we parameterize t over the order of total differentiation n and number of parameters p:

There is a simple relation \lceil r \rceil^{(n,p)} which lifts t-terms into \tnp-terms.

12Modular equations - christoph.hoeger@tu-berlin.de

Notation


General Idea: Generalize Automatic Differentiation (e.g. Dual Numbers) to Derivative Matrices

Where:

13Modular equations - christoph.hoeger@tu-berlin.de

Integration/Differentiation


\begin{align*} \Delta \begin{vmatrix} r_{0,0} & \cdots & r_{0,p} \\ \vdots & \ddots & \vdots \\ r_{n,0} & \cdots & r_{n,p} \\ \end{vmatrix} &= \begin{vmatrix} r_{1,0} & \cdots & r_{1,p} \\ \vdots & \ddots & \vdots \\ r_{n,0} & \cdots & r_{n,p} \\ \end{vmatrix} \end{align*}

14Modular equations - christoph.hoeger@tu-berlin.de

Correct Evaluation


Again, a strict big step semantics \redad{n}

AD-Evaluation of a term yields correct total and partial derivatives.

15Modular equations - christoph.hoeger@tu-berlin.de

Addition

Addition is simply matrix-addition

16Modular equations - christoph.hoeger@tu-berlin.de

Multiplication

Multiplication is defined recursively

17Modular equations - christoph.hoeger@tu-berlin.de

Multiplication II

18Modular equations - christoph.hoeger@tu-berlin.de

In the Paper:

Composition similar to Multiplication, using the chain-rule

Correctness-proof by structural induction over t

19Modular equations - christoph.hoeger@tu-berlin.de

Summary

AD allows for precise, arbitrary order derivation of precompiled terms

This means, we can compile any equation into t^{(n,p)} and decide during runtime, what n and p is required.

Questions?

20Modular equations - christoph.hoeger@tu-berlin.de