8 Linear Solvers
This chapter describes the iterative algorithms used in the library routines. Throughout, we consider solving the linear system whose coefficient matrix is a real matrix. Each section gives the algorithm and its notation. The details of the convergence check, the handling of breakdowns and non-finite values, and the returned values are given in the solver() section of each solver in the API Reference (“Common Handling in the Linear Solvers”). denotes the inner product and the 2-norm. All four linear solvers (pcg, pbicgstab, pgmres, pcagmres) check convergence by comparing the relative residual with the value set by set_tolerance() (convergence when ). The matrices each method can handle and its characteristics are listed below.
| Method | Class | Target matrix | Characteristics |
|---|---|---|---|
| Preconditioned conjugate gradient method | parcel::krylov::pcg |
Symmetric positive definite (the preconditioner matrix also symmetric positive definite) | Few operations and collective communications per iteration |
| Preconditioned biconjugate gradient stabilized method | parcel::krylov::pbicgstab |
Symmetric or nonsymmetric | Right preconditioning. Performs SpMV and preconditioning twice each per iteration. The residual does not necessarily decrease monotonically |
| Preconditioned generalized minimal residual method | parcel::krylov::pgmres |
Symmetric or nonsymmetric | Right preconditioning. Minimizes the residual norm within the restart length |
| Preconditioned communication-avoiding generalized minimal residual method | parcel::krylov::pcagmres |
Symmetric or nonsymmetric (the moment method only for symmetric matrices without preconditioning) | Right preconditioning. Generates basis vectors at once and orthogonalizes them, performing iterations equivalent to GMRES() with fewer collective communications. Whether the orthonormal basis is formed explicitly can be selected with set_explicit_q() (if not, orthogonalization uses the Cholesky factorization of the Gram matrix) |
In the algorithms and formulas of this manual, iteration numbers are written as parenthesized superscripts (, ), and components of a vector and indices within a set of vectors as subscripts (, ). A superscript without parentheses is a power (), is the transpose and the inverse. Matrices are written in upper case, vectors and scalars in lower-case italics, and English keywords and function names (, , etc.) in upright type. is the order of the matrix (the number of global rows) and the number of rows owned by each rank. Symbols are defined per section and may have a different meaning in another section.
The convergence status constants and their meaning for each solver are summarized in “Convergence Status” in the API Reference.
8.1 Preconditioned Conjugate Gradient Method [1]
The conjugate gradient method (CG method) is a Krylov subspace method for symmetric matrices. Both the coefficient matrix and the preconditioner matrix are assumed to be symmetric positive definite.
- Algorithm
is the initial guess passed as the argument x of solver(), is the preconditioner matrix specified by set_precon_algo() and related functions (see the “Preconditioners” chapter; without preconditioning), is the convergence tolerance set by set_tolerance() (default 1.0e-8), and is the maximum number of iterations set by set_max_iteration() (default 10000). is the preconditioned residual, is the search direction, is , and , , , and are scalars.
In the implementation, by default the solution update of at line 11 is performed at every iteration and only one search direction is kept. If the environment variable PARCEL_PSTEP is set to a value , search directions are accumulated and added to together every iterations (the reads and writes of drop to , which is slightly faster, at the cost of the memory of vectors; see “Choosing Between Memory and Speed”). The solution is mathematically the same; only the order of rounding changes. Convergence is checked with at line 12, so the number of iterations does not depend on PARCEL_PSTEP.
The details of the convergence check, the handling of breakdowns and non-finite values, the returned values and the implementation details are given in “Convergence by Solver” in the API Reference.
8.2 Preconditioned Biconjugate Gradient Stabilized Method [1]
The biconjugate gradient stabilized method (Bi-CGSTAB) is a Krylov subspace method for nonsymmetric matrices. The preconditioner is applied as a right preconditioner; that is, the iteration is performed on and the solution is updated with the directions and multiplied by , so the residual corresponds to the unpreconditioned residual .
- Algorithm
is the initial guess passed as the argument x of solver(), is the preconditioner matrix specified by set_precon_algo() and related functions, is the value of set_tolerance() (default 1.0e-8), and is the value of set_max_iteration() (default 10000). is the initial residual, and is the dual (shadow) residual, which is kept fixed during the iteration. is the search direction, is the intermediate residual, and , , , , and are scalars.
The details of the convergence check, the handling of breakdowns and non-finite values, the returned values and the implementation details are given in “Convergence by Solver” in the API Reference.
8.3 Preconditioned Generalized Minimal Residual Method [1]
The generalized minimal residual method (GMRES(m)) is a Krylov subspace method for nonsymmetric matrices. It updates the approximate solution by minimizing the residual norm over the subspace built by steps of the Arnoldi process, and then restarts the iteration using the result as the initial guess (restarting). The PARCEL pgmres uses right preconditioning: the Arnoldi process is performed on , and is applied only when the approximate solution is updated. The residual being minimized is therefore the unpreconditioned residual itself. The classical Gram-Schmidt method and the modified Gram-Schmidt method are available as the orthogonalization methods of the Arnoldi process.
- Algorithm
is the initial guess passed as the argument x of solver(), is the approximate solution at the start of the -th restart, is the preconditioner matrix specified by set_precon_algo() and related functions, is the restart length set by set_restart() (default 30), and is the value of set_tolerance() (default 1.0e-8). The maximum number of restarts is determined from the value of set_max_iteration() (default 10000) as (if is not a multiple of , the last restart stops after the remaining columns). are the orthonormal basis vectors, are the entries of the Hessenberg matrix, and are the Givens rotation coefficients, is the rotated right-hand-side vector, is the upper triangular matrix consisting of the rotated (), and denotes the first components of . Lines 12-15 show the case where the modified Gram-Schmidt method (parcel::qr::QR_MGS, the default) is selected with set_qr_algo(). The implementation computes and with both signs reversed; the two reversals cancel, and the result is the same.
The details of the convergence check, the handling of breakdowns and non-finite values, the returned values and the implementation details are given in “Convergence by Solver” in the API Reference.
8.4 Preconditioned Communication-Avoiding Generalized Minimal Residual Method [2,3]
The communication-avoiding generalized minimal residual method (CA-GMRES(s,t)) is a Krylov subspace method for nonsymmetric matrices. It generates, at once, the basis vectors corresponding to iterations of GMRES(m) and orthogonalizes them block by block. This is repeated times, the approximate solution is updated with the resulting basis vectors, and the iteration is restarted with the result as the initial guess. corresponds to the restart length of GMRES(m). Mathematically, CA-GMRES(s,t) and GMRES(m) have equivalent convergence, and by applying a communication-avoiding QR factorization, CA-GMRES reduces the number of collective communications compared with GMRES(m). However, because basis vectors are generated at once, if is too large, rounding errors destroy the orthogonality of the basis vectors and the convergence becomes worse than that of GMRES. PARCEL supports only the monomial basis (); the Newton basis is not implemented. As in pgmres, right preconditioning is used.
- Algorithm
is the initial guess passed as the argument x of solver(), is the approximate solution at the start of the -th restart, is the preconditioner matrix specified by set_precon_algo() and related functions, and are the values set by set_restart(s, t) (default , ), and is the value of set_tolerance() (default 1.0e-8). The maximum number of restarts is determined from the value of set_max_iteration() (default 10000) as (if is not a multiple of , the last restart solves the least-squares problem with the remaining columns only). The QR factorization method at lines 19 and 26 is selected with set_qr_algo() (parcel::qr::QR_CGS, QR_MGS (default), QR_CHOLESKYQR; see the “QR Factorization” chapter). The algorithm below forms the orthonormal basis explicitly. The case without forming is described below.
is the change-of-basis matrix of the monomial basis (; is the -th unit vector), is its first rows, and is its entry in row , column . An underlined symbol denotes the version with one more vector (column or row) than the symbol without the underline. are the basis vectors generated in the -th block, and are those vectors excluding the first. is the orthonormalized basis, and denotes its first columns. and are the QR factors of , and and are the QR factors of . is the coefficient matrix of the block classical Gram-Schmidt method (), is its columns excluding the first (corresponding to ), and is the first columns of with the last row removed. is the upper triangular matrix obtained by the QR factorization, is its leading block, and are the upper components and the diagonal entry of its -th column, and is the entry of in row , column . is the Hessenberg matrix for , and is that matrix with the last row removed. and are the parts of the columns added to in the -th block that lie in the rows of the previous blocks and of the -th block, respectively, and is the entry in its last row. is the rotated right-hand-side vector, denotes its first components, is the entry of , and and are the Givens rotation coefficients. After the rotations, is upper triangular.
Lines 14-17 generate the monomial basis of the -th block ( is fixed) and consist only of preconditioning and sparse matrix-vector products (no collective communication). Lines 35-44 apply the Givens rotations to each column of the Hessenberg matrix of the blocks, and lines 45-47 update the solution.
The details of the convergence check, the handling of breakdowns and non-finite values, the returned values and the implementation details are given in “Convergence by Solver” in the API Reference.
8.4.1 How Q Is Formed (set_explicit_q)
pcagmres lets you choose with set_explicit_q(mode) whether the orthogonalized basis is formed explicitly (the value can be obtained with get_explicit_q()). mode is one of the following constants in the namespace parcel::krylov.
| Constant | Value | Behavior |
|---|---|---|
CAGMRES_Q_AUTO (default) |
0 | Forms as in the algorithm above, except that is not formed when QR_CHOLESKYQR is used with |
CAGMRES_Q_EXPLICIT |
1 | Always forms (also with QR_CHOLESKYQR and ) |
CAGMRES_Q_IMPLICIT |
2 | Does not form for any (below). The QR factorization is QR_CHOLESKYQR (used if set_qr_algo() is not called) or QR_CAGMRES_CHOLESKYQR (the moment method) |
The combinations of CAGMRES_Q_IMPLICIT with QR_CGS or QR_MGS, and of QR_CAGMRES_CHOLESKYQR with CAGMRES_Q_AUTO or CAGMRES_Q_EXPLICIT, throw std::invalid_argument at the entry of solver() (the setters may be called in any order, so the combination is checked at the entry). Out-of-range values make set_explicit_q() throw std::invalid_argument. get_qr_algo() returns the QR factorization actually used. The selected mode is shown at the end of the timing line (the pcagmres time line), such as Q = auto: formed or Q = implicit: not formed, CholeskyQR.
8.4.2 When Q Is Not Formed (CAGMRES_Q_IMPLICIT) [2,3,7]
When set_explicit_q(parcel::krylov::CAGMRES_Q_IMPLICIT) is specified, the following three points differ from the algorithm above.
- The orthonormal basis is not formed explicitly. The basis is kept as it is, and only the upper triangular matrix () is obtained from the Cholesky factorization of the Gram matrix . The Hessenberg matrix is assembled from with the same formulas as in the algorithm above, and the solution update uses instead of . The default (
CAGMRES_Q_AUTO) withQR_CHOLESKYQRomits only when , whereasCAGMRES_Q_IMPLICITomits it also for . - The basis is stored separately in even- and odd-numbered vectors, and their storage precisions can be selected with the template arguments
Teven_basisandTodd_basisofsolver()(both default toTbasis; not used except withCAGMRES_Q_IMPLICIT). - With
set_qr_algo(parcel::qr::QR_CAGMRES_CHOLESKYQR), the Gram matrix of the first block is built from the moments (QR Factorization chapter). This is correct only when is symmetric and there is no preconditioning.
- Algorithm
is the initial guess passed as the argument x of solver(), is the approximate solution at the start of the -th restart, is the preconditioner matrix specified by set_precon_algo() and related functions, and are the values set by set_restart(s, t) (default , ), and is the value of set_tolerance() (default 1.0e-8). The maximum number of restarts is determined from the value of set_max_iteration() (default 10000) as . In this section the basis vectors are numbered from 0; , is the submatrix of in rows to and columns to , are the basis vectors newly generated in the -th block, and is the -th unit vector (0-based). denotes the upper triangular matrix of the Cholesky factorization of a symmetric matrix . and are the same as in the pcagmres algorithm above, and the Givens rotations in lines 28-30 are the same computation as lines 35-44 of the algorithm above.
in line 13 is the -th column of ; only the starting vector of each block is built from and (corresponding to line 12, , of the algorithm above). in line 23 is the coefficient of the block classical Gram-Schmidt method, and line 24 is the Cholesky QR of the projected ; is extended one block at a time while staying upper triangular. In line 26, uses the same formulas as lines 21-22 of the algorithm above, and the same formulas as lines 28-32, with and . in line 31 is the upper triangular matrix obtained by removing the last row of the rotated .
The details of the convergence check, the handling of breakdowns and non-finite values, the returned values and the implementation details are given in “Convergence by Solver” in the API Reference.
8.5 Precision of Orthogonalization and of the Basis
GMRES-type solvers iterate while orthogonalizing the basis of the Krylov subspace. In pgmres and pcagmres, the precision in which the basis is stored and the precision in which orthogonalization is computed can be specified separately (for the syntax see “Calling a Linear Solver” in “Usage”).
In this section, is the local number of rows and is the restart length of pgmres (set_restart(m)). and are the parameters of CA-GMRES(s,t) (pcagmres), specified with set_restart(s, t) (default , ).
- : the number of basis vectors generated in a row without orthogonalization in one block. From the first vector of the block, the vectors of the monomial basis are generated, and these vectors are QR-factorized together. There is no collective communication while the SpMVs and preconditionings are performed in a row.
- : the number of blocks generated in one restart. From the second block on, each block is orthogonalized against the orthogonalized basis of the previous blocks before its QR factorization. Since the last vector of a block is the first vector of the next block, one restart has basis vectors, and the restart length corresponds to GMRES() (Linear Solvers chapter).
With rounding errors, the orthogonalized basis is not exactly orthogonal. The loss of orthogonality is determined by the unit roundoff of the precision used to compute the orthogonalization and by the condition number of the basis before orthogonalization. It is proportional to for the modified Gram-Schmidt method [8], and to for the classical Gram-Schmidt method [9] and the Cholesky QR method [11]. is about in double precision, about in single precision, and about in half precision. The Cholesky QR method fails when approaches 1, because the Gram matrix is then no longer numerically positive definite. In addition, storing the orthogonalized at a lower precision degrades the orthogonality by its rounding (relative in each entry of ).
The Arnoldi process of pgmres orthogonalizes each new vector against the previously orthogonalized basis, one vector at a time. GMRES with the modified Gram-Schmidt method is backward stable, and orthogonality is lost significantly only after the residual has become sufficiently small [10]. Therefore, even with a low precision for the orthogonalization precision TGS, the iteration proceeds, and the effect appears mainly as a lower limit on the achievable residual (the limit grows with ).
In pcagmres, orthogonalization has two stages, and and act on them respectively.
- Within a block ( acts): the vectors of the monomial basis are generated without orthogonalization, so their condition number grows rapidly with . Since they are QR-factorized, the computation precision of the QR factorization directly determines whether orthogonalization succeeds. In particular, the Cholesky QR method (
QR_CHOLESKYQRofpcagmres, including the variant that does not form ,CAGMRES_Q_IMPLICIT) depends on , so with a large the factorization itself easily breaks down at low precision. This ill-conditioning is also why the Cholesky QR variants ofpcagmrescannot be used with FP16 data or computation precision (the variants that form can be used; “Known Limits at Low Precision”). - Between blocks ( acts): the -th block () subtracts its projection onto the previous ( vectors) once (the block classical Gram-Schmidt method, without reorthogonalization) before the QR factorization within the block. The loss of orthogonality between blocks depends on the computation precision of the single projection and on the condition number of the block before projection, and as blocks are stacked (larger ), errors in orthogonality to the previous blocks may accumulate in the basis.
The detection of rank deficiency of the basis (a lucky breakdown) uses a threshold determined from ( for the Cholesky QR method, otherwise).
The computations on vectors of length (dot products and updates) handled by each argument, and their precisions, are shown below. Note that in pcagmres, the roles of TcalcQR and THessenberg differ depending on whether the orthogonal basis is formed explicitly (set_explicit_q(); Linear Solvers chapter).
| Solver | Argument | Handles | Data size |
|---|---|---|---|
pgmres |
Tvec (data precision) |
Storage of the basis vectors | |
pgmres |
TGS |
Dot products and coefficients of the Gram-Schmidt orthogonalization | Dot products of length |
pgmres |
THessenberg |
Precision in which the solution of the least-squares problem (solved on the host) is passed to the device | Length |
pcagmres |
Tbasis |
Storage of the basis and the orthogonalized basis | is , is |
pcagmres (when is formed) |
TcalcQR |
Computation of the QR factorization within a block (dot products of length ) | Dot products of length |
pcagmres (when is formed) |
THessenberg |
Computation of the projection between blocks (dot products of length ) and its subtraction from ; storage of , the projection coefficients and the Hessenberg matrix | Dot products of length , |
pcagmres (CAGMRES_Q_IMPLICIT) |
TcalcQR |
Computation of the Gram matrix (all dot products of length within and between blocks) | Dot products of length |
pcagmres (CAGMRES_Q_IMPLICIT) |
THessenberg |
Storage of the Gram matrix, and the Hessenberg matrix | About |
pcagmres (CAGMRES_Q_IMPLICIT) |
Todd_basis, Teven_basis |
Storage of the odd- and even-numbered vectors of the basis | in total |
The samples fix TcalcQR and THessenberg to double precision for the following reason. Lowering the precision reduces memory and data movement for the basis (Tbasis), which holds or more vectors of length . On the other hand, what decides whether orthogonalization succeeds is the computation precision of the orthogonalization within and between blocks (TcalcQR and THessenberg in pcagmres, and TcalcQR in the variant that does not form , CAGMRES_Q_IMPLICIT). These are the precisions in which dot products are accumulated while reading the basis, and raising them does not change the amount of basis data read and written. The stored matrices (, the Hessenberg matrix, etc.) are small, about . Hence the basis alone is lowered to match the data precision, while the orthogonalization computations and the small matrices are kept in double precision. The orthogonality is then preserved to the level determined by the rounding of Tbasis, which stores the basis . The C and Fortran wrapper (capi/wrapper_parcel_sycl.cpp) gives these two with the macro parcel_solver_calc_qr_type (default parcel_double), and the verification sample tests/verify/parcel_krylov_sample_verify.cpp fixes them to parcel_double. TGS and THessenberg of pgmres are both given the data precision (the library default is parcel_double). All 13 representative configurations in “Precision Configurations” use double precision for TcalcQR and THessenberg of pcagmres (including the variant that does not form ). Convergence when these are lowered has not been checked.