Return to Question

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-Krylov-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$ that can be computed directly (which is good), but 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).

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

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^2w&=1\\ zw&=1\\ z+2y-4&=0\\ \sqrt{8}x+y^2-5&=0 \end{aligned} $$

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

Is there any expectable or even provable advantage regarding convergence in using the system with redundant variables $G$ 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. 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$ that can be computed directly (which is good), but 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).

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-Krylov-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$ that can be computed directly (which is good), but 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).

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^2w&=1\\ zw&=1\\ z+2y-4&=0\\ \sqrt{8}x+y^2-5&=0 \end{aligned} $$

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

Is there any expectable or even provable advantage regarding convergence in using the system with redundant variables $G$ 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. What remains is a set of equations for every binary operator (referencing three variables) or unary operator/elementary function (referencing two variables) instead of having more complicated compound functions $f(x_1,...,x_n)$ that can be computed directly (which is good), but 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 locally coupled) system with many variables (most of which just represent intermediate results of function computations).

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^2w&=1\\ zw&=1\\ z+2y-4&=0\\ \sqrt{8}x+y^2-5&=0 \end{aligned} $$

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

Is there any expectable or even provable advantage regarding convergence in using the system with redundant variables $G$ 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. 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$ that can be computed directly (which is good), but 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).