# [ODE] More speed???

Nguyen Binh ngbinh at glassegg.com
Thu Nov 6 11:17:18 MST 2003

```Hi Martin,

MCM> Actually, O(n*n*n) vs. O(n).  Check out the stepfast section in the ODE
MCM> docs.
Yes! You're right!

MCM> Wow, that really is surprising.  Can you post a test case and your code?
MCM>   The "n" above, that determines the speed, is the number of DOF
MCM> removed.  Are these bodies connected together?  Are they colliding?  The
MCM> stepfast tests kind of maximize that.  Have you tried them?
My test scene is very simple. It's test_boxstack.cpp in ODE test
with about 200 bodies.And yes, they are collided.

MCM> Well, that is the heart of the constraint satisfaction, i.e. it's doing
MCM> all the hard work of balancing all the constraints, so it doesn't
MCM> surprise me.  What does surprise me is that the LU decomposition of the
MCM> matrix (O(n^3)) takes less time than the substitution steps.
Yes, that's what I mean.But think of dSolveL1T() and dSolveL1()
What do they do? They solve L*X=b  with L is an n*n lower triangular
matrix with ones on the diagonal.
So:
x1 = b1/L11 = b1;
xi = (bi - SUM(Lij*bj)with j= i+1 -> n );

Fairly simple? So what I feel surprise is we have to spend nearly
half of our computing power to do such simple thing.
More on your comments, I don't mean ONE factoring take less time than
ONE solving.The function dFactorLDLT() may take more time than one
dSolveL1T() but called much lesser.So I mean on the whole,
solving takes more time than factoring, i.e many  dSolveL1T()
take alot more time than lesser dFactorLDLT(). OK! Profile it,
you'll see...

I'd guess SIMDize dSolveL1() and dSolveL1T() will save us!

MCM> True, now that I think about it, while they're inspired by the same
MCM> idea, the details are quite different.  But solving the linear system
MCM> iteratively would be at best O(n^2), since the matrix A has O(n^2)
MCM> elements, and you need to touch each one.  Is that true?  Is A sparse?
MCM> Maybe that explains why the LU decomposition is so fast.
I think so too. On my test case, A is about 150x150 but the
factoring is not too expensive. So A should be sparse.(a matrix dump
here will clear the point)

MCM> Conjugate gradient is for finding the minimum of an arbitrary function
MCM> that has a single output.  It more or less assumes that the function
MCM> you're trying to minimize is locally quadratic.  It doesn't directly
MCM> apply to solving linear equations, and if you modify the problem to fit
MCM> (e.g. by minimizing ||A.x - b||^2), it's guaranteed to be slower that
MCM> directly solving it, I think.
Is that? I didn't expect so! But let me experiment....

MCM> This will be true if most constraints are contact, and I think you need
MCM> friction of zero in one direction to boot.  If your constraints are
MCM> regular joints, n is 3 for ball and socket, 4 for slider & universal &
MCM> hinge2, 5 for hinge, 6 for fixed.  If you use the joint motor or joint
MCM> limits, the numbers go up.
Argg... I forgot to mention. We need another way to deal with
joints in StepFast.I think we should classified joint by number
of DOF it remove and use specialized code to solve for each
class.

MCM> At least one of the stepfast tests has a bunch of cars.  Cars use hinges
MCM> and hinge2 joints.  You should really test your code with that as well.
Yes. That's the first thing I do when I have time....

MCM> You make a good point about the varying sizes though; there are
MCM> certainly cases where the individual matrices are small, and it would be
MCM> great to handle at least 2x2 and 3x3 separately, and maybe the others as
MCM> well.  That could speed things up quite a bit!

As you said about types of joints. I remember someone said that
we should treat contact differently beetween normal joint cause
contact joint is inequality but others are equality.

--
Best regards,

---------------------------------------------------------------------
Nguyen Binh
Software Engineer
Glass Egg Digital Media

E.Town Building
7th Floor, 364 CongHoa Street
Tan Binh District,
HoChiMinh City,
VietNam,

Phone : +84 8 8109018
Fax   : +84 8 8109013

www.glassegg.com
---------------------------------------------------------------------

```