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


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.