# Questions tagged [multigrid]

An approach to solving systems of equations by projecting the problem from a fine scale representation onto a coarser one. A coarse representation generally has fewer unknowns, making it faster to solve than the original problem. The coarse solution can then be projected back onto the finer problem as an initial guess of the solution to the finer problem.

86 questions
Filter by
Sorted by
Tagged with
3k views

### What is the advantage of multigrid over domain decomposition preconditioners, and vice versa?

This is mostly aimed for elliptic PDEs over convex domains, so that I can get a good overview of the two methods.
1k views

### Which libraries have good high-level support for multigrid?

I'm planning to use multigrid to calulate some eigenvalues and vectors, and I noticed PETSc has high-level support for multigrid. The PETSc documentation says that this part of PETSc should not be ...
2k views

### multigrid method to solve PDE

I need simple explanation of the Multigrid Method or some literature about this. I am familiar with iterational methods including BiCGStab,CG,GS,Jacobi and preconditioning, but I am a beginner with ...
2k views

### Can a Krylov subspace method be used as a smoother for multigrid?

As far as I am aware, multigrid solvers use iterative smoothers such as Jacobi, Gauss-Seidel, and SOR to dampen the error at various frequencies. Could a Krylov subspace method (like conjugate ...
598 views

### Is there a multigrid algorithm that solves Neumann problems and has a convergence rate independent of the number of levels?

Multigrid methods usually solve Dirichlet problems on levels (e.g. point Jacobi or Gauss-Seidel). When using continuous finite element methods, it is much less expensive to assemble small Neumann ...
4k views

### Is the Thomas algorithm the fastest way to solve a symmetric diagonally dominant sparse tridiagonal linear system

I am wondering if the Thomas algorithm is the fastest way (provably?) to solve a symmetric diagonally dominate sparse tridiagonal system in terms of algorithmic complexity (not looking for ...
1k views

### How is Krylov-accelerated Multigrid (using MG as a preconditioner) motivated?

Multigrid (MG) may be used to solve a linear system $Ax=b$ by constructing an initial guess $x_0$ and repeating the following for $i=0,1..$ until convergence: Compute the residual $r_i = b-Ax_i$ ...
322 views

### Is it usual to have no convergence checking in Multigrid?

I just read Chapter 3 in "A Multigrid Tutorial" by Briggs/Henson/McCormick, link. The text is about Multigrid cycles such as V-cycle, mu-cycle, FMG. What caught my eye: In most iterative procedures ...
491 views

### Algebraic Multigrid: Why does the product of interpolation and restriction not result in something with norm 1?

I'm currently working with "A Multigrid Tutorial" by Briggs et al, Chapter 8. The construction of the interpolation operator is given as: Then construction of restriction operator and fine grid ...
2k views

### How exactly does the *full* multigrid algorithm run?

So I understand (or at least I believe I do) how a V-cycle runs. I've written in Matlab the 1-D, recursive version of a V-cycle. However, when I ran my code for FMG, my solution wasn't converging. I ...
372 views

### In what application cases are additive preconditioning schemes superior to multiplicative ones?

In both domain decomposition (DD) and multigrid (MG) methods, one may compose the application of the block updates or coarse corrections as either additive or multiplicative. For pointwise solvers, ...
4k views

### Algebraic Multigrid Code

I would like to understand more details about the implementation of Algebraic Multigrid Methods (AMG). I have been reading "A Multigrid Tutorial", which is quite good and explain all the details of ...
2k views

### How can one parallelize a multigrid method for solving a linear system of equations?

As I understand it, the multigrid method solves a linear system by solving a coarser version of the same problem (there by eliminating low frequency error) then projecting back to the fine grid to ...
3k views

### How to construct a prolongation and restriction operator for an algebraic multigrid solver?

I am trying to solve a linear system of equations that is sparse, but lacks any kind of banded structure. I have heard that there is a way to extend the principles of a multigrid solver for implicit ...
481 views

### FAS-multigrid slower than linear defect correction?

I have implemented a V-Cycle multigrid solver using both a linear defect correction (LDC) and full approximation scheme (FAS). My problem is the following: Using LDC the residual is reduced by a ...
287 views

### Multigrid on “not perfectly rectangular” grid

Multigrid introductions normally use a rectangular grid. Interpolation of values is then straight forward: Just interpolate linearly on the edge between two adjacent nodes of the coarse grid to find ...
391 views

### Increasing V-cycles for constant Coarsest Grid Size and increasing Fine Grid size

Problem statement I implemented geometric multigrid for $-\nabla^{2}=f$ where $f=\frac{3\pi^{2}}{4}sin \frac{\pi x}{2} sin \frac{\pi y}{2} sin \frac{\pi z}{2}$ on $\Omega \in [0,1]$ on a unit cube. ...
120 views

### Algebraic multigrid for complex valued matrices

Assume one uses the classical AMG with Ruge-Stuben coarsening and direct interpolation for solving real valued problems. How can this approach be recycled to also solve complex valued problems like ...
247 views

### Is multigrid useful for finding all eigenvalues and eigenvectors of a differential equation, or only the lowest eigenvalues?

I've been considering using a multigrid method to calculate the eigenvalues of a particular PDE. I know that multigrid is extremely good at finding the least eigenvalues and their associated ...
294 views

### Question about the smoothing operators in multigrid methods for nonlinear PDEs

Suppose we are dealing with a nonlinear problem, say $$A u := L u + G(u) = f$$ the nonlinearity of the operator $A$ is the polynomial type, ie, $L$ is a linear operator, and $G(u) = u^k$, or ...
311 views

### Periodic BC for Multigrid in MD

I know that this question might be very specific and maybe nobody will know the answer, but this is probably the only community where I could find an answer: So, as part of my master's project, I am ...
741 views

### How to use grid sizes that are not powers of two in Geometric Multigrid

I am trying to solving a poisson equation in structured grid with Geometric Multigrid method. However, when coarsening the fine grid, I simply double the grid spacing at each successive level. That ...
190 views

### How to perform multigrid technique when relaxation methods don't converge?

It is well known that, when a system of linear equations is obtained from discretization of partial differential equation, the solution process can be accelerate significantly by multigrid technique. ...
382 views

### Full Multigrid Prolongation Operator

I am looking into full multigrid, FMG, and several sources, including these slides, that a lot of people are referring to, state that the prolongation operator used in FMG the first time you visit a ...
968 views

### restriction and interpolation in multigrid method

I need detailed explanation of the formula below A2=I1*A1*I2 I suppose this formula computes matrix A2 on a coarse grid and here A1 is original matrix on fine ...
284 views

### I'm having trouble debugging multigrid. What to do?

I've spent far too much time coding and debugging multigrid. While I clearly can't post all of my code as it would be silly to ask someone to go through all that code, is there anything I should pay ...
116 views

### Does algebraic multigrid reuse its coarse grids?

Admittedly, I'm new to the subject, so this is probably a really simple question. Let's assume I want to solve the (large sparse) linear system Ax = b multiple times with algebraic multigrid and b ...
243 views

### Robust smoothers for geometric multigrid

I'm searching for robust smoothers for geometric multigrids. By robust I mean: Effective for high order approximations (say spectral element, spectral Discontinuous Galerkin), Parallel (suitable for ...
93 views

### Why does smoothed aggregation multigrid method used as preconditioner in conjugate gradient slows down the solution time?

I'm solving a system of linear equations obtained from the FEM discretization of a simple linear elasticity problem on a cube with zero displacements at one plane and a load on the opposite one. The ...