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. More...

#include <ginkgo/core/solver/multigrid.hpp>

Inheritance diagram for gko::solver::Multigrid:

[legend]

Collaboration diagram for gko::solver::Multigrid:

[legend]

Classes
class	Factory

struct	parameters_type

class	reuse_data_type
	Records the hierarchy of generate_reuse() and the reuse data of its levels, smoothers and coarsest solver. More...

Public Member Functions
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. More...

std::vector< std::shared_ptr< const gko::multigrid::MultigridLevel > >	get_mg_level_list () const
	Gets the list of MultigridLevel operators. More...

std::vector< std::shared_ptr< const LinOp > >	get_pre_smoother_list () const
	Gets the list of pre-smoother operators. More...

std::vector< std::shared_ptr< const LinOp > >	get_mid_smoother_list () const
	Gets the list of mid-smoother operators. More...

std::vector< std::shared_ptr< const LinOp > >	get_post_smoother_list () const
	Gets the list of post-smoother operators. More...

std::shared_ptr< const LinOp >	get_coarsest_solver () const
	Gets the operator at the coarsest level. More...

multigrid::cycle	get_cycle () const
	Get the cycle of multigrid. More...

void	set_cycle (multigrid::cycle cycle)
	Set the cycle of multigrid. More...

const parameters_type &	get_parameters () const

Public Member Functions inherited from gko::LinOp
void	apply (ptr_param< const LinOp > b, ptr_param< LinOp > x) const
	Applies a linear operator to a vector (or a sequence of vectors). More...

void	apply (ptr_param< const LinOp > alpha, ptr_param< const LinOp > b, ptr_param< const LinOp > beta, ptr_param< LinOp > x) const
	Performs the operation x = alpha * op(b) + beta * x. More...

const dim< 2 > &	get_size () const noexcept
	Returns the size of the operator. More...

LinOp &	operator= (const LinOp &)=default
	Copy-assigns a LinOp. More...

LinOp &	operator= (LinOp &&other)
	Move-assigns a LinOp. More...

	LinOp (const LinOp &)=default
	Copy-constructs a LinOp. More...

	LinOp (LinOp &&other)
	Move-constructs a LinOp. More...

Public Member Functions inherited from gko::PolymorphicObject
virtual void	validate_data () const
	Throws gko::InvalidData exception if we found the data inside the object does not fulfill certain property up to our knowledge.

PolymorphicObject &	operator= (const PolymorphicObject &)

std::shared_ptr< const Executor >	get_executor () const noexcept
	Returns the Executor of the object. More...

Public Member Functions inherited from gko::log::EnableLogging< PolymorphicObject >
void	add_logger (std::shared_ptr< const Logger > logger) override

void	remove_logger (const Logger *logger) override

void	remove_logger (ptr_param< const Logger > logger)

const std::vector< std::shared_ptr< const Logger > > &	get_loggers () const override

void	clear_loggers () override

Public Member Functions inherited from gko::log::Loggable
void	remove_logger (ptr_param< const Logger > logger)

Public Member Functions inherited from gko::solver::EnableSolverBase< Multigrid >
EnableSolverBase &	operator= (const EnableSolverBase &other)
	Creates a shallow copy of the provided system matrix, clones it onto this executor if executors don't match.

EnableSolverBase &	operator= (EnableSolverBase &&other)
	Moves the provided system matrix, clones it onto this executor if executors don't match. More...

	EnableSolverBase (std::shared_ptr< const LinOp > system_matrix)

	EnableSolverBase (const EnableSolverBase &other)
	Creates a shallow copy of the provided system matrix.

	EnableSolverBase (EnableSolverBase &&other)
	Moves the provided system matrix. More...

int	get_num_workspace_ops () const override

std::vector< std::string >	get_workspace_op_names () const override

std::vector< int >	get_workspace_scalars () const override
	Returns the IDs of all scalars (workspace vectors with system dimension-independent size, usually 1 x num_rhs).

std::vector< int >	get_workspace_vectors () const override
	Returns the IDs of all vectors (workspace vectors with system dimension-dependent size, usually system_matrix_size x num_rhs).

Public Member Functions inherited from gko::solver::SolverBase< LinOp >
std::shared_ptr< const LinOp >	get_system_matrix () const
	Returns the system matrix, with its concrete type, used by the solver. More...

