Asynchronous waveform relaxation methods for ordinary differential equations on multiprocessors

Abstract

Multiprocessor architecture machines offer promising opportunities to achieve significant speedup in solving large systems of Ordinary Differential Equations (ODEs.) Often, large systems of ODEs have components that vary with different rates. If numerical solution is computed for the system as a whole, the step size will limited by the fastest component. Multirate methods avoid this restriction by partitioning the system of equations into smaller subsystems and integrating each separately. Step sizes are chosen for each subsystem and are synchronized among slow and fast subsystems. A partitioned system of ODEs can be integrated in parallel but synchronization of step sizes can severely limit speedup. The synchronization overhead can be avoided by using waveform relaxation methods that iteratively integrate subsystems. Asynchronous waveform relaxation methods are proposed in this study. By extending the results for synchronous waveform relaxation methods, the asynchronous waveform methods are shown to converge under certain conditions. The design and implementation issues of such methods on multiprocessors as a general purpose code are presented. The performance of the code in solving a variety of systems of ODEs is tested and the results presented. These results show significant speedup can be achieved over sequential waveform methods for the solution of ODEs.