BLOCK COLORING SCHEMES FOR THE SOR METHOD ON LOCAL MEMORY PARALLEL COMPUTERS

We introduce the concept of a block colouring which we use to obtain parallel versions of the SOR method. Block colourings are particularly well suited for banded linear systems and finite difference discretizations. We show that on a local memory parallel computer block colour SOR often induces less communicational overhead than the traditional multicolour SOR method. This is confirmed by numerical experiments with two simple examples on a 64-processor binary tree computer. © 1990.