[ODE] parallel ODE

[Misha Smelyanskiy]

I noticed that you parallelize pivoting algorithm for solving LCP.
  1. Am I write by observing that game community is more in the favor of iterative algorithms, such as PGS (implemented in ODE)?
  2. If this is the case, then one would want to parallelizde PGS, which is difficult due to dependences (within a single island of course).
  Any comments on (1) and (2).
  Thanks everyone for this discussion; it is very useful.
  Mike

Daniel Duhprey <duhprey at yahoo.com> wrote:
  
Sure, http://www.tosos.com/parallelLCP.pdf

I'm not sure if this would be a good way to solve the LCP in parallel, but I 
would like to know if anyone disagrees that it is a way.

On Thu, 23 Feb 2006, Nguyen Binh wrote:

-->It would be nice if you share with us your algorithm.
-->In my knowledge, there are no real good ways to solve LCP in parallel except
-->using iterative methods which is not accurate enough in some applications.
-->
-->
-->On 2/23/06, Daniel Duhprey wrote:
-->>
-->> On Thu, 23 Feb 2006, Misha Smelyanskiy wrote:
-->>
-->> -->Yes that is what I mean. Either stepping islands in parallel, or
-->> parallelizing a single island, if there are only a few islands. For CD, I
-->> mean parallelizing a given space: both broad and narrow phases.
-->> --> Seems like none has done it yet.
-->>
-->> i wrote a paper for a class last year describing an algorithm
-->> parallelizing
-->> the LCP itself. It was a bit of a cheat because the LCP is such a long
-->> winded
-->> algorithm, but it was surprisingly easy (don't tell my professor.) I
-->> haven't
-->> had time to go back and look at incremental algorithms to see if there's
-->> any
-->> advantage there, but I know they still beat my parallelLCP. Anyway I
-->> think
-->> the net result, if I'm reading the right section, is that the original
-->> O(N^3)
-->> process can be done with O(N^3) processors in O(N) time. The "processors"
-->> in
-->> this case need to know only multiply and add, I believe. Probably more
-->> useful
-->> for a FPGA than a CPU, really. I thought it was interesting :)
-->>
-->> --
-->> ------------
-->> email: duhprey at tosos.com www: http://paradox.tosos.com/ icq: 129354442
-->> Computer Science is no more about computers than astronomy is about
-->> telescopes. Dijkstra
-->> The European finds intercourse with Americans easy and
-->> agreeable. Einstein
-->> Not a shred of evidence exists in favor of the idea that life is
-->> serious. Gill
-->> _______________________________________________
-->> ODE mailing list
-->> ODE at q12.org
-->> http://q12.org/mailman/listinfo/ode
-->>
-->
-->
-->
-->--
-->--------------------------------------------------
-->Binh Nguyen
-->Computer Science Department
-->Rensselaer Polytechnic Institute
-->Troy, NY, 12180
-->--------------------------------------------------
-->

-- 
------------
email: duhprey at tosos.com www: http://paradox.tosos.com/ icq: 129354442
Computer Science is no more about computers than astronomy is about telescopes. Dijkstra
The European finds intercourse with Americans easy and agreeable. Einstein
Not a shred of evidence exists in favor of the idea that life is serious. Gill
_______________________________________________
ODE mailing list
ODE at q12.org
http://q12.org/mailman/listinfo/ode
  

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://q12.org/pipermail/ode/attachments/20060223/1d2314f8/attachment-0001.htm