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