[petsc-dev] Parallel Gauss - Seidel

[Jed Brown]

On Sun, Jun 10, 2012 at 12:30 PM, Barry Smith <bsmith at mcs.anl.gov> wrote:

>   For clarification it sounds like you color your matrix (with independent
> sets) and then march through the colors, each color gets smoothed (in
> parallel since they are independent) then on to the next color?


Not independent sets, just by data dependency. For example, everyone
relaxes a block along the right boundary (implying an ordering that visits
those blocks in rank order, except that those strips never touch each other
so they can be done in parallel), then send the updated state to the proc
on the right. While waiting for the message, he might smooth another set
that does not have a data dependency. When a process receives the first
message (from the proc to the left), it can relax that part. There is a
picture in Mark's paper that should make the algorithm clear. This approach
doesn't suffer from the atrocious memory access pattern of classical
coloring; it's also asynchronous and completes with fewer messages in total.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-dev/attachments/20120610/4353f218/attachment.html>