**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Multigrid method

Summary

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 c

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related publications (43)

Loading

Loading

Loading

Related people (5)

Related units (3)

Related courses (4)

ME-474: Numerical flow simulation

This course provides practical experience in the numerical simulation of fluid flows. Numerical methods are presented in the framework of the finite volume method. A simple solver is developed with Matlab, and a commercial software is used for more complex problems.

MICRO-512: Image processing II

Study of advanced image processing; mathematical imaging. Development of image-processing software and prototyping in JAVA; application to real-world examples in industrial vision and biomedical imaging.

ME-104: Introduction to structural mechanics

The student will acquire the basis for the analysis of static structures and deformation of simple structural elements. The focus is given to problem-solving skills in the context of engineering design.

Related concepts (5)

Computational fluid dynamics

Computational fluid dynamics (CFD) is a branch of fluid mechanics that uses numerical analysis and data structures to analyze and solve problems that involve fluid flows. Computers are used to perfor

Finite element method

The finite element method (FEM) is a popular method for numerically solving differential equations arising in engineering and mathematical modeling. Typical problem areas of interest include the tr

Sparse matrix

In numerical analysis and scientific computing, a sparse matrix or sparse array is a matrix in which most of the elements are zero. There is no strict definition regarding the proportion of zero-va

A domain decomposition technique to solve large-scale aerodynamics problems on unstructured grids is investigated. The linear system, arising when an implicit time-advancing scheme is used, is preconditioned using a Schwarz-based method. The key idea of the Schwarz preconditioner is to solve (approximately) a linear problem on each subdomain, then to exchange information only with neighbouring subdomains. Unfortunately, the performance of the Schwarz-type preconditioner deteriorates as the number of processors grows. So, in this case, a key element for obtaining a scalable preconditioner is to provide a coarse level operator. Since many of the coarse operators proposed in literature are difficult to implement on unstructured 2D and 3D meshes, a purely algebraic procedure, that requires the entries of the matrix only, has been developed. This procedure may be seen as an Algebraic MultiGrid (AMG) method applied as a coarse grid correction operator. The key idea is to take advantage of the use of local data of domain decomposition preconditioners, and of the automatic coarsening procedures of AMG methods. Two possible schemes to introduce the coarse grid operator will be described. Both cases have been implemented and tested in a distributed parallel environment, using the MPI library. It will be shown that for suitable values of the rank of the coarse grid operator it is possible to obtain a considerable reduction in the number of iterations compared to the Schwarz preconditioner without coarse operator

2002The purpose of this thesis is to investigate methods for the solution of multiscale problems both from the mathematical and numerical point of view, with a particular concern on applications to flows through heterogeneous porous media. After an overview of the recent developments in this vast field, a study of two representative multiscale techniques is carried out. The multiscale finite element method and a conjugate gradient iterative method preconditioned with an overlapping Schwarz domain decomposition preconditioner are compared in the one-dimensional case. Both methods are well suited for parallel environments and have comparable performance and accuracy. Then, we focus our attention on an aggregation-based two-level overlapping Schwarz domain decomposition preconditioner. We study its theoretical properties and show its robustness to mesh refinement as well as to strong variations in the multiscale coefficients of our model problem. We carry out a convergence analysis to give upper bounds for the condition number of the preconditioned linear system arising from the finite element discretization of the problem at hand. We make explicit the relation between the multiscale coefficient and the coarse space basis functions and show that the condition number can be bounded independently of the ratio of the values of the multiscale coefficient even when the discontinuities in the coefficient are not resolved by the coarse mesh. A new aggregation algorithm is proposed according to the suggestions issuing from the theory which builds a coarse space able to cope with the multiscale coefficient. Numerical experiments on various configurations show that the bounds are sharp and that the method is robust with respect to strong variations. Finally, an application of this preconditioning technique to a two-phase flow problem is presented in order to investigate its performance.

We present a multi-level algorithm to approximate the inverse of the fluid block in a Navier-Stokes saddle-point matrix where the coarse level is defined as a restriction of the degrees of freedom to those of lower order finite elements. A one-level scheme involving P1 and P2 finite elements is studied in details and several transfer operators are compared by means of two reference problems. Numerical results show that restriction and prolongation operators based on L2 projection lead to faster GMRES convergence of the fluid part, for all the examined combinations of mesh size, time step and Reynolds number.

2013Related lectures (8)