Penentu matriks Vandermonde umum

Matriks Moore mirip dengan matriks Vandermonde tetapi memiliki definisi yang sedikit dimodifikasi. http://en.wikipedia.org/wiki/Moore_matrix

Apa kompleksitas komputasi determinan dari yang diberikan $n \times n$ rank penuh Moore matriks modulo suatu bilangan bulat?

Can Moore penentu dikurangi dari $O(n^{3})$ menggunakan teknik FFT ke $O(n\log^{a}n)$ untuk beberapa $a \in \mathbb{R}_{+} \cup \{0\}$ ?

Apakah kompleksitas modul Moore det integer dan Vandermonde det sama? Kompleksitas penentu Vandermonde adalah $O(n\log^{2}n)$ (Halaman 644 dalam Buku Pegangan Ilmu Komputer Teoritis: Algoritma dan kompleksitas Oleh Jan Leeuwen)

Posting mirip dengan yang sekarang: Modul determinan m

cc.complexity-theory algebraic-complexity T ....
sumber

Dapatkah penentu Moore bahkan dapat dihitung dalam waktu O (n ^ 3) (pada integer RAM)?

Jeffε

@ Jɛ ff E Itu sebabnya saya sebutkan modulo acak

N \in N

$N \in \mathbb{N}$ .

T ....

Omong-omong, dan saya hanya ingin tahu, apakah ada aplikasi yang dikenal yang akan mendapat manfaat dari algoritma "super cepat" seperti itu?

Juan Bermejo Vega

FFE, apakah Anda kebetulan tahu jika komputasi eksponensial modular ganda lebih

di BPP untuk sepele

?. Karena itu masalah untuk menghitung koefisien matriks.

ε

$\varepsilon$

N

$N$

N

$N$

Juan Bermejo Vega

Jawaban:

Secara umum, ada algoritma teoretis waktu untuk menemukan dekomposisi LU dari matriks arbitrer menggunakan algoritma Coppersmith-Winograd , yang kemudian jelas menghasilkan determinan (menambahkan waktu waktu). Namun ada masalah bahwa algoritma Coppersmith-Winograd tidak dianggap dapat digunakan dalam praktik. Afaik, kebanyakan orang menggunakan algoritma Strassen waktu . Tidakkah Meningkatkan Bo_factorize UBLAS menggunakan ini? $O(n^{2.376})$ $O(n)$ $O(n^{2.807})$

Dalam kasus Anda, matriks Moore harus mengakui optimasi yang cukup karena pada dasarnya setiap prosedur seperti eliminasi Gaussian seperti dekomposisi LU dapat dilakukan secara abstrak. Memang, Anda akan menemukan formula untuk menghitung determinan Moore yang direferensikan oleh wikipedia , yang mungkin terbukti dengan hanya mengerjakan dekomposisi LU secara umum. $O(n)$

Jeff Burdges
sumber

Hai Jeff: Referensi mana yang Anda rujuk untuk rumus O (n ^ 2). Saya pikir Vandermonde det dapat dihitung dalam O (nlogn) tetapi saya tidak dapat menemukan referensi. Jadi haruskah Moore det juga berada di O (nlogn)?

T ....

Ya, saya seharusnya mengatakan O (n) jelas, benar-benar O (n log n) untuk n besar.

Jeff Burdges

Hai Jeff: Apakah Anda punya referensi?

T ....

@JeffBurdges: Jika waktu berjalan adalah O (n log n) "untuk n besar", maka menurut definisi, waktu berjalan adalah O (n log n), bukan O (n).

Jeffε

O (n)

$O(n)$

Θ (n^{2})

$\Theta(n^2)$

$\mathbb{Z}_m$ $m$ $a^{q^e}\mod m$ $O(\log (mn) \; M(\log m))$

a^{q^{i}} \equiv a^{q^{i} (\mod φ (m))} (\mod m)

$a^{q^i}\equiv a^{q^i\pmod{\varphi(m)}}\pmod m$

m

$m$

Jika adalah prima atau dapat difaktorkan secara efisien, kompleksitas kasus terburuk didominasi oleh jumlah langkah yang Anda butuhkan untuk perkalian matriks . Misalnya, pendekatan bentuk normal Smith yang saya sebutkan di posting mitra akan menghitung penentu dalam waktu jika Anda menggunakan "lambat" algoritma multiplikasi . dapat dipilih menjadi 2.373. $m$ $O(n^\omega)$ $O\left( n^\omega \; \log^2m\; \log (mn) \right)$ $^*$ $\omega$

