Title: Department of Computer Science Seminar
Date: Wed, Nov. 29, 2000
Time: 11:00 am to 12:00pm
Venue: Room N101, CSIT Building [108]
Speaker: Dr Peter Strazdins (Department of Computer Science, Australian National University)
Description: "Stability and Parallelization Issues in
                 Solving General Symmetric Linear Systems"


                        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 behaviors 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. 




URL: http://cs.anu.edu.au/lib/seminars/seminars00/dept20001129b

Biography:

Peter Strazdins has been a Lecturer in the Department of Computer
Science at ANU and a Research Fellow of the ANU-Fujitsu CAP Project
since 1990.  He has worked extensively on dense linear algebra
algorithms and libraries on high performance (especially distributed
memory) computers.  Currently, he is leader of the CAP Program which is
focusing on operating systems and memory hierarchy architecture for
large scale shared memory computers.