#
Stability and Parallelization Issues in
Solving General Symmetric Linear Systems

Peter Strazdins,*
Stability and Parallelization Issues in
Solving General Symmetric Linear Systems
*,
Department of Computer Science Seminar, ANU, Nov 29 2000;
slides (13 pages, 170K)

## Abstract

In this talk we will begin by describing why the solution of general
symmetric linear systems is an increasingly important computation,
and introduce two applications, Electromagnetic Compatibility analysis
and Data Mining, where such systems can be large and dense.
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.