Anda mendapatkan slow-down di Moore vs Vandermonde karena Anda harus melipatgandakan eksponen koefisien dari matriks. Ketika Anda dapat factorise ini lambat-down hanya polylogarithmic pada . Jika tidak, algoritme yang disajikan memberi Anda pengurangan Cook menjadi Double-Modular-Exponentiation pada . $m$ $m$ $\mathbb{Z}_m$

Catatan *: algoritma yang lebih cepat untuk perkalian integer memungkinkan Anda mengganti dengan . $\log^2 m$ $M(\log m \log\log m)$

Pembaruan : tentang kemungkinan mencapai . $O(n\log^a n)$

Saya tidak punya jawaban pasti untuk ini, tetapi saya menemukan beberapa informasi yang dapat memperketat pencarian Anda.

Algoritma untuk matriks terstruktur yang menghitung jumlah seperti penentu dalam waktu disebut "superfast" dalam literatur. Semua algoritma "superfast" yang dikenal untuk matriks terstruktur (Vandermonde, Toeplitz, Hankel) tampaknya mengandalkan properti umum dari matriks ini yang dikenal sebagai "peringkat perpindahan" rendah. Berikan diskusi pada bab pertama buku ini (halaman akses terbuka), atau dalam artikel ini [ACM] , [PDF] . $O(n\log^a n)$

Dari apa yang saya baca, diberikan Moore matriks , jika Anda dapat menemukan matriks , sedemikian rupa sehingga matriks baru (atau sebagai alternatif ) memiliki struktur sebagai berikut $m\times n$ $M$ $A$ $B$ $L(M)=AM-MB$ $L(M)=M- AMB$

L (M) = \sum_{k = 1}^{r} g_{k} h_{k}^{T}

$L(M) = \sum_{k=1}^r g_k h_k^T$

, dan peringkat kecil (baik konstan atau dibatasi oleh ), maka Anda dapat menerapkan teknik yang ada (periksa bab 5 buku ini, buka- mengakses halaman) untuk membuat segitiga dan, karenanya, menghitung , menggunakan . Di atas, , menunjukkan vektor. Jika Anda tidak dapat menemukan buku di atas untuk membaca semuanya, artikel ini juga memiliki banyak informasi tentang metode ini. $r>0$ $o(\text{min} \;\{m,n\})$ $M$ $\det{M}$ $O(n\log^2 n)$ $g_k$ $h_k$

Sayangnya, saya belum dapat menemukan struktur peringkat-perpindahan rendah untuk matriks Moore (Vandermonde miliki). Komplikasi utama di sini tampaknya muncul dari sifat "non-linear" dari eksponensial ganda. Jika itu membantu, kasus-kasus untuk Vandermonde, Cauchy, Toeplitz, Hankel dikerjakan dalam buku ini.

Juan Bermejo Vega
sumber

Saya dapat membuat matriks saya hidup di bidang char . Namun, ukuran huruf untuk aplikasi yang saya maksudkan akan besar. Jadi adalah dari bentuk untuk beberapa yang cukup besar .

3

$3$

m

$m$

3^{k}

$3^{k}$

k

$k$

T ....

Tidak apa-apa, karena Anda dapat menghitung fungsi total dari :)

3^{k}

$3^k$

Juan Bermejo Vega

baik itu tidak menyederhanakan kerumitan, saya akan mengatakan karena bidangnya sangat sangat besar.

T ....

Itu memang menyederhanakan masalah yang saya sebutkan dengan eksponensial ganda. Karena , Anda dapat menggunakan teorema Euler untuk menggandakan eksponensial : pertama, hitung , lalu . Anda dapat melakukan ini dalam waktu . Dengan menggunakan algoritma multiplikasi sekolah, , dan Anda akan mendapatkan biaya akhir "netto" mana yang efisien.

φ (3^{k}) = 3^{k} - 3^{k - 1}

$\varphi(3^k)=3^k-3^{k-1}$

a^{q^{i}} \mod m

$a^{q^i}\mod m$

b = q^{i} \mod φ (3^{k})

$b=q^i\mod \varphi(3^k)$

a^{b} \mod 3^{k}

$a^b\mod 3^k$

O (\log (n 3^{k}) M (k \log 3))

$O(\log(n3^k)M(k \log3))$

M (n) = n^{2}

$M(n)=n^2$

O (n^{ω} k^{2} l o g^{2} 3 (\log n + k \log 3))

$O(n^\omega k^2 log^2 3 (\log n + k\log 3))$

Juan Bermejo Vega

Bisakah kita mengganti dengan ? Itu adalah penghematan biaya saya penasaran (mungkin dari struktur matriks). Dengan , saya tidak mendapatkan apa pun untuk tujuan saya.

ω

$\omega$

1 + ϵ

$1 + \epsilon$

ω \geq 2

$\omega \ge 2$

T ....