Real-Time Physics Simulation Forum

New paper about impulse-based dynamic simulation

2006-11-28T15:05:53+00:00

After the discussion about the complexity of my impulse-based method I tried to formulate the system of linear equations (SLE) for the impulses in an equivalent way as Baraff did for the Lagrange multipliers. And in fact I found an equivalent formulation of the problem. So I was able to solve the SLE in the same way as Baraff. This works in linear time (and requires O(n) space).

By computing the impulses in linear time even the simulation of the tree with 255 joints was faster than real-time on my 3.4 GHz Pentium. So it was faster than using PARDISO.

I probably will write a paper about the linear-time dynamics with my impulse-based method. You just have to wait for it

Jan

Statistics: Posted by Jan Bender — Tue Nov 28, 2006 3:05 pm

New paper about impulse-based dynamic simulation

2006-11-16T08:14:56+00:00

yes however if i see a sparse LU decomposition i think that the solver i designed for large n .

But the k can be very big due to other reasons. For example, if you use the Lagrange multipliers, you have to compute continuous constraint forces. When integrating the body states e.g. with Runge Kutta 4, you have to evaluate these forces for different time step sizes. By using the impulse-based approach you have to compute the impulses just once per time step. So the constant k will be probably smaller.

We have a good implementation of Baraffs method and the results I mentioned were surprising but they were made with a fair test. I regret that I don't have an implementation of the Featherstone algorithm. It would be interesting to compare all methods.

Jan

Statistics: Posted by Jan Bender — Thu Nov 16, 2006 8:14 am

New paper about impulse-based dynamic simulation

2006-11-15T18:58:00+00:00

i dont know the details of the Baraff's method, however Feastherstone gets faster than any method when n > 7 if im not wrong, where n is the number of DOFs. Of course Feastherstone covers only branched chains but thats what you used for your tests isnt it?
On the other side you can't say that a method with linear complexity is the fastest for every model. A complexity of O(n) always means that you have k*n computations where k is a constant. So if k is very big the method can be very slow for small models. But it depends on the method what is "small".
Jan

yes however if i see a sparse LU decomposition i think that the solver i designed for large n .

cheers,
Antonio

Statistics: Posted by Antonio Martini — Wed Nov 15, 2006 6:58 pm

New paper about impulse-based dynamic simulation

2006-11-16T10:59:38+00:00

i think it was n = 9. In any case detailed analysis of the complexity of the Featherstone algorithms and other algorithms can be found in:

Robotic Dynamics Algorithms
Roy Feathestone
Kluwer Academic Press
I know this one but I don't think that there is proof that considers all methods that exist.

algorithms typically used in robotics and considered very efficient by the experts in the relevant field are considered.So published algorithms at the time of writing were considered.
So at least there is some reasoning behind the claims. Im not trying to state which algorithm is the best, im just stating that in order to show that a solver is more efficient than another one, a proper analysis must be conducted, those books are a good example on how such analsys maybe conducted and its not sufficient to take 2 particular implementations and compare them like you did. If you compare your algorithm to the Baraff's one i presume that you assumed a similar context of application and so you assumed that they are comparable. Also stating that a method is very simple to implement when it requires a sparse LU decomposition package seems a contradiction to me. If PARADISO is used at least we should know how it works, as that may well be the reason why it is faster in that case.
I have the maximum respect for your work, i will read it in more detail as i have more available time, for now i just dont feel very motivated to do it for the reasons i have exposed.

cheers,
Antonio

Statistics: Posted by Antonio Martini — Wed Nov 15, 2006 6:34 pm

New paper about impulse-based dynamic simulation

2006-11-15T18:05:47+00:00

i think it was n = 9. In any case detailed analysis of the complexity of the Featherstone algorithms and other algorithms can be found in:

Robotic Dynamics Algorithms
Roy Feathestone
Kluwer Academic Press

I know this one but I don't think that there is proof that considers all methods that exist.

Anyway I am sure that the Featherstone algorithm is one of the best and fastest methods. But it has also some disadvantages as every other method too.

of course we are in the context of "exact" solvers.

My method converges also to the exact solution. There is a proof for this in "On the Convergence and Correctness of Impulse-Based Dynamic Simulation".

Jan

Statistics: Posted by Jan Bender — Wed Nov 15, 2006 6:05 pm

New paper about impulse-based dynamic simulation

2006-11-15T17:54:19+00:00

i dont know the details of the Baraff's method, however Feastherstone gets faster than any method when n > 7 if im not wrong, where n is the number of DOFs. Of course Feastherstone covers only branched chains but thats what you used for your tests isnt it?
Faster than ANY method? I would like to see a proof for that.

i think it was n = 9. In any case detailed analysis of the complexity of the Featherstone algorithms and other algorithms can be found in:

Robotic Dynamics Algorithms
Roy Feathestone
Kluwer Academic Press

Efficient Dynamic Simulation of Robotic Mechanisms
Kathhryn W. Lilly
Kluwer Academic Press

of course we are in the context of "exact" solvers.

cheers,
Antonio

Statistics: Posted by Antonio Martini — Wed Nov 15, 2006 5:54 pm

