Ordering, Anisotropy and Factored Sparse Approximate Inverses

Robert Bridson and Wei-Pai Tang

Department of Computer Science, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada


We consider ordering techniques to improve the performance of factored sparse approximate inverse preconditioners, concentrating on the AINV technique of M. Benzi and M. Tuma. Several practical existing unweighted orderings are considered along with a new algorithm, Minimum Z-Priority (MZP), that we propose. We show how good orderings such as these can improve the speed of preconditioner computation dramatically, and also demonstrate a fast and fairly reliable test of how good an ordering is in this respect. Our heuristic reasoning that these orderings should improve convergence of conjugate gradient methods is verified experimentally. We then turn to the effect of anisotropy and argue that weighted orderings, which take into account the numerical values in the matrix, must be considered. After developing a simple heuristic for dealing with anisotropy we propose several practical algorithms to implement it. Our Weighted Nested Dissection ordering shows clear promise for an effective method.