5
$\begingroup$

Suppose I have $n$ generally nonlinear equations for $n$ variables, like e.g. for $n=2$ the system $F(x,y)=0$

$$ \begin{aligned} x^2+2y-4&=0\\ \sqrt{8}x+y^2-5&=0 \end{aligned} $$

By introducing variables for intermediate results, I can transform this into an (almost, at least, up to some additional singularities, which I don't care about for my question) equivalent set of equations with more variables, like e.g. the set of 4 equations for 4 variables $G(x,y,z,w)=0$

$$ \begin{aligned} x\cdot x-z&=0\\ y\cdot y-w&=0\\ z+2y-4&=0\\ \sqrt{8}x+w-5&=0 \end{aligned} $$

Now I want to solve a system like this numerically, say e.g., with a Newton-Solver like KINSOL.

Is there any expectable or even provable advantage regarding convergence in using the system $G$ with redundant variables ($z$ and $w$) over using the reduced system $F$? Or is it normally rather worse?

If this question can be answered at all, is the answer sensitive to choosing a different solver?

With hand-waving arguments I can equally well come to opposite speculations:

  1. The more variables, the more freedom the algorithm has for finding the roots and doesn't get stuck so easily in difficult regions (like locally bad condition number or high curvature)
  2. The more variables, the higher dimensional the search space, and so the more likely it is that the algorithm can go astray

I can't imagine that this problem has never been dealt with before. But obviously, I don't know the right keywords.

Addendum (20180310): the main idea behind this question is that the above principle can be driven to the limit by introducing auxlliary variables for every intermediate result in a complicated set of equations. What remains is a set of kind of 'atomic' equations for every binary operator (referencing three variables), $b(x_i,x_j)-x_k=0$, or unary operator/elementary function (referencing two variables), $u(x_l)-x_m = 0$, instead of having more complicated compound equations $f(x_1,...,x_n)=0$ the constraint violations of which can be computed directly (which is good), but that are referencing many variables (which is bad).

So a dense nonlinear system is reduced to a sparse nonlinear system, and similarly during solution this results in a sparse linear system. The 'atomic' equations are probably (hopefully) easier for a root-finding algorithm to be dealt with.

Thus the question could be reformulated as: is it better (w.r.t. nonlinear convergence speed) to solve a dense (or very nonlocally coupled) system with less variables, or is it better to solve an equivalent sparse (or only quite locally coupled) system with many variables (most of which just represent intermediate results of function computations).

$\endgroup$
  • $\begingroup$ Is this backed up by some numerical experiences? Did you really try to solve the above systems and the one with added variables worked better? $\endgroup$ – Beni Bogosel Mar 6 '18 at 19:47
  • $\begingroup$ @Beni Bogosel: when you suggest experimentation, do you think that any result, regardless of whether it is in favor or against the hypothesis, could be generalized to an arbitrary system of equations? But after all we are talking about mathematics, aren't we. $\endgroup$ – oliver Mar 6 '18 at 20:12
  • 2
    $\begingroup$ I think you're right that it could make a difference (e.g., if it greatly improves the conditioning of the system), but since there's no good mathematical way of determining the number of iterations in advance, your best bet is to treat this as a purely empirical question and just test the two approaches experimentally. $\endgroup$ – Kirill Mar 10 '18 at 18:52
  • $\begingroup$ @Kirill: I will try that. I thought there was an analytical way of looking at the problem, but as has been already mentioned by HBR, this is gonna be heavily dependent on the solver type. I am still in the middle of learning to apply sundials/kinsol to simple problems, but I think I will be able to test it this week. $\endgroup$ – oliver Mar 10 '18 at 20:29
5
+50
$\begingroup$

In terms of computational effort, it is useless. I mean, you are still having a nonlinear problem with a bigger Jacobian (which is the worst part to be computed quickly).

For next thoughts: dense problems are always worse that sparse ones. Try to solve a sparse system and compare it with the time needed to solve a dense one.

Convergence does depend on the function that is going to be solved and the used scheme for that purspose. For example, the idea you proposed may be useful if fixed point iteration is used, I mean, you need that the Jacobian largest eigenvalue is less than unity for the scheme to be convergent. This can be achieved with smart arrangements of the function to be solved.

$\endgroup$
  • $\begingroup$ Thanks. Of course, it was clear to me that there is no computational advantage with the proposed scheme. Thus my question about faster convergence because this potentially means less function evaluations. So you basically agree, that the transition to sparse could be beneficial? $\endgroup$ – oliver Mar 10 '18 at 16:10
  • $\begingroup$ The convergence is related with the method: Newton method has second order convergence near the solution whatever the function. $\endgroup$ – HBR Mar 10 '18 at 16:12
  • $\begingroup$ So near the solution sparsity doesn't matter for Newton? But could't one hope that far from the solution the "greater freedom" allows Newton to navigate more easily through difficult terrain / narrow valleys and such? Sorry for the vague language, I'm not doing numerics regularly... $\endgroup$ – oliver Mar 10 '18 at 16:15
  • 2
    $\begingroup$ Sparsity only speeds it up. If the function is not smooth I doubt it would be adding more variables, because you still have the same function. $\endgroup$ – HBR Mar 10 '18 at 16:28

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.