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.

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;

Consider the ideal representation of the cartesian Pendulum: $$\begin{align} x^2 + y^2 &=& 1\\ \ddot{x} &=& F x \\ \ddot{y} &=& F y - 9.81 \end{align}$$

The dual Problem (in LP sense) to the assignment problem introduces slack variables \(\bar{c}, \bar{d}\) and a consistency condition: $$d_j - c_i \geq \sigma_{ij}$$

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: $$\sum d_j - \sum c_i$$

Incidence matrix: $$\sigma = \begin{vmatrix} {\color{grey} x} & {\color{grey} y} & {\color{grey} F} & \\ 0 & 0 & - \infty & {\color{grey} x^2 + y2 - 1} \\ 2 & -\infty & 0 & {\color{grey} \ddot{x} - Fx} \\ -\infty & 2 & 0 & \color{grey} \ddot{y} - Fy + 9.81\\ \end{vmatrix}$$

Solution: $$\begin{align*} \bar{c} &=& (2,0,0)\\ \bar{d} &=& (2,2,0)\\ \end{align*}$$

Sorting derived equations: $$\begin{align} x &\mapsto& x^2 + y^2 &=& 1\\ \dot{x} &\mapsto& x\dot{x} + y\dot{y} &=& 0\\ \ddot{x} &\mapsto& {\dot{x}}^2 + x \ddot{x} + {\dot{y}}^2 + y \ddot{y} &=& 0\\ F &\mapsto& \ddot{x} &=& F x \\ \ddot{y} &\mapsto& \ddot{y} &=& F y - 9.81 \end{align}$$

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

We start with a small term language \(t\) $$\begin{aligned} \tau ::= & \unk{n}{d} & | & \tau \oplus \tau \\ | & \tau \otimes \tau & | & \phi ~ \tau \\ | & \mathbb{R} \end{aligned}$$

\(\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)

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.

$$\frac{}{\env \mathtt{u}_{n,k} \reduce \der{k}{x_n}(v)}{n \leq p}$$

$$\frac{\env \tau_1 \reduce r_1 ~~ \env \tau_2 \reduce r_2}{\env \tau_1 \oplus \tau_2 \reduce (r_1 + r_2)}$$

Let \(f : \xdomain \times \mathbb{D} \rightarrow \mathbb{R} \) an \(n\)-times differentiable function, then: $$\env \tau \leadsto f \Leftrightarrow \env \tau \reduce f(\bar{x}, v)$$

(\(\tau\) computes \(f\))

To include AD, we parameterize \(t\) over the order of total differentiation \(n\) and number of parameters \(p\): $$\begin{aligned} \tau^{(n,p)} ::= & \unk{m}{k} & | & \tau^{(n,p)} \oplus \tau^{(n,p)} \\ | & \tau^{(n,p)} \otimes \tau^{(n,p)} & | & \phi ~ \tau^{(n,p)} \\ | & \mathbb{R}^{n+1 , p+1} \\ \end{aligned}$$

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

General Idea: Generalize Automatic Differentiation (e.g. Dual Numbers) to Derivative Matrices $$\Dermatrix{n}{p}{f} = \begin{vmatrix} \partial_{j} \der{i} f(\bar{x}, v) \end{vmatrix} \in \mathbb{R}^{n+1,p+1}$$

Where: $$\begin{align*} \partial_0 f &=& f \\ \partial_j f &=& \frac{\partial f}{\partial x_j}, ~~ i \in 1 \ldots p\\ \der{i} f &=& \frac{\mathtt{d}^i f}{\mathtt{d}v^i} \\ \end{align*}$$

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

\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*}

Again, a strict big step semantics \(\redad{n}\) $$\frac{}{\env \unk{m}{k} \redad{n} \Dermatrix{n}{p}{\der{k} x_m}}$$

AD-Evaluation of a term yields correct total and partial derivatives. $$\env \tau \leadsto f \Rightarrow \env \lift{n}{p}{\tau} \redad{n} \Dermatrixshort{n}{p}{f}$$

Addition is simply matrix-addition $$\frac{\begin{align*}\env \tau_1 \redad{n} A \\ \env \tau_2 \redad{n} B\end{align*}}{\env \tau_1 \oplus \tau_2 \redad{n} A + B}$$

Multiplication is defined recursively $$\frac{\begin{align*}\env \tau_1 \redad{0} \bar{a} \\ \env \tau_2 \redad{0} \bar{b} \end{align*}} {\env \tau_1 \otimes \tau_2 \redad{0} \bar{a} \Multop \bar{b}}$$

$$\begin{align*} (\bar{a} \Multop \bar{b})_0 &= a_0 \times b_0 & \\ (\bar{a} \Multop \bar{b})_i &= a_i \times b_0 + b_i \times a_0 & i \in 1 \ldots p \end{align*}$$

$$\frac{\begin{align*} \env &\tau_1 \redad{n+1} A \\ \env &\tau_2 \redad{n+1} B \\ \env \Delta(A)& \otimes I(B) \redad{n} C \\ \env \Delta(B)& \otimes I(A) \redad{n} D\end{align*}} {\env \tau_1 \otimes \tau_2 \redad{n+1} \begin{vmatrix} A_0 \Multop B_0 \\ C + D \end{vmatrix}}$$

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?