Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

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: math.nyu.edu/faculty/greengar/poiss2d.pdf –  Paul Nov 22 '12 at 15:01
1  
Should not finite element discretization with a multigrid solver for the resulting system of linear equation do it in $O(n)$? –  Thomas Witkowski Nov 23 '12 at 6:10
add comment

1 Answer

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

share|improve this answer
add comment

Your Answer

 
discard

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.