Analysis, Implementation, and Evaluation of Vaidya's Preconditioners

                                    
                                  Sivan Toledo
                               Tel-Aviv University

A decade ago Pravin Vaidya proposed a new class of preconditioners and a new 
technique for analyzing preconditioners. Preconditioners are essentially 
easy-to-compute approximate inverses of matrices that are used to speed up 
iterative linear solvers. Vaidya proposed several families of 
preconditioners. The simplest one is based on maximum spanning trees (MST) of 
the underlying graph of the matrix. The second one augments the MST with 
extra edges to speed up convergence. A third, which Vaidya only mentioned 
briefly, is based on a maximum-weight basis (MWB) of the matroid associated 
with the graph of the matrix.

In this talk I will describe 
* a detailed experimental study of the first two families, which have never
  been implemented or tested before,
* a theoretical analysis of the convergence properties of the third
  family, based on MWB, which has never been investigated before, and
* an efficient algorithm for constructing preconditioners from Vaidya's 
   third family.

Our results show that on large 2D problems, Vaidya's preconditioners 
outperform widely-used preconditioners, such as drop-tolerance modified and 
unmodified incomplete Cholesky preconditioners.

Our full analysis of Vaidya's MWB preconditioners utilizes graph theory, 
advanced algorithms and data structures, and a new algebraic tool due to 
Boman and Hendrickson to analyze the numerical behavior of preconditioners.

The talk describes joint work with my student Doron Chen.