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

1 Common Items

This reference presents the PARCEL API in separate chapters for each language. Items that do not depend on the language (solvers, input matrix, meaning and defaults of the settings, constants, meaning of the results, convergence states, handling under MPI) are collected in this chapter and in the next chapter, “Convergence by Solver”. The chapters for each language give the names and syntax in that language, how errors are reported, and examples. Read this chapter, the next one, and the chapters of the language you use. Switch the language with the tabs at the top of each page.

Language Chapters
C++ From PARCEL SYCL Classes to parcel::krylov::ks_arnoldi
C C API
Fortran Fortran API
Python Python API

The beginning of each language’s chapters has a table that maps the settings, constants and results of this chapter to the names in that language.

1.1 Format of the Entries

Each function or type entry in the language chapters consists of the following fields. Fields that do not apply are omitted.

Field Contents
Description What the function does
Synopsis The declaration in that language
Arguments Name, direction (In / Out / In/Out), type, description, and default value. The default value is the value the library uses when nothing is specified
Requirements Valid range of the arguments and the behavior when they are violated. If the library does not check them, “not checked” is stated
Return Value Meaning of the return value
MPI Whether the operation is collective, and whether all ranks must pass the same value
Notes Remarks on usage
See Also Related functions and chapters
Example A call example

1.2 Solvers

PARCEL has the following seven solvers. The solver names are common to all languages. The algorithms are described in the “Linear Solvers” and “Eigenvalue Solvers” chapters of the User Guide, and how to choose among them in “Choosing a Solver”.

Solver Method Problem
pcg Preconditioned conjugate gradient method Ax=bAx = b with AA and the preconditioner matrix KK symmetric positive definite
pbicgstab Preconditioned stabilized biconjugate gradient method Ax=bAx = b (nonsymmetric matrices)
pgmres Preconditioned generalized minimal residual method (right preconditioning, with restarts) Ax=bAx = b (nonsymmetric matrices)
pcagmres Preconditioned communication-avoiding generalized minimal residual method (CA-GMRES). It generates ss basis vectors at once and orthogonalizes them by QR factorization Ax=bAx = b (nonsymmetric matrices)
power Power method One eigenpair of AA with the largest magnitude
inverse_power Inverse power method. At each iteration an inner linear solver solves Ay=xAy = x One eigenpair of AA with the smallest magnitude
ks_arnoldi Arnoldi process with Krylov-Schur restarts. Also handles nonsymmetric matrices and complex conjugate eigenvalue pairs Several eigenpairs of AA on the side of the largest magnitude; in shift-invert mode, the eigenpairs closest to the shift σ\sigma

The eigenvalue solvers handle the standard eigenvalue problem Ax=λxAx = \lambda x. When the spectrum of the preconditioned matrix is selected, they compute the eigenvalues of AK−1AK^{-1} instead of AA. Solvers can be excluded from the build (“Selecting the Solvers to Build” in the User Guide). What happens when an excluded solver is called is described in each language’s chapter.

1.3 Symbols and Terms

This reference uses the following symbols and terms.

Symbol / term Meaning
nlocaln_{local} Number of rows owned by each rank
nglobaln_{global} Sum of nlocaln_{local} over all ranks (number of rows of the matrix)
toltol Convergence tolerance
NN Maximum number of iterations
mm Restart length of pgmres; maximum dimension of the Krylov subspace of ks_arnoldi
ss, tt Number of vectors generated in one basis generation of pcagmres, and the number of basis generations before a restart (setting)
kkeepk_{keep}, nevnev Number of eigenpairs that ks_arnoldi keeps after a restart (and returns at the end), and number of eigenpairs checked for convergence (setting)
NRN_{R} Maximum number of restarts of ks_arnoldi
KK, KinK_{in} Preconditioner matrix (built from AA according to the preconditioner settings) and the preconditioner matrix of the inner linear solver of the eigenvalue solvers
shift-invert Method for finding the eigenvalues near a shift σ\sigma. It computes the eigenvalues θ\theta of largest magnitude of (A−σI)−1(A - \sigma I)^{-1} and maps them back by λ=σ+1/θ\lambda = \sigma + 1/\theta
Op\mathrm{Op} Operator to which ks_arnoldi applies the Arnoldi process: AA, AK−1AK^{-1} (when the spectrum of the preconditioned matrix is computed), and in shift-invert mode (A−σI)−1(A - \sigma I)^{-1} or (AK−1−σI)−1(AK^{-1} - \sigma I)^{-1}
Ritz pair (θ,x)(\theta, x) Approximate eigenvalue θ\theta and approximate eigenvector xx of Op\mathrm{Op} computed within the Krylov subspace
True residual Relative residual ∥b−Ax∥/∥b∥\|b - Ax\| / \|b\| recomputed from the solution xx. In contrast, the residual updated by the recurrence of the iteration is called the recurrence residual
Lucky breakdown The Krylov subspace becomes an invariant subspace and the next basis vector cannot be built. The solution (eigenpair) lies in that subspace, so this by itself is not a failure
rank 0 The rank with number 0 in the communicator. It writes the progress and the results to standard output

