Iterative vs. direct solver

[Don Shepherd]

I wrote an article on something to be aware of if you use the HP solver and expect the direct solver to be used, but instead the iterative solver is used.

[Bill (Smithville, NJ)]

Hi Don,

Good article. Thanks for posting it.

Yoou are deffinitely the solver king.

Bill

[Don Shepherd]

Thanks Bill. I'm no king, but I do enjoy using the solver to take advantage of its many capabilities. Years ago, you first turned me onto the "bible" for all things solver, the Technical Applications Manual for the 27s/19b. In fact, at the top of page 14 it discusses what I reported in my article, about the direct solver failing if the variable you are solving for appears more than once formally, and also how to change the reference to the variable so the direct solver will work.

Fascinating stuff. I sure hope the guys who designed that solver got some kind of award/reward for it, they sure deserved it.

[Namir]

The Solver King is Professor Kahan. The King of iterative solution for nonlinear equations ... is .... uhum ... yours truly! It has been a passion and (dare I say obsession) of mine since the mid 70s!!

Namir

PS: In fact in the last few months I have been studying the methods for iterative solution of linear systems. The topic is fascinating. The stationary methods are interesting but come with limitations as to what kind of (large) linear systems they can solve. The non-stationary method use conjugate gradient methods to solve the linear systems as an optimization problem. I have been tinkering with the algorithms to solve sets of 500, 1000, and 2000 linear equations. So far, no new discovery :-(

PS2: My lack of modesty is due to jet lag effects, having returned from Europe a few days ago!!

Edited: 18 May 2012, 3:57 a.m. after one or more responses were posted

[Paul Dale]

Care to write a non-linear iterative solver for the 34S :-)

- Pauli

[Namir]

Is the current solver for the 34S inadequate???!!!

Namir

[Paul Dale]

I'm not sure, but I am sure it can be improved :)

- Pauli

[Namir]

Pauli,

I can certainly look at the pseudo-code for your solver and see if I can improve it.

Namir

[Paul Dale]

Namir,

The source code is trunk/xrom/solve.wp34s on the subversion site.

I use a combination of quadratic interpolation, Ridder's method, secant and bisection with lots of guards etc. It seems to work okay most of the time but it is the difficult problems that really show up this kind of code.

- Pauli

[Namir]

Pauli,

Do you monitor the sign of the updates in the guess for the root, to guard against the guess resonating between two different regions of values?

Also do you check for low slope values?

Sorry for asking questions that may be trivial to you. These are two general cases of root-seeking problems that come to mind.

Namir

[Paul Dale]

Once the two estimates' signs are different I force all future guesses to be within the interval -- I switch to bisection if the more sophicated methods give guesses outside this interval. I know that this will locate discontinuities that across zero but I can live with that. My previous solver used bisection if the split between the new guess and the current bounds was too small but I've stopped doing this -- Ridder's steps seem more effective after a bisection.

I'm not exactly sure what you mean by low slope values -- I do limit the jump distance if both guesses have the same sign to ten times the width between the guesses. I also limit jumps when the function appears constant, although not much.

- Pauli

[Namir]

The low slope (function derivative) value is a problem when using Newton's method. Other methods like Ridder and Bisection are not affected by the slope.

Namir

[Paul Dale]

Until the solution is bracketed, I don't use Ridder's or bisection, only secant and quadratic interpolation. Once the solution is bracketed, there is no need to limit the distance jumped -- only to keep future estimates inside the bracketed interval.

I guess I could disable the limiting for quadratic interpolation. Is it a problem here too or not? My gut feeling is quadratic interpolation will be confused too, although not so badly as the secant method -- gut feelings are notoriously fickle though.

- Pauli