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.
6
votes
2answers
73 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
87 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
0answers
22 views
Preconditioning grad(ln(u)) term
I am trying to solve a nonlinear diffusion-type problem using the finite element method which has the following terms:
$-\nabla\cdot k_1\nabla u - \nabla\cdot k_2\nabla\mathrm{ln}(u) = 0$ in $\Omega$
...
0
votes
1answer
33 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 ...
4
votes
0answers
233 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
213 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 ...
4
votes
3answers
221 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
204 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
165 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
123 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?
5
votes
0answers
132 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
83 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
129 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
159 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
434 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
102 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 ...
6
votes
1answer
232 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
370 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
357 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
71 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
737 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
123 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 ...
8
votes
1answer
311 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
258 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
223 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
198 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
136 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
150 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
109 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 ...
1
vote
2answers
145 views
Specific questions for 2-D Multigrid
I am simulating $\nabla^{2}u=0$ with mixed Dirichlet-Neumann boundary conditions on 2-D using 2-Grid method. Dirichlet ...
13
votes
1answer
716 views
How is Krylov-accelerated Multigrid (using MG as a preconditioner) motivated?
Multigrid (MG) may be used to solve a linear system $Ax=b$ by constructing an initial guess $x_0$ and repeating the following for $i=0,1..$ until convergence:
Compute the residual $r_i = b-Ax_i$
...
1
vote
0answers
47 views
Optimization of nonlocal stencil-like operator on subset of regular grid
I am trying to optimize the execution time for this particular piece of fortran code.
Details:
i_gc is a (ngpts, 3) array of containing (i,j,k) indices for each grid point. This is a subset of the ...
3
votes
2answers
221 views
Can F-cycle substitue FMG for update of existent solution?
I have a nicely working multigrid solver, which I use for solving the Poisson equation from an electrostatic problem. I solve this equation first without any charges, and then many times with a slowly ...
2
votes
2answers
97 views
Infinite Function Value on Dirichlet Boundary
I have been working on a multigrid solution to a non-homogeneous Dirichlet boundary value problem. However, the function goes to infinity on the boundary. This causes numerical overflow errors to be ...
0
votes
2answers
107 views
How to determine the number of c points in algebraic multi grid
I am trying to write an algebraic multi-grid solver (in c++). At a given level I determine which nodes are c-points and which nodes are f-points (where the total number of c and f points equals the ...
13
votes
3answers
3k views
Is the Thomas algorithm the fastest way to solve a symmetric diagonally dominant sparse tridiagonal linear system
I am wondering if the Thomas algorithm is the fastest way (provably?) to solve a symmetric diagonally dominate sparse tridiagonal system in terms of algorithmic complexity (not looking for ...
4
votes
1answer
228 views
Multigrid stops converging when more grid levels are used
I'm having a problem with multigrid code I wrote. If I solve Laplace's equation in 2D and use more than 5 grid levels, the V-cycles stop converging after a few cycles (see below, convergence factor > ...
0
votes
1answer
194 views
What libraries provide an implementation of multigrid?
I am working on numerical method of Multigrid. What's the available implementation(solver) (actually used in scientific computation) of multigrid method?
3
votes
1answer
300 views
Linear Algebra / Numerical Solution Of Matrix With Nullspace
I have a question relating to linear algebra.
We have a fluid solver that solves the poisson equation for pressures. When there are areas of the domain that are entirely enclosed by Neumann ...
3
votes
2answers
368 views
Full Multigrid Performance for Poisson's equation using Higher Order Compact scheme as a Gauss Seidel smoother
I have a question regarding the FMG (Full Multi Grid) performance while computing Poisson's equation using Higher Order Compact discretization. I am using a sixth order compact scheme to discretize ...
6
votes
1answer
327 views
Full Multigrid Prolongation Operator
I am looking into full multigrid, FMG, and several sources, including these slides, that a lot of people are referring to, state that the prolongation operator used in FMG the first time you visit a ...
9
votes
3answers
426 views
FAS-multigrid slower than linear defect correction?
I have implemented a V-Cycle multigrid solver using both a linear defect correction (LDC) and full approximation scheme (FAS).
My problem is the following: Using LDC the residual is reduced by a ...
6
votes
1answer
166 views
How to perform multigrid technique when relaxation methods don't converge?
It is well known that, when a system of linear equations is obtained from discretization of partial differential equation, the solution process can be accelerate significantly by multigrid technique. ...
3
votes
1answer
114 views
explicitly forming coarse matrices with polynomial smoothing AMG
I've been reading about the algebraic multigrid algorithm and came across polynomial smoothers in this paper. It's my understanding that usually the coarse-level matrices
$A_H = I_h^HA_hI_H^h$
are ...
0
votes
1answer
47 views
Clarification on interpolation equalities given by Briggs
Briggs, "A Multigrid Tutorial" (pg. 35) has the following expressed as 2-D interpolation:
\begin{align*}
v^h_{2i,2j} &= v_{i,j}^{2h}\\
v^h_{2i+1,2j} &= 0.5\cdot(v_{i,j}^{2h} + v_{i+1,j}^{2h})\\...
3
votes
1answer
769 views
Prolongation/Restriction Operator in Multigrid
In Multigrid, using Poisson's equation, does the equality below always hold regardless of what type of boundary conditions you use?
$$
R= c\cdot I^T, \text{ for some constant }c
$$
where $R$ and $I$ ...
5
votes
1answer
268 views
Periodic BC for Multigrid in MD
I know that this question might be very specific and maybe nobody will know the answer, but this is probably the only community where I could find an answer:
So, as part of my master's project, I am ...
5
votes
2answers
263 views
I'm having trouble debugging multigrid. What to do?
I've spent far too much time coding and debugging multigrid. While I clearly can't post all of my code as it would be silly to ask someone to go through all that code, is there anything I should pay ...
5
votes
1answer
793 views
restriction and interpolation in multigrid method
I need detailed explanation of the formula below
A2=I1*A1*I2
I suppose this formula computes matrix A2 on a coarse grid and here A1 is original matrix on fine ...
14
votes
3answers
2k views
multigrid method to solve PDE
I need simple explanation of the Multigrid Method or some literature about this.
I am familiar with iterational methods including BiCGStab,CG,GS,Jacobi and preconditioning, but I am a beginner with ...
