Misalkan kita memiliki polinomial derajat paling banyak , , sedemikian sehingga jumlah total koefisien bukan nol adalah (yaitu polinomialnya jarang). Saya tertarik pada algoritma yang efisien untuk menghitung polinomial:
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 < 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 (∑ k p k ( x ) 2 n n f ( n 2 , 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 ω
sumber
Jawaban:
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 < √xi O(x2i) xi<nlogn−−−−−√ ∑ixi=n xi nlogn−−−−−√ O(n/logn−−−−−−√) O(n3/2(logn)1/2) O(mnlogn) m Θ(n/logn−−−−−−√)
sumber
Bukan jawaban lengkap tapi mungkin bermanfaat.
Peringatan: Ini hanya berfungsi dengan baik jika dukungan dari kecil.p2i
Untuk polinomial , misalkan S q = { i ∣ a i ≠ 0 } menjadi pendukungnya dan s q = | S q | menjadi ukuran dukungan. Sebagian besar p i akan jarang, yaitu akan memiliki dukungan kecil.q=a0+a1x+⋯+anxn Sq={i∣ai≠0} 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.4323a b ab
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.ab Sa+Sb S T S+T:={s+t∣s∈S,t∈T} 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 ia b ab a b S+S S |S+S|/|S| pi , maka Anda bisa mendapatkan algoritma cepat untuk masalah Anda.
sumber
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) .
sumber