[ODE] Speed of ODE's constraint method

Russ Smith russ at q12.org
Sun Oct 27 21:16:01 2002


> A good reference on iterative LCP methods is chapter 9
> of Murty's book

interesting. i read chapter 9 and implemented some of the methods there
in matlab. the sparsity-preserving SOR (successive over-relaxation)
method described on p378 seems to be the closest to what you describe,
as its main computational step is multiplying M by some vector. in ODE
'M' is J*inv(M)*J', which boils down to a bunch of 6xN matrix operations
as you described.

for the random PD matrices i was testing with i found that the SOR
method scaled as O(n^3), the same as the direct method. i found that if
a 0.1% error was the termination condition then SOR was 3-4 times less
flop count than ODE's direct solver for 100*100 matrices (the crossover
point below which the direct method was faster was about 20*20).
however! --> typical rigid body system matrices have a much more useful
spectrum than my random matrices, so i suspect that if ODE had an SOR it
would (a) be much faster than direct LCP, and (b) scale O(n) or O(n^2)
depending on the structure of the RB system. i will investigate this
later. SOR would not be too hard to implement in ODE at all (it would be
an optional method). chosing the parameter values (e.g. w) presents a
problem.

> Although this should give you an idea about what I
> mean by iterative LCP, I should point out that we dont
> use any of the methods in that chapter.

are you using a method related to the SOR method?

russ.

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