Next, will look at the dominant algorithm for this computation, called the Bunch-Kaufman algorithm, one of a class of algorithms known as the diagonal pivoting method. After introducing a few simple principles of numerical stability, we will discuss how flaws were recently discovered in the proof of stability of this algorithm, even after a quarter a century of widespread use and acceptance. On the other hand, implementations of this algorithm have very competitive performance, and have been recently shown to be especially suited to parallel implementation.
However, alternative algorithms, also based on the diagonal pivoting method, but with strong guarantees of stability, have been recently proposed. The first is a variant of the Bunch Kaufman algorithm which performs extra searches to find a guaranteed stable pivot at each elimination stage. The second, previously only applied to sparse matrices, searches for any stable pivot within the current elimination block. We will describe these two algorithms and how they can be combined to produce an efficient algorithm for the dense parallel case.
We will then compare the performance of these algorithms by first analysing their pivoting behaviours and then by comparing performance results on a 16 node Fujitsu AP3000. These show that the more accurate algorithms can be made competitive with the original Bunch Kaufman algorithm, and we suggest how further performance improvements may be made.