Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
I think your question should contain more details. For instance, what is $n$ in $O(n)$ ? –  Denis Serre Dec 22 '10 at 13:24
    
There was an ICM talk about this. cs-www.cs.yale.edu/homes/spielman/icm2010.pdf –  rcompton Dec 27 '10 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 '11 at 21:45
add comment

2 Answers

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

share|improve this answer
add comment

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

share|improve this answer
    
@Steve, I guess FMM techniques use hierarchical techniques like MultiGrid techniques. Actually, I was looking for a randomised/approximate version. –  CSK Varma Dec 23 '10 at 4:15
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.