10 Preconditioners
In general, for iterative methods, choosing a preconditioner matrix such that reduces the number of iterations required for convergence. A computation of the form “” appearing in the algorithms corresponds to “approximately solving for ”. Improving the accuracy of this approximation reduces the number of iterations, but increases the overhead of this part of the computation. In non-parallel computation, the incomplete LU factorization is often used for this approximation, but parallel computation requires a parallel method for the preconditioning computation. This library adopts the point Jacobi, block Jacobi, and Jacobi methods as parallel preconditioners. The notation follows the conventions given at the beginning of the Linear Solvers chapter.
The preconditioner is selected by passing one of the following values to the solver’s set_precon_algo(). In the sample programs it can be specified at compile time with -Dparcel_solver_precon_algo=<value> and at run time with the environment variable PARCEL_PRECON=<value>.
| Value | Constant | Preconditioner | Associated settings |
|---|---|---|---|
| 0 | parcel::PRECON_NONE |
No preconditioning () | None |
| 1 | parcel::PRECON_POINTJACOBI |
Point Jacobi preconditioner | None |
| 2 | parcel::PRECON_BLOCKJACOBI |
Block Jacobi preconditioner (ILU(0) within blocks) | set_blockjacobi(nb), set_scaling_matrix(), set_scaling_vector() |
| 4 | parcel::PRECON_JACOBI |
Jacobi preconditioner | set_jacobi(ITER), set_scaling_matrix(), set_scaling_vector() |
Below, the coefficient matrix is split as ( is the diagonal part, and and are the strictly lower and strictly upper triangular parts), and we write . Each algorithm shows the content of one application of the preconditioner, “”.
10.1 Scaling
Matrix scaling and vector scaling can be combined with the block Jacobi and Jacobi preconditioners. Both are intended to keep values within the representable range of low precision (half precision). They can be specified explicitly with set_scaling_matrix() and set_scaling_vector(); if not specified, they are determined automatically as follows.
Block Jacobi preconditioner: always enabled for both the matrix and the vector
Jacobi preconditioner: enabled only when the arithmetic precision of the preconditioner or the storage precision of the preconditioner matrix is half precision (disabled for double and single precision)
Matrix scaling: computes from the maximum absolute value of each row and scales the rows with .
Vector scaling: divides the preconditioner input by ( when matrix scaling is disabled), applies the preconditioner, and multiplies the result by . Since this is a linear operation, it does not change the action of the preconditioner.
Which preconditioners have their action changed by matrix scaling is described in each section.
10.2 Point Jacobi Preconditioner [1]
Only the diagonal entries of the coefficient matrix are used as the preconditioner matrix (). Its effect is smaller than that of other preconditioners such as the incomplete LU factorization, but each row can be processed independently and no interprocessor communication is needed. For rows whose diagonal entry is 0, the diagonal element of is replaced with 1. No scaling is performed.
Selection:
set_precon_algo(parcel::PRECON_POINTJACOBI)(value 1)Algorithm
is a diagonal element of , is a diagonal element of , and is the number of rows owned by each MPI process.
Lines 1 to 7 are performed only once, when the preconditioner matrix is built. The preconditioner is applied as follows.
10.3 Jacobi Preconditioner [1]
The Jacobi preconditioner is a PARCEL-specific preconditioner that approximately solves by Jacobi iteration. Since there are no dependencies between rows within one iteration, it is a preconditioner suited to GPUs. The number of iterations is specified with set_jacobi(ITER) (default 1; in the sample programs, at compile time with -DJACOBI_ITER=<value>).
- Selection:
set_precon_algo(parcel::PRECON_JACOBI)(value 4) andset_jacobi(ITER)
When the preconditioner matrix is built, is computed and stored (for rows with , the element of is set to 1). By default (except in builds for A64FX) the values of are not stored; line 5 computes on the fly from the values of and (rounded to the preconditioner matrix precision in the same way as when stored, so the values are the same; to use memory for speed, build with -DPARCEL_JACOBI_ONTHEFLY=0, see “Choosing Between Memory and Speed”). A diagonal element must be stored in every row. PARCEL does not check this, so if a row has no stored diagonal element, the result of the preconditioner is invalid. The preconditioner is applied as follows. is 1 when vector scaling is disabled.
- Algorithm
Line 5 is equivalent to , and the iteration starts from the initial value . Therefore the action is which equals Jacobi iterations (damping factor 1) from a zero initial value. Even with , , which differs from the point Jacobi preconditioner ().
shares the row pointers and column indices of the coefficient matrix without copying them. When the values are stored (-DPARCEL_JACOBI_ONTHEFLY=0, or the cases excluded below), only the values are held, in the same order as (0 at the diagonal positions); line 5 skips the diagonal using the diagonal position recorded for each row. By default the values of are also read at every application. Each solver builds the preconditioner inside solver() and uses it only there (as do the inner linear solvers of the eigenvalue solvers), so in normal use it suffices not to destroy or modify while solver() is running (changing the values of between calls is fine, because the preconditioner is rebuilt at every call). If you construct and use a preconditioner matrix parcel::precon_matrix directly (e.g. external_precon of pgmres; not normally done), do not destroy or modify before you finish using it. With (the default), no work vectors for the iteration are allocated.
The values of are computed on the fly for CRS matrices when matrix scaling is disabled and none of the coefficient matrix, the preconditioner matrix and the preconditioner computation precision is double-double. Half-precision (FP16) preconditioners enable matrix scaling by default, so they store the values. In the excluded cases the values are stored, as with -DPARCEL_JACOBI_ONTHEFLY=0.
In MPI parallel runs, the halo of ( in the first iteration) is communicated before line 5. Since is defined as a global matrix including communication, the action of the preconditioner does not depend on the number of MPI partitions.
When matrix scaling is enabled, and are built from , and is multiplied by in line 2. Since and are divided by the same factor, and are unchanged, and the action of the preconditioner does not change (except for rounding errors).
10.4 Block Jacobi Preconditioner [1]
The block diagonal part of the coefficient matrix is taken as the preconditioner matrix , and the incomplete LU factorization without fill-in (ILU(0)) is used within each block. Entries outside the blocks are ignored. Since the rows owned by each MPI process are divided into contiguous blocks (with or rows each), no block spans processes, no communication is needed, and each block can be processed fully in parallel. On the other hand, the action of the preconditioner depends on the number of MPI partitions and on .
- Selection:
set_precon_algo(parcel::PRECON_BLOCKJACOBI)(value 2). The number of blocks is specified withset_blockjacobi(nb). If not specified, the number of threads per MPI process is used on CPUs, and the value giving 2 rows per block () is used on GPUs.
ILU(0) is an incomplete LU factorization that, when approximately factoring a square matrix into the product of a lower triangular matrix and an upper triangular matrix , does not allow values to enter positions other than the nonzero positions (nonzero pattern) of (fill-in). By ignoring fill-in, the memory usage of the factored matrix is kept the same as that of the original matrix.
- Algorithm (building the preconditioner matrix; ILU(0) within blocks)
and are the first and last rows of block , and is the nonzero pattern of . overwrites a copy of the elements of .
After the factorization, (a unit lower triangular matrix) is formed from the strictly lower triangular part within the block and unit diagonal elements, and from the upper triangular part including the diagonal.
- Algorithm (applying the preconditioner)
and are elements of and , is the matrix scaling factor (1 when disabled), and is the vector scaling factor (1 when disabled).
Even when matrix scaling is enabled, the ILU(0) factorization is applied to the unscaled , and the input is multiplied by in line 4. The action is therefore (), and unlike the Jacobi preconditioner, the action of the preconditioner changes depending on whether matrix scaling is used. For a matrix in which is the same in all rows (e.g., a 7-point difference matrix with center -6), is a scalar multiple, which does not affect the iterations of the linear solver, but the eigenvalues of change by that factor.
Finer blocks increase parallelism, but weaken the effect of the preconditioner because more entries are ignored. How to choose on GPUs is shown in “Preconditioners” in “Choosing a Solver”.