2-Dimensional Poisson Problem: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 12: | Line 12: | ||
== Parameters == | == Parameters == | ||
$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} | | [[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} | | [[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} | | [[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} | | [[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} | | [[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} | | [[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} | | [[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 08: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
Space Complexity Graph
Time-Space Tradeoff
