Massimiliano Ferronato
A Factored Sparse Approximate Inverse software package (FSAIPACK) for the parallel preconditioning of linear systems

University of Padova
via Trieste 63
35121 Padova
Italy
ferronat@dmsa.unipd.it
Carlo Janna
Giuseppe Gambolati
Flavio Sartoretto

The Factored Sparse Approximate Inverse (FSAI) is a well-known preconditioner for Symmetric Positive Definite (SPD) linear systems $A{\bf x}={\bf b}$ . The native FSAI algorithm was originally introduced by Kolotilina and Yeremin [1] about 20 years ago. They proposed a Frobenius norm minimization procedure for computing an explicit sparse approximation of the inverse of the exact lower Cholesky factor of $A$ . FSAI is a robust preconditioner featuring attractive theoretical properties, however its performance in the solution of SPD systems often proves lower than that of other competing approximate inverses, such as AINV [2] or SPAI [3]. Recently, FSAI has experienced a renewed interest in connection with the growing popularity and diffusion of parallel computers. Since its computation proceeds independently row-by-row, it can be easily and efficiently distributed among many processors. Such an interest has led to the development of a number of variants that aim at improving its performance.

A crucial factor for attaining good FSAI quality and efficiency is the selection of an appropriate sparsity pattern. Originally, the algorithm was conceived assuming that a pattern $\cal{S}$ for the non-zero entries of the preconditioner is statically guessed by the user. Based upon Neumann series expansion of $A^{-1}$ , a typical setting assumes taking as $\cal{S}$ the lower part of the pattern of a small power of $A$ , or of a sparsified $A$ [4]. A post-filtration of the resulting FSAI factor is also recommended [5]. More recently, a dynamic pattern computation strategy has been proposed [6]. It is based upon adaptively choosing for each row the most significant terms to be retained. Another interesting strategy consists of building the preconditioner recursively, i.e., computing a dense and high quality FSAI as the product of a few sparse factors [7].

Identifying the most efficient technique for generating an FSAI non-zero pattern is strongly problem-dependent. In most cases, a combination of existing strategies provides the best efficiency. For example, it is often a good idea to generate a very sparse static pattern using a small power of the sparsified $A$ , and then improve it by means of a few steps of a dynamic procedure. Alternatively, one can build a symbolic FSAI dynamically, and then compute the preconditioner using the symbolic factor as the pattern.

This communication describes a new software package, called FSAIPACK, that collects a comprehensive set of algorithms for computing FSAI preconditioners in a parallel computational environment. FSAIPACK implements the following methods:

• FSAI computation given a prescribed ``static'' pattern;
• generation of the pattern via a sparsified matrix power;
• dynamic computation using an adaptive pattern generation;
• dynamic computation using a self-preconditioned inner iteration;
• recurrent FSAI construction as the product of several factors;
• FSAI post-filtration strategy.

The detailed algorithm of each method is given in [8]. In this context, the dynamic computation of FSAI via a self-preconditioned inner iteration is a novel method not advanced before. FSAIPACK allows for combining different strategies to build the non-zero pattern $\cal{S}$ , both in static and dynamic ways, thus better exploiting the preconditioner potential. Different strategies can be easily combined by using an ad hoc command language, that offers high flexibility and ease of use. FSAIPACK is coded in Fortran90, using OpenMP directives for shared memory parallel computations. The package is freely available, for research purposes, at the website

http://www.dmsa.unipd.it/~janna/software.html

An open source driver implementing the command language interface is included.

The scope of this work is to collect a comprehensive set of techniques for building FSAI preconditioners into an integrated computational environment, thus providing the user with a flexible and efficient tool that can be easily incorporated into existing codes. The FSAIPACK potential is demonstrated by a set of numerical experiments that combine static and dynamic preconditioners and prove more cost effective than any single algorithm. In particular, our experiments show that combining different methods for building FSAI can significantly improve the native preconditioner quality, becoming fully competitive with, and often superior to, other approximate inverse techniques.

References:

[1] L.Y. Kolotilina and A.Y. Yeremin, Factorized sparse approximate inverse preconditioning I. Theory, SIAM Journal on Matrix Analysis and Applications, 14 (1993), 45-58.

[2] M. Benzi, C.D. Meyer, and M. Tuma, A sparse approximate inverse preconditioner for the conjugate gradient method, SIAM Journal on Scientific Computing, 17 (1996), 1135-1149.

[3] M. Grote and T. Huckle, Parallel preconditioning with sparse approximate inverses, SIAM Journal on Scientific Computing, 18 (1997), 838-853.

[4] E. Chow, A priori sparsity patterns for parallel sparse approximate inverse preconditioners, SIAM Journal on Scientific Computing, 21 (2000), 1804-1822.

[5] L.Y. Kolotilina and A.Y. Yeremin, Factorized sparse approximate inverse preconditioning. IV. Simple approaches to rising efficiency, Numerical Linear Algebra with Applications, 6 (1999), 515-531.

[6] C. Janna and M. Ferronato, Adaptive pattern research for Block FSAI preconditioners, SIAM Journal on Scientific Computing, 33 (2011), 3357-3380.

[7] L. Bergamaschi and A. Martinez, Banded target matrices and recursive FSAI for parallel preconditioning, Numerical Algorithms, 61 (2012), 223-241.

[8] C. Janna, M. Ferronato, G. Gambolati, and F. Sartoretto, FSAIPACK: a software package for high performance Factored Sparse Approximate Inverse preconditioning, ACM Transactions on Mathematical Software, submitted.