5
$\begingroup$

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?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Hi @MathieuDutourSikiric, and welcome to Scicomp! Have you looked at this method: math.nyu.edu/faculty/greengar/poiss2d.pdf $\endgroup$ – Paul♦ Nov 22 '12 at 15:01
  • 1
    $\begingroup$ Should not finite element discretization with a multigrid solver for the resulting system of linear equation do it in $O(n)$? $\endgroup$ – Thomas W. Nov 23 '12 at 6:10
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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