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.

Filter by
Sorted by
Tagged with
2 votes
1 answer
87 views

Creating nonuniform grids for FDM with multiple points of concentration

If I am creating a grid in the $S_i$ direction with $N_S+1$ grid points. If I want more steps around some $K$, I can use: $$ S_i=K+c \sinh \left(\xi_i\right), \quad i=0,1, \ldots, N_S $$ where $c=\...
THAT'S MY QUANT MY QUANTITATIV's user avatar
2 votes
0 answers
84 views

Why multigrid is inefficient?

I am trying to solve the Stokes equation containing viscosity nonlinearity using the open source finite element software underworld2 with nested PETSc. The resolution is 2000*200. The solution results ...
Darcy's user avatar
  • 21
2 votes
2 answers
120 views

Defining the restriction operator in nested multigrid FEM

I'm new in the multigrid approach and I'm trying to implement an algorithm from this paper: https://www.researchgate.net/publication/242913687_A_Multigrid_Algorithm_for_the_p-Laplacian I'm stuck with ...
Timofej's user avatar
  • 21
2 votes
2 answers
471 views

Iteration counts of AMG solver changes in parallel

I am solving the linear elasticity equation within a FEM library with a complex 3D geometry. The resulting linear system is solved with CG, preconditioned by AMG (Algebraic Multigrid). The computed ...
FEGirl's user avatar
  • 281
3 votes
1 answer
225 views

Generalized eigenvalue problem for large, potentially ill-conditioned systems

Say that I have a generalized eigenvalue problem of the form $$Ax=\lambda Bx.$$ Using MATLAB, some naive ways that one may solve this is by either directly inverting $B$ then applying the ...
user45844's user avatar
0 votes
0 answers
66 views

Compatibility condition for Poisson equation in cylindrical symmetry

I'm trying to implement multigrid approach for a Poisson equation $\frac{1}{r}\frac{\partial}{\partial r}\left( r \frac{\partial H}{\partial r} \right) = f$ with all Neumann boundary conditions. ...
Yakovenko Ivan's user avatar
0 votes
1 answer
71 views

How to combine multigrid preconditioner with jacobi preconditioner?

I have not found any relevant information in the literature on the following rather simple problem: How to combine (geometric) multigrid preconditioned conjugate gradient (MGPCG) with an additional ...
zx-81's user avatar
  • 1
1 vote
1 answer
73 views

Reason for why apparent acceleration of algebraic multigrid solve by addition of positive definite diagonal matrix

In passing I was told by someone that $K^{\prime}\in\mathbb{R}^{n\times n}$, will be easier to solve by an algebraic multigrid preconditioned conjugate gradient (CG-AMG) solver than $K$, where $K$ is ...
Tucker's user avatar
  • 189
1 vote
0 answers
58 views

Anisotropic lines identification algorithm

I am implementing an algorithm to identify the anisotropic lines in an unstructured mesh. This is done in the framework of an Agglomeration algorithm for Non-Structured multigrid applied to FV ...
albiremo's user avatar
  • 410
0 votes
1 answer
83 views

Interpolation and Restriction operators in Multigrid

I saw in several places that interpolation operator ($P$) and restriction operator ($P^T$) are usually transposes of each other (up to multiplication by a constant). As I understood it related to ...
ChaosPredictor's user avatar
0 votes
2 answers
121 views

Eigenvectors of Laplacian

I am studying introduction to Multigrid methods. In all tutorials, authors write that eigenvectors of Laplacian (1D, finite difference) are given as $w_k(x_i) = \sin(k \pi x_i),$ where $x_i$ is a ...
student1's user avatar
1 vote
1 answer
102 views

Algebraic Multigrid on fine mesh vs. just starting with coarse mesh?

So if I've understood it correctly, the Algebraic Multigrid Method (AMG) basically takes a fine mesh, coarsens it, solves the coarse mesh and projects the solution back on the fine mesh. Wouldn't it ...
MaxD's user avatar
  • 167
2 votes
1 answer
294 views

Prolongation and restriction operators in multigrid for high order PDEs

If I have the Poisson equation $\Delta u = f$ a standard transfer operator (for a regular grid) is the full weighting/bilinear interpolation scheme: $$K = \frac{1}{4}\begin{bmatrix}\frac{1}{4} & \...
lightxbulb's user avatar
  • 1,994