1.4 Input Matrix

The coefficient matrix is given in CRS format. When solving in parallel with MPI, each rank owns a block of contiguous rows (nlocaln_{local} rows from the global row number nstartnstart) and passes only those rows. The format is explained in the data structure section of the User Guide.

The library checks the following conditions; if they are not satisfied, all ranks report the same error (how errors are reported is described in each language’s chapter).

The following conditions are not checked; if they are not satisfied, wrong results may be returned silently.

In a build without MPI, one process owns the whole matrix (all rows).

1.5 Settings

The behavior of the solvers is determined by the following settings. Settings that are not specified take the defaults in the table. The names in each language are given in the mapping table of each language’s chapters. Values outside the accepted values are rejected (an error is reported). Give the same values on all ranks.

Setting Used by Meaning Accepted values Default
Convergence tolerance toltol All solvers Threshold for the relative residual ∥r∥/∥b∥\|r\|/\|b\| in the linear solvers, for the relative change of the eigenvalue in power and inverse_power, and for the relative residual ∥Opx−θx∥/(|θ|∥x∥)\|\mathrm{Op}\,x-\theta x\|/(|\theta|\|x\|) of the Ritz pairs (θ,x)(\theta, x) in ks_arnoldi (in shift-invert mode it is checked on θ\theta before mapping back to λ\lambda) Finite positive number 1.0e-8
Maximum number of iterations NN Linear solvers, power, inverse_power Upper limit of the iterations: the total number of inner iterations in pgmres and pcagmres, the number of outer iterations in power and inverse_power. ks_arnoldi does not use it (it uses the maximum number of restarts) 1 or greater. Need not be a multiple of mm (stst) in pgmres and pcagmres 10000
Preconditioner type All solvers Type of the preconditioner matrix KK (constants). In the linear solvers it is the preconditioner of the iteration; in the eigenvalue solvers it is KK used when the spectrum of the preconditioned matrix is computed None, point Jacobi, block Jacobi, Jacobi None
Number of Jacobi iterations When the preconditioner is Jacobi Number of Jacobi iterations 1 or greater 1
Number of block Jacobi blocks When the preconditioner is block Jacobi Number of blocks per rank, equal to the degree of parallelism of the application. Finer blocks make the preconditioner weaker 1 or greater and at most the number of owned rows (the upper bound is not checked) Automatic. On CPUs, the environment variable PARCEL_NBLOCK, otherwise the number of OpenMP threads, otherwise the value given at build time. On GPUs, 2 rows per block
Scaling of the preconditioner matrix and vectors When the preconditioner is block Jacobi or Jacobi Whether to divide the matrix and residual by their maximum to bring them into the range of half precision (specified separately for the matrix and the vectors) On, off, automatic Automatic (on for block Jacobi; otherwise on only when the arithmetic precision of the preconditioner or the precision of the preconditioner matrix is half precision)
Restart length mm pgmres Memory for m+1m + 1 basis vectors is allocated 1 or greater 30
Orthogonalization method pgmres Orthogonalization in the Arnoldi process (constants) Classical Gram-Schmidt, modified Gram-Schmidt Modified Gram-Schmidt
Basis generation size ss, tt pcagmres Number of vectors ss generated at once and number of basis generations tt before a restart. The restart length is s×ts \times t Both 1 or greater s=8s = 8, t=4t = 4
QR factorization method pcagmres QR factorization of the basis (constants, combination rules) Classical Gram-Schmidt, modified Gram-Schmidt, Cholesky QR, Cholesky QR by the moment method Modified Gram-Schmidt (Cholesky QR when QQ is not formed)
Q mode pcagmres Whether the orthonormal basis QQ is formed explicitly (constants, combination rules) AUTO, EXPLICIT, IMPLICIT AUTO
Spectrum of the preconditioned matrix Eigenvalue solvers False: compute the eigenvalues of AA; the outer eigenvalue iteration does not use the preconditioner. True: compute the eigenvalues of AK−1AK^{-1} (notes) True, false False
Type of the inner linear solver inverse_power Inner linear solver (constants). pcg is only for symmetric (positive or negative definite) AA (not checked). When the spectrum of the preconditioned matrix is computed, pgmres is used regardless of the type pgmres, pcg pgmres
Tolerance of the inner linear solver inverse_power, shift-invert of ks_arnoldi Threshold for the relative residual of the inner linear solver Finite positive number 1.0e-10
Maximum iterations of the inner linear solver Same as above Upper limit of the iterations of the inner linear solver (for pgmres, the total number of inner iterations; need not be a multiple of the restart length) 1 or greater inverse_power 5000, ks_arnoldi 2000
Restart length of the inner linear solver Same as above Restart length of the inner pgmres. Not used when the inner solver is pcg 1 or greater 30
Preconditioner of the inner linear solver Same as above Type of the preconditioner KinK_{in} of the inner linear solver, number of Jacobi iterations, number of block Jacobi blocks, scaling (notes) Same as for the preconditioner type, iterations, blocks and scaling Jacobi (1 iteration); blocks and scaling automatic
Shift-invert ks_arnoldi When enabled, computes the eigenvalues closest to σ\sigma. The value is the shift σ\sigma Any real number. σ\sigma must not coincide with an eigenvalue (not checked) Disabled
Size of the Krylov subspace mm, kkeepk_{keep}, nevnev ks_arnoldi Maximum dimension mm of the subspace, number of eigenpairs kkeepk_{keep} kept after a restart (and returned at the end), number of eigenpairs nevnev checked for convergence 1≤nev≤kkeep<m≤nglobal1 \leq nev \leq k_{keep} < m \leq n_{global} m=30m = 30, kkeep=10k_{keep} = 10, nev=4nev = 4
Maximum number of restarts NRN_{R} ks_arnoldi Upper limit on the number of restarts 1 or greater 200
Orthogonalization method (ks_arnoldi) ks_arnoldi Orthogonalization of the Arnoldi process (constants). Either method is applied twice (classical Gram-Schmidt twice = CGS2, modified Gram-Schmidt twice = MGS2). The accuracy of the eigenvalues is equivalent; only the speed differs Classical Gram-Schmidt, modified Gram-Schmidt Classical Gram-Schmidt (CGS2). Can be changed to modified Gram-Schmidt when building the library
Initial vector ks_arnoldi Initial vector of the Arnoldi process. power and inverse_power always use the default vector Any vector. If its norm is 0 or non-finite, it is replaced by the default vector (rank 0 reports this) Vector built from the global row numbers (independent of the row partitioning)

