In the previous section, we developed the theoretical foundations of
parallel Gauss-Seidel methods with block-diagonal-bordered sparse
matrices, and now we will discuss the procedures required to generate
the permutation matrices, , to produce
block-diagonal-bordered/multi-colored sparse matrices so that our
parallel Gauss-Seidel algorithm is efficient. We must reiterate that
all parallelism for our Gauss-Seidel algorithm is identified from the
interconnection structure of elements in the sparse matrix during this
preprocessing phase. We must order the sparse matrix in such a manner
that processor loads are balanced. The technique we have chosen for
this preprocessing phase is to:
This preprocessing phase incurs significantly more overhead than solving a single instance of the sparse matrix; consequently, the use of this technique will be limited to problems that have static matrix structures that can reuse the ordered matrix and load balanced processor assignments multiple times in order to amortize the cost of the preprocessing phase over numerous matrix solutions.