Dalam karya terbaru, rekor kecepatan baru ditetapkan untuk mengalikan dua matriks . Ini juga menandai akhir era untuk metode yang telah digunakan para ilmuwan untuk penelitian selama beberapa dekade.
Matematikawan berusaha keras untuk mencapai tujuan mitos - derajat kedua (eksponen dua), yaitu mengalikan sepasang matriks n x n hanya dalam n 2 langkah. Peneliti semakin dekat dengan tujuan mereka, tetapi apakah mereka akan pernah bisa mencapainya?
Bagi ilmuwan komputer dan matematikawan, gagasan tentang "derajat kedua" dikaitkan dengan gagasan tentang dunia yang sempurna.
“Sulit untuk membedakan antara pemikiran ilmiah dan lamunan tanpa dasar,” Chris Umans dari California Institute of Technology mengakui . "Saya ingin gelar menjadi dua karena itu indah."
Dari sudut pandang jumlah langkah yang diperlukan, "derajat kedua" adalah kecepatan eksekusi yang idealsalah satu operasi matematika yang paling mendasar adalah perkalian matriks. Jika derajat kedua dapat dicapai, maka perkalian matriks dapat dilakukan secepat mungkin secara fisik. Jika tidak demikian, maka kita terjebak di dunia yang tidak sesuai dengan impian kita.
Matriks adalah susunan angka. Jika kedua matriks sepakat (jumlah kolom pada faktor pertama sama dengan jumlah baris pada faktor kedua), keduanya dapat dikalikan untuk mendapatkan yang ketiga. Misalnya, jika Anda memulai dengan pasangan matriks 2 x 2, hasil perkaliannya juga berupa matriks 2 x 2 yang berisi empat elemen. Secara umum, hasil kali pasangan matriks n x n adalah matriks n x n lain dengan n 2 elemen.
Oleh karena itu, jumlah langkah terkecil yang mungkin untuk mengalikan pasangan matriks adalah n 2 , yaitu jumlah langkah yang diperlukan untuk menuliskan jawabannya. Oleh karena itu nama "derajat kedua".
Dan sementara tidak ada yang tahu pasti apakah ini bisa tercapai, para peneliti terus bergerak ke arah ini.
Artikel yang diterbitkan pada bulan Oktober itu semakin mendekati tujuan dan menjelaskan metode tercepat untuk mengalikan dua matriks sejauh ini. Hasil tersebut diterima oleh Josh Alman , mahasiswa PhD di Harvard University, dan Virginia Wasilewska Williamsdari Massachusetts Institute of Technology, menurunkan derajat yang terbaik sebelumnya sekitar seperseratus ribu. Ini benar-benar pencapaian yang luar biasa di bidang ini, yang dicapai melalui kerja keras.
Untuk mendapatkan pemahaman yang lebih baik tentang proses ini dan bagaimana memperbaikinya, mari kita mulai dengan sepasang matriks 2 x 2, A dan B. Saat menghitung setiap elemen dari produknya, Anda menggunakan baris yang sesuai dari A dan kolom yang sesuai dari B.Untuk mendapatkan elemen kanan atas, kalikan angka pertama di baris pertama A dengan angka pertama di kolom kedua B, lalu kalikan angka kedua di baris pertama A dengan angka kedua di kolom kedua B dan tambahkan kedua produk tersebut.
Samuel Velasco / Majalah Quanta
Operasi ini dikenal sebagai mendapatkan "hasil kali titik" dari sebuah baris dengan kolom (terkadang disebut "hasil kali dalam"). Untuk menghitung elemen lain dalam produk matriks, ulangi prosedur dengan baris dan kolom yang sesuai.
Secara umum metode perkalian matriks klasik 2x2 terdiri dari delapan perkalian dan beberapa penjumlahan. Biasanya, metode perkalian dua matriks n x n ini membutuhkan n 3 perkalian.
Dengan bertambahnya ukuran matriks, jumlah perkalian yang dibutuhkan untuk menemukan hasil perkaliannya tumbuh jauh lebih cepat daripada jumlah penjumlahan. Untuk mencari perkalian matriks 2 x 2, hanya diperlukan delapan perkalian antara, dan untuk mencari hasil perkalian dari matriks 4 x 4 sudah ada 64 diantaranya.Namun, jumlah penjumlahan yang diperlukan untuk mendapatkan jumlah matriks tersebut adalah tidak jauh berbeda. Biasanya jumlah penjumlahan sama dengan jumlah elemen dalam matriks, yaitu empat untuk matriks 2 x 2 dan 16 untuk matriks 4 x 4. Perbedaan antara penjumlahan dan perkalian ini memperjelas mengapa peneliti mengukur kecepatan perkalian matriks hanya dalam hal jumlah perkalian yang dibutuhkan.
Perkalian adalah segalanya, kata Umans. Eksponen pada akhirnya bergantung sepenuhnya pada jumlah perkalian. Penambahan menghilang dalam arti tertentu. "
Selama berabad-abad, orang percaya bahwa n 3 adalah cara tercepat untuk mengalikan matriks . Pada tahun 1969, Volker Strassen dilaporkan berusaha untuk membuktikan bahwa tidak mungkin untuk mengalikan matriks 2 x 2 menggunakan kurang dari delapan perkalian. Rupanya, dia masih belum dapat menemukan bukti, dan setelah beberapa saat dia mengerti mengapa: sebenarnya, ada cara untuk melakukan ini dengan menggunakan tujuh perkalian!
Strassen datang dengan satu set relasi kompleks yang memungkinkannya mengganti salah satu dari delapan perkalian ini dengan 14 tambahan tambahan. Perbedaannya mungkin tampak seperti perbedaan yang halus, tetapi itu terbayar karena perkalian berkontribusi lebih dari sekadar penambahan. Menemukan cara untuk menghilangkan satu perkalian untuk matriks kecil 2 x 2, Strassen menemukan kemungkinan yang dapat ia gunakan saat mengalikan matriks yang lebih besar.
“Perubahan kecil ini menghasilkan peningkatan besar dalam menangani matriks besar,” kata Williams.
Virginia Wasilewska Williams dari Massachusetts Institute of Technology dan Josh Alman dari Harvard University menemukan cara tercepat untuk mengalikan dua matriks dalam langkah n 2,3728596 . Jared Charney; Richard T.K. Elang
Misalkan Anda ingin mengalikan pasangan matriks 8 x 8. Salah satu cara melakukannya adalah dengan membagi setiap matriks besar menjadi empat matriks 4 x 4 sehingga masing-masing memiliki empat elemen. Karena elemen-elemen matriks juga dapat berupa matriks, Anda dapat menganggap matriks asli sebagai pasangan matriks 2 x 2, yang masing-masing dari keempat elemennya merupakan matriks 4 x 4. Dengan beberapa manipulasi, masing-masing dari 4 matriks ini x 4 matriks dapat dibagi menjadi empat matriks berukuran 2 x 2.
Ide di balik pemisahan beberapa matriks besar menjadi lebih kecil adalah bahwa Anda dapat menerapkan algoritme Strassen ke matriks yang lebih kecil berulang kali dan menggunakan metodenya untuk mengurangi jumlah langkah di setiap langkah. Secara umum, algoritma Strassen meningkatkan kecepatan perkalian matriks dengan n 3 sampai n 2,81 langkah perkalian.
Langkah penting berikutnya dalam pengembangan gagasan terjadi pada akhir 1970-an, ketika pendekatan baru yang fundamental untuk memecahkan masalah ini muncul. Ini melibatkan penerjemahan perkalian matriks ke dalam soal aljabar linier komputasi lain menggunakan objek yang disebut tensor. Tensor yang digunakan dalam soal ini adalah deretan angka tiga dimensi yang terdiri dari banyak bagian berbeda, yang masing-masing terlihat seperti masalah perkalian matriks kecil.
Perkalian matriks dan masalah tensor ini dalam arti setara satu sama lain, tetapi para peneliti sudah memiliki prosedur yang lebih cepat untuk menyelesaikan yang terakhir. Jadi, mereka dihadapkan pada tugas untuk menentukan "nilai tukar" di antara mereka: Matriks ukuran apa yang dapat dikalikan dengan biaya komputasi yang sama yang diperlukan untuk menyelesaikan masalah tensor?
"Ini adalah konsep yang sangat umum dalam ilmu komputer teoretis: untuk mengubah tugas dan menarik analogi di antara tugas-tugas tersebut untuk menunjukkan bahwa mereka sama-sama sederhana atau kompleks," kata Alman.
Pada tahun 1981, Arnold Schönhage menggunakan pendekatan ini untuk membuktikan bahwa perkalian matriks dapat dilakukan dalam n 2.522 langkah. Strassen kemudian menyebut pendekatan ini sebagai "metode laser" .
Selama beberapa dekade terakhir, setiap peningkatan dalam perkalian matriks berasal dari peningkatan metode laser karena para peneliti telah menemukan cara yang lebih efisien untuk mengubah masalah. Dalam bukti baru mereka, Alman dan Williams mengaburkan perbedaan antara dua masalah dan menunjukkan bahwa mungkin saja untuk mengurangi jumlah perkalian. "Secara keseluruhan, Josh dan Virginia menemukan cara untuk menerapkan komputasi mesin dalam metode laser dan mendapatkan hasil terbaik hingga saat ini," kata Henry Cohn.dari Microsoft Research.
Dalam artikel mereka, batas teoritis tentang kecepatan perkalian matriks ditingkatkan menjadi n 2,3728596 .
Juga berkat penelitian ini, Williams dapat memperoleh kembali mahkota di bidang perkalian matriks, yang berhak diterimanya pada tahun 2012 (n 2,372873 ), dan kemudian kalah pada tahun 2014 oleh François Le Gall (n 2,3728639 ).
Tetapi, terlepas dari semua ras dan kemenangan ini, menjadi jelas bahwa dalam kasus pendekatan ini, hukum keuntungan yang semakin berkurang, atau keuntungan yang semakin berkurang, beroperasi. Kemungkinan besar, peningkatan Alman dan Williams hampir sepenuhnya menghabiskan kemungkinan metode laser, tetapi tidak memungkinkan pencapaian tujuan teoretis akhir.
“Tidak mungkin Anda bisa mendekati gelar kedua dengan menggunakan metode keluarga ini,” kata Umans.
Ini akan membutuhkan penemuan metode baru dan keyakinan kuat bahwa itu mungkin sama sekali.
Williams ingat salah satu percakapannya dengan Strassen tentang ini: "Saya bertanya kepadanya apakah menurutnya mungkin untuk mendapatkan gelar kedua untuk perkalian matriks, dan dia menjawab:" Tidak, tidak, tidak, tidak pernah! ".