Tag Info

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

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

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,152

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".
• 11.6k

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 ...
• 55.8k

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

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 ...
• 55.8k

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 ...
• 55.8k
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 ...
• 1,008

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 ...
• 55.8k
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,197

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,089

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 ...
• 55.8k

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,126
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 ...
• 55.8k
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 ...
• 55.8k
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,909

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  ...
• 11.6k

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 ...
• 55.8k
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,143
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
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
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,692

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

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 ...
• 4,936

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,089
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 ...
• 55.8k

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 ...
• 55.8k
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,197