Optimal Convolution SOR Acceleration of Waveform Relaxation with Application to Parallel Simulation of Semiconductor Devices

In this paper we describe a novel generalized successive overrelaxation (SOR) algorithm for accelerating the convergence of the dynamic iteration method known as waveform relaxation. A new waveform convolution SOR algorithm is presented, along with a theorem for determining the optimal convolution SOR parameter. Both analytic and experimental results are given to demonstrate that the convergence of the waveform convolution SOR algorithm is substantially faster than that of the more obvious ordinary waveform SOR algorithm. Finally, to demonstrate the general applicability of this new method, it is used to solve the differential-algebraic system generated by spatial discretization of the time-dependent semiconductor device equations. Results from experiments on serial and parallel machines are presented to indicate a dramatic speedup over a more conventional method such as pointwise GMRES.