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

learn more… | top users | synonyms

9
votes
2answers
109 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 ...
1
vote
1answer
42 views

FENICS subdomains - restriction/ prolongation operators

I am trying to implement my own multigrid method in fenics. Is there any "smart/ fenics" way how to assemble subdomains and obtain restriction/ prolongation operators ? Thanks!
3
votes
1answer
63 views

stabilizing advection-diffusion with multi-grid?

If one chooses to discetize the advection-diffusion (AD) equation using the standard Galerkin finite element method, stability issues may arise in cases of high Peclet number (i.e., high advection to ...
0
votes
0answers
27 views

Injection Vs Full Restriction in Dirichlet-Neumann 3-D Multigrid

I have implemented the Multigrid method for a Mixed Dirichlet-Neumann boundary value problem where $\nabla^{2}{u}=0$, $u = 1+x+y+z$ for Dirichlet and $\frac{\partial e}{\partial n} = 1$ for Neumann ...
0
votes
0answers
38 views

basic and simple algebraic multigrid code

I am looking for a basic and simple algebraic multigrid code to have a better understanding of this method and get an idea to start write my code (in C#). I found some codes online like : AMG1R5 , ...
3
votes
1answer
119 views

Challenges in implementing Algebraic Multigrid on millions of processors

I just implemented an Algebraic Multigrid solver for a Mixed Dirichlet-Neumann Boundary Value problem and was surprised to see the speed-up as compared to a simple iterative solver for a large problem ...
1
vote
1answer
65 views

A doubt in Multigrid V-cycle

Assume I have 3 levels of grids. Finest Grid = level 2, Coarser Grid = level 1, Coarsest Grid = level 0. Relax $u$ on $Au = b$ at level 2 for 3 times. Find residual $r2$ at level 2, then restrict to ...
1
vote
2answers
86 views

Specific questions for 2-D Multigrid

I am simulating $\nabla^{2}u=0$ with mixed Dirichlet-Neumann boundary conditions on 2-D using 2-Grid method. Dirichlet ...
6
votes
1answer
142 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$ ...
0
votes
0answers
33 views

Optimization of nonlocal stencil-like operator on subset of regular grid

I am trying to optimize the execution time for this particular piece of fortran code. Details: i_gc is a (ngpts, 3) array of containing (i,j,k) indices for each grid point. This is a subset of the ...
2
votes
1answer
80 views

Can F-cycle substitue FMG for update of existent solution?

I have a nicely working multigrid solver, which I use for solving the Poisson equation from an electrostatic problem. I solve this equation first without any charges, and then many times with a slowly ...
2
votes
2answers
75 views

Infinite Function Value on Dirichlet Boundary

I have been working on a multigrid solution to a non-homogeneous Dirichlet boundary value problem. However, the function goes to infinity on the boundary. This causes numerical overflow errors to be ...
0
votes
2answers
91 views

How to determine the number of c points in algebraic multi grid

I am trying to write an algebraic multi-grid solver (in c++). At a given level I determine which nodes are c-points and which nodes are f-points (where the total number of c and f points equals the ...
8
votes
2answers
901 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 ...
4
votes
1answer
164 views

Multigrid stops converging when more grid levels are used

I'm having a problem with multigrid code I wrote. If I solve Laplace's equation in 2D and use more than 5 grid levels, the V-cycles stop converging after a few cycles (see below, convergence factor > ...
0
votes
1answer
161 views

What libraries provide an implementation of multigrid?

I am working on numerical method of Multigrid. What's the available implementation(solver) (actually used in scientific computation) of multigrid method?
3
votes
1answer
179 views

Linear Algebra / Numerical Solution Of Matrix With Nullspace

I have a question relating to linear algebra. We have a fluid solver that solves the poisson equation for pressures. When there are areas of the domain that are entirely enclosed by Neumann ...
3
votes
2answers
253 views

Full Multigrid Performance for Poisson's equation using Higher Order Compact scheme as a Gauss Seidel smoother

I have a question regarding the FMG (Full Multi Grid) performance while computing Poisson's equation using Higher Order Compact discretization. I am using a sixth order compact scheme to discretize ...
6
votes
1answer
158 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 ...
8
votes
3answers
227 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 ...
5
votes
1answer
124 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. ...
3
votes
1answer
91 views

explicitly forming coarse matrices with polynomial smoothing AMG

I've been reading about the algebraic multigrid algorithm and came across polynomial smoothers in this paper. It's my understanding that usually the coarse-level matrices $A_H = I_h^HA_hI_H^h$ are ...
0
votes
1answer
45 views

Clarification on interpolation equalities given by Briggs

Briggs, "A Multigrid Tutorial" (pg. 35) has the following expressed as 2-D interpolation: \begin{align*} v^h_{2i,2j} &= v_{i,j}^{2h}\\ v^h_{2i+1,2j} &= 0.5\cdot(v_{i,j}^{2h} + ...
2
votes
1answer
378 views

Prolongation/Restriction Operator in Multigrid

In Multigrid, using Poisson's equation, does the equality below always hold regardless of what type of boundary conditions you use? $$ R= c\cdot I^T, \text{ for some constant }c $$ where $R$ and $I$ ...
5
votes
1answer
155 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 ...
4
votes
2answers
188 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 ...
3
votes
1answer
328 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 ...
10
votes
3answers
804 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 ...
2
votes
1answer
504 views

Full Multigrid convergence is too slow. What could possibly be causing it?

I've coded full multigrid in Matlab and it doesn't seem to be converging fast enough. When I increase the number of grids or the number of iterations, it converges to the analytical solution. But FMG ...
10
votes
1answer
443 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 ...
5
votes
2answers
300 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 ...
6
votes
1answer
172 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 ...
7
votes
4answers
2k 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 ...
10
votes
1answer
710 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 ...
9
votes
3answers
1k 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 ...
8
votes
1answer
719 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 ...
11
votes
5answers
1k 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.
15
votes
2answers
872 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 ...
8
votes
3answers
200 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, ...
7
votes
1answer
153 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 ...
11
votes
1answer
340 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 ...