Sparsified And Incomplete Sparse Factored Inverse Preconditioners

Incomplete LU factorization is a valuable preconditioning approach for sparse iterative solvers. An "ideal" preconditioner for the iterative solution of Ax = b is A \Gamma1 itself. This paper describes a preconditioner based on sparse approximations to the inverses and partitioned inverses of the L and U factors of A. These inverses and partitioned inverses are normally somewhat sparse. Their sparsity can be enhanced with suitable ordering and partitioning algorithms. Sparse approximations to these partitioned inverses can be obtained by discarding selected nonzero entries of these inverses. Experimental results indicate that the use of these approximate partitioned inverses as preconditioners results in excellent highly parallel preconditioners. The reasons for this performance are: first, perturbations to certain entries in these partitioned inverses do not propagate to the entire solution vector; second, the numerical values of many of these partitioned nonzero entries are quite ..