[ODE] Optimization maybe?

[Russ Smith]

> Nonetheless, I'd like to see if I can help a little; one of the things
> I have some experience in is low-level programming. I'd appreciate if
> somebody could show me to the part of the ODE code that is the most CPU
> intensive

there are two things right now: (A) the factorization of large matrices
(fast_ldlt.c) and solving right hand sides (fast_lsolve.c) and (B) the
formation of that matrix in the first place (parts of step.cpp). problem
(A) can be made faster by rewriting the factorizer/solver functions to use
SIMD assembly, for various platforms (XMM, altivec, whatever). problem
(B) is harder because it's a mix of detailed algorithm and many small
matrix multiplies - probably implementing XMM versions of the small
matrix multiplies would make it faster.

note that there has been some talk about using some other, faster (but
less precise) dynamics algorithms instead of the big-matrix-factorizing
technique (e.g. iterative LCP), but there are still plenty of reasons to
optimize the big-matrix algorithms:
  - they're faster for systems less than N*N, where N is maybe around 20.
  - they're more precise, and will give good answers in some cases where
    iterative LCP might fail.
  - the work done (and experience gained) optimizing the big-matrix
    algorithms will also apply to optimizing the other algorithms that
    come along later.
  - they'll probably be easier to optimize this way.

> hmmm... and maybe somebody should tell me how the matrix would
> typically look (random values all over, mostly just a diagonal, or
> whatever)

the big system matrix 'A' is block-sparse. get some test cases by printing
out A at the entry to dSolveLCP() in lcp.cpp.

> And what would a suitable matrix
> size be for testing purposes? (50x50, 200x200, smaller, bigger?)

it depends - you can optimize for large or small problems. i would
optimize for 20x20 to 50x50 sizes, as systems larger than this will
benefit (eventually) from other solver algorithms.

> Anything else I should know? (Maybe give-up now, before its too late?)

don't give up just yet! search the archive of this mailing list for
messages of mine that mention SIMD, XMM or the factorizer, because i've
written about this topic before. you'll also want to look at the
factorizer builder code in ode/fbuild for an idea of how the current code
is constructed. also reading a good book on numerical code will help, e.g.
"numerical recipes in C, 2nd ed". (before someone retorts that NRC is not
a good book ... on the subject of factorizers it has a good introduction
and coverage of the basic issues, even though the code examples they
provide are either lame, broken or both).

russ.

--
Russ Smith
http://www.q12.org/