At first sight, the Gauss-Seidel method (and the SOR method which has the same basic structure) seems to be a fully sequential method. A more careful analysis, however, reveals a high degree of parallelism if the method is applied to sparse matrices such as those arising from discretized partial differential equations.
We start by partitioning the unknowns in wavefronts. The first
wavefront contains those unknowns that (in the directed graph of
) have no predecessor; subsequent wavefronts are then sets (this
definition is not necessarily unique) of successors of elements of the
previous wavefront(s), such that no successor/predecessor relations hold
among the elements of this set. It is clear that all elements of a
wavefront can be processed simultaneously, so the sequential time of
solving a system with can be reduced to the number of
wavefronts.
Next, we observe that the unknowns in a wavefront can be computed as soon as all wavefronts containing its predecessors have been computed. Thus we can, in the absence of tests for convergence, have components from several iterations being computed simultaneously. Adams and Jordan [2] observe that in this way the natural ordering of unknowns gives an iterative method that is mathematically equivalent to a multi-color ordering.
In the multi-color ordering, all wavefronts of the same color are
processed simultaneously. This reduces the number of sequential steps
for solving the Gauss-Seidel matrix to the number of colors, which is
the smallest number 
such that wavefront 
contains no
elements that are a predecessor of an element in wavefront 
.
As demonstrated by O'Leary [164], SOR theory still holds in an approximate sense for multi-colored matrices. The above observation that the Gauss-Seidel method with the natural ordering is equivalent to a multicoloring cannot be extended to the SSOR method or wavefront-based incomplete factorization preconditioners for the Conjugate Gradient method. In fact, tests by Duff and Meurant [79] and an analysis by Eijkhout [85] show that multicolor incomplete factorization preconditioners in general may take a considerably larger number of iterations to converge than preconditioners based on the natural ordering. Whether this is offset by the increased parallelism depends on the application and the computer architecture.