Menghitung jumlah polinomial yang jarang dikuadratkan dalam waktu O (n log n)?

18

Misalkan kita memiliki polinomial p1,...,pm derajat paling banyak , , sedemikian sehingga jumlah total koefisien bukan nol adalah (yaitu polinomialnya jarang). Saya tertarik pada algoritma yang efisien untuk menghitung polinomial:nn>mn

ipi(x)2

Karena polinomial ini memiliki derajat paling banyak , ukuran input dan output adalah . Dalam kasus kita dapat menghitung hasilnya menggunakan FFT dalam waktu . Bisakah ini dilakukan untuk ? Jika ada bedanya, saya tertarik pada kasus khusus di mana koefisien adalah 0 dan 1, dan perhitungan harus dilakukan melalui bilangan bulat.O ( n ) m = 1 O ( n log n ) m < n2nO(n)m=1O(nlogn)m<n

Memperbarui. Saya menyadari bahwa solusi cepat untuk hal di atas akan menyiratkan kemajuan dalam perkalian matriks cepat. Secara khusus, jika maka kita dapat membacakan sebagai koefisien dalam . Jadi, menghitung berhubungan dengan menghitung produk luar dari dua vektor, dan menghitung jumlah berhubungan dengan menghitung produk matriks. Jika ada solusi menggunakan waktu untuk komputasi maka kita bisa kalikan dua -by- matriks dalam waktu a i k b k j x i + n j p k ( x ) 2 p k ( x ) 2 Σ k p k ( x ) 2 f (pk(x)=i=1naikxi+j=1nbkjxnjaikbkjxi+njpk(x)2pk(x)2kpk(x)2k p k ( x ) 2 n n f ( n 2 , n )f(n,m)kpk(x)2nnf(n2,n), yang berarti bahwa untuk akan membutuhkan terobosan besar. Tetapi , di mana adalah eksponen saat ini dari perkalian matriks, dimungkinkan. Gagasan, siapa saja?m n f ( n , m ) = n ω / 2 ωf(n,m)=O(nlogn)mnf(n,m)=nω/2ω

Rasmus Pagh
sumber
1
Hai Rasmus. Saya pikir Anda bermaksud untuk ini pergi di situs utama. Ini adalah situs meta, untuk pertanyaan tentang situs tersebut.
Suresh Venkat

Jawaban:

3

Mengkuadratkan polinomial dengan koefisien bukan nol membutuhkan waktu menggunakan perkalian term-by-term biasa, jadi ini harus lebih disukai daripada FFT untuk polinomial-polinomial mana . Jika , maka jumlah polinomial dengan lebih besar dari adalah , dan ini akan membutuhkan waktu untuk menyiku dan menggabungkan (seperti halnya polinomial yang tersisa). Ini merupakan peningkatan dari terikat ketika adalah . O ( x 2 i ) x i < xiO(xi2)xi<nlognixi=nxinlognO(n/logn)O(n3/2(logn)1/2)O(mnlogn)mΘ(n/logn)

mjqxxxx
sumber
1
Apa yang saya tertarik adalah metode yang menghitung jumlah tanpa menghitung setiap istilah. Melakukan FFT atau penggandaan istilah demi istilah untuk setiap produk akan terlalu lambat untuk aplikasi yang ada dalam pikiran saya.
Rasmus Pagh
2

Bukan jawaban lengkap tapi mungkin bermanfaat.

Peringatan: Ini hanya berfungsi dengan baik jika dukungan dari kecil.pi2

Untuk polinomial , misalkan S q = { i a i0 } menjadi pendukungnya dan s q = | S q | menjadi ukuran dukungan. Sebagian besar p i akan jarang, yaitu akan memiliki dukungan kecil.q=a0+a1x++anxnSq={iai0}sq=|Sq|pi

Ada algoritma untuk kalikan jarang polinomial dan b dalam waktu kuasi-linear dalam ukuran dukungan dari produk sebuah b , lihat misalnya http://arxiv.org/abs/0901.4323abab

Dukungan dari adalah (yang terkandung dalam) S a + S b , di mana jumlah dari dua set S dan T didefinisikan sebagai S + T : = { s + t | s S , t T } . Jika dukungan dari semua produk kecil, katakanlah, linear di n total, maka salah satu dapat hanya menghitung produk dan menambahkan semua monomials.abSa+SbSTS+T:={s+tsS,tT}n

Namun sangat mudah untuk menemukan polinomial dan b sehingga ukuran dukungan dari sebuah b adalah kuadrat dalam ukuran dukungan dari sebuah dan b . Dalam aplikasi khusus ini, kami mengkuadratkan polinomial. Jadi pertanyaannya adalah berapa banyak lebih besar S + S dibandingkan dengan S . Ukuran yang biasa untuk ini adalah angka pengganda | S + S | / | S | . Ada set dengan nomor pengganda tanpa batas. Tetapi jika Anda dapat mengecualikan set dengan angka penggandaan besar sebagai dukungan dari p iabababS+SS|S+S|/|S|pi, maka Anda bisa mendapatkan algoritma cepat untuk masalah Anda.

5501
sumber
1
Meskipun saya tidak akrab dengan kombinatorik aditif, saya pikir bahwa perkembangan aritmatika umum dan teorema Freiman-Ruzsa adalah tentang set dengan penggandaan kecil .
Tsuyoshi Ito
@ Tsuyoshi: Anda benar, saya akan mengedit jawaban saya. Namun demikian, ada GAP dengan konstanta pengganda yang besar.
5501
Secara pribadi saya tidak berpikir bahwa pendekatan ini menjanjikan. Implikasi (cukup tidak akurat) dari teorema Freiman-Ruzsa adalah bahwa | S + S | / | S | kecil hanya dalam kasus khusus, dan oleh karena itu bagian "Jika Anda dapat mengecualikan set dengan angka penggandaan yang lebih besar sebagai dukungan p_i" adalah if yang sangat besar . Namun, seperti yang saya katakan, saya tidak terbiasa dengan kombinatorik aditif, dan Anda harus mengambil kata-kata saya di atasnya dengan sebutir garam.
Tsuyoshi Ito
Tentu saja itu hanya berfungsi jika aplikasi dalam pikiran (yang saya tidak tahu) memberikan dukungan yang bagus.
5501
Maka akan lebih mudah untuk dipahami jika Anda membuat asumsi itu lebih eksplisit dalam jawaban Anda. Cara saat menulis asumsi dalam jawaban menunjukkan bahwa Anda menganggap bahwa asumsi angka penggandaan kecil bukanlah masalah besar.
Tsuyoshi Ito
2

Hanya ingin mencatat algoritma perkiraan alami. Ini tidak mengambil keuntungan dari sparsity.

Anda dapat menggunakan urutan acak (σi)i[n] Mengambil X=iσipi(x) kita dapat menghitung X2 dalam nlogn waktu menggunakan FFT. Kemudian EX2=ipi(x)2=S dan VX2=O(S). Jadi Anda bisa mendapatkanperkiraan1+εdalam waktuO(ε2nlogn).

Thomas Ahle
sumber
Pendekatan yang bagus! Tetapi tidakkah Anda membutuhkan lebih banyak repetisi untuk mendapatkan semua koefisien yang benar dengan probabilitas tinggi?
Rasmus Pagh
@RasmusPagh Benar, Anda mungkin akan mendapatkan istilah jika Anda ingin semua koefisien dipertahankan dengan probabilitas 1 - δ . log(n/δ)1δ
Thomas Ahle