Solving Algebraic Loops with Constraint Graphs

February 23, 2022

Share This Article

In my previous blog post I introduced constraint graphs and showed that they are useful for both math analysis and solving. Without the need of untangling equations by hand, ETAS SCODE-CONGRA (CONstraint GRAph) finds a computational path through the model and generates program code directly from the initially undirected formulas.

Apparently, implementing a model is not always as easy as just putting the equations in the right order. When confronted with an algebraic loop, finding a solution will certainly increase the efforts to implement a physical model (and eventually your frustration level).
In the following, you will find the answer to two common questions in equation-based modeling:

What are algebraic loops?
How to solve algebraic loops?

And you’ll recognize that constraint graphs are a great instrument to deal with algebraic loops!

What is an Algebraic Loop?

Contrary to the popular opinion, algebraic loops are not caused by either bad luck or bad modeling. While they are a general subject across every engineering domain, consider the following example to understand the fundamental structural problem behind algebraic loops and why algebraic loops are inevitable.

Voltage Divider

The electric circuit in Figure 1 contains two linear resistors in a series connection. When you apply $u_0=12V$ at the input, what is the voltage drop $u_2$ at the second resistor?

Figure 1 Circuit sketch of a basic voltage divider: Two resistors in a series connection. Equations 1 and 2 we know from Ohm’s Law and Equation 3 we obtain by applying Kirchhoff’s Second Law.

Let’s try to find the solution and determine a computational sequence from input $u_0$ to output $u_2$ :

From $u_0$ , with equation 3, we could compute $u_2$ , but we need $u_1$
Via equation 1, voltage $u_1$ requires to know the current $i$
Current $i$ depends on $u_2$ in equation 2

Isn’t that a strange circular situation? To compute $u_2$ we must know $u_2$ ? Unfortunately, the same applies for $u_1$ and $i$ : None of these variables can be computed directly from the applied voltage $u_0$ because they somehow depend on themselves.
The constraint graph of the electric network model in Figure 2 illustrates that relationship: With $u_0$ as input, the yellow part of the graph has no arrows because it’s not clear which of the variables should be solved first.

Figure 2 Constraint Graph Model of the voltage divider. Left: Undirected System (except the fixed resistance values). Right: Computational Flow with input $u_0$ – Algebraic Loop is colored yellow.

What may be described best as a chicken-and-egg problem is already the most basic definition of an algebraic loop:

Algebraic loop: At least two equations must be solved simultaneously

But how?

Untangle the Math: Substitution

As long as only few variables are involved, we know how to deal with mathematical problems of the above kind: Substituting equation 2 into equation 1 and plugging into equation 3 leads to

$u_0 = R_1 i + u_2 = \frac{R_1}{R_2} u_2 + u_2 = (\frac{R_1}{R_2} + 1)u_2 = \frac{R_1 + R_2}{R_2} u_2$

With that we can solve for $u_2 = ... = 9V$ (and $u_1 = 3V)$ .
The resistors share the applied voltage according to the ratio of their resistance (3:1). The result should not be a surprise: Two resistors in a series connection are called a voltage divider [1].

What’s Wrong with Algebraic Loops?

Nothing! The model equations are right, and the choice of input variable $u_0$ is legit. An algebraic loop is nothing but a particular computational request to a model that has a certain structure. We’re facing similar loop structures often when dealing with model implementation: Ultimately, our programs can only compute variables from a sequence of assignments while in the physical model all equations happen at the same time.

Instead of reformulating the math we should accept this natural parallelism in our models and treat algebraic loops accordingly.

How to Solve Algebraic Loops?

Breaking the algebraic loop apart was easy with the voltage divider. Sometimes a change of variables can solve implementation, but this workaround is not very constructive. And – as you’ll find out in this section – it is even impossible sometimes.

Solving algebraic loops requires making a distinction between those loops than can be solved easily and those that can’t. Let’s consider the easy ones first:

Symbolic Solutions

With larger models, containing more variables and maybe more complicated equations, solving for unknown variables and applying the right substitutions quickly becomes inconvenient and nontrivial.

