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 is symmetric positive definite.
| Matrix | First choice | Next choice |
|---|---|---|
| Symmetric positive definite (the preconditioner matrix 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 and 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 (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 ( basis vectors) | Minimizes the residual norm within one restart. The default is (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 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 |
SpMVs and preconditionings combined, then orthogonalization | Proportional to | Mathematically equivalent to GMRES(), with fewer collective communications. The default is , (equivalent to GMRES(32)); change it with set_restart(s, t). With a large , 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 it may deteriorate earlier than with QR_MGS. QR_CAGMRES_CHOLESKYQR is limited to symmetric , no preconditioning and an even (the symmetry of is not checked) |
The guidelines are as follows.
- If the matrix is symmetric positive definite, use
pcg. A matrix that is symmetric but not positive definite does not satisfy the assumption ofpcg, so use a solver for nonsymmetric matrices. - For nonsymmetric matrices, try
pgmreswhen there is enough memory and stable convergence is wanted, andpbicgstabwhen each iteration should be light. Ifpbicgstabstops withDIVERGED_BREAKDOWN, switch topgmres. - The communication-avoiding solver (
pcagmres) is for reducing the number of collective communications when waiting inMPI_Allreducedominates with many ranks. It is less robust to rounding errors thanpgmres; if the number of iterations increases much compared withpgmresat the default , or it does not converge, make smaller. Increase only after confirming that it converges in the same number of iterations aspgmres. - Check whether the solver converged with
is_converged()andget_converged_reason(). Forpcgandpbicgstab, check the accuracy of the solution withget_true_residual()(the true residual; “Numerical Accuracy and Reproducibility”). - By default,
pcgkeeps only one search direction. If there is enough memory, settingPARCEL_PSTEP=4at run time batches the solution updates and makes it slightly (1-3%) faster (“Choosing Between Memory and Speed”).
6.2 Eigenvalue Solvers
All three eigenvalue solvers handle the standard eigenvalue problem ; 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 is symmetric and positive (or negative) definite, the inner solver can be made pcg with set_linsolve_algo(parcel: |
| Eigenvalues close to a shift (interior eigenvalues) | shift-invert of ks_arnoldi (set_shift(σ) and as the fourth argument) |
Most of the computation time is spent in the inner pgmres. Moving closer to an eigenvalue reduces the number of restarts, but worsens the condition number of 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 |
inverse_power uses a real Rayleigh quotient and does not converge to a complex conjugate pair |
| Condition number of the preconditioned matrix | set_precon_spectrum(true) with power and inverse_power |
Take the ratio of the eigenvalues at both ends. The eigenvalues of 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 ). 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”.
set_precon_spectrum(false)(default): returns the eigenvalues of . Preconditioner settings such asset_precon_algo()are not used in the outer eigenvalue iteration. To speed up the inner linear solver ofinverse_powerand shift-invert, specify it separately withset_linsolve_precon_algo()and related functions (the returned eigenvalues are still those of ).set_precon_spectrum(true): returns the eigenvalues of the preconditioned matrix . is built from according toset_precon_algo()and related settings. Used to evaluate a preconditioner (the spectrum and condition number of ).
If you want the eigenvalues of , 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) | 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 | 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 |
- On GPUs, the Jacobi preconditioner is the first choice. The block Jacobi preconditioner needs blocks of only a few rows to obtain enough parallelism on a GPU (the default is 2 rows per block), and in most cases the Jacobi preconditioner is faster.
- By default, the Jacobi preconditioner does not keep the values of to save memory and computes them at each application. If there is enough GPU memory, building with
-DPARCEL_JACOBI_ONTHEFLY=0makes the preconditioner faster (one iteration ofpcgwith NX=512 on 4 devices is 14% shorter on V100 and 23% shorter on MI300A; “Choosing Between Memory and Speed”). - The effect of the block Jacobi preconditioner depends on the number of ranks and the number of blocks, so changing the number of ranks also changes the number of iterations. To compare results with different numbers of ranks, use the Jacobi or point Jacobi preconditioner.
pcgassumes that is symmetric positive definite. With matrix scaling enabled, the block Jacobi preconditioner becomes , so for a matrix whose rows have different maximum absolute values, may not be symmetric (block Jacobi preconditioner in the Preconditioners chapter). The verification sample can check withPARCEL_PRECON_SYMCHECK=1.- The restrictions when combining with low precision (such as an FP16 preconditioner combined with the point Jacobi preconditioner) are shown in “Numerical Accuracy and Reproducibility”.