3
$\begingroup$

I was working on a problem recently (calculating all flows in a network given input and output flows, basically what Hardy-Cross tries to achieve) which can be formulated as a well-determined system of $N$ equations (with $N$ variables), of which $M$ equations are linear and $K$ are non-linear (so $M + K = N$, and generally $K < M$).

The easiest way to solve this was to just use a nonlinear solver and put in all $N$ equations. However, taking inspiration from the Hardy-Cross method I decided to instead split the problem into a linear part and a non-linear part, then first solve the linear part directly and proceed to solve the $K$-dimensional non-linear part iteratively. More concretely, the steps I took were as follows:

  1. Suppose the linear part is $A x=b$. Find a solution $x_{lin}$ that satisfies $A x_{lin} = b$ using least squares ($A$ is underdetermined so this is possible).
  2. The space of solutions to the linear part can be written as $\{v \mid A (v - x_{lin}) = 0 \}$. This space will be $K$-dimensional. Build the space of solutions by constructing a basis of the nullspace of $A$. Store them as the columns of a matrix $A_{null}$.
  3. Suppose the nonlinear part is given by a function $f: \mathbb{R}^N \to \mathbb{R}^K$ and the objective $f(x) = 0$. To solve this, we'll look for a solution in the $K$-dimensional space we constructed before. We can transform a given 'reduced' solution $z \in \mathbb{R}^K$ into a 'full' solution $x \in \mathbb{R}^N$ by doing $x = A_{null} z + x_{lin}$, and the reverse is $z = A_{null}^* (x - x_{lin})$ where $^*$ indicates the (left) psuedo-inverse. We can therefore transform our function $f$ into a 'reduced' variant $g: \mathbb{R}^K \to \mathbb{R}^K$ where $g(z) = f(A_{null} z + x_{lin})$.
  4. Solve $g(z) = 0$ using any nonlinear solver. The solution $z_{sol}$ can be transformed into a solution for the full system of equations as $x_{sol} = A_{null} z_{sol} + x_{lin}$.

This method seems to be quite a bit faster than just solving the whole system of equations using the same nonlinear solver, and to give the same results (in my situation). Now, I don't think I'm the first one ever to have thought of this, so my question is: is this (similar to) an existing method or principle, and what is it called? It would be nice to base my application of this on something a bit more rigorous. I haven't been able to find anything comparable, but I might simply not have the right context or search terms ;)

New contributor
nardi is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
2
  • 1
    $\begingroup$ This method essentially means using the linear part of the problem to solve for some variables in terms of the others and substitute those in the nonlinear part to reduce its dimensionality. That would be an obvious thing to try if there were only two equations, one linear and one nonlinear. But I haven't seen this described in the literature for multiple equations, and personally I would want to see the details of this and how it works in practice in a published paper because I can think of many applications of it. So I would say write it up and send it to a journal, and let them decide. $\endgroup$ Jun 21 at 2:46
  • $\begingroup$ @MaximUmansky well I'm flattered you think it would be enough for a publication, but to be honest I don't have the time to do a proper write-up with experiments etc. I was hoping this was some established method and I could find out something more about it from people more knowledgeable in the field :) $\endgroup$
    – nardi
    2 days ago

0

Your Answer

nardi is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.