2 votes
1 answer
99 views

Restriction in (geometric) multigrid for vectors of non-even length

Naive restriction operators in geometric multigrid that I have seen are typically implemented as a convolution and a subsequent averaging of every two entries in a vector $v^h$. For example: $$\tilde{...
lightxbulb's user avatar
  • 1,994
0 votes
0 answers
81 views

Differences between Two-Grid Correction and V-Cycle Scheme

I found in A Multigrid Tutorial: Second Edition by William L. Briggs‏, Van Emden Henson‏, Steve F. (here) the following Schemes: Two-Grid Correction Scheme, p. 37: And V-Cycle Scheme, p. 40 I want ...
ChaosPredictor's user avatar
2 votes
0 answers
86 views

Multigrid method: linear solver and modified residual

I am trying to better understand the FAS multigrid algorithm for Euler equation in FV discretization. The usage of the modified residual (the residual with forcing) inside the different cases: ...
albiremo's user avatar
  • 410
1 vote
0 answers
80 views

Multigrid: Gauss–Seidel eigenvalues and eigenvectors

I am trying to figure out the questions from Multigrid Tutorial by Briggs. However I am stuck on these two questions. https://www.researchgate.net/publication/...
codelearner's user avatar
1 vote
1 answer
182 views

Algebraic multigrid as solver and as preconditioner

My question is around the efficiency of AMG. In which case AMG can perform better,as solver or as a preconditioner(for example a Krylov space method as CG)? Assume the case of elliptic pdes.
spyros's user avatar
  • 481
4 votes
0 answers
771 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 ...
sebsan's user avatar
  • 41
1 vote
0 answers
62 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 ...
spyros's user avatar
  • 481
2 votes
0 answers
157 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 ...
spyros's user avatar
  • 481
1 vote
1 answer
197 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/...
Freewill's user avatar
4 votes
1 answer
182 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 ...
Alexander's user avatar
2 votes
1 answer
111 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 ...
spyros's user avatar
  • 481
1 vote
1 answer
134 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 ...
computational_scientist's user avatar
2 votes
0 answers
396 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, ...
user31765's user avatar
  • 101
2 votes
1 answer
151 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?
spyros's user avatar
  • 481
1 vote
1 answer
64 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?
spyros's user avatar
  • 481
3 votes
1 answer
90 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?
spyros's user avatar
  • 481
2 votes
0 answers
72 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 ...
vydesaster's user avatar
1 vote
0 answers
44 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 ...
Happy's user avatar
  • 961
1 vote
1 answer
110 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 ...
spyros's user avatar
  • 481
2 votes
0 answers
75 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 ...
computational_scientist's user avatar
1 vote
1 answer
210 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 ...
spyros's user avatar
  • 481
1 vote
0 answers
62 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 ...
spyros's user avatar
  • 481
2 votes
2 answers
145 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 ...
spyros's user avatar
  • 481
2 votes
1 answer
91 views

Is there any method to incorporate minor changes into solved meshes to speed convergence in particle-in-cell solvers?

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). Because of the large number of ...
0xDBFB7's user avatar
  • 123
3 votes
1 answer
109 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 ...
arc_lupus's user avatar
  • 543
3 votes
1 answer
410 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 ...
vydesaster's user avatar
7 votes
2 answers
148 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 ...
vydesaster's user avatar
3 votes
1 answer
628 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. ...
vydesaster's user avatar
0 votes
1 answer
59 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 ...
huseyin tugrul buyukisik's user avatar
3 votes
0 answers
800 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 ...
Gaurav Saxena's user avatar
1 vote
1 answer
824 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 ...
Michael's user avatar
  • 1,463
4 votes
3 answers
398 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 ...
EngDR's user avatar
  • 191
1 vote
2 answers
382 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 ...
Jeremy Lim's user avatar
1 vote
1 answer
405 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 ...
nukeguy's user avatar
  • 158
3 votes
1 answer
145 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?
Abdelhafid Elharoussi's user avatar
5 votes
0 answers
180 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 $...
56th's user avatar
  • 901
1 vote
0 answers
89 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 ...
user20867's user avatar