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 eas-ily, and recent investigations have shown that substantial speedups are attainable 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 certain characteristics of the problem make it difficult to apply standard divide-and-conquer techniques in order to arrive at a stable parallel algorithm. In the past, sev-eral algorithms have been proposed for the parallel solution of the ABD system, but many are potentially unstable or offer only limited parallelism. The proper treatment of the ABD system has proven to be a challenge in the design of parallel BVP codes. In this thesis we present three parallel algorithms for the numerical solution of ABD sys-tems. A parallel algorithm for this problem can be up to ¢¡¤£¦¥¨§ © times faster than the fastest sequential algorithm, where the fastest sequential algorithm requires steps. Each parallel algorithm we present attains this theoretically optimal speedup if enough processors are avail