Gagasan umum dalam penggandaan Karatsuba, Gauss dan Strassen

19

Identitas yang digunakan dalam algoritma perkalian oleh

tampaknya sangat terkait erat. Apakah ada kerangka abstrak umum / generalisasi?

algorithms matrices sdcvvc
sumber
3
Lihat ketidaksamaan jumlah asimtotik Schönhage.
Yuval Filmus
Identitas mana yang Anda bicarakan? Apakah kita seharusnya membaca ketiga artikel untuk menjawab? Harap tambahkan informasi yang relevan ke pertanyaan Anda.
Raphael
1
@Raphael: Identitas yang merupakan fondasi untuk algoritme, yang menyatakan 4 penggandaan angka dengan 3 perkalian, dan 8 penggandaan matriks dengan 7.
sdcvvc

Jawaban:

5

Kerangka kerja klasik adalah salah satu dari algoritma bilinear dan dekomposisi peringkat tensor; pada dasarnya, Anda membangun tensor 3 arah yang terkait dengan peta bilinear , berdasarkan koefisien, kemudian mencari dekomposisi sebagai jumlah peringkat-satu tensor (yaitu , orang-orang dari bentuk ). Anda akan menemukan ini dijelaskan lebih detail, misalnya, dalam artikel ini oleh Bläser , atau dalam buku karya Bürgisser, Clausen, Shokrollahi, Teori Kompleksitas Aljabar .f(A,B)=A⋅BTi,j,k=uivjwk

Sejauh yang saya mengerti, perumusan kembali dalam bentuk representasi kelompok yang Suresh sebutkan dalam jawabannya adalah yang kemudian, dan saya merasa kurang cocok untuk pendekatan pertama pada subjek (tetapi, tentu saja, itu mungkin bias di pihak saya ).

Federico Poloni
sumber
1
Ini jawaban yang benar. Salah satu aspek yang hilang adalah tensorisasi / divide-and-conquer yang berada di belakang algoritma Karatsuba dan algoritma multiplikasi matriks cepat (kuadrat).
Yuval Filmus
8

Jawaban parsial untuk pertanyaan Anda adalah pendekatan teori kelompok yang pertama kali dikembangkan oleh Cohn dan Umans dan selanjutnya dikembangkan oleh Cohn, Kleinberg, Szegedy dan Umans. Ia dapat "mengurutkan" menangkap Strassen dan Coppersmith-Winograd untuk perkalian matriks.

Suresh
sumber
Ini benar-benar merindukan intinya. Pendekatan teori kelompok sebenarnya hanyalah salah satu cara untuk membuat identitas seperti itu sejak awal.
Yuval Filmus