Public Member Functions inherited from gko::solver::EnableIterativeBase< Multigrid >
EnableIterativeBase &	operator= (const EnableIterativeBase &other)
	Creates a shallow copy of the provided stopping criterion, clones it onto this executor if executors don't match.

EnableIterativeBase &	operator= (EnableIterativeBase &&other)
	Moves the provided stopping criterion, clones it onto this executor if executors don't match. More...

	EnableIterativeBase (std::shared_ptr< const stop::CriterionFactory > stop_factory)

	EnableIterativeBase (const EnableIterativeBase &other)
	Creates a shallow copy of the provided stopping criterion.

	EnableIterativeBase (EnableIterativeBase &&other)
	Moves the provided stopping criterion. More...

void	set_stop_criterion_factory (std::shared_ptr< const stop::CriterionFactory > new_stop_factory) override
	Sets the stopping criterion of the solver. More...

Public Member Functions inherited from gko::solver::IterativeBase
std::shared_ptr< const stop::CriterionFactory >	get_stop_criterion_factory () const
	Gets the stopping criterion factory of the solver. More...

Static Public Member Functions
static auto	build () -> decltype(Factory ::create())

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. More...

Friends
class	EnableApplyWithInitialGuess< Multigrid >

Detailed Description

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{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} \]

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.

The factory supports LinOpFactory::generate_reuse(): the recorded hierarchy is reused as long as its levels reproduce their coarse sizes, and levels, smoothers and the coarsest solver are generated through their own generate_reuse(). Below the first level that comes out different, everything is generated anew. Levels such as Pgm keep choices made from the values of the first matrix, so it should be representative of the later ones.

Member Function Documentation

◆ apply_uses_initial_guess()

bool gko::solver::Multigrid::apply_uses_initial_guess ( ) const

inlineoverridevirtual

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

Reimplemented from gko::LinOp.

References gko::solver::provided.

◆ get_coarsest_solver()

std::shared_ptr<const LinOp> gko::solver::Multigrid::get_coarsest_solver ( ) const

inline

Gets the operator at the coarsest level.

Returns: the coarsest operator

◆ get_cycle()

multigrid::cycle gko::solver::Multigrid::get_cycle ( ) const

inline

Get the cycle of multigrid.

Returns: the multigrid::cycle

References gko::solver::Multigrid::parameters_type::cycle.

◆ get_mg_level_list()

std::vector<std::shared_ptr<const gko::multigrid::MultigridLevel> > gko::solver::Multigrid::get_mg_level_list ( ) const

inline

Gets the list of MultigridLevel operators.

Returns: the list of MultigridLevel operators

◆ get_mid_smoother_list()

std::vector<std::shared_ptr<const LinOp> > gko::solver::Multigrid::get_mid_smoother_list ( ) const

inline

Gets the list of mid-smoother operators.

Returns: the list of mid-smoother operators

◆ get_post_smoother_list()

std::vector<std::shared_ptr<const LinOp> > gko::solver::Multigrid::get_post_smoother_list ( ) const

inline

Gets the list of post-smoother operators.

Returns: the list of post-smoother operators

◆ get_pre_smoother_list()

std::vector<std::shared_ptr<const LinOp> > gko::solver::Multigrid::get_pre_smoother_list ( ) const

inline

Gets the list of pre-smoother operators.

Returns: the list of pre-smoother operators

◆ parse()

static parameters_type gko::solver::Multigrid::parse	(	const config::pnode &	config,
		const config::registry &	context,
		const config::type_descriptor &	td_for_child = `config::make_type_descriptor<>()`
	)

static

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.

Parameters

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

Returns: parameters

Note: Multigrid does not support the selector option in file config

◆ set_cycle()

void gko::solver::Multigrid::set_cycle ( multigrid::cycle cycle )

inline

Set the cycle of multigrid.

Parameters

multigrid::cycle the new cycle

References gko::solver::Multigrid::parameters_type::cycle.

The documentation for this class was generated from the following file:

ginkgo/core/solver/multigrid.hpp

Classes

Public Member Functions

Static Public Member Functions

Friends

Detailed Description

Member Function Documentation

◆ apply_uses_initial_guess()

◆ get_coarsest_solver()

◆ get_cycle()

◆ get_mg_level_list()

◆ get_mid_smoother_list()

◆ get_post_smoother_list()

◆ get_pre_smoother_list()

◆ parse()

◆ set_cycle()