PARCEL SYCL v1.2 / User Guide User Guide API Reference Search Download 日本語

10 Preconditioners

In general, for iterative methods, choosing a preconditioner matrix such that K≈AK \approx A reduces the number of iterations required for convergence. A computation of the form “solvezfromKz=r\mathrm{solve}\ z\ \mathrm{from}\ Kz = r” appearing in the algorithms corresponds to “approximately solving Az=rAz = r for zz”. 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 (z=rz = r) 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 A=LA+DA+UAA = L_A + D_A + U_A (DAD_A is the diagonal part, and LAL_A and UAU_A are the strictly lower and strictly upper triangular parts), and we write R=LA+UAR = L_A + U_A. Each algorithm shows the content of one application of the preconditioner, “solvezfromKz=r\mathrm{solve}\ z\ \mathrm{from}\ Kz = r”.


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.

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 AA are used as the preconditioner matrix KK (K=DAK = D_A). 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 KK is replaced with 1. No scaling is performed.

aiia_{ii} is a diagonal element of AA, did_{i} is a diagonal element of K−1K^{-1}, and nlocaln_{local} is the number of rows owned by each MPI process.

  1. fori=1,…,nlocalinparallel\mathrm{for}\ i = 1,\ldots,n_{local}\ \mathrm{in}\ \mathrm{parallel}
  2.   ifaii=0then\mathrm{if}\ a_{ii} = 0\ \mathrm{then}
  3.     di=1d_{i} = 1
  4.   else\mathrm{else}
  5.     di=1/aiid_{i} = 1\ /\ a_{ii}
  6.   endif\mathrm{endif}
  7. end\mathrm{end}

Lines 1 to 7 are performed only once, when the preconditioner matrix is built. The preconditioner is applied as follows.

  1. fori=1,…,nlocalinparallel\mathrm{for}\ i = 1,\ldots,n_{local}\ \mathrm{in}\ \mathrm{parallel}
  2.   zi=diriz_{i} = d_{i}r_{i}
  3. end\mathrm{end}


10.3 Jacobi Preconditioner [1]

The Jacobi preconditioner is a PARCEL-specific preconditioner that approximately solves Az=rAz = r by Jacobi iteration. Since there are no dependencies between rows within one iteration, it is a preconditioner suited to GPUs. The number of iterations ITERITER is specified with set_jacobi(ITER) (default 1; in the sample programs, at compile time with -DJACOBI_ITER=<value>).

