Kasus-kasus sistem linear yang hampir terpecahkan waktu linear

Biarkan a persegi matriks nyata dan dua vektor dan dengan panjang , sedemikian rupa sehingga {\ bf A} {\ bf x} = {\ bf b} . Memecahkan untuk {\ bf x} melalui standar Gaussian Elimination menghasilkan kompleksitas agregat hampir O (n ^ 3) . Namun, ada beberapa kasus di mana penyelesaian (atau \ epsilon -sebaliknya penyelesaian) untuk {\ bf x} menelan biaya O (n \ log ^ \ rho n) , seperti sistem di mana {\ bf A} merupakan matriks yang dominan secara simetris dan diagonal (diagonal). misalnya, seorang Laplacian) [1].$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}$

Yang keluarga lain dari sistem linear (yaitu, matriks) mengakui solusi waktu linear (atau nontrivial poli (n))? Jika kita mempertimbangkan bidang hingga bukan matriks nyata, adakah keluarga matriks di sana yang menerima solusi waktu yang hampir linier?

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

Sistem linier dengan matriks sirkuler dapat diselesaikan dalam menggunakan transformasi Fourier cepat. Matriks sirkulant memiliki entri sehingga sepenuhnya ditentukan oleh kolom pertama. Matriks Circulant didiagonalisasi oleh transformasi Fourier cepat (waktu log-linear) dan sistem linear dengan matriks diagonal dapat diselesaikan dalam waktu linier. Lihat misalnya artikel Wikipedia http://en.wikipedia.org/wiki/Circulant_matrix untuk rincian lebih lanjut.$O(n \log n)$$a_{i,j} = a_{1,i+j-1 \bmod n}$

Mohon maaf jika ini terlalu sepele untuk disebutkan di sini.