[ODE] More speed???

[Nguyen Binh]

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
---------------------------------------------------------------------