Cases of nearly linear time solvable linear systems

Question

Let a square $n\times n$ real matrix ${\bf A}$ and two vectors ${\bf x}$ and ${\bf b}$ of length $n$, such that $${\bf A}{\bf x}={\bf b}.$$ Solving for ${\bf x}$ through standard Gaussian Elimination yields an aggregate complexity of almost $O(n^3)$. However, there are cases where solving (or $\epsilon$-approximately solving) for ${\bf x}$ costs $O(n\log^\rho n)$, such as systems where ${\bf A}$ is a symmetric and diagonally dominant matrix (e.g., a Laplacian) [1].

Which other families of linear systems (i.e., matrices) admit linear (or nontrivial poly(n)) time solutions? If we consider finite fields instead of real matrices, are there any families of matrices there that admit nearly linear time solutions?

[1] http://www.cs.yale.edu/homes/spielman/Research/linsolve.html

Answer 1

Linear systems with circulant matrices can be solved in $O(n \log n)$ using the fast Fourier transform. A circulant matrix has entries $a_{i,j} = a_{1,i+j-1 \bmod n}$ so it is completely specified by the first column. Circulant matrices are diagonalized by the fast Fourier transform (log-linear time) and linear systems with diagonal matrices can be solved in linear time. See for instance the Wikipedia article http://en.wikipedia.org/wiki/Circulant_matrix for more details.

Apologies if this is too trivial to be mentioned here.