MathJax TeX Test Page      We solve numerically a DAE of the general form \[ f_i (t, \text{$x_j$ and the derivatives of them}) = 0\qquad i=1:n, \] where $x_j$, $j=1:n$, are state variables that are functions of the independent variable $t$, usually regarded as time.

     We call our structural analysis the $\Sigma$-method, because we constructs for a DAE an $n\times n$ SIGnature MAtrix $\Sigma=(\sigma_{ij})$ defined as \[ \sigma_{ij}= \begin{cases} \text{the highest-order derivative to which $x_j$ occurs in $f_i$, or}\\[1ex] -\infty\qquad\text{if $x_j$ and its derivatives do not occur in $f_i$.} \end{cases} \]      A highest-value transversal (HVT) $T$ is a set of $n$ positions $(i,j)$ with one entry in each row and each column, such that $\sum_{(i,j)\in T} \sigma_{ij}$ is the largest possible. We call this sum the value of $\Sigma$, written $\text{Val}(\Sigma)$.

     When the DAE is structurally well posed---that is, there is a one-to-one correspondence between equations and variables---$\text{Val}(\Sigma)$ is finite. We associate $c_i$ with each equation $f_i$ , and associate $d_j$ with each variable $x_j$. These integers $c_1,\ldots,c_n;d_1,\ldots,d_n$ are equation and variable offsets, respectively, which satisfy \begin{align} c_i\ge 0\qquad\text{for all $i=1:n$;} \qquad d_j-c_i \ge \sigma_{ij} \qquad\text{for all $i,j=1:n$, with equality on $T$.} \end{align}      Usually we write $\mathbf{c}=(c_1,\ldots,c_n)$ and $\mathbf{d}=(d_1,\ldots,d_n)$. Offsets are never unique, but there exists a smallest componentwise solution to the above inequalities; $\mathbf{c},\mathbf{d}$ of this solution are termed the canonical offsets, which are the most often used in the theory.

