2-Dimensional Poisson Problem (Poisson Problem)

Description

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

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

$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