Some settings cannot be specified in some languages, or are expressed differently from the table (for example, “use the default” expressed as 0). These are shown in the mapping table of each language’s chapters.

1.5.1 Notes on the Preconditioners

1.5.2 Notes on the Eigenvalue Solvers

1.5.3 Q Modes and QR Factorization of pcagmres

The Q modes (constants) are as follows.

Mode Behavior
AUTO QQ is not formed only when the QR factorization is Cholesky QR and t=1t = 1; otherwise QQ is formed
EXPLICIT QQ is always formed (even for Cholesky QR with t=1t = 1)
IMPLICIT QQ is not formed for any tt. Only RR is obtained from the Cholesky factorization of the Gram matrix of the basis VV, and the solution is updated with V(R−1y)V(R^{-1}y). The QR factorization must be Cholesky QR or Cholesky QR by the moment method

The combination of the Q mode and the QR factorization is checked at the entry of the solve, independently of the order in which the settings are given, and the following cases are rejected (the same judgment on all ranks).

Cholesky QR by the moment method (moment method) is only for symmetric AA. This is not checked; with a nonsymmetric AA a wrong RR is used and wrong results are returned. AUTO and EXPLICIT perform the same computation except for Cholesky QR with t=1t = 1. IMPLICIT computes in a different order, so its results differ within rounding errors even with the same ss, tt and QR factorization. With IMPLICIT, the orthogonality error of the Cholesky QR method is proportional to the square of the condition number of the basis, so a larger ss can worsen convergence. With FP16 data or arithmetic precision, do not use the Cholesky QR family (IMPLICIT and the moment method): the result is NaN or no convergence regardless of ss and tt (not checked). The methods are described in the “Linear Solvers” chapter and the “QR Factorization” chapter of the User Guide.

1.6 Constants

The values of the settings are expressed with the following constants. The values are the same in all languages; the names in each language are given in that language’s chapters.

Preconditioner type:

Constant Value Preconditioner
NONE 0 No preconditioning
POINTJACOBI 1 Point Jacobi preconditioner
BLOCKJACOBI 2 Block Jacobi preconditioner
JACOBI 4 Jacobi preconditioner

