Przypadki prawie liniowych układów liniowych rozwiązanych w czasie

Niech kwadratowa rzeczywista macierz A i dwa wektory x i b o długości n , takie, że A x = b . Rozwiązanie x poprzez standardową eliminację Gaussa daje łączną złożoność prawie O ( n 3 ) . Są jednak przypadki, w których rozwiązywanie (lub ϵ - rozwiązywanie w przybliżeniu) dla x kosztuje O ( n log ρ n ) , takie jak systemy, w których $n\times n$${\bf A}$${\bf x}$${\bf b}$$n$

$${\bf A}{\bf x}={\bf b}.$$ ${\bf x}$$O(n^3)$$\epsilon$${\bf x}$$O(n\log^\rho n)$${\bf A}$ jest macierzą symetryczną i dominującą po przekątnej (np. Laplaciana) [1].

Które inne rodziny układów liniowych (tj. Macierzy) dopuszczają liniowe (lub nietrywialne rozwiązania poli (n))? Jeśli weźmiemy pod uwagę pola skończone zamiast prawdziwych macierzy, czy istnieją tam rodziny macierzy, które dopuszczają rozwiązania prawie liniowe w czasie?

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

$O(n \log n)$$a_{i,j} = a_{1,i+j-1 \bmod n}$

Przepraszamy, jeśli jest to zbyt trywialne, aby o tym tutaj wspomnieć.