Questions tagged [multigrid]
An approach to solving systems of equations by projecting the problem from a fine scale representation onto a coarser one. A coarse representation generally has fewer unknowns, making it faster to solve than the original problem. The coarse solution can then be projected back onto the finer problem as an initial guess of the solution to the finer problem.
84
questions
3
votes
0answers
61 views
Construction of Prolongation and Restriction Operator for Geometric Multigrid (2D-FEM): Resulting in a Decreasing Solution
Consider the following problem,
$$ -\Delta u(x) = f(x), \qquad x \in \Omega \\ u(x) = 0,\qquad x \in \partial \Omega$$
with $\Omega = [0,1]\times [0,1]$ being the domain and $\partial \Omega$ being ...
0
votes
0answers
33 views
How can the choice of coarsening factor affect Multigrid's convergence?
The linear system $Ax=b$ is coming from the discretization of an elliptic PDE. Multigrid method is used in order to solve it. Suppose $c_0$ is the coarsening factor on level 0 and $c_m$ the coarsening ...
1
vote
0answers
34 views
Multigrid Reduction In Time Convergence
I am trying to solve a 2D dynamic linear elasticity model parallel in time using Xbraid. The spatial domain is [0,1]x[0,1] and time domain [0,1]. For time integration I am using a backward Euler ...
2
votes
0answers
148 views
Parallel In Time with Multigrid
I am trying to solve the linear finite element equation $M\ddot{u}+Ku=F(t)$, where $M$ is the mass matrix ,$K$ the stiffness matrix and $F(t)$ the external load vector, parallel in time using XBraid ...
0
votes
1answer
88 views
coarsening coefficient matrixes (A2h, A4h…) for geometric multigrid method in 2-D/3-D
I am learning about multigrid methods from the textbook section 6.3 Multigrid Methods, which shows a geometric multigrid algorithm for 1-D examples in detail, including how to build restriction/...
4
votes
1answer
76 views
Why does smoothed aggregation multigrid method used as preconditioner in conjugate gradient slows down the solution time?
I'm solving a system of linear equations obtained from the FEM discretization of a simple linear elasticity problem on a cube with zero displacements at one plane and a load on the opposite one. The ...
2
votes
1answer
42 views
Calculating coarse grid matrix in geometric multigird
The coarse grid matrix is calculated via RAP where R,P are the restriction and interpolation matrix,respectively.By checking a typical MG algorithm
I want to ask how to calculate efficiently coarse ...
1
vote
1answer
81 views
Full approximation scheme - smoothers - literature recomendation
I would like to use full approximation scheme(FAS) for solving nonlinear PDE. I am looking into practical implementation of FAS in parallel(MPI) settings. I noticed the most common/effective smoother ...
2
votes
0answers
81 views
Residual of Poisson equation with periodic boundaries
I am trying to write a multigrid solver for Poisson's equation, $-\Delta u=f$, on the unit square, $\Omega=(0,1)^2$ with periodic boundaries. My primary source has been Multigrid by Trottenberg, ...
1
vote
1answer
72 views
How the number of pre-smoothing and post-smoothing steps affect the asymtotic convergence rate of geometrical Multigrid?
Does the convergence rate of multigrid depend on the total number of smoothing steps or on the number of pre and post smoothing steps seperately?
1
vote
1answer
52 views
How coarsening rate affects MG convergence?
If we use an aggresive coarsening how does this affect the convergence of a MG cycle?Is the convergence slower?Do we need more cycles in this case?
2
votes
1answer
59 views
Why post-smoothing in MG is needed?
In pre-smoothing we eliminate high frequencies,but what about post-smoothing?Is it used for the remain high frequencies that pre-smoothing didn't eliminate?
2
votes
0answers
51 views
Avoid matrix multiplication in algebraic multigrid method
Currently when I try to solve a linear algebra system of the form of $A x =b$ I use the algebraic multigrid method. The algebraic multigrid method uses a Galerkin product to form the coarse grid ...
1
vote
0answers
32 views
What kind of problem or matrices are suitable for multigrid method?
For Poisson or Convection-diffusion equation as follows:
$$
-\Delta u=f,\qquad u|_\Omega = g.
$$
or
$$
-\Delta u +\vec{w}.\nabla u=f,\qquad u|_\Omega = g.
$$
using FDM or FEM discretization, we can ...
0
votes
1answer
68 views
How to implement Geometric Multigrid in non-rectangular grids?
It is quite easy to implement multigrid on a rectangular grid but what about an non-rectangular?How to coarse a non-rectangular grid and apply multigrid(assume an easy non-rectangular grid capital ...
2
votes
0answers
57 views
Multilevel minimization - boundary conditions
I am interested in minimizing
$$min_{x \in R^{n^l}} f^l(x),$$
where $f^l(x)$ is nonlinear objective function arising from discretization of PDE. I would like to use nonlinear multilevel minimization ...
1
vote
1answer
173 views
How suitable is multigrid method for time-dependent PDEs?
For elliptic PDEs (Poisson-type), the multigrid method is very sufficient, but how about time-dependent problems (i.e parabolic or hyperbolic PDEs)?
Is it efficient to solve such problems using a ...
1
vote
0answers
59 views
Can the standard multigrid performance be used for time-dependent PDEs?
Consider a time dependent pde(i.e u(x,t)).I know when only space-coarsening is used the standard multigrid performance can be applied but what if instead we use only time-coarsening?Can we apply the ...
2
votes
2answers
81 views
Can a direct method like Thomas be used in a multigrid method as a smoother?
As far as I know, multigrid uses stationary iterative methods as smoothers (i.e GS), but can we use a direct method also?
For example, in case we have a tridiagonal system (for example 1D heat ...
1
vote
1answer
52 views
Is there any method to incorporate minor changes into solved meshes to speed convergence in particle-in-cell solvers?
Apologies for the terrible title.
I'm trying to perform a 10^6 timestep electrostatic particle-in-cell simulation on a rather large mesh, with very limited computational resources (a single GPU). ...
3
votes
1answer
96 views
How do multigrid approaches deal with Gibbs phenomenon?
I know (from https://scicomp.stackexchange.com/a/31339/20545, among others) that I need a certain mesh density in FEM, else I might get non-physical oscillations in my solution.
How do multigrid ...
2
votes
1answer
109 views
Null space for smoothed aggregation algebraic multigrid
I do not really get the point of null space usage for creating the prolongation operator for smoothed aggregation algebraic multigrid. I know what the null space is per definition and I know that the ...
7
votes
2answers
108 views
Algebraic multigrid for complex valued matrices
Assume one uses the classical AMG with Ruge-Stuben coarsening and direct interpolation for solving real valued problems. How can this approach be recycled to also solve complex valued problems like ...
1
vote
1answer
198 views
Multigrid preconditioner for conjugate gradient methods
When solving $A*x=b$ using preconditioned conjugate gradient methods one has to solve $z=K^{-1}*r$ for the preconditioning where $K$ is the preconditioner of $A$ and $r$ is the residual vector.
...
0
votes
1answer
35 views
Converting mass density to point mass approximation on a grid
In an nbody gravity simulation, instead of doing exact(all-pair brute force) solution, I added masses of each body into cells of a 3D grid(each cell is just a float value having a mass value). Then ...
3
votes
0answers
435 views
Neumann-Neumann boundary intersection
I am trying to solve a Vertex Centered, Finite Difference, Poisson equation $-\nabla^{2}u=f$ with Dirichlet boundaries on the left and bottom and Neumann boundaries on the top and right using ...
1
vote
1answer
380 views
Algebraic multigrid in PETSc
Consider a potential/poisson equation on a very large, complicated geometry. Currently, an self-written FEM and linear solvers from NumPy are used. Performance is, of course, not good enough for ...
3
votes
3answers
285 views
For which problems Krylov subspace methods are preferred over multigrid methods?
As multigrid methods are known to have grid independent convergence rates with $O(N)$ computational cost, then why would one be interested in using Krylov subspace methods at all, for which ...
1
vote
2answers
271 views
V-cycle Multigrid for 2D transient heat transfer on a square plate using finite difference
I'm currently developing a program to solve 2D transient state heat conduction on a square plate using the V-cycle multigrid. Althought my program is able to reach the steady state solution, it's ...
1
vote
1answer
257 views
What is the default smoother for the “PCMG” preconditioner in PETSc?
For a large parallel sparse matrix (mpiaij type matrix) in my code, I was experimenting with various preconditioners to see which one would do best with GMRES/BiCGSTAB. I tried the PCMG ...
3
votes
1answer
131 views
Can I use multigrid to solve linear algebra problems that do not arise from a differential equation?
Can the Multigrid method be applied to solve a linear system of equations in the form $Ax=b$, that is not necessarily related to differential equations?
4
votes
0answers
154 views
Geometric Multigrid for Conform and Non–″ Elements: Restriction Operators
First of all, let me set up some notations.
Suppose we have a hierarchy of meshes $\mathcal{T}_0 \subset \mathcal{T}_1 \subset \dots \subset \mathcal{T}_n$. For simplicity I restrict myself here to $...
1
vote
0answers
84 views
What does it take to prove that a multigrid algorithm scales linearly with system size?
It is my understanding that the multigrid solution techniques are generally the preferable method to solve large Poisson problems. Now assume I have written a multigrid solver that is tailored to my ...
3
votes
0answers
179 views
Multigrid for Robin boundary conditions
I have a question regarding the treatment of Robin boundary conditions in a multigrid solver. I am solving the Poisson equation in $\Omega=(0,1)^2$ with Robin boundary conditions on the boundary,
$$- \...
1
vote
0answers
188 views
Algorithm for Adaptive Mesh Refinement
I am trying to implement Adaptive Mesh Refinement. I am not a Mathematics/Computational Science person so I will try to write the algorithm in a simpler way. I will be grateful if experts can comment ...
3
votes
2answers
610 views
Python environments for AMG and Gauss Seidel as solvers instead of preconditioners
I am working on block preconditioning and seemingly it is common to write customised Krylov solvers for them. Within each solver, the individual block linear system with preconditioners are ...
5
votes
1answer
111 views
Does algebraic multigrid reuse its coarse grids?
Admittedly, I'm new to the subject, so this is probably a really simple question.
Let's assume I want to solve the (large sparse) linear system Ax = b multiple times with algebraic multigrid and b ...
5
votes
1answer
240 views
Robust smoothers for geometric multigrid
I'm searching for robust smoothers for geometric multigrids.
By robust I mean:
Effective for high order approximations (say spectral element, spectral Discontinuous Galerkin),
Parallel (suitable for ...
2
votes
1answer
437 views
How to define residual in multigrid approach?
I wish to solve the two-dimensional Navier Stokes equations using multigrid method on a collocated grid using the Predictor-Corrector method mentioned below. But first, let me elaborate on what I had ...
12
votes
2answers
463 views
Algebraic Multigrid: Why does the product of interpolation and restriction not result in something with norm 1?
I'm currently working with "A Multigrid Tutorial" by Briggs et al, Chapter 8.
The construction of the interpolation operator is given as:
Then construction of restriction operator and fine grid ...
2
votes
1answer
74 views
Solving new linear system that comes from an $p$ enrichment
Let's say I am solving a simple Poisson problem using a Mixed (DG) finite element method. If we use orthogonal polynomials as basis functions we can write the finite-dimensional linear system as
$$
...
0
votes
1answer
927 views
Quadtree type Grid
I would like to code for a quadtree type meshing but don't know how to do. If anyone can help or can share any starting code?
2
votes
1answer
138 views
Solve FEM matrix from coupled system
I'm developing an FEM solver for a coupled system. I have diffusion and potential equations which result in positive definite matrices for each equation, but the coupling makes the overall system ...
9
votes
1answer
373 views
Increasing V-cycles for constant Coarsest Grid Size and increasing Fine Grid size
Problem statement
I implemented geometric multigrid for $-\nabla^{2}=f$ where $f=\frac{3\pi^{2}}{4}sin \frac{\pi x}{2} sin \frac{\pi y}{2} sin \frac{\pi z}{2}$ on $\Omega \in [0,1]$ on a unit cube. ...
12
votes
3answers
304 views
Is it usual to have no convergence checking in Multigrid?
I just read Chapter 3 in "A Multigrid Tutorial" by Briggs/Henson/McCormick, link.
The text is about Multigrid cycles such as V-cycle, mu-cycle, FMG. What caught my eye: In most iterative procedures ...
9
votes
2answers
270 views
Multigrid on “not perfectly rectangular” grid
Multigrid introductions normally use a rectangular grid. Interpolation of values is then straight forward: Just interpolate linearly on the edge between two adjacent nodes of the coarse grid to find ...
1
vote
1answer
230 views
FENICS subdomains - restriction/ prolongation operators
I am trying to implement my own multigrid method in fenics. Is there any "smart/ fenics" way how to assemble subdomains and obtain restriction/ prolongation operators ?
Thanks!
3
votes
1answer
164 views
stabilizing advection-diffusion with multi-grid?
If one chooses to discetize the advection-diffusion (AD) equation using the standard Galerkin finite element method, stability issues may arise in cases of high Peclet number (i.e., high advection to ...
3
votes
1answer
157 views
Challenges in implementing Algebraic Multigrid on millions of processors
I just implemented an Algebraic Multigrid solver for a Mixed Dirichlet-Neumann Boundary Value problem and was surprised to see the speed-up as compared to a simple iterative solver for a large problem ...
1
vote
1answer
116 views
A doubt in Multigrid V-cycle
Assume I have 3 levels of grids. Finest Grid = level 2, Coarser Grid = level 1, Coarsest Grid = level 0.
Relax $u$ on $Au = b$ at level 2 for 3 times.
Find residual $r2$ at level 2, then restrict to ...
