Circuit partitioning and iteration scheme for waveform relaxation on multicomputers

An algorithm is presented for the global iteration in the waveform relaxation method for circuit simulation: the n-colored Gauss-Seidel algorithm. The authors also investigate a simple method for circuit partitioning, the source-drain partitioning. These methods are compared with others in experiments on both sequential and concurrent computers. One conclusion is that the n-colored algorithm can be used successfully when the number of subsystems in the circuit is significantly larger than the number of nodes in the multicomputer. The source-drain partitioning algorithm gives improved convergence rates for all test cases but fails to decrease the CPU time for some circuits, since model evaluation time per iteration increases