# Can redundant variables be beneficial for root-finding convergence

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).

• 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? – Beni Bogosel Mar 6 '18 at 19:47
• @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. – oliver Mar 6 '18 at 20:12
• 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. – Kirill Mar 10 '18 at 18:52
• @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. – oliver Mar 10 '18 at 20:29