next up previous
Next: Node-tearing Nodal Analysis Up: The Preprocessing Phase Previous: Ordering the Matrix

Ordering the Last Diagonal Block

The application of diakoptic techniques yields a block-diagonal-bordered matrix form that identifies the basic network structure and provides parallelism for the majority of calculations within a Gauss-Seidel iteration. However, without additional ordering, the last diagonal block would be purely sequential, limiting the potential speedup of the algorithm in accordance with Amdahl's law. The last diagonal block represents the interconnection structure within the equations that couple the partitions found in the previous step. In other words, the variables in the last-diagonal block are the interconnections within the equations that tie the entire matrix together. Graph multi-coloring has been used for ordering this portion of the matrix --- all nodes of the same color share no interconnections, consequently, the values of in these rows can be calculated in any order without violating the strict precedence rules in the Gauss-Seidel method. As a result, rows within a color can be solved in parallel.

The multi-coloring algorithm we selected for this work is based on the saturation degree ordering algorithm. We also require load balancing, a feature not commonly implemented within graph multi-coloring. As part of our implementation we added a feature that equalizes the number of rows per color to provide some basic load balancing. The graph multi-coloring technique is discussed in greater detail in section 7.



David P. Koester
Sun Oct 22 15:29:26 EDT 1995