Ordering, anisotropy, and factored sparse approximate inverses

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 inverse penalty (MIP), 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 way of testing how good an ordering is in this respect. Our test results also show that these orderings generally improve convergence of Krylov subspace solvers but may have difficulties particularly for anisotropic problems. We then argue that weighted orderings, which take into account the numerical values in the matrix, will be necessary for such systems. After developing a simple heuristic for dealing with anisotropy we propose several practical algorithms to implement it. While these show promise, we conclude a better heuristic is required for robustness.