12
votes
Iteration counts of AMG solver changes in parallel
This is something that can happen in almost any numerical algorithm running in parallel.
It's important to know that floating-point addition is not associative due to round-off errors. Thus you can't ...
- 18.9k
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.9k
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,162
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".
- 12k
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 ...
- 56.2k
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 ...
- 56.2k
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 ...
- 56.2k
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 ...
- 996
4
votes
Iteration counts of AMG solver changes in parallel
@brianborchers has already given one answer. Here is another: When you throw a matrix into an AMG algorithm, it needs to figure out a coarsening strategy whereby it determines a smaller linear system ...
- 56.2k
3
votes
Accepted
Restriction in (geometric) multigrid for vectors of non-even length
I have found what I was looking for in Wesseling's book: An introduction to multigrid methods. For vectors with an even number of elements, a cell-centered approach is employed where coarser grid ...
- 2,352
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,099
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 ...
- 56.2k
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,136
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 ...
- 56.2k
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 ...
- 56.2k
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,919
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
$$
...
- 12k
3
votes
Intergrid transfer operator for Discontinuous Galerkin method (multigrid)
There is really nothing different between continuous and discontinuous finite element spaces: The injection mapping you state is exact in the sense that you can represent a coarse function on the fine ...
- 56.2k
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,205
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,712
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.7k
2
votes
How to implement Geometric Multigrid in non-rectangular grids?
The catch here is that refining a mesh is easy/mechanical, but coarsening really isn't. So think about the problem from the other direction: mesh your problem as coarsely as possible, just enough to ...
- 5,046
2
votes
How suitable is multigrid method for time-dependent PDEs?
This statement seems a bit reductive for what is a rather large and involved problem. But multigrid, although it was developed for and is ideal for elliptic problems, is still just about the best we ...
- 2,099
2
votes
Accepted
Can a direct method like Thomas be used in a multigrid method as a smoother?
If you can solve the linear system with a direct solver, then that's exactly what you should be doing. Multigrid is a method that can be used if you don't have the time or memory resources to use a ...
- 56.2k
2
votes
How coarsening rate affects MG convergence?
Yes, quicker coarsening means that your coarse grid correction is not as good and that you need more MG cycles. For a well-tuned multigrid, you reduce the error by about a factor of 5-10 for each CG ...
- 56.2k
2
votes
Accepted
Algebraic Multigrid on fine mesh vs. just starting with coarse mesh?
It does seem like that should help at first but it doesn't. The thing to understand is that that would entail a great deal of wasted computation as in multigrid you don't solve the coarse grid problem,...
- 2,099
2
votes
Accepted
Prolongation and restriction operators in multigrid for high order PDEs
I found out how the kernels are typically constructed - the coefficients arise from sampling on the finer grid the interpolation synthesis function $\phi_k$ defined on the coarser grid. The synthesis ...
- 2,352
Only top scored, non community-wiki answers of a minimum length are eligible