[ODE] Speeding up iterative techniques

[david@csworkbench.com]

The only iterative solution I've got working so far doesn't really attempt
to converge.... It just takes timesteps small enough that the "first best
guess" (i.e. the solution of each of the joints individually) is close
enough to right.  It throws in a few more optimizations that allow you to
do a few expensive tasks once every timestep instead of once every
iteration, but it doesn't really try to converge on the global min.

The algorithm I'm working on now also solves the A*x = b for each joint
individually (and A*delta_x = A*x - b on subsequent iterations).  I'm
trying to save space and time by not forming the huge A matrix that ODE
uses currently.  But since I have incomplete information about the forces
that affect the bodies attached to this joint, I attempted to solve the
equation with local information, then add the forces to the bodies as
external forces (represented in b) and resolve.  The problem is that while
x tends to converge to the correct answer for b very quickly, b tends to
oscillate rather than converge, so x can't converge, either.  I'll try
enforcing convergence (by limiting hi and lo to the lcp solver to a
fraction of the delta_x last iteration), and seeing if it converges to the
*correct* answer, but I don't know if it will or not.  (I guess that's
basically a simulated annealing algorithm).  Anyone have any other ideas?

A question about the LCP solver: given that I will be giving it the same A
several times, is there a way to save the decomposition of the matrix and
only have to backsolve for x in subsequent iterations somehow?  Numerical
recipes mentioned something to that effect, but with LU decomposition. 
However, standard solvers seem to render fmax (and probably some other
things) useless.  I have yet to find a good source of documentation about
LCP solvers....

David

> I've been wondering about the following for quite a while now - since I
> never saw this mentioned anywhere I figured there is either a flaw, or
> more likely nobody has considered this possibility:
>
> An iterative approach gives a stab at the correct solution and with each
> iteration gets a bit closer to the real solution. The convergence may be
> linear or something else. My guess is that the iterative approach
> discussed in the ODE mailing list converges linearly (but I don't think
> it matters all that much).
>
> Given (any) linearly convergent series, this series can be accelerated
> using Aitken's delta-squared method, this method is improved upon with a
> method called Steffensen's method - these can make a linearly convergent
> series converge quadratically. And the computations involved are
>>extremely< simple and fast.
>
> I think it is something promising to look into, if you cannot find
> references to the technique let me know, I can forward some more
> information.
>
> (If the technique cannot be applied to the iterative approach used
> currently (because it is of a higher order then linear), maybe a FAST
> linear iteration can be made that is then accelerated to quadratic using
> Steffensen's method.)
>
>
> _______________________________________________
> ODE mailing list
> ODE@q12.org
> http://q12.org/mailman/listinfo/ode