Welcome to MathOverflow

Question

1

2

Are there some approximate or randomised algorithms to numerically solve Poisson's Equation in Partial Differential Equations.(http://en.wikipedia.org/wiki/Poisson%27s_equation). The best algorithms I know of are Multigrid methods(http://en.wikipedia.org/wiki/Multigrid_methods), but they are deterministic and are O(n). Are there Randomised or approximate algos to solve this problem.

flag	asked Dec 21 2010 at 18:26 CSK Varma 59●1

I think your question should contain more details. For instance, what is $n$ in $O(n)$ ? – Denis Serre Dec 22 2010 at 13:24

There was an ICM talk about this. cs-www.cs.yale.edu/homes/spielman/icm2010.pdf – rcompton Dec 27 2010 at 20:08

3

You ask for random or approximate algorithms. You then mention the multigrid method. This gives approximate solutions to PDEs. Haven't you answered your question already? In addition, you say "the best algorithms I know are ... but ... are O(n)". The use of "but" implies that O(n) (whatever n is) conflicts with "approximate or randomised". I can't see why and it suggests you've left something out. Maybe you particularly seek fast algorithms. What actually is your question? – Dan Piponi Jan 4 2011 at 21:45

Steve Huntsman · Answer 1 · 2010-12-21 19:45:04Z UTC

0

How about the fast multipole method? (Or does that count as multigrid?)

answered Dec 21 2010 at 19:45

Steve Huntsman
8,139●1●22●56

@Steve, I guess FMM techniques use hierarchical techniques like MultiGrid techniques. Actually, I was looking for a randomised/approximate version. – CSK Varma Dec 23 2010 at 4:15

Andrew Homan · Answer 2 · 2011-02-15 21:22:16Z UTC

1

You can modify the method described here for the Laplace equation to work for Poisson.

answered Feb 15 2011 at 21:22

Andrew Homan
263●1●8

Approximate Algorithms for Poisson’s Equation (PDE)

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.