To save valuable time, ETAS SCODE-CONGRA uses computer algebra systems [2] to solve algebraic loops automatically. If there is an analytic solution, SCODE-CONGRA will probably find it and put the right expressions in the generated code. When the solution is ambiguous – nonlinear systems of equations can have multiple solutions – it prompts the user to choose one.
Again: No manual equation handling is necessary.

At this point SCODE-CONGRA is an intuitive interface to symbolic solvers: Visualize math problems and let them be solved automatically. But there is more!

Numerical Solutions

Until now, nothing was really hard about algebraic loops because we were able to solve them. But that’s only half of the truth. Some equations don’t have symbolic solutions – and unfortunately this is true for most engineering problems.
Here’s an example: What’s the solution of $e^x = -x$ ?*

When you must deal with transcendental equations [3] – formulas which contain exponential and trigonometric expressions or interpolation look-up tables – searching for symbolic solutions becomes hopeless. The only way out here is to be content with numerical approximations of the solutions.

Let’s see how we can do this with an example.

*The solution is approximately $-0.5671$

Nonlinear Voltage Divider

Consider again the voltage divider from above: You may find that the linear model for the second resistor reflects your real system behavior only poorly. That’s fair because we all know that only the boring effects are linear. See in Figure 3 that the second resistor is replaced by a nonlinear element. The corresponding voltage-current curve (red) is implemented by an interpolation routine between data samples.
Finding a closed-form solution for $u_2$ in this setup suddenly becomes non-trivial.

Figure 3 Voltage divider with a nonlinear component. On the right both Voltage-Current characteristics.

Breaking the Algebraic Loop: Tearing

Tearing is an established method to solve large (and non-analytic) algebraic loops numerically, see [4] for detailed technical background information. The basic idea is to formulate a residual at a (target) variable – in general any variable within the algebraic loop can be a target – and find the other variables such that the residual vanishes.

We can illustrate the tearing mechanism in a constraint graph intuitively. In Figure 4, on the right, we applied a tearing edge from $u_2$ to $i$ . Follow the arrows: Tearing means to compute both ways around the algebraic loop from source to target. Only when the residual is close to zero, we can conclude that we have found a valid solution $u_2^*$ .

Tearing: Compute both ways in the algebraic loop

Figure 4: Having exchanged the second resistor with a look-up table, the structure does not change and the algebraic loop remains. Note that the characteristic curve has a predetermined direction already in the system definition. As the flow has no analytic solution it must be solved with numerical tearing.

The main advantage about tearing algebraic loops apart with SCODE-CONGRA is, once again, the minimal application effort. Draw a tearing edge from source to target and the code generator does the implementation.
Compare with the quick-and-dirty hacks in our application software to find approximated solutions numerically: Just a few clicks in the constraint graph model and solution finding methods can be applied and monitored easily.

As tearing was originally used in offline simulation environments with (rather) unlimited computational resources, SCODE-CONGRA today enables solving complicated math problems on conventional embedded controllers.
The available advanced solving methods are numerically robust and guaranteed to converge quickly. And they have been proven successful for real-time applications in series production.

There is a lot more to say about the technical details of the tearing mechanism and it’s configuration flexibility in SCODE-CONGRA, but that is clearly beyond the scope of this article. I’ll cover that in the next blog of this series!

Summary

ETAS SCODE-CONGRA is an acausal modeling tool that enables dealing with math problems in a unique, graphical way. As constraint graphs reveal structural properties of equation-based models, in this article we examined a special structure: Algebraic loops.

Algebraic loops can’t be avoided, because they’re deeply rooted in our physical models. But we must not be afraid of them because the right strategy to solve algebraic loops is only a few clicks away:

Solve symbolically, if possible – solve numerically, if necessary

We think only undetected algebraic loops cause trouble – and by using constraint graph analysis you will not be able to overlook them.

If you want to know more about numerical tearing, or if you are keen to know why we discourage to deconstruct algebraic loops with time delays (it’s a hidden fixed point iteration!) please contact me directly at Henner.Schmidt@etas.com.