2-Dimensional Poisson Problem: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
No edit summary
No edit summary
Line 12: Line 12:
== Parameters ==  
== Parameters ==  


No parameters found.
$n$: dimension of grid (where grid is discretized)


== Table of Algorithms ==  
== Table of Algorithms ==  
Line 26: Line 26:
| [[5-point Gauss elimination (2-Dimensional Poisson Problem Poisson Problem)|5-point Gauss elimination]] || 1945 || $O(n^{4})$ || $O(n^{4})$ || Exact || Deterministic ||   
| [[5-point Gauss elimination (2-Dimensional Poisson Problem Poisson Problem)|5-point Gauss elimination]] || 1945 || $O(n^{4})$ || $O(n^{4})$ || Exact || Deterministic ||   
|-
|-
| [[5-point Gauss Seidel iteration (2-Dimensional Poisson Problem Poisson Problem)|5-point Gauss Seidel iteration]] || 1945 || $O(n^{4} logn)$ || $O(n^{2})$? || Exact || Deterministic ||   
| [[5-point Gauss Seidel iteration (2-Dimensional Poisson Problem Poisson Problem)|5-point Gauss Seidel iteration]] || 1945 || $O(n^{4} \log n)$ || $O(n^{2})$? || Exact || Deterministic ||   
|-
|-
| [[5-point SOR iteration (2-Dimensional Poisson Problem Poisson Problem)|5-point SOR iteration]] || 1954 || $O(n^{3} logn)$ || $O(n^{2})$? || Exact || Deterministic ||   
| [[5-point SOR iteration (2-Dimensional Poisson Problem Poisson Problem)|5-point SOR iteration]] || 1954 || $O(n^{3} \log n)$ || $O(n^{2})$? || Exact || Deterministic ||   
|-
|-
| [[5-point ADI iteration (2-Dimensional Poisson Problem Poisson Problem)|5-point ADI iteration]] || 1955 || $O(n^{2} log^{2}n)$ || $O(n^{2})$? || Exact || Deterministic ||   
| [[5-point ADI iteration (2-Dimensional Poisson Problem Poisson Problem)|5-point ADI iteration]] || 1955 || $O(n^{2} \log^{2} n)$ || $O(n^{2})$? || Exact || Deterministic ||   
|-
|-
| [[9-point SOR iteration (2-Dimensional Poisson Problem Poisson Problem)|9-point SOR iteration]] || 1956 || $O(n^{3})$ || $O(n^{2})$? || Exact || Deterministic ||   
| [[9-point SOR iteration (2-Dimensional Poisson Problem Poisson Problem)|9-point SOR iteration]] || 1956 || $O(n^{3})$ || $O(n^{2})$? || Exact || Deterministic ||   
Line 36: Line 36:
| [[9-point Tensor product (2-Dimensional Poisson Problem Poisson Problem)|9-point Tensor product]] || 1964 || $O(n^{3})$ || $O(n^{2})$? || Exact || Deterministic || [https://epubs.siam.org/doi/pdf/10.1137/0113067 Time]
| [[9-point Tensor product (2-Dimensional Poisson Problem Poisson Problem)|9-point Tensor product]] || 1964 || $O(n^{3})$ || $O(n^{2})$? || Exact || Deterministic || [https://epubs.siam.org/doi/pdf/10.1137/0113067 Time]
|-
|-
| [[9-point ADI iteration (2-Dimensional Poisson Problem Poisson Problem)|9-point ADI iteration]] || 1965 || $O(n^{2} logn)$ || $O(n^{2})$? || Exact || Deterministic ||   
| [[9-point ADI iteration (2-Dimensional Poisson Problem Poisson Problem)|9-point ADI iteration]] || 1965 || $O(n^{2} \log n)$ || $O(n^{2})$? || Exact || Deterministic ||   
|-
|-
| [[5-point FFT (2-Dimensional Poisson Problem Poisson Problem)|5-point FFT]] || 1965 || $O(n^{2} logn)$ || $O(n^{2})$? || Exact || Deterministic ||   
| [[5-point FFT (2-Dimensional Poisson Problem Poisson Problem)|5-point FFT]] || 1965 || $O(n^{2} \log n)$ || $O(n^{2})$? || Exact || Deterministic ||   
|-
|-
| [[9-point ADI iteration + smooth guess (2-Dimensional Poisson Problem Poisson Problem)|9-point ADI iteration + smooth guess]] || 1969 || $O(n^{2} logn)$ || $O(n^{2})$? || Exact || Deterministic ||   
| [[9-point ADI iteration + smooth guess (2-Dimensional Poisson Problem Poisson Problem)|9-point ADI iteration + smooth guess]] || 1969 || $O(n^{2} \log n)$ || $O(n^{2})$? || Exact || Deterministic ||   
|-
|-
| [[5-point cyclic reduction (2-Dimensional Poisson Problem Poisson Problem)|5-point cyclic reduction]] || 1970 || $O(n^{2} logn)$ || $O(n^{2})$? || Exact || Deterministic ||   
| [[5-point cyclic reduction (2-Dimensional Poisson Problem Poisson Problem)|5-point cyclic reduction]] || 1970 || $O(n^{2} \log n)$ || $O(n^{2})$? || Exact || Deterministic ||   
|-
|-
| [[9-point FFT (2-Dimensional Poisson Problem Poisson Problem)|9-point FFT]] || 1978 || $O(n^{2} logn)$ || $O(n^{2})$? || Exact || Deterministic ||   
| [[9-point FFT (2-Dimensional Poisson Problem Poisson Problem)|9-point FFT]] || 1978 || $O(n^{2} \log n)$ || $O(n^{2})$? || Exact || Deterministic ||   
|-
|-
|}
|}

