<p>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 <a href="http://en.wikipedia.org/wiki/Circulant_matrix" rel="noreferrer">http://en.wikipedia.org/wiki/Circulant_matrix</a> for more details.</p>

<p>Apologies if this is too trivial to be mentioned here. </p>

CC BY-SA 3.0
2011-10-24T09:54:44.667Z
2011-10-24T09:54:44.667Z
Jitse Niesen
<p>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].</p>

<p>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?</p>

<p>[1] <a href="http://www.cs.yale.edu/homes/spielman/Research/linsolve.html">http://www.cs.yale.edu/homes/spielman/Research/linsolve.html</a></p>

<cc.complexity-theory><linear-algebra><matrices>
Cases of nearly linear time solvable linear systems
Dimitris
# Cases of nearly linear time solvable linear systems

(Asked by: username_0 on 2011-10-21)

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>

**Tags:** cc.complexity-theory, linear-algebra, matrices


---

## 1 answers

### Answer by username_1 on 2011-10-24. Score: 7

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.


---

