An $O(n^2 )$ Method for Solving Constant Coefficient Boundary Value Problems in Two Dimensions
Randolph E. Bank, Donald J. Rose · SIAM Journal on Numerical Analysis · 1975
Let M be an $n^2 \times n^2 $ block tridiagonal matrix of form $M = [ - I\quad T\quad - I]$, where T is an $n \times n$ tridiagonal matrix and I is the $n \times n$ identity. In the context of numerical computational complexity, we show that the system $Mx = k$ can be solved in $O(n^2 )$ arithmetic operations with $O(n^2 )$ storage. Numerical stability is a problem and is briefly discussed.