Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

For the 2D Poisson equation, there exist on finite difference mesh, some code taking $O(n \log(n))$ operations to solve it on a mesh with $n$ nodes. They rely on Fast Fourier Transform or Block Cyclic Reduction.

Is there anything as fast on unstructured meshes? I am afraid no, but fast solution of Poisson equation on unstructured meshes is a common problem. Any known efficient solution method?

share|improve this question
Hi @MathieuDutourSikiric, and welcome to Scicomp! Have you looked at this method: – Paul Nov 22 '12 at 15:01
Should not finite element discretization with a multigrid solver for the resulting system of linear equation do it in $O(n)$? – Thomas W. Nov 23 '12 at 6:10

Multigrid solves the Poisson equation with complexity $O(n)$ which is the optimal possible complexity.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.