# Tag Info

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

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

### Multigrid on "not perfectly rectangular" grid

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

### For which problems Krylov subspace methods are preferred over multigrid methods?

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

### Can I use multigrid to solve linear algebra problems that do not arise from a differential equation?

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

### Eigenvectors of Laplacian

They're on Wikipedia, for instance, in a page with the slightly unclear name of "Eigenvalues and eigenvectors of the second derivative".
Accepted

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

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

Yes, it is normal to have no convergence checks in MG for a few reasons. First, if you use a different number of iterates on each pass, then the MG operator is no longer linear, and you would have to ...

### Why post-smoothing in MG is needed?

Post-smoothing reduces the high frequency error that is introduced by the coarse grid correction. If you visualize a correction computed on a mesh of size $2h$, then it has no kinks on half of the ...

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

Definitely not. To pick one example, the book Multigrid has a plot on page 53 (Figure 2.10) that shows the decrease in the residual as a function of the number of V or W cycles. You would stop ...

### Multigrid on "not perfectly rectangular" grid

Lets say that you have the following grid composed of rectangular elements: Now if you perform your interpolation assuming a normal structured rectangular grid then you will be introducing errors ...

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

There are two parts of the answer. First, you don't get the identity because you throw away information during the restriction operation (if you think of a larger mesh than just the three points you ...

### For which problems Krylov subspace methods are preferred over multigrid methods?

This question is pretty well discussed in literature. However, there are lots of questions concerning multigrid on SciComp, so I decided to compose more or less detailed answer. I. When multigrid ...

### Algebraic multigrid as solver and as preconditioner

Most people use (algebraic as well as geometric) multigrid as preconditioners these days. It's an empirical observation that that leads to faster convergence in terms of iterations, given that in a ...

### Interpolation and Restriction operators in Multigrid

It's fundamentally because if you have that $A^h$ is a symmetric matrix, you want that $A^{2h}=P^TA^hP$ is also a symmetric matrix. You want this because you want to again use the same kind of ...
Accepted

### Generalized eigenvalue problem for large, potentially ill-conditioned systems

For large systems, any direct solver methods tend to be a dead end as what often starts as a sparse system ends up becoming dense. In fact, just storing all eigenvectors is itself typically impossibly ...

### Algebraic multigrid for complex valued matrices

Check Algebraic Multigrid Solvers for Complex-Valued Matrices by MacLachlan and Osterlee. On the implementation side of things, PyAMG supports complex-valued matrices. I've used it before and it ...
Accepted

### Is there any method to incorporate minor changes into solved meshes to speed convergence in particle-in-cell solvers?

Every iterative solver -- Jacobi, SSOR, CG, etc -- starts with an initial approximation. One often just uses the zero vector, but there is nothing wrong with using the solution of the previous time ...
Accepted

### How do multigrid approaches deal with Gibbs phenomenon?

The point important to understand when thinking about multigrid is that the lower levels of the hierarchy do not actually have to solve the problem accurately. Rather, the operators at the lower ...
Accepted

### Does algebraic multigrid reuse its coarse grids?

In algebraic multigrid there are usually two steps: 1) Setup: Here we compute the $A$ matrices and interpolation matrices ($W$, $W'$) at each grid level. This is based on computing c-points and f-...

### How the number of pre-smoothing and post-smoothing steps affect the asymtotic convergence rate of geometrical Multigrid?

Separately, but it does depend. Not very strongly, however: A very large number of pre- and post-smoothing steps only improves the convergence rate a little bit over a large number of steps. The ...

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

If I understand your question correctly you're solving a linear elasticity problem using conjugate gradient and it's preconditioned with a preconditioned AMG solver? It seems to me that this may be ...

### Reason for why apparent acceleration of algebraic multigrid solve by addition of positive definite diagonal matrix

The computation in your update does most of the work towards a solution. You just need to note that $\frac{\varepsilon_1}{\varepsilon_2} \leq \frac{\max D_{ii}}{\min D_{ii}} = \kappa(D)$, and that  ...
Accepted

### FENICS subdomains - restriction/ prolongation operators

There is currently no documented 'FEniCS way' to do this. However, since FEniCS is a pretty standard finite element code behind all the UFL and code generation magic, you can implement things like ...
Accepted

### Solving new linear system that comes from an $p$ enrichment

What you are thinking of is something that uses the structure of the augmented matrix to make solution of the system simpler. For example, one could be tempted to think of forming the Schur complement ...

Writing C++ code from the ground up for adaptive mesh refinement (as part of a PDE solver) is a relatively complicated endeavor and can easily involve thousands of lines of code for even simple ...
Accepted

### Python environments for AMG and Gauss Seidel as solvers instead of preconditioners

FEniCS tends to hide the details about the actual matrices it builds, and prevent easy manipulation of them. As far as I can tell this is a design decision, as they are trying to create an all-...
Accepted

### Null space for smoothed aggregation algebraic multigrid

First of all, I find the name "Smoothed Aggregation" a bit misleading, because the method - as I understood it - consists of both smoothing a tentative prolongation operator and implicitly considering ...
Accepted

### Algebraic multigrid for complex valued matrices

How can this approach be recycled to also solve complex valued problems like every harmonic simulation? The difference of an harmonic simulation to a static simulation are bigger than just replacing ...