Orthogonalization and QR factorization method:

Constant Value Method Solvers
CGS 0 Classical Gram-Schmidt method pgmres, pcagmres (when QQ is formed), ks_arnoldi (applied twice)
MGS 1 Modified Gram-Schmidt method pgmres, pcagmres (when QQ is formed), ks_arnoldi (applied twice)
CHOLESKYQR 2 Cholesky QR method pcagmres
CAGMRES_CHOLESKYQR 202 Cholesky QR method by the moment method (symmetric matrices without preconditioning only) pcagmres (IMPLICIT only)

Type of the inner linear solver:

Constant Value Solver
PGMRES 0 Right-preconditioned pgmres
PCG 1 pcg

Q mode of pcagmres:

Constant Value Behavior
AUTO 0 See above
EXPLICIT 1 Same as above
IMPLICIT 2 Same as above

The constants of the convergence states are given in the section below.

1.7 Results

Besides the solution (the eigenvalues and eigenvectors for the eigenvalue solvers), a solve returns the following values. They are the same on all ranks. The details of their meaning differ between the solvers and are given in the convergence status section and in the next chapter.

Result Meaning
Convergence state One of the convergence state constants. Positive means converged, negative means failure, and 0 means that no solve has been run
Iteration count How iterations are counted differs between the solvers (table below)
Residual Relative value compared with the convergence tolerance (table below). NaN if it has not been computed
True residual ∥b−Ax∥/∥b∥\|b - Ax\|/\|b\| computed at the end of a linear solver, returned without additional computation. NaN for the eigenvalue solvers. The residual of pcg and pbicgstab is the recurrence residual, which can drift from the true residual through rounding errors; to check the accuracy of the solution, look at the true residual
Number of converged eigenpairs Number of eigenpairs among the nevnev ones that satisfied the tolerance in the last convergence check of ks_arnoldi (NaN is not counted; if true residuals were checked, for example in an invariant subspace, that number). nevnev on convergence. 0 for the other solvers
Number of inner solver failures Number of times the inner linear solver ended without satisfying its tolerance in inverse_power and the shift-invert mode of ks_arnoldi. 0 for power and ks_arnoldi without a shift. Not reflected in the outer convergence state. If it is not 0, review the maximum iterations and the preconditioner of the inner linear solver

1.7.1 Output of Eigenvalues and Eigenvectors

1.8 Convergence Status

The convergence state returned by a solve is one of the following constants (following PETSc’s KSPConvergedReason: positive means converged, negative means failure).

Constant Value Meaning
CONVERGED_RTOL 1 The convergence tolerance was satisfied
ITERATING 0 Not run (before a solve, or not solved because of an argument error)
DIVERGED_ITS -1 The maximum number of iterations (for ks_arnoldi, the maximum number of restarts) was reached
DIVERGED_NANORINF -2 NaN / Inf appeared in the residual or eigenvalue estimate used for the convergence check
DIVERGED_BREAKDOWN -3 Breakdown of the algorithm (table below)

The cases in which each state occurs are shown for each solver. The details are given in the next chapter.

Solver CONVERGED_RTOL DIVERGED_NANORINF DIVERGED_BREAKDOWN
pcg Relative recurrence residual <tol< tol. ∥b∥=0\|b\| = 0 (x=0x = 0 without iterating, iteration count 0). Relative initial residual <tol< tol (xx left at the initial guess without iterating, iteration count 0) Stops as soon as the relative recurrence residual becomes non-finite Does not occur (division by zero is not detected; if the result is non-finite, NANORINF)
pbicgstab Same as pcg. Stopped at v=Aê=0v = A\hat{e} = 0 with ∥e∥/∥b∥<tol\|e\|/\|b\| < tol (lucky breakdown) Same as pcg ⟨r*,q⟩\langle r^{\ast},q \rangle is 0 or non-finite, ω=0\omega = 0, ρ=0\rho = 0, or v=0v = 0 with ∥e∥/∥b∥≥tol\|e\|/\|b\| \geq tol
pgmres True relative residual at the start of a restart <tol< tol, or true relative residual at termination <tol< tol when the iteration limit was reached. ∥b∥=0\|b\| = 0 Stops as soon as the true relative residual or hh of the Arnoldi process becomes non-finite Lucky breakdown with no column usable for the update (HH singular at the first column)
pcagmres Same as pgmres Stops as soon as the true relative residual becomes non-finite No column usable for the update after a lucky breakdown (rank deficiency of RR, hi+1,i≈0h_{i+1,i} \approx 0)
power, inverse_power Relative change of the eigenvalue <tol< tol Stops as soon as the eigenvalue estimate, its relative change, or an inner product used for the check becomes non-finite (inverse_power: also when the inner linear solver ended with NANORINF) power: AK−1x=0AK^{-1}x = 0; inverse_power: the solution of the inner linear solver is 0
ks_arnoldi Ritz residual estimates of the nevnev target pairs ≤tol\leq tol (with an invariant subspace or random directions, also confirmed by the true residual) Stops as soon as a value of the Arnoldi process, a Ritz value, or a residual estimate becomes non-finite An invariant subspace that cannot be confirmed by the true residual, an effective dimension below nevnev, or a LAPACK failure

