Richard Pancer, Department of Computer Science, University of Toronto:

The Parallel Solution of ABD Systems Arising in Numerical Methods for BVPs for ODEs

Many numerical algorithms for the solution of Boundary Value Problems (BVPs) for Ordinary Differential Equations (ODEs) contain significant components that can be parallelized easily, and this parallelization can result in substantial speedups on machines with a modest number of processors. An important step in most of these algorithms, and often the most computationally-intensive step, is the numerical solution of an Almost Block Diagonal (ABD) system of linear algebraic equations. The parallelization of this step is not so straightforward as the obvious approach leads to a potentially unstable algorithm. The proper treatment of the ABD system has proven to be a challenge in the design of parallel BVP codes.

In this talk we present three algorithms for the parallel solution of ABD systems. Two of the algorithms, SLF-QR and SLF-LU, were discovered independently by us and by S.J. Wright in the 1990s. These algorithms use standard QR and LU factorizations, respectively, to control stability. In earlier papers, Wright proved SLF-QR is stable and showed SLF-LU is stable under certain assumptions.

The third algorithm, RSCALE, is based on a notably different numerical technique which reduces fill-in and local operation counts. RSCALE is more than twice as fast as SLF-QR and marginally faster than SLF-LU. Moreover, we show that a variant of SLF-LU is potentially unstable on a surprising number of randomly-generated, well-posed problems. Since these problems pose no difficulty for either of the other two algorithms, we believe that SLF-QR, not SLF-LU, may be RSCALE's nearest competitor in terms of both speed and reliability.