This video shows how to divide space for parallelising Laplacian operations on a rectangular grid in 2D or 3D. A 2D grid can be partitioned into strips or square blocks, but partioning into diamonds is best, because communicated boundary data in most cases are used twice. It is shown how this approach can be made practical so that we can tile the whole grid with diamonds.
In 3D, communication is even more important than in 2D, and we can save up to a factor of 1.68 in communication cost by using truncated octahedra as the basic grid cell to assign to a processor.
A good partitioning with diamond-like processor boundaries can also be obtained by translating the grid to a sparse matrix, then partitioning this matrix using the Mondriaan partitioner, and finally translating the solution to a partitioning of the grid.
This video corresponds to Section 4.9 of the book Parallel Scientific Computation: A Structured Approach Using BSP, Second Edition, by Rob H. Bisseling, Oxford University Press, 2020.
An expanded set of slides, solutions to the homework questions, and software accompanying the book can all be found on my personal book page:
https://webspace.science.uu.nl/~bisse101/Book2/psc2
