Ifpack2 Templated Preconditioning Package  Version 1.0
Trilinos/Ifpack2: Incomplete factorizations, relaxations, and domain decomposition for Tpetra objects

# What is Ifpack2?

Ifpack2 provides incomplete factorizations, relaxations, and domain decomposition operators for linear algebra objects (sparse matrices, operators, and dense vectors and multivectors) provided by the Tpetra package. You may use these operators however you wish: for example as preconditioners in an iterative solver, or as smoothers for algebraic multigrid.

Ifpack2 aims at offering the same functionality as the Ifpack package, though it does not promise backwards compatibility. Ifpack only works for Epetra linear algebra objects; Ifpack2 only works for Tpetra objects.

# Why Ifpack2?

Why do you want to use Ifpack2? First, if you are using Tpetra, you need to use Ifpack2 if you want incomplete factorizations, relaxations, or domain decomposition. Second, Ifpack2 gives you the same advantages as Tpetra. You can solve problems with more than two billion unknowns, by using 64-bit global indices, yet save memory at the same time by only storing 32-bit local indices. You can use matrices and vectors with any sensible data type, not just double. For example, you can use float to save memory, or an extended-precision type like dd_real or qd_real to improve robustness for difficult problems. Ifpack2 even works with complex-valued data, like std::complex<float> and std::complex<double>. Finally, Ifpack2's algorithms use and produce Tpetra objects, so you can exploit Tpetra's hybrid (MPI + threads) parallelism features without effort.

# Methods that Ifpack2 implements

## Relaxations and smoothers

Ifpack2 implements the following relaxations, smoothers, and related preconditioners:

• Diagonal scaling
• Jacobi (with optional damping)
• Gauss-Seidel
• Successive Over-Relaxation (SOR)
• Symmetric versions of Gauss-Seidel and SOR
• Chebyshev iteration (as a smoother)

Gauss-Seidel is actually a special case of SOR, when the damping parameter $$\omega = 1$$. Ifpack2 calls them both "Gauss-Seidel." You may specify the sweep direction: forward, backward, or symmetric (first forward, then backward). We do not currently implement other sweep directions or parallelization schemes (such as red-black ordering), but you may reorder the rows yourself if you have a specific sweep direction in mind.

Ifpack2's implementation of (Gauss-Seidel and) SOR is actually a "hybrid" relaxation. This means that it only performs SOR within an MPI process, but does Jacobi-type updates between MPI processes. While this can reduce effectiveness of the algorithms as preconditioners or smoothers, Ifpack2 implements an "L1" option to improve convergence despite this. For details, please refer to the following publication:

A. H. Baker, R. D. Falgout, T. V. Kolev, and U. M. Yang. "Multigrid Smoothers for Ultraparallel Computing." SIAM J. Sci. Comput., Vol. 33, No. 5 (2011), pp. 2864-2887.

For diagonal scaling, see the Ifpack2::Diagonal class. The Ifpack2::Relaxation class implements Jacobi, Gauss-Seidel, SOR, and the symmetric variants of the latter two. The Ifpack2::Chebyshev class implements Chebyshev iteration.

## Incomplete factorizations

Ifpack2 implements two different incomplete factorizations: ILUT (Ifpack2::ILUT) and RILU(k) (Ifpack2::RILUK). ILUT is a threshold-based incomplete LU factorization, and RILU(k) is a "relaxed" incomplete LU with level k fill.

Both of these only perform the factorization on a matrix in a single MPI process.

Our ILUT implementation factors each MPI process' part of the matrix independently, and treats multiple processes via nonoverlapping domain decomposition. Our RILU(k) implementation's factorization reaches across processes by overlapping off-process entries up to a specified integer level of overlap, and factoring them redundantly on each process. For details on each algorithm and its options, please refer to the specific class' documentation. Also, for ILUT, please refer to the following publication:

Youcef Saad, "ILUT: A dual threshold incomplete LU factorization," Numer. Linear Algebra Appl., Vol. 1 (1994), pp. 387-402.

## Domain decomposition

Finally, Ifpack2 implements additive Schwarz domain decomposition, via the Ifpack2::AdditiveSchwarz class. The user may specify any subdomain solver they wish.

# Interface to Ifpack2 methods

All Ifpack2 operators inherit from the base class Ifpack2::Preconditioner. This in turn inherits from Tpetra::Operator. Thus, you may use an Ifpack2 operator anywhere that a Tpetra::Operator works. For example, you may use Ifpack2 operators directly as preconditioners in Trilinos' Belos package of iterative solvers.

You may either create an Ifpack2 operator directly, by using the class and options that you want, or by using Ifpack2::Factory. Ifpack2::Factory is templated on a specialization of Tpetra::CrsMatrix. The Factory will use that template parameter to get all the information that it needs to make a preconditioner of the right type. All the specific Ifpack2 operators are also templated on a specialization of Tpetra::CrsMatrix. Some of them only accept a Tpetra::CrsMatrix instance as input, while others also may accept a Tpetra::RowMatrix (the base class of Tpetra::CrsMatrix). Some Ifpack2 methods prefer a Tpetra::CrsMatrix, because they can use faster computational kernels in that case. Those methods may try to guess whether your Tpetra::RowMatrix is really a Tpetra::CrsMatrix.

# Examples

The ifpack2/test/belos directory includes a test program which shows how to create Ifpack2 operators and use them as preconditioners with Belos iterative solvers. See belos_solve.cpp and belos_extprec_solve.cpp in that directory. The test program is entirely driven by XML input files, which specify the matrix file to be used, as well as parameters for the preconditioner, and the Belos iterative solver type to use.

If you build Belos with examples enabled, the example will build as Ifpack2_tif_belos.exe and will be installed in the packages/ifpack2/test/belos directory.