When the preconditioner matrix is built, DA−1D_A^{-1} is computed and stored (for rows with aii=0a_{ii} = 0, the element of DA−1D_A^{-1} is set to 1). By default (except in builds for A64FX) the values of B=DA−1RB = D_A^{-1}R are not stored; line 5 computes bij=di−1aijb_{ij} = d_i^{-1}a_{ij} on the fly from the values of AA and DA−1D_A^{-1} (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. ψ\psi is 1 when vector scaling is disabled.

  1. ψ=max⁡i|ηiri|\psi = \max_{i}|\eta_{i}r_{i}|
  2. c=DA−1r/ψc = D_{A}^{-1}r\ /\ \psi
  3. z(0)=cz^{(0)} = c
  4. fork=1,…,ITER\mathrm{for}\ k = 1,\ldots,ITER
  5.   z(k)=c−Bz(k−1)z^{(k)} = c - Bz^{(k - 1)}
  6. end\mathrm{end}
  7. z=ψz(ITER)z = \psi z^{(ITER)}

Line 5 is equivalent to z(k)=z(k−1)+DA−1(r/ψ−Az(k−1))z^{(k)} = z^{(k-1)} + D_A^{-1}(r/\psi - Az^{(k-1)}), and the iteration starts from the initial value z(0)=DA−1r/ψz^{(0)} = D_A^{-1}r/\psi. Therefore the action is K−1=∑l=0ITER(−DA−1R)lDA−1K^{-1} = \sum_{l=0}^{ITER}\left( -D_A^{-1}R \right)^{l}D_A^{-1} which equals ITER+1ITER + 1 Jacobi iterations (damping factor 1) from a zero initial value. Even with ITER=1ITER = 1, K−1=DA−1−DA−1RDA−1K^{-1} = D_A^{-1} - D_A^{-1}RD_A^{-1}, which differs from the point Jacobi preconditioner (K−1=DA−1K^{-1} = D_A^{-1}).

BB shares the row pointers and column indices of the coefficient matrix AA 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 AA (0 at the diagonal positions); line 5 skips the diagonal using the diagonal position recorded for each row. By default the values of AA 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 AA while solver() is running (changing the values of AA 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 AA before you finish using it. With ITER=1ITER = 1 (the default), no work vectors for the iteration are allocated.

The values of BB 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 z(k−1)z^{(k-1)} (cc in the first iteration) is communicated before line 5. Since BB 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, DA−1D_A^{-1} and BB are built from ηiaij\eta_i a_{ij}, and rr is multiplied by ηi\eta_i in line 2. Since DAD_A and RR are divided by the same factor, BB and cc 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 AA is taken as the preconditioner matrix KK, and the incomplete LU factorization without fill-in (ILU(0)) is used within each block. Entries outside the blocks are ignored. Since the nlocaln_{local} rows owned by each MPI process are divided into nbnb contiguous blocks (with ⌊nlocal/nb⌋\lfloor n_{local}/nb \rfloor or ⌊nlocal/nb⌋+1\lfloor n_{local}/nb \rfloor + 1 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 nbnb.

ILU(0) is an incomplete LU factorization that, when approximately factoring a square matrix AA into the product of a lower triangular matrix LL and an upper triangular matrix UU, does not allow values to enter positions other than the nonzero positions (nonzero pattern) of AA (fill-in). By ignoring fill-in, the memory usage of the factored matrix is kept the same as that of the original matrix.

𝑓𝑖𝑟𝑠𝑡b\mathit{first}_{b} and 𝑙𝑎𝑠𝑡b\mathit{last}_{b} are the first and last rows of block bb, and PP is the nonzero pattern of AA. aija_{ij} overwrites a copy of the elements of AA.

  1. forb=1,…,nbinparallel\mathrm{for}\ b = 1,\ldots,nb\ \mathrm{in}\ \mathrm{parallel}
  2.   fori=𝑓𝑖𝑟𝑠𝑡b+1,…,𝑙𝑎𝑠𝑡b\mathrm{for}\ i = \mathit{first}_{b} + 1,\ldots,\mathit{last}_{b}
  3.     fork=𝑓𝑖𝑟𝑠𝑡b,…,i−1with(i,k)∈P\mathrm{for}\ k = \mathit{first}_{b},\ldots,i - 1\ \mathrm{with}\ (i,k) \in P
  4.       aik=aik/akka_{ik} = a_{ik}\ /\ a_{kk}
  5.       forj=k+1,…,𝑙𝑎𝑠𝑡bwith(i,j)∈Pand(k,j)∈P\mathrm{for}\ j = k + 1,\ldots,\mathit{last}_{b}\ \mathrm{with}\ (i,j) \in P\ \mathrm{and}\ (k,j) \in P
  6.         aij=aij−aikakja_{ij} = a_{ij} - a_{ik}a_{kj}
  7.       end\mathrm{end}
  8.     end\mathrm{end}
  9.   end\mathrm{end}
  10. end\mathrm{end}

After the factorization, LL (a unit lower triangular matrix) is formed from the strictly lower triangular part within the block and unit diagonal elements, and UU from the upper triangular part including the diagonal.

lijl_{ij} and uiju_{ij} are elements of LL and UU, ηi\eta_{i} is the matrix scaling factor (1 when disabled), and ψ\psi is the vector scaling factor (1 when disabled).

  1. ψ=max⁡i|ηiri|\psi = \max_{i}|\eta_{i}r_{i}|
  2. forb=1,…,nbinparallel\mathrm{for}\ b = 1,\ldots,nb\ \mathrm{in}\ \mathrm{parallel}
  3.   fori=𝑓𝑖𝑟𝑠𝑡b,…,𝑙𝑎𝑠𝑡b\mathrm{for}\ i = \mathit{first}_{b},\ldots,\mathit{last}_{b}
  4.     yi=ηiri/ψ−∑j=𝑓𝑖𝑟𝑠𝑡bi−1lijyjy_{i} = \eta_{i}r_{i}\ /\ \psi - \sum_{j = \mathit{first}_{b}}^{i - 1} l_{ij}y_{j}
  5.   end\mathrm{end}
  6.   fori=𝑙𝑎𝑠𝑡b,…,𝑓𝑖𝑟𝑠𝑡b\mathrm{for}\ i = \mathit{last}_{b},\ldots,\mathit{first}_{b}
  7.     zi=(yi−∑j=i+1𝑙𝑎𝑠𝑡buijzj)/uiiz_{i} = (y_{i} - \sum_{j = i + 1}^{\mathit{last}_{b}} u_{ij}z_{j})\ /\ u_{ii}
  8.   end\mathrm{end}
  9. end\mathrm{end}
  10. z=ψzz = \psi z

Even when matrix scaling is enabled, the ILU(0) factorization is applied to the unscaled AA, and the input is multiplied by ηi\eta_i in line 4. The action is therefore K−1=U−1L−1SK^{-1} = U^{-1}L^{-1}S (K=S−1LUK = S^{-1}LU), and unlike the Jacobi preconditioner, the action of the preconditioner changes depending on whether matrix scaling is used. For a matrix in which max⁡j|aij|\max_j |a_{ij}| is the same in all rows (e.g., a 7-point difference matrix with center -6), SS is a scalar multiple, which does not affect the iterations of the linear solver, but the eigenvalues of AK−1AK^{-1} 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”.