`gko::solver::Multigrid`#

Multigrid framework. A composable solver that accepts a coarsening strategy (e.g. gko::multigrid::Pgm), per-level smoothers, and a coarse-grid solver, and runs V/W/F cycles between them. Used both as a standalone solver and as a preconditioner inside Krylov methods.

class Multigrid #

Inherits from

public gko::EnableLinOp<Multigrid>
public gko::solver::EnableSolverBase<Multigrid>
public gko::solver::EnableIterativeBase<Multigrid>
public gko::solver::EnableApplyWithInitialGuess<Multigrid>

Multigrid solves a linear system by combining cheap iterative sweeps (smoothers) on a hierarchy of progressively coarser representations of the operator with corrections transferred between adjacent levels. A smoother on the fine level removes the high-frequency components of the error quickly; the remaining low-frequency error is well-resolved on a coarser space, where it is computed by a cheaper solve — or, recursively, by another multigrid call. The correction is prolongated back to the fine level and a second smoothing sweep removes any high-frequency error introduced by the transfer. Because each coarser level holds only a fraction of the unknowns of the next, the total work per cycle stays close to that of a single fine-level matrix-vector apply.

Each level \( \ell \) holds a system matrix \( A_\ell \), a smoother \( S_\ell \), a restriction operator \( R_\ell : \mathbb{R}^{n_\ell} \to \mathbb{R}^{n_{\ell+1}} \) and a prolongation operator \( P_\ell : \mathbb{R}^{n_{\ell+1}} \to \mathbb{R}^{n_\ell} \). The Galerkin coarse operator is \( A_{\ell+1} = R_\ell\, A_\ell\, P_\ell \). One V-cycle step at level \( \ell \) on a fine-level system \( A_\ell x = b \) is:

\[\begin{split} \begin{aligned} x &\leftarrow x + S_\ell^{\mathrm{pre}}(b - A_\ell x) && \text{(pre-smooth)}, \\ r_{\ell+1} &= R_\ell\, (b - A_\ell x) && \text{(restrict)}, \\ e_{\ell+1} &\approx A_{\ell+1}^{-1}\, r_{\ell+1} && \text{(recursive coarse solve)}, \\ x &\leftarrow x + P_\ell\, e_{\ell+1} && \text{(prolongate and correct)}, \\ x &\leftarrow x + S_\ell^{\mathrm{post}}(b - A_\ell x) && \text{(post-smooth)}. \end{aligned} \end{split}\]

At the coarsest level the recursive call is replaced by a direct or iterative coarse solver. W- and F-cycles differ from V only in how many recursive coarse-solves are performed per level (see the cycle enum above).

Ginkgo uses the index from 0 for finest level (original problem size) ~ N for the coarsest level (the coarsest solver), and its level counts is N (N multigrid level generation).

References

Briggs, W. L., Henson, V. E., McCormick, S. F. A Multigrid Tutorial. 2nd ed. SIAM, 2000. https://doi.org/10.1137/1.9780898719505
Trottenberg, U., Oosterlee, C. W., Schüller, A. Multigrid. 1st ed. Academic Press, 2001. ISBN 978-0-12-701070-0.

Public Functions

inline bool apply_uses_initial_guess() const override#

Return true as iterative solvers use the data in x as an initial guess or false if multigrid always set the input as zero

Returns:: bool it is related to parameters variable zero_guess

inline std::vector<std::shared_ptr<const gko::multigrid::MultigridLevel>> get_mg_level_list( ) const#

Gets the list of MultigridLevel operators.

Returns:: the list of MultigridLevel operators

inline std::vector<std::shared_ptr<const LinOp>> get_pre_smoother_list( ) const#

Gets the list of pre-smoother operators.

Returns:: the list of pre-smoother operators

inline std::vector<std::shared_ptr<const LinOp>> get_mid_smoother_list( ) const#

Gets the list of mid-smoother operators.

Returns:: the list of mid-smoother operators

inline std::vector<std::shared_ptr<const LinOp>> get_post_smoother_list( ) const#

Gets the list of post-smoother operators.

Returns:: the list of post-smoother operators

inline std::shared_ptr<const LinOp> get_coarsest_solver() const#

Gets the operator at the coarsest level.

Returns:: the coarsest operator

inline multigrid::cycle get_cycle() const#

Get the cycle of multigrid

Returns:: the multigrid::cycle

inline void set_cycle(multigrid::cycle cycle)#

Set the cycle of multigrid

Parameters:: multigrid::cycle – the new cycle

Public Static Functions

static parameters_type parse( const config::pnode &config, const config::registry &context, const config::type_descriptor &td_for_child = config::make_type_descriptor<>(), )#

Create the parameters from the property_tree. Because this is directly tied to the specific type, the value/index type settings within config are ignored and type_descriptor is only used for children configs.

Note

Multigrid does not support the selector option in file config

Parameters:

config – the property tree for setting
context – the registry
td_for_child – the type descriptor for children configs

Returns:

parameters

struct parameters_type #

Inherits from

public gko::solver::enable_iterative_solver_factory_parameters<parameters_type, Factory>

Public Members

std::vector<std::shared_ptr<const LinOpFactory>> mg_level#: MultigridLevel Factory list

std::function<size_type(const size_type, const LinOp*)> level_selector#

Custom selector size_type (size_type level, const LinOp* fine_matrix) Selector function returns the element index in the vector for any given level index and the matrix of the fine level. The level 0 is the finest level and it is ascending when going to coarser levels. For each level, this function is used to select the smoothers and multigrid level generation from the respective lists. For example,

[](size_type level, const LinOp* fine_matrix) {
    if (level < 3) {
        return size_type{0};
    } else if (matrix->get_size()[0] > 1024) {
        return size_type{1};
    } else {
        return size_type{2};
    }
}

It uses the 0-idx element if level < 3, the 1-idx element if level >= 3 and the number of rows of fine matrix > 1024, or the 2-idx elements otherwise.

default selector: use the level as the index when the level < #mg_level and reuse the last one when the level >= #mg_level

std::vector<std::shared_ptr<const LinOpFactory>> pre_smoother#

Pre-smooth Factory list. Its size must be 0, 1 or be the same as mg_level’s. when size = 0, use default smoother when size = 1, use the first factory when size > 1, use the same selector as mg_level

If this option is not set (i.e. size = 0) then the default smoother is used. The default smoother is one step of iterative refinement with a scalar Jacobi preconditioner.

If any element in the vector is a nullptr then the smoother application at the corresponding level is skipped.

std::vector<std::shared_ptr<const LinOpFactory>> post_smoother#: Post-smooth Factory list. It is similar to Pre-smooth Factory list. It is ignored if the factory parameter post_uses_pre is set to true.

std::vector<std::shared_ptr<const LinOpFactory>> mid_smoother#: Mid-smooth Factory list. If it contains available elements, multigrid always generates the corresponding smoother. However, it is only involved in the procedure when cycle is F or W. It is similar to Pre-smooth Factory list. It is ignored if the factory parameter mid_case is not mid.

bool post_uses_pre#: Whether post-smoothing-related calls use corresponding pre-smoothing-related calls.

multigrid::mid_smooth_type mid_case#

Choose the behavior of mid smoother between two cycles close to each other in the same level. The default is multigrid::mid_smooth_type::standalone.

gko::solver::Multigrid#

`gko::solver::Multigrid`#