# Tag Info

18

Yes, you can, but Krylov methods generally do not have great smoothing properties. This is because they target the whole spectrum in an adaptive way that minimizes the residual or a suitable norm of the error. This will generally include some low frequency (long wavelength) modes that the coarse grids would have handled fine. Krylov smoothers also make the ...

16

Multigrid and multilevel domain decomposition methods have so much in common that each can usually be written as a special case of the other. The analysis frameworks are somewhat different, as a consequence of the different philosophies of each field. Generally speaking, multigrid methods use moderate coarsening rates and simple smoothers while domain ...

15

The main idea behind multigrid is projection. I try to think about it as follows: Suppose I want to solve a PDE on with a lot of accuracy, so I proceed to discretize the domain (let's say, using finite difference method) on a very fine grid with lots and lots of points. In the end, I setup my system of equations and I'm ready to solve it. I try using my ...

15

This site is possibly not a good place to ask for a detailed explanation with pseudocode (as stated in the FAQ, "If you can imagine an entire book that answers your question, you’re asking too much."), so you might want to start with one of the classical books on this topic (listed below) and come back with specific questions about concrete details you have ...

14

Parallel geometric multigrid is straightforward to implement on structured grids. Algebraic and unstructured multigrid are more technical, see this answer for links to implementations. In a multiplicative method (e.g. $V$-cycles), only one level can be computed on at a time. Since the number of levels is $\log_{c} N$ where $N$ is the number of degrees of ...

13

First, if you have a structured grid, you might want to use geometric instead of algebraic multigrid due to some theoretical and efficiency advantages (e.g. ability to rediscretize instead of using Galerkin coarse grid operators). Algebraic multigrid methods generally fall in two categories. Classical Algebraic Multigrid This method was introduced by ...

12

I believe comparing an iterative method (multigrid) to a direct/exact method (Thomas) in terms of exact operation count isn't really meaningful. IIRC, Thomas operation count is $8N$ for any tridiagonal system. The only time I can imagine multigrid conceivably beating that is for a trivial case of having a linear solution, and even then the cost of evaluating ...

11

PETSc multigrid (as a preconditioner) is quite mature and may be used with any of the KSP (iterative Krylov method) solvers in PETSc by typing: -pc_type mg However, this requires that you have some way of generating your coarse levels, such as having structured grids defined by PETSc DA objects, which will be coarsened automatically. Or, if you want to ...

11

Where did you come up with interpolating the "error"? (And how do you measure the error?) On the first visit to a finer grid, the entire solution $u$ must be interpolated, ideally using a higher order operator (e.g., postprocessed/reconstructed solution for FEM). This FMG interpolation is $u^h \gets \mathbb{I}_H^h u^H$. (It's okay to use the a normal ...

11

The short answer is that the Thomas algorithm will be faster than any iterative scheme for almost all cases. The exception would perhaps be applying a single iteration of a very simple iterative scheme such as Gauss-Seidel, but this is highly unlikely to give an acceptable solution. Also, this is ignoring parallel processing concerns. Multigrid is an ...

10

Given interpolation $I_H^h$ and restriction $I_h^H$ (where restriction is typically $(I_H^h)^T$ for symmetric problems), with fine grid discretized operator $A^h$, there are two common approaches for constructing the coarse grid operator $A^H$. (Petrov-)Galerkin coarse operators This explicitly computes the matrix triple product $$A^H = I_h^H A^h I_H^h .$$...

10

BoomerAMG is a part of the Hypre package, which is dead simple to acquire. A much less complex code if you're starting out looking at these methods might be PyAMG.

10

In some cases, (F)MG provides an algorithm with optimal properties. For instance, properly tuned FMG can solve some elliptic problems in a small number of "work units", where a work unit is defined to be the computational effort required to express the problem itself - in this case the operations to form the residual $b-Ax$ on the finest grid. This is such ...

9

This is an excellent writeup but I think saying that (multilevel) DD and MG have a lot in common is not accurate, or at least not useful. The methods are very different and I don't think that expertise in one is very useful in the other. First, the two communities use different definitions of complexity: DD optimizes the condition number of the ...

8

One simpler explanation - the range of the restriction operator is the coarse grid space, while the range of the interpolation operator is the fine grid space. Unless the two are equal, interpolation + restriction will not result in an identity matrix, because there will always be components of $x$ which are truncated by the restriction operator and lost.

7

Brandt's book Multigrid techniques has a good discussion of the Full Approximation Scheme, the 1982 Guide to Multigrid Development also has some discussion. As with linear problems, the requirement is for the smoothers to remove high-frequency components of the residual. The formal spectral analysis only applies to linearized problems, but FAS theory only ...

7

I assume you are solving a nice elliptic problems like the Laplacian with smooth coefficients. (You should always check convergence in this friendly setting first.) Confirm that interpolation is as accurate as necessary. There usual rule for vertex-centered MG is that the sum of interpolation and restriction orders should be at least as high as the order of ...

7

Both PETSc and Trilinos have good algebraic multigrid methods. deal.II implements geometric multigrid methods for finite element discretizations, see for example the step-16 tutorial program.

7

I don't directly know your answer as I mainly use FAS instead of correction since I do multigrid for nonlinear problems, but some thoughts you can look into: You're applying a linear correction scheme to a linear problem, so it's not shocking that it does very well. Consider your boundary conditions: make sure you're doing them correctly, and also note that ...

6

Additive methods expose more concurrency. They are generally only faster than multiplicative methods if you can use that concurrency. For example, coarse levels of multigrid are typically latency-limited. If you move coarse levels to smaller subcommunicators, then they could be solved independently from the finer levels. With a multiplicative scheme, all the ...

6

This isn't a multigrid issue, it's a problem formulation issue. Consider the symmetric system $A x = b$ and suppose that $A e = 0$ for some nonzero vector $e$ (the constant when $A$ is the Laplacian with periodic or Neumann boundary conditions). This system is singular and has no solution if you choose $b$ such that $e^T b \ne 0$. Indeed, the exact periodic ...

6

If you are using a vertex-centered discretization, then state restriction should be injection rather than the full-weighted residual restriction that it appears you use. That is, replace $I_h^H$ with $\hat I_h^H$ when restricting the state. Using full-weighted restriction for state produces aliasing of high-frequency components of the state which after ...

6

Multigrid doesn't need a Cartesian (rectangular), uniform grid. What it needs is that you can define a fine and a coarse level (possibly recursively, if you want to go from a two-level to a multi-level scheme), and that you can define interpolation operators between these levels. The easiest way to explain this is if you indeed have a Cartesian grid, but you ...

6

There are "Algebraic Multigrid Methods" that can be applied to general systems $Ax=b$.

5

The smoother, restriction and prolongation can be tested independently. In essence, take a periodic domain, put in a particular Fourier mode and see if the code behaves in accordance with Fourier analysis. Also, in Briggs, Henson and McCormick's A Multigrid Tutorial you will find a section called Diagnostic tools (Chapter 4). That should help you with ...

5

Another classic: Wesseling, An Introduction to Multigrid Methods, John Wiley & Sons, 1992. Example codes can be found at MGNet

5

For SPD problems additive methods are better for MG smoothing for several reasons as mentioned already and a few more: @Article{Adams-02, author = {Adams, M.~F. and Brezina, M. and Hu, J. J. and Tuminaro, R. S.}, title = {Parallel multigrid smoothing: polynomial versus {G}auss-{S}eidel}, journal = {J. Comp. Phys.}, year = {2003}, volume = {188}, ...

5

There are two different flavors of smoothing and stability. The spurious oscillations in convection-diffusion problems are not an artifact of the linear solver but an inevitable artifact of the discretization method. Any linear solver for non-symmetric matrices you use will give you the same wiggly answer, or it's wrong. Multi-grid is one such linear solver. ...

5

The answer depends somewhat on the discretization; for example, some boundary integral discretizations result in very well-conditioned matrices, for which a Krylov solver works just fine without having to introduce the multi-level machinery of multigrid. For ill-conditioned matrices arising from finite difference or finite element methods, Krylov solvers ...

4

According to Jed's answer, MG uses moderate coarsening while DD uses rapid coarsening. I think this makes a difference when they are parallelized. There will be multiples of communications and synchronizations for MG to go through many levels of coarsening that are equivalent to a single coarsening of DD. Another point from Jed's answer is MG uses cheap ...

Only top voted, non community-wiki answers of a minimum length are eligible