DIVERGED_ITS means that none of the above occurred and the maximum number of iterations (for ks_arnoldi, the maximum number of restarts) was reached. The algorithms are described in the “Linear Solvers” chapter and the “Eigenvalue Solvers” chapter of the User Guide.

1.8.1 Meaning of the Iteration Count and Residuals

The meanings of the iteration count, the residual and the true residual for each solver are as follows.

Solver Iteration count Residual True residual
pcg, pbicgstab Number of iterations Relative recurrence residual ∥r∥/∥b∥\|r\|/\|b\| (∥e∥/∥b∥\|e\|/\|b\| when pbicgstab stops at v=0v = 0) True relative residual computed at termination
pgmres Total number of inner iterations (number of restarts × mm; the maximum number of iterations if the limit was reached) True relative residual computed at the start of each restart. If the iteration limit was reached, the value after the last update (= the true residual) Same as left
pcagmres Total number of basis vectors (number of cycles × s×ts \times t; the maximum number of iterations if the limit was reached) Same as pgmres Same as left
power, inverse_power Number of outer iterations Relative change of the eigenvalue |λ(i)−λ(i−1)|/|λ(i)||\lambda^{(i)} - \lambda^{(i-1)}|/|\lambda^{(i)}|. NaN if stopped on a non-finite value NaN
ks_arnoldi Number of restarts performed Maximum of the Ritz residual estimates of the nevnev target pairs (the maximum of the true residuals if those were checked) NaN

1.8.2 Common Handling in the Linear Solvers

In the linear solvers (pcg, pbicgstab, pgmres, pcagmres), ∥b∥=0\|b\| = 0 returns x=0x = 0 without iterating, with the state CONVERGED_RTOL (iteration count 0; residual and true residual 0). Rank 0 writes the line ||b|| = 0 : x = 0.

If the relative initial residual ∥b−Ax(0)∥/∥b∥\|b - Ax^{(0)}\| / \|b\| of the initial guess x(0)x^{(0)} is below toltol (including the case where x(0)x^{(0)} is already the solution), every linear solver returns CONVERGED_RTOL without iterating (iteration count 0) and leaves xx at the initial guess. The residual and the true residual are this relative initial residual.

1.8.3 Standard Output

Rank 0 writes one line of the following form to standard output at the end of a solve (non-finite values are printed as n/a). inverse_power appends , linsolve_failures = ..., and ks_arnoldi appends , ks_nconv = <number converged>/nev (plus linsolve_failures in shift-invert mode).

Example: converged_reason = 1 (CONVERGED_RTOL) , its = 27 , residual = 4.200000e-10 , true_residual = 4.211375e-10

In addition, rank 0 writes the progress of the iteration and a breakdown of the computing time. The linear solvers write the true relative residual at termination on the line finish : residual true norm. pcagmres does not write this line when it returns at the check before the iteration. The format of the standard output is not part of the API. To obtain the results from a program, use the result interface of each language.

1.9 Settings and MPI

1.10 Precision

PARCEL can choose the precision in which data are stored (data precision) and the precision of the arithmetic (arithmetic precision) separately for each operation (SpMV, preconditioner, vector operations, inner products) and each piece of data (matrix, vectors, preconditioner matrix, etc.). The types are half precision (FP16), single precision, double precision, long double, and double-double (about quadruple precision). How the precision is chosen differs between the languages.

Language Choosing the precision
C++ Template arguments for each operation and each piece of data (PARCEL Data Types)
C, Fortran Fixed by macros when the wrapper is compiled; cannot be changed at run time (all double precision by default). The input and output arrays are double precision
Python Double precision only

With configurations that use half precision, there is a lower limit on the relative residual that the precision can reach; with a tolerance below it, the iteration stagnates or breaks down with NaN. The details of the restrictions are given in “Specifying the Precision” in the “Usage” chapter and in “Numerical Accuracy and Reproducibility” of the User Guide.