Welcome to MathOverflow

Question

2

1

I have a system of nonlinear algebraic equations which I'm wanting to solve numerically (for example with a Newton iteration based technique). I can formulate this either as the single system of size N:

f( x ) = 0

or as the nested systems of size P, Q:

g( y, z) = 0,

h( z ) = 0.

It may be that P+Q < N (ie, the nested problem reduces the size of my system to solve).

Is it known which approach is more computationally efficient?

edited Jun 10 2011 at 7:31

asked Jun 9 2011 at 9:26

Ian
21●3

3

You're kinda low on the detail level. "solve $f(x)=0$, with $f$ nonlinear" could easily describe 90% of the world's problems. – Federico Poloni Jun 9 2011 at 14:02

What is the nature of this decomposition? Do $h(z)$ and $g(y,z)$ have any special properties (linearity, etc.)? – Gilead Jun 9 2011 at 21:14

I think the key word that I missed was algebraic, and the example of Newton iteration. The particular applications are generalizations of the implicit algorithm described in section 9.2 of <a href="relativity.livingreviews.org/Articles/lrr-2003-7/… review</a>. In particular, they involve a multi-dimensional implicit root-find for ${\bf x}$. There's two cases that I'm interested in; one will convert the 2d root-find for ${\bf x}$ into a pair of nested 1d root-finds. The other converts a 4d root find into a 2d nested within a 1d. I can't see any particular special properties. – Ian Jun 10 2011 at 7:40

Federico Poloni · Answer 1 · 2011-06-10 14:01:32Z UTC

There's a third option I'd consider: alternated iterations. Namely, call $N[p]$ the Newton iteration for a function $p(x)$, and solve $$ z_{k+1}=N[h](z_k) $$ $$ y_{k+1}=N[g(\cdot,z_{k+1})](y_k) $$ (I hope the notation is understandable).

Typically this kind of ideas get you slightly better results than vanilla Newton, since the updated $z_{k+1}$ is used "as soon as it's available". I do not have specific information or references to this approach for this exact problem though. Give it a try maybe and see if it works.

Nested root finding algorithm

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.