Is a checkerboard block decomposition of a matrix useful when solving a linear system with a parallel conjugate gradient method?

Question

According to these lecture notes, a checkerboard block decomposition should exhibit better scalability when applied to parallel matrix-vector multiplication (presumably because of greater cache hit rate). Since the conjugate gradient method also uses a matrix-vector multiplication, I would think that this form of block decomposition would be common place, if not standard. However, when I look at software like PETSc, it seems that row or column striped block decomposition is more common. Is there any advantage to row or column striped block decomposition of the matrix over the checkerboard counterpart for a parallel conjugate gradient method (other than, perhaps, ease of coding)?

Answer 1

These lecture notes apply to dense matrices. Krylov methods like CG are most commonly used with sparse matrices. PETSc's most commonly used matrix formats are also intended for sparse matrices. Assuming a good ordering, sparse matrices tend to have good locality in the sense that there are many more entries in the "diagonal block" (relating owned parts of the vector to owned parts of the vector) than in the "off-diagonal block". In these cases, a block row (or column) partition is practical and close to optimal.

For dense matrices, there are communication advantages to using block- or element-cyclic distributions for the matrix. ScaLAPACK uses a block-cyclic distribution. Jack Poulson's Elemental library (see this paper and references therein) demonstrates advantages of elemental cyclic distributions.