Revision as of 09:22, 10 April 2023

Description

Given $f$, solve for $u$ in the 2-dimensional Poisson equation:

$u_{xx} + u_{yy} = f(x,y)$

Related Problems

Related: 3-Dimensional Poisson Problem

Parameters

$n$: dimension of grid (where grid is discretized)

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
5-point star Cramer's rule 1945 $O({4}^{(n^{2})})$ $O({4}^{(n^{2})})$ for sure, $O(n^{2})$ possibly??? (if super conservative) Exact Deterministic
5-point Gauss elimination 1945 $O(n^{4})$ $O(n^{4})$ Exact Deterministic
5-point Gauss Seidel iteration 1945 $O(n^{4} \log n)$ $O(n^{2})$? Exact Deterministic
5-point SOR iteration 1954 $O(n^{3} \log n)$ $O(n^{2})$? Exact Deterministic
5-point ADI iteration 1955 $O(n^{2} \log^{2} n)$ $O(n^{2})$? Exact Deterministic
9-point SOR iteration 1956 $O(n^{3})$ $O(n^{2})$? Exact Deterministic
9-point Tensor product 1964 $O(n^{3})$ $O(n^{2})$? Exact Deterministic Time
9-point ADI iteration 1965 $O(n^{2} \log n)$ $O(n^{2})$? Exact Deterministic
5-point FFT 1965 $O(n^{2} \log n)$ $O(n^{2})$? Exact Deterministic
9-point ADI iteration + smooth guess 1969 $O(n^{2} \log n)$ $O(n^{2})$? Exact Deterministic
5-point cyclic reduction 1970 $O(n^{2} \log n)$ $O(n^{2})$? Exact Deterministic
9-point FFT 1978 $O(n^{2} \log n)$ $O(n^{2})$? Exact Deterministic

Time Complexity Graph

Error creating thumbnail: Unable to save thumbnail to destination

Space Complexity Graph

Error creating thumbnail: Unable to save thumbnail to destination

Time-Space Tradeoff

Error creating thumbnail: Unable to save thumbnail to destination