Two-Stage Preconditioners Using Wavelet Band Splitting
                       and Sparse Approximation


                        Tony F. Chan  and Ke Chen


                                July 24, 2000



                                   ABSTRACT

        The wavelet sparse approximate inverse preconditioners previously 
studied are re-examined and improved for iterative solution of sparse linear
systems arising from PDE's.  Our new idea is to improve the approximation of
a wavelet transformed matrix by banded matrices based on treating smooth and 
non-smooth splittings differently in a two-stage preconditioning setting. 
We introduce the concept of a wavelet band splitting and use it to derive a theoretical result on our two-stage preconditioners. Our preconditioner combines simple sparse scaling preconditioning with wavelet sparse approximate
inversion.  We propose an iterative method for finding the optimal splitting
that minimises the wavelet band approximation errors for the diagonal case. 
Preliminary numerical experiments have been successful.



AMS subject class: 65Y05, 65F35, 65Y20.

Keywords: Preconditioning, band splitting and approximation, 
          sparse matrices, wavelets, minimization.


________________________________
   Department of Mathematics, University of California, Los Angeles, 
      CA 90095-1555, USA. Email: chan@math.ucla.edu.
                            Web: http://www.math.ucla.edu/~chan

   Department of Mathematical Sciences, University of Liverpool, Peach Street,
      Liverpool L69 7ZL, UK. Email: k.chen@liverpool.ac.uk. 
                               Web: http://www.liv.ac.uk/~cmchenke