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

6 Choosing a Solver

This chapter gives guidelines for choosing a solver and a preconditioner from the properties of the problem. The algorithm of each solver is described in the “Linear Solvers”, “Eigenvalue Solvers” and “Preconditioners” chapters. The solvers available from C and Fortran are shown in the “Usage” chapter.


6.1 Linear Solvers

First, distinguish by whether the coefficient matrix AA is symmetric positive definite.

Matrix First choice Next choice
Symmetric positive definite (the preconditioner matrix KK also symmetric positive definite) pcg pgmres (e.g., when the preconditioner is not symmetric)
Nonsymmetric, or symmetric but not positive definite pgmres or pbicgstab pcagmres when there are many ranks and collective communication is the bottleneck

The characteristics of each solver are shown below.

Solver Main operations per iteration Vectors held Characteristics and notes
pcg 1 SpMV, 1 preconditioning Few (fixed) Assumes that AA and KK are symmetric positive definite. The lightest. Convergence is checked with the recurrence residual
pbicgstab 2 SpMVs, 2 preconditionings Few (fixed) For nonsymmetric matrices. The residual does not necessarily decrease monotonically. May break down, e.g., when ⟨r*,q⟩=0\langle r^{\ast},q \rangle = 0 (DIVERGED_BREAKDOWN). With FP16 as the dot-product precision Tdot, it tends to break down at tolerances close to the precision limit. Convergence is checked with the recurrence residual
pgmres 1 SpMV, 1 preconditioning, orthogonalization Proportional to the restart length mm (m+1m + 1 basis vectors) Minimizes the residual norm within one restart. The default is m=30m = 30 (31 basis vectors). For difficult problems increase it with set_restart(), and decrease it when memory is short. Convergence is checked only with the true residual at the beginning of each restart, so the number of iterations is a multiple of mm except when the iteration limit is reached. With the default modified Gram-Schmidt method (QR_MGS), orthogonalization performs a collective communication of a dot product for each basis vector; QR_CGS combines them into one
pcagmres ss SpMVs and preconditionings combined, then orthogonalization Proportional to stst Mathematically equivalent to GMRES(stst), with fewer collective communications. The default is s=8s = 8, t=4t = 4 (equivalent to GMRES(32)); change it with set_restart(s, t). With a large ss, the monomial basis becomes ill-conditioned and convergence becomes worse than GMRES. Do not use the Cholesky QR variants with FP16 data or computation precision. With set_explicit_q(CAGMRES_Q_IMPLICIT), the orthonormal basis is not formed explicitly, and orthogonalization uses only the Cholesky factorization of the Gram matrix of the basis (1 to 2 collective communications per basis block). The orthogonality error is then proportional to the square of the condition number of the basis, so with a large ss it may deteriorate earlier than with QR_MGS. QR_CAGMRES_CHOLESKYQR is limited to symmetric AA, no preconditioning and an even ss (the symmetry of AA is not checked)

The guidelines are as follows.


6.2 Eigenvalue Solvers

All three eigenvalue solvers handle the standard eigenvalue problem Ax=λxAx = \lambda x; generalized eigenvalue problems are not supported. Choose by the eigenvalues you want.

What you want Solver and settings Notes
One eigenvalue of largest magnitude power The convergence rate is determined by the ratio of the largest and the second largest eigenvalues in magnitude. Slow when the ratio is close to 1
One eigenvalue of smallest magnitude inverse_power Solves the inner linear system in each iteration. If AA is symmetric and positive (or negative) definite, the inner solver can be made pcg with set_linsolve_algo(parcel::krylov::LINSOLVE_PCG)
Eigenvalues close to a shift σ\sigma (interior eigenvalues) shift-invert of ks_arnoldi (set_shift(σ) and A−σIA - \sigma I as the fourth argument) Most of the computation time is spent in the inner pgmres. Moving σ\sigma closer to an eigenvalue reduces the number of restarts, but worsens the condition number of A−σIA - \sigma I and makes the inner pgmres heavier
Several eigenvalues, complex conjugate pairs ks_arnoldi Specify the size of the subspace and the number of eigenvalues to check with set_ks_subspace(m, k_keep, nev). Convergence is not guaranteed for the outputs beyond nev
The smallest-magnitude eigenvalues are a complex conjugate pair, or several smallest-magnitude eigenvalues of a nonsymmetric matrix shift-invert of ks_arnoldi with σ=0\sigma = 0 inverse_power uses a real Rayleigh quotient and does not converge to a complex conjugate pair
Condition number of the preconditioned matrix AK−1AK^{-1} set_precon_spectrum(true) with power and inverse_power Take the ratio of the eigenvalues at both ends. The eigenvalues of AK−1AK^{-1} tend to cluster around 1, and power converges slowly

power and inverse_power do not converge when the eigenvalue at the wanted end is a complex conjugate pair, or when there are several eigenvalues of equal magnitude (for example ±λ\pm\lambda). Use ks_arnoldi for such matrices.

The inner linear solver of inverse_power and of shift-invert is configured separately from the outer iteration, with set_linsolve_tolerance(), set_linsolve_max_iteration(), set_linsolve_precon_algo() and so on. The default inner preconditioner is the Jacobi preconditioner (1 iteration). If the inner solver takes many iterations, change or strengthen the preconditioner with set_linsolve_precon_algo() and set_linsolve_jacobi(). How to check the inner convergence is shown in “Checking the Convergence Status”.

6.2.1 Meaning of set_precon_spectrum()

In the eigenvalue solvers, preconditioning changes “which matrix’s eigenvalues are computed”.

If you want the eigenvalues of AA, specifying only set_precon_algo() does not speed up the outer iteration. How each solver uses the preconditioner is shown in the tables of the Power Method, Inverse Power Method and Krylov-Schur Method sections.


6.3 Preconditioners

Preconditioner Cost of one application Communication Effect of the preconditioner and MPI partitioning Suitable for
None (0) None None — The reference for comparing the effect of preconditioners. Default of set_precon_algo() (the default of the inner linear solver of the eigenvalue solvers is the Jacobi preconditioner)
Point Jacobi (1) nn multiplications None Independent of the partitioning The cheapest. Small effect
Block Jacobi (2) Forward and backward substitution within the blocks None Depends on the number of ranks and the number of blocks nbnb CPUs (the default number of blocks is the number of threads per rank)
Jacobi (4) ITER SpMVs (set_jacobi()) Halo exchange in every Jacobi iteration Independent of the partitioning GPUs. Each row can be computed independently