Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
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 '11 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 '11 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/">this 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 '11 at 7:40
add comment

1 Answer

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.

share|improve this answer
    
Thanks; I'm mainly using black boxes for the root finding, so this may take a while to check. –  Ian Jun 10 '11 at 14:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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