2-Dimensional Poisson Problem: Difference between revisions

Revision as of 14:45, 15 February 2023

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

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

No parameters found.

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} logn)$	$O(n^{2})$?	Exact	Deterministic
5-point SOR iteration	1954	$O(n^{3} logn)$	$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} logn)$	$O(n^{2})$?	Exact	Deterministic
5-point FFT	1965	$O(n^{2} logn)$	$O(n^{2})$?	Exact	Deterministic
9-point ADI iteration + smooth guess	1969	$O(n^{2} logn)$	$O(n^{2})$?	Exact	Deterministic
5-point cyclic reduction	1970	$O(n^{2} logn)$	$O(n^{2})$?	Exact	Deterministic
9-point FFT	1978	$O(n^{2} logn)$	$O(n^{2})$?	Exact	Deterministic

@@ Line 56: / Line 56: @@
 [[File:Poisson Problem - 2-Dimensional Poisson Problem - Space.png|1000px]]
-== Space-Time Tradeoff Improvements ==
+== Time-Space Tradeoff ==
 [[File:Poisson Problem - 2-Dimensional Poisson Problem - Pareto Frontier.png|1000px]]