26
edits
Because <math> \begin{bmatrix} A \end{bmatrix} </math> is block tridiagonal and sparse, many methods of solution
have been developed to optimally solve this linear system for <math> \begin{bmatrix} U \end{bmatrix} </math>.
Among the methods are a generalized [[Thomas algorithm]] with a resulting computational complexity of <math> O(n^{2.5}) </math>, [[cyclic reduction]], [[successive overrelaxation]] that has a complexity of <math> O(n^{1.5}) </math>, and [[Fourier transform]]s which is <math> O(n log(n)) </math>. An optimal <math> O(n) </math> solution can also be computed using [[multigrid methods]]. <ref>CS267: Notes for Lectures 15 and 16, Mar 5 and 7, 1996, https://people.eecs.berkeley.edu/~demmel/cs267/lecture24/lecture24.html</ref>
[[File:Convergence of Iterative Numerical Methods for Poisson System with 16384 elements.svgthumbcenter500pxPoisson convergence of various iterative methods with infinity norms of residuals against iteration count and computer time.]]

edits