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.
