Real-Time Physics Simulation Forum

Projected Gauss Seidel patent and other physics patents

2006-01-06T17:32:16+00:00

I appreciate and respect all contributions. Therefore no post have been removed, only split.

Antonio asked to have the topic split into patent-related posts and pgs-impulse comparison posts. This is what I did. See this post:
http://www.continuousphysics.com/Bullet ... .php?t=208

I removed 2 lines, because they linked the two together.
Those lines where:
1) the split request of Antonio, because it had be executed
2) a comment from Erin Catto to Jerez that linked the two topics together, which don't make sense anymore after splitting.

Sorry for the confusion of the split, there were no intension to remove any comments.

Statistics: Posted by Erwin Coumans — Fri Jan 06, 2006 5:32 pm

Projected Gauss Seidel patent and other physics patents

2006-01-05T12:59:10+00:00

My post of this thread had been answered to other post.

I see that some of the other post had been edited and other had been removed after I replied Leaving just my answer dangling like a complete idiot out of context.
This is not the first time this had happens here.
I cannot do that except on the very last post.

Thank you very much.

Statistics: Posted by Julio Jerez — Thu Jan 05, 2006 12:59 pm

Projected Gauss Seidel patent and other physics patents

2006-01-04T23:27:33+00:00

as i said i wrote that stuff many years ago however i dont remember of throwing away the factorization. So i guess i was somehow doing the perfect ordering thing you mention whatever it may be. It would be interesting to see if ODE is discarding the factorization at some point in the direct solver. Or if we are lucky and Russ is reading this, he might tell us directly. The mathengine patent is his after all:)

I do not really care for Gauss Seidle or Pivoting Lemkel/Danzig method although I do question the claims.

I thought we finish this conversation with the last post but if you insist.
I am more than happy to explain to you why the factorization most be throwing out when you remove a row. (I hope you understand my broken English).

Say you are adding the N active variable from the inactive set and it just happens this new active variable forces another active variable to the inactive set.
It just happens that the forced out variable could be anywhere in the array.
Since the construction of each row is an n^2 order, and you have a probability of n/2 of the variable to been anywhere on the active set. You end up with
n/2 rows of ( n *n ) operation for re-factorizations.
the only thing the incremental factorization do is that is reduces the constant in front of the 0(n4) by a significat value.
you can probably get a factor of 2 or 3 speed up but never one order of magnitud reduction.

And since the majority of the non-zero elements of the lower diagonal matrix are by the end of the array. The lower haft of the factorization carry almost full n * n *n cost statistically. So yes I say with 100% of certainty Baraff implementation of dazing is a precise O(n4) average case
This is not a thing that is a matter of a person opinion this is an absolute fact.
If ODE or your implementation is not doing it that way then my apologies that is a patent able claim if it works. Or it is just wrong.

Statistics: Posted by Julio Jerez — Wed Jan 04, 2006 11:27 pm

Projected Gauss Seidel patent and other physics patents

2006-01-04T21:54:48+00:00

if in Newton you did the same or similar but nobody know about it that's not public domain knowledge i guess.
Well I am solving systems that can be as high as 16000 x 16000 you think I am doing magically? The proof is there and the Newton engine has been around long before this claim.

the fact that you can solve a problem of similar/equal size at the same speed doesn't invalidate the patent claim. You may be reaching similar or even better performances by using a different method not publicly available. It's like concluding for the same cause given the same observed effect. It seems logically fallacious to me.
So unless you published the method somewhere it may not be that easy. . However i stress this again, i am not an expert about patents and related legislation. it would be interesting to hear other people opinions.

well the claim is no so, is only apply if you can sort the row in perfect order when row are to be remove the incremental factorization has to be thrown out. And you get the same o(n3) factorization.

as i said i wrote that stuff many years ago however i dont remember of throwing away the factorization. So i guess i was somehow doing the perfect ordering thing you mention whatever it may be. It would be interesting to see if ODE is discarding the factorization at some point in the direct solver. Or if we are lucky and Russ is reading this, he might tell us directly. The mathengine patent is his after all:)

Statistics: Posted by Antonio Martini — Wed Jan 04, 2006 9:54 pm

Projected Gauss Seidel patent and other physics patents

2006-01-04T21:31:12+00:00

if in Newton you did the same or similar but nobody know about it that's not public domain knowledge i guess.

Well I am solving systems that can be as high as 16000 x 16000 you think I am doing magically? The proof is there and the Newton engine has been around long before this claim.

It looks like that you have misunderstood what im trying to say and im going to try to be clearer here. Im _not_ in favour of patents, however there is a law, if somebody applies for a patent that laws applies if we like it or not. So what im interested it's not if many other people did the same or better in their secret room given that i have no doubts about it. But im more interested to see if it possible to show that at the moment of the application there was sufficient available information (papers/code) in order t invalidate the "invention"

Then you am I agree. I just found the claim very disingenuous and I still believe it is public knowledge.

given that you seems so good at it i would advice you to do also some critical analysis of your writing style;)

Well you know what they say old dogs do not learn new tricks. I am just happy I can barely communicate. this is why I do not write novels.

wasn't in an incremental LU/cholesky factorization done in O(n^2)?

well the claim is no so, is only apply if you can sort the row in perfect order when row are to be remove the incremental factorization has to be thrown out. And you get the same o(n3) factorization.

I think you are right it is about the patent so maybe you am I agree. We were just discussing the details of what makes the patent legitimate.

Statistics: Posted by Julio Jerez — Wed Jan 04, 2006 9:31 pm

Projected Gauss Seidel patent and other physics patents

2006-01-04T20:39:15+00:00

For the record that goes to show you are reading the paper and relating what you read with very little critical analysis.