Example
A simple pendulum in Cartesian coordinate system is \begin{align*} 0 = f_1 &= x'' + x\lambda\\[1ex] 0 = f_2 &= y'' + y\lambda - G \\[1ex] 0 = f_3 &= x^2 + y^2 - L^2 \end{align*} Here $x, y, \lambda$ are state variables; $G$ is gravity, and $L>0$ is the length of the pendulum.
     The signature matrix of this DAE is \[\begin{array}{r} \\f_1 \\ \Sigma=\,\, f_2 \\ f_3 \\ \end{array} \begin{aligned} \begin{array}{ccc} \,\,\,\,x\,\,\, & \,\,\,\,y\,\,\,\, & \,\,\,\,\lambda\,\,\,\, \end{array} \\ \left( \begin{array}{ccc} {\color{green}2} & -\infty & {\color{blue}0} \\ -\infty & {\color{blue}2} & {\color{green}0} \\ {\color{blue}0} & {\color{green}0} & -\infty \end{array} \right) \end{aligned} \] There are two HVTs in $\Sigma$: one in $\color{green}{green}$, the other in $\color{blue}{blue}$. The value of $\Sigma$ is $\text{Val}(\Sigma)=2$. The canonical offsets are $\mathbf{c}=(0,0,2)$ and $\mathbf{d}=(2,2,0)$.


     Critical to the numerical solution method is a System Jacobian associated with some $\mathbf{c},\mathbf{d}$ and defined as \[ \mathbf{J} = \frac{\partial f_i^{(c_i)}}{\partial x_j^{(d_j)}}= \left\{ \begin{array}{ll} \partial f_i\big/\partial x_j^{\left(\sigma_{ij}\right)} &\quad\text{if $d_j-c_i=\sigma_{ij}$}\\[1ex] 0 &\quad\text{otherwise.} \end{array} \right. \] These offsets $\mathbf{c},\mathbf{d}$ prescribes a solution scheme that indicates how to compute the derivatives of the solution using a Taylor series method. They are computed in a stagewise manner; a stage counter $k$ counts up from $k_d=-\max_j d_j$: \[k = k_d, k_d+1, \ldots, 0, 1, \ldots.\] At each stage we solve a subsystem of equations \[0 = f_i^{(k+c_i)} \qquad\text{for all $i$}\quad \text{s.t. $k+c_i\ge 0$}\] for \[x_j^{(k+d_j)} \qquad\text{for all $j$}\quad \text{s.t. $k+d_j\ge 0$}\] using \[x_j^{(r)} \qquad\text{for all $(j,r)$}\quad \text{s.t. $0\le r\lt k+d_j$.} \]
     The Jacobian of a subsystem in stages $k\ge 0$ is exactly the System Jacobian $\mathbf{J}$ of the DAE. If $\mathbf{J}$ is nonsingular and the derivatives $x_j^{(r)}$, for all $0\le r\le d_j$ and $j=1:n$, are uniquely determined in stages $k=k_d:0$, we say the $\Sigma$-method succeeds. Otherwise, if the solution scheme cannot be carried out up to stage $k=0$, then we say this SA fails.
     In the success case, we use the canonical offsets $\mathbf{c},\mathbf{d}$ to determine the structural index and DOF \[ \nu_S= \left\{ \begin{array}{ll} \max_i c_i+1 &\quad\text{if some $d_j=0$}\\[1ex] \max_i c_i &\quad\text{otherwise,} \end{array} \right. \qquad \text{DOF} = \text{Val}(\Sigma) = \sum_j d_j - \sum_i c_i. \]
Example: For the simple pendulum DAE above, the structural index and DOF of the pendulum are \[ \nu_S=\max_i c_i+1=c_3+1=3 \quad\text{(since $d_3=0$)} \qquad\text{DOF}=\text{Val}(\Sigma)=2. \]      Success of the $\Sigma$-method occurs on provably many DAEs of practical interest. However, the method can fail on simple solvable DAEs; we explain this caveat and show how to resolve these failures in [7][8].

References:
  • [1] Pryce, J.D.: A simple structural analysis method for DAEs. BIT Numerical Mathematics 41(2), 364–394 (2001)

  • [2] Nedialkov, N.S., Pryce, J.D.: Solving differential-algebraic equations by Taylor series (I): Computing Taylor coefficients. BIT Numerical Mathematics 45, 561–591 (2005)

  • [3] Nedialkov, N.S., Pryce, J.D.: Solving differential-algebraic equations by Taylor series (II): Computing the system Jacobian. BIT Numerical Mathematics 47(1), 121–135 (2007)

  • [4] Nedialkov, N.S., Pryce, J.D.: Solving differential algebraic equations by Taylor series (III): the DAETS code. JNAIAM J. Numer. Anal. Indust. Appl. Math 3, 61–80 (2008)

  • [5] Pryce, J.D., Nedialkov, N.S., Tan, G.: DAESA: A Matlab tool for structural analysis of differential-algebraic equations: Theory. ACM Trans. Math. Softw. 41(2), 9:1–9:20 (2015). DOI 10.1145/2689664. URL http://doi.acm.org/10.1145/2689664

  • [6] Nedialkov, N.S., Pryce, J.D., Tan, G.: Algorithm 948: DAESA: A Matlab tool for structural analysis of differential-algebraic equations: Software. ACM Trans. Math. Softw. 41(2), 12:1–12:14 (2015). DOI 10.1145/2700586. URL http://doi.acm.org/10.1145/2700586

  • [7] G. Tan, N. S. Nedialkov, and J. D. Pryce, Symbolic-numeric methods for improving structural analysis of differential-algebraic equation systems. Tech. report CAS-15-07-NN. Deparment of Computing and Software, McMaster University, Hamilton, ON, Canada. 84 pages, URL http://www.cas.mcmaster.ca/cas/0reports/CAS-15-07-NN.pdf

  • [8] G. Tan, N. S. Nedialkov, and J. D. Pryce, Symbolic-numeric methods for improving structural analysis of differential-algebraic equation systems. Tech. report CAS-15-08-NN. URL http://www.cas.mcmaster.ca/cas/0reports/CAS-15-08-NN.pdf Submitted to AMMCS 2015 proceedings.
  • Theory review of the Sigma method

    © Gary Guangning Tan, 2015