8
votes
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 ...
- 3,102
6
votes
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-...
- 53.6k
6
votes
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 ...
- 3,102
6
votes
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$.
- 18.4k
6
votes
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".
- 10.6k
5
votes
Accepted
stabilizing advection-diffusion with multi-grid?
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 ...
- 10.9k
5
votes
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 ...
- 4,249
5
votes
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 ...
- 53.6k
4
votes
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 ...
- 483
4
votes
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 ...
- 1,869
4
votes
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 ...
- 53.6k
4
votes
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 ...
- 901
4
votes
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 ...
- 53.6k
4
votes
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 ...
- 53.6k
4
votes
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 ...
- 813
3
votes
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 ...
- 3,108
3
votes
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 ...
- 53.6k
3
votes
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 ...
- 53.6k
3
votes
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-...
- 1,869
3
votes
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 ...
- 53.6k
3
votes
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 ...
- 2,069
3
votes
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
$$
...
- 10.6k
2
votes
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 ...
- 1,074
2
votes
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 ...
- 53.6k
2
votes
Quadtree type Grid
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 ...
- 1,869
2
votes
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-...
- 3,063
2
votes
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 ...
- 131
2
votes
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 ...
- 2,141
2
votes
Accepted
Converting mass density to point mass approximation on a grid
It seems like you are inventing Barnes-Hut-type algorithm, which is a fundamental accelerated algorithm for n-body simulations. It follows a similar logic: you combine masses on a grid. But, it is ...
- 8,592
2
votes
Algebraic multigrid in PETSc
AMG can be used with all examples in PETSc. There are three robust implementations that you might want to use
-pc_type gamg is a native (smoothed) aggregation ...
- 25.5k
Only top scored, non community-wiki answers of a minimum length are eligible