Red Black Parallel Gauss Seidel II
In red-black, you color every alternate point red and every other point black
This gives a checkerboard pattern shown on previous foil
Now label update so first update all red points, then update all black points
Updating red points to iterate k only requires black points at level k-1
Updating black points to level k requires NO black points but just read points at level k
So can divide parallel update into two phases
- Phase I: Update all Red Points
- Phase II: Update all Black Points