Multigrid method | EPFL Graph Search

Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

In numerical analysis, a multigrid method (MG method) is an algorithm for solving differential equations using a hierarchy of discretizations. They are an example of a class of techniques called multiresolution methods, very useful in problems exhibiting multiple scales of behavior. For example, many basic relaxation methods exhibit different rates of convergence for short- and long-wavelength components, suggesting these different scales be treated differently, as in a Fourier analysis approach to multigrid. MG methods can be used as solvers as well as preconditioners. The main idea of multigrid is to accelerate the convergence of a basic iterative method (known as relaxation, which generally reduces short-wavelength error) by a global correction of the fine grid solution approximation from time to time, accomplished by solving a coarse problem. The coarse problem, while cheaper to solve, is similar to the fine grid problem in that it also has short- and long-wavelength errors. It can also be solved by a combination of relaxation and appeal to still coarser grids. This recursive process is repeated until a grid is reached where the cost of direct solution there is negligible compared to the cost of one relaxation sweep on the fine grid. This multigrid cycle typically reduces all error components by a fixed amount bounded well below one, independent of the fine grid mesh size. The typical application for multigrid is in the numerical solution of elliptic partial differential equations in two or more dimensions. Multigrid methods can be applied in combination with any of the common discretization techniques. For example, the finite element method may be recast as a multigrid method. In these cases, multigrid methods are among the fastest solution techniques known today. In contrast to other methods, multigrid methods are general in that they can treat arbitrary regions and boundary conditions. They do not depend on the separability of the equations or other special properties of the equation.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (10)

Personnes associées (3)

Concepts associés (4)

Cours associés (8)

Séances de cours associées (46)

ME-372: Finite element method

L'étudiant acquiert une initiation théorique à la méthode des éléments finis qui constitue la technique la plus courante pour la résolution de problèmes elliptiques en mécanique. Il apprend à applique

MATH-453: Computational linear algebra

This course provides an overview of advanced techniques for solving large-scale linear algebra problems, as they typically arise in applications. A central goal of this course is to give the ability t

MATH-251(c): Numerical analysis

Le cours présente des méthodes numériques pour la résolution de problèmes mathématiques comme des systèmes d'équations linéaires ou non linéaires, approximation de fonctions, intégration et dérivation

Low-rank tensor methods for large Markov chains and forward feature selection methods

Francisco Santos Paredes Quartin de Macedo

In the first part of this thesis, we present and compare several approaches for the determination of the steady-state of large-scale Markov chains with an underlying low-rank tensor structure. Such st

EPFL2018

Multigrid Methods Combined With Low-Rank Approximation For Tensor-Structured Markov Chains

Daniel Kressner, Francisco Santos Paredes Quartin de Macedo

Markov chains that describe interacting subsystems suffer from state space explosion but lead to highly structured matrices. In this work, we propose a novel tensor-based algorithm to address such ten

2018

MATHICSE Technical Report : Multigrid methods combined with low-rank approximation for tensor structured Markov chains

Daniel Kressner, Francisco Santos Paredes Quartin de Macedo

Markov chains that describe interacting subsystems suffer, on the one hand, from state space explosion but lead, on the other hand, to highly structured matrices. In this work, we propose a novel tens

MATHICSE2016

En analyse numérique, la méthode des éléments finis (MEF, ou FEM pour finite element method en anglais) est utilisée pour résoudre numériquement des équations aux dérivées partielles. Celles-ci peuvent par exemple représenter analytiquement le comportement dynamique de certains systèmes physiques (mécaniques, thermodynamiques, acoustiques).

En analyse numérique, une méthode itérative est un procédé algorithmique utilisé pour résoudre un problème, par exemple la recherche d’une solution d’un système d'équations ou d’un problème d’optimisation. En débutant par le choix d’un point initial considéré comme une première ébauche de solution, la méthode procède par itérations au cours desquelles elle détermine une succession de solutions approximatives raffinées qui se rapprochent graduellement de la solution cherchée. Les points générés sont appelés des itérés.

Compare les approches globales et locales de la méthode des éléments finis.

Explore l'approche locale dans la méthode des éléments finis, couvrant les fonctions de forme nodale et l'assemblage.

Explore l'approche locale de la méthode des éléments finis, couvrant les fonctions de forme nodale, les restrictions de solution, les tailles, les conditions aux limites et les opérations d'assemblage.