New paper about impulse-based dynamic simulation

2006-11-15T17:36:27+00:00

i dont know the details of the Baraff's method, however Feastherstone gets faster than any method when n > 7 if im not wrong, where n is the number of DOFs. Of course Feastherstone covers only branched chains but thats what you used for your tests isnt it?

Faster than ANY method? I would like to see a proof for that.

a method with a worse complexity can be faster simply because its has been better implemented. So you can take any algorithm, implement the best one in a very bad way and show that the worst one is "much better". I depends on how much you are willing to optimize in the end, just change PARDISO with something else and the total speed will drastically change.

That is clear. Since I have a very similar matrix structure as Baraff I am sure that I can solve my system of linear equations in the same way as him. In this case my algorithm would have a linear complexity. But this will probably be the topic of my next paper

I think that before stating that your algorithm is better, at least an analysis of the computational complexity, storage requirements and in general an analisys of why it is faster and when is the minimum that it is required. Otherwise in the best case it would be reaching the right conclusions from the wrong premises.

I never said it is better, it was just faster for the tree model. It always depends on the application which method is the best for you.

On the other side you can't say that a method with linear complexity is the fastest for every model. A complexity of O(n) always means that you have k*n computations where k is a constant. So if k is very big the method can be very slow for small models. But it depends on the method what is "small".

Jan

Statistics: Posted by Jan Bender — Wed Nov 15, 2006 5:36 pm

New paper about impulse-based dynamic simulation

2006-11-15T16:21:38+00:00

both the Baraff's method and the Featherstone algorithm have O(n) complexity for equality constraints, so you solve a system of linear equations in less than O(n) and this by doing the LU decomposition? am i missing something? whats the computational complexity of your method? and what are the storage requirements?
I use PARDISO to solve the system of linear equations. I can't tell you which complexity it has. It is optimized for sparse matrices but I don't think that it has linear complexity in the worst case. Baraff can guarantee this. But the complexity that you have in praxis for a special model is something different.

For the simulation I used the model proposed by Baraff himself. If you simulate a special model it is not guaranteed that a O(n) algorithm is faster than an algorithm with a higher complexity. Only if n increases there will be a point where the O(n) algorithm gets faster. Baraff has to solve a bigger matrix than me and has to solve a system of differential equations with continuous forces. That's why his method is slower than mine when simulating the tree with 255 joints.
Jan

i dont know the details of the Baraff's method, however Feastherstone gets faster than any method when n > 7 if im not wrong, where n is the number of DOFs. Of course Feastherstone covers only branched chains but thats what you used for your tests isnt it?
it can also be extended in order to deal with contacts:
http://research.scea.com/research/pdfs/ ... DC2004.pdf

a method with a worse complexity can be faster simply because its has been better implemented. So you can take any algorithm, implement the best one in a very bad way and show that the worst one is "much better". I depends on how much you are willing to optimize in the end, just change PARDISO with something else and the total speed will drastically change.
I think that before stating that your algorithm is better, at least an analysis of the computational complexity, storage requirements and in general an analisys of why it is faster and when is the minimum that it is required. Otherwise in the best case it would be reaching the right conclusions from the wrong premises.

I read you paper very quickly, so i apologise in advance if i have missed something.

cheers,
Antonio

Statistics: Posted by Antonio Martini — Wed Nov 15, 2006 4:21 pm

New paper about impulse-based dynamic simulation

2006-11-15T15:07:44+00:00

both the Baraff's method and the Featherstone algorithm have O(n) complexity for equality constraints, so you solve a system of linear equations in less than O(n) and this by doing the LU decomposition? am i missing something? whats the computational complexity of your method? and what are the storage requirements?

I use PARDISO to solve the system of linear equations. I can't tell you which complexity it has. It is optimized for sparse matrices but I don't think that it has linear complexity in the worst case. Baraff can guarantee this. But the complexity that you have in praxis for a special model is something different.

For the simulation I used the model proposed by Baraff himself. If you simulate a special model it is not guaranteed that a O(n) algorithm is faster than an algorithm with a higher complexity. Only if n increases there will be a point where the O(n) algorithm gets faster. Baraff has to solve a bigger matrix than me and has to solve a system of differential equations with continuous forces. That's why his method is slower than mine when simulating the tree with 255 joints.

Jan

Statistics: Posted by Jan Bender — Wed Nov 15, 2006 3:07 pm

Re: New paper about impulse-based dynamic simulation

2006-11-15T14:13:10+00:00

Furthermore a new method is presented that allows to compute all required impulses by using a system of linear equations. This method is very fast. We have compared it with the method of David Baraff presented in "Linear-Time Dynamics using Lagrange Multipliers". The simulation of a tree with 255 joints was more than 5 times faster with my new method.

both the Baraff's method and the Featherstone algorithm have O(n) complexity for equality constraints, so you solve a system of linear equations in less than O(n) and this by doing the LU decomposition? am i missing something? whats the computational complexity of your method? and what are the storage requirements?

cheers,
Antonio

Statistics: Posted by Antonio Martini — Wed Nov 15, 2006 2:13 pm