Wrote

Hello w3bsurf3r,

Let's go again with testing

I attached a file where all solvers failed. Do not understand why. Could you take a look at it please.

Regards,
Radovan

Thank you omorr

There was an hidden omission in the parser that limited to 7 the maximum number of equations... issue fixed and plugin reupdated.


best regards,

w3b5urf3r


P.S. I've deleted the old plugin code from the previous post, the updated code is attached here.

---

20120914#2_NonLinearSolvers.zip (578 KiB) downloaded 76 time(s).

Thank you w3bsurf3r the quick response

I am very grateful to you and that my examples can finaly be solved in SMath . There will be more examples to come, of course.

Could you please check this out once more. Actually, HRE crashes for the same example. It might be due to my computer WinXP(32). I will check this out tommorow on Win7(64) as well.

Regards,
Radovan

---

Wrote

Thank you w3bsurf3r the quick response

I am very grateful to you and that my examples can finaly be solved in SMath . There will be more examples to come, of course.

Could you please check this out once more. Actually, HRE crashes for the same example. It might be due to my computer WinXP(32). I will check this out tommorow on Win7(64) as well.

Regards,
Radovan

Happy to be useful

About the crash, I have no ideas

The [MATH lang=eng]HRE(f(XX#),X0)[/MATH] works fine for me (win7 x64), with any optimization and decimal outputs...

The only difference between HRE and HRE.B was the solvers (Newton/Broyden) and both works for you; I think that Andrey could know the cause, for me is absolute darkness


regards,

w3b5urf3r

Thank you w3b5urf3r,

I put this on the Bugs forum including the Hang report. Hope that this will make any help to Andrey.

Regards,
Radovan

EDIT: Unfortunately, it crashes on Win7(64) and in Ubuntu for me as well. In Ubuntu "Stack overflow" error appeared.

---

Primer43-Ubuntu (53 KiB) downloaded 55 time(s).

Wrote

Thank you w3b5urf3r,

I put this on the Bugs forum including the Hang report. Hope that this will make any help to Andrey.

Regards,
Radovan

EDIT: Unfortunately, it crashes on Win7(64) and in Ubuntu for me as well. In Ubuntu "Stack overflow" error appeared.

Hi,

I've made some performance improvements inside HRE (the plugin is in this attachment), could you test if the bug is still present?


P.S.

New resources about Homotopy:
- Computers and Chemical Engineering 25 (2001) 1003–1019 - Global homotopy continuation procedures for seeking all roots of a nonlinear equation
- Introduction to Numerical Continuation Methods


regards,

w3b5urf3r

---

4TESTINGONLY_NonLinearSolvers.zip (9 KiB) downloaded 66 time(s).

Hello w3b5urf3r

This is working now just great . Thank you very much
Find attached the pictures both from the WinXP(32) and Win7(64)

Regards,
Radovan

---

Hello w3b5urf3r, me again

I have to excuse my self but it seems you will not get rid of me so easily

Here is another of my teaching class files. It seems that HRE.B will have problems now. Anyway, it is a linear system again and NewtonRaphson based solvers did the job, Broyden was quite Ok but HRE.B failed now.

Regards,
Radovan

---

Wrote

Hello w3b5urf3r

This is working now just great . Thank you very much
Find attached the pictures both from the WinXP(32) and Win7(64)

Regards,
Radovan

Great,

it seems that the number of nested iterations was excessive to handle, I just placed some eval here and there... :d

Wrote

Hello w3b5urf3r, me again

I have to excuse my self but it seems you will not get rid of me so easily

Here is another of my teaching class files. It seems that HRE.B will have problems now. Anyway, it is a linear system again and NewtonRaphson based solvers did the job, Broyden was quite Ok but HRE.B failed now.

Regards,
Radovan

A first check show me that Broyden returns a wrong result, but I don't know why; comparing them with the snippet in the reference sheets (using γ:1) the script works fine... I'll check it a little more

EDIT: the snippet is wrong, use Newton instead of Broyden, so the results are a little bit differents but are both wrong (so I think that HRE.B() can't be used in this example...)


regards,

w3b5urfer

Hello w3b5urfer,

Here is another similar problem like the previous ones. This is a 17x17 problem. Again, problem is linear and solved with nonlinear solvers (roots() failed here). The results are quite good except the HRE.B gives a bit poorer results.

Regards,
Radovan

---

Wrote

Hello w3b5urfer,

Here is another similar problem like the previous ones. This is a 17x17 problem. Again, problem is linear and solved with nonlinear solvers (roots() failed here). The results are quite good except the HRE.B gives a bit poorer results.

Regards,
Radovan

Hi omorr,

most likely both will be revisited...

actually HRE/HRE.B are based on the simplest algorithm that I've found, and seems that it's quite onerous (Broyden and Newton are both much more faster), so I think that Homotopy function (at the time, at least) should be used only for testing purposes or when both Broyden and Newton fails; consequently I've limited the CPU usage using this convergence criterion: f(x)<10^-2 with no more than 100 sub-iterations for each Homotopy iteration (no more than 1100=100x11 iterations for HRE and 2200=100x2x11 iterations for HRE.B).

BTW note that in both case the convergence criterion is met (see the attachment).


regards,

w3b5urf3r

---

Hello w3b5urfer,

Glad that you are continuing this adventure . Nonlinear equations can sometimes be a real pain in the .

Just look at the next example. I just tried to solve 12x12 in SMath. I solved that already but not in SMath yet and it just drives me crazy for quite a long time

There are three different f(x) functions, doing the same thing - but there is no solution. Broyden will work somehow but the guess values must be quite close to the solution. As you would see, finding Jacobian (derivatives) is a nightmare for me . Therefore, I think roots() and NewtonRaphson can not be used. I just do not know how to deal with it. I have the impression that many problems like this one are almost impossible to solve at the moment.

Regards,
Radovan

---

Primer47w.sm (135 KiB) downloaded 61 time(s).

PLUGIN UPDATED

- added optional Convergence checking on bracket width (for bracketed algorithms only: BDQRF(),Bisection(),Brent(),Ridder());

- fixed issues of Brent() with units of measurement.


regards,

w3b5urf3r


EDIT: added plugin sources

---

sources_NonLinearSolvers_20120926.zip (588 KiB) downloaded 69 time(s).

More resources for making the nonlinear solver, I hope they are useful ^^

Homotopy pseudocode (as well as other methods) on this work about numerical methods for nonlinear systems
(document page 215; pdf page 227)

I've read on this paper "prac_no_lineal"
that this other method works well for great number of dimensions:
Inexact Newton methods like "Newton-Krylov method". Again you can find a matlab implementation on
Tim Kelley's page (you can download his pdf book as well)
see the code "nsoli.m"

Also on that paper "prac_no_lineal" pdf page 8, there are also codes for "homotopy using runge-kutta order 4" and for a method based on changing Newton's convergence.

Finally more matlab codes on this thesis about
efficient iterative methods for nonlinear systems (pdf page 181)

FOR TESTING PURPOSES ONLY

Hi all,

a (big) little update in the attached plugin:

- New feature: solvers for systems of equations now accept multiple unknowns names (see the example below)

- Broyden convergence criterion revisited

- Plugin Jacobian(...) unlocked


NOTES:
- known starting values must be placed with reference to the alphabetical order of the unknowns (a,A,b,B,c,C,...,z,Z,α,Α,β,Β,γ,Γ,...). If you are unsure about the order, call the function mapUnknowns(1) (see the example below);
- Jacobian() generates derivatives, gradients or Jacobians depending on the type of arguments.

PLEASE REPORT ANY ISSUE

regards,

w3b5urf3r

---

BETA_NonLinearSolvers.dll.zip (11 KiB) downloaded 62 time(s).

Hello w3b5urf3r

I was playing a bit with this test version, of course .

This feature you included if awesome

Broyden is working very well, just playing with tolerance, Decimal places and Exponential threshold - everything looks fine then (see the picture please ). I was just playing a bit with it, it seems quite good for this example except HRE.B gives different results with and without multiple unknown names - see the attached file please. Actually, no big deal about homotopy methods at the moment as you explained

Regards,
Radovan

---

Hi w3b5urf3r and Radovan,


I'm delighted seeing your interesting work.
I tried to apply the plugin to one of my problems - one equation - here attached.
It is obvious that the ability of various algorithms is enough dependent on the initial guess.
I'm interested if you have some suggestions concerning the initial unknown guess strategy for this case, seeing the parameters variation ranges.


Thanks and congratulations again for your work,


Ioan,

---

longflamb eq.sm (29 KiB) downloaded 50 time(s).

Wrote

Hello w3b5urf3r

I was playing a bit with this test version, of course .

This feature you included if awesome

Broyden is working very well, just playing with tolerance, Decimal places and Exponential threshold - everything looks fine then (see the picture please ). I was just playing a bit with it, it seems quite good for this example except HRE.B gives different results with and without multiple unknown names - see the attached file please. Actually, no big deal about homotopy methods at the moment as you explained

Regards,
Radovan

Hi omorr, :d

yes the new features are very awesome

when I have more time I will try to improve the Homotopy functions; as already said the target precision is [MATH]10^-2[/MATH] and is reached in both the examples

Wrote

Hi w3b5urf3r and Radovan,


I'm delighted seeing your interesting work.
I tried to apply the plugin to one of my problems - one equation - here attached.
It is obvious that the ability of various algorithms is enough dependent on the initial guess.
I'm interested if you have some suggestions concerning the initial unknown guess strategy for this case, seeing the parameters variation ranges.


Thanks and congratulations again for your work,


Ioan,

Hi Ioan

The HRE functions need 2 arguments, no more (see the attachment).

The initial unknown guess strategy It's a common issue, Homotopy and Bisection I think they are the best approaches.

Note that in your script a "large" bound it's better than a little bound.


best regards,

w3b5urf3r

P.S. in the previous post I've reupdated the plugin, the previous librery have a little issue with the x variable, when already defined

---

Thanks for your effort!
Please w3b5rf3r, take a look at this pseudocode for homotopy with test functions and iteration results (pdf page 227)
http://www.iit.upcomillas.es/pfc/resumenes/450608814dabe.pdf
This method uses Runge-Kutta 4th order on every iteration, the followed algorithm is explained above the pseudocode section. The same strategy of runge-kutta 4 is explained more clearly on this paper pdf page 8
http://personales.upv.es/dginesta/docencia/posgrado/prac_no_lineal.pdf

Wrote

Thanks for your effort!
Please w3b5rf3r, take a look at this pseudocode for homotopy with test functions and iteration results (pdf page 227)
http://www.iit.upcomillas.es/pfc/resumenes/450608814dabe.pdf
This method uses Runge-kutta with 4 steps on every iteration, the followed algorithm is explained above on the document.

Very interesting method. As I understand it, he does it so: Draghilev.jpg

Roots count: 81 - this is not entirely true. In fact it is the number of solutions which found an algorithm, but it may be repeated. Here in the picture is a solution along the blue curve (3D). In places where it crosses zero, we find the roots.



Example 1: Draghilev1.pdf
Example 2: Draghilev2.pdf

Sorry Uni, I don't understand your pdfs
Homotopy methods seem to be appropriate to guess an initial zero on large systems since the usual methods need a good initial approximation to converge.
That's what I grasped from the above document: Homotopy is based on deform your equation f(1) into another one f(0) easier (known) to resolve. Then you have to get to f(1) from f(0) through a path like a segment (or another curve if it doesn't make sense this road to get to the solution)
f(t)=(1-t)f(0)+tf(1), where t is a number between 0 and 1.
Now he assumes X(t) as the solution for f(t), so f(t)(x(t))=0, then he derivates this expression resulting an ode system to resolve x(t), since x(0) is known he says to resolve the initial value problem with RK4 (good balance between cost and precision) or the ode23() matlab function.