given that you seems so good at it i would advice you to do also some critical analysis of your writing style;)

The inner loop of the method solves n x n a linear system by either LU or Colesky factorization.

wasn't in an incremental LU/cholesky factorization done in O(n^2)?

no time to read the rest and to be honest im not that interested given that it's a long time that i dont work on that stuff anymore.Among the other things it's offtopic in repect to this thread which is more about patents rather than computational complexity.

Statistics: Posted by Antonio Martini — Wed Jan 04, 2006 8:39 pm

Projected Gauss Seidel patent and other physics patents

2006-01-04T20:31:08+00:00

I have implemented the baraff's algorithm many years ago with all the due respect for your language. In a bilateral constraint the forces are in the range -+ infinite.Contact allows for forces in the range 0,+infinite. the boxed LCP for low-high,limits. What you are basically saying is that something which is very simple is not an invention.

Well maybe that was your intepretation, I had been working with simplex Convex quadratic programming long before Baraff paper. When I Saw his formulation I implemented and I never used the 0 and infinity limit as matter of fact that infinity mombo-jumpo has hampered ODE for many years into making gratuitous explosion for nto particular reason (so there you go)

The baraff algorithm is O(n^3).

For the record that goes to show you are reading the paper and relating what you read with very little critical analysis.
Here is the proff the LCP is O(n4)
Baraff did not lie but he mislead the people into thinking the method is and O(n3) and he say that is a worse case np complete. Whicj is a way of saying that is can only be expressed as a polynioming of O (n + n2 + ?n^n) it is truth but it is measleading.
In fact the method is presiselly O(n^4) average case and best case O(n3)

Proof:
The inner loop of the method solves n x n a linear system by either LU or Colesky factorization.

The outer loop solve either a n x n or (n+ 1 * n+1) linear system
So the time complexity is a geometric progression of the form

O = k * 1^3 + K * 2^3 + ?. .k * N ^ 3

The general turn of that regrasion is (goolgel for it if you like)

S = K1 * O(N^3) + K2 * O(N * 4)

The average come for the fact that the clamped variable are solve at last
So the lower composed of the regression are zero they are insignificant compare to the largers systems .

For example say you have a stack with 100 rows, and only 4 at the bottom are contacts
That is 4 of those rows are to be clamped.

The total time is assuming k is const

96^ 3 + 97^3 + 98^3 +100^3 =
if all o fteh point are contacts then the added values is totally marginal

since the larger part of the row are contacts yes the method is and average o(n4)

Statistics: Posted by Julio Jerez — Wed Jan 04, 2006 8:31 pm

Projected Gauss Seidel patent and other physics patents

2006-01-04T20:23:52+00:00

Danzig and Lenkel methods both allowed for up and downs limits.
David Baraff was derived to handle specifically contacts, in that case the lower limit is zero and you do not need the code. In his paper he explain how to extend it to handle bilateral constraint. So adding the complement part to check the lower limit is not an invention.

i was referring to what you wrote:

"Baraff paper and the Patent match line by line, except that Baraff paper is predate the patent by 6 years."

and it seems clear in what i replied:

"they are not the same line by line, the Baraff algorithm doesn't allow for low and hi force limits. Motors and Friction require such force limits in the karma solver(or ODE's direct solver). "

but now you seem to agree that they don't match line by line anymore. So problem solved;) The Baraff's algorithm with equality constraints added is not the same as the low-high force limits case but is the special case of when low=-inf and high=+inf. both friction and motors in the model employd by ODE and Karma required finite force limits.

Statistics: Posted by Antonio Martini — Wed Jan 04, 2006 8:23 pm

Projected Gauss Seidel patent and other physics patents

2006-01-04T21:05:53+00:00

In his paper he explain how to extend it to handle bilateral constraint. So adding the complement part to check the lower limit is not an invention.
It is okay because no one really takes that seriously as the method is a 0(n4) time complexity.

I have implemented the baraff's algorithm many years ago with all the due respect for your language. In a bilateral constraint the forces are in the range -+ infinite.Contact allows for forces in the range 0,+infinite. the boxed LCP for low-high,limits. What you are basically saying is that something which is very simple is not an invention. To me that's not necessarily the case, given that slight modification allows to solve a wider range of problems. The baraff algorithm is O(n^3).
I agree that each single algorithm we are talking about could have been
"invented" by anybody working in the field at the same time o many year before. But inventions are more about who did it first i guess, or better about who did first and made it public, this considered that around there are many simple great original ideas and they still count as invention dont they?:)

About Richard Tongue he is claiming the invention of storing J and JM into and indexed flat array. This is not an invention I had been using that as early as 1999. And I am not claiming an invention. I do not think anybody is.
Did you know that long before ODE realizes this could be done that way there were other engines doing the same publicly. I did it in Newton.
Or you also think that My solve is a copy of ODE like the stablishment hint in many circles.
In a nut shell this is what he is claim this in three lines of symbolic math:

if in Newton you did the same or similar but nobody know about it that's not public domain knowledge i guess. It looks like that you have misunderstood what im trying to say and im going to try to be clearer here. Im _not_ in favour of patents, however there is a law, if somebody applies for a patent that laws applies if we like it or not. So what im interested in it's not if many other people did the same or bettter in their secret room given that i have no doubts about it. But im more interested to see if it possible to show that at the moment of the application there was sufficient available information (papers/code) in order t invalidate the "invention"

Statistics: Posted by Antonio Martini — Wed Jan 04, 2006 7:59 pm

Projected Gauss Seidel patent and other physics patents

2006-01-04T20:00:43+00:00

sorry double post

Statistics: Posted by Julio Jerez — Wed Jan 04, 2006 7:58 pm