REKOR BARU UNTUK MENGALIKAN KISI-KISI BILANGAN

Mengalikan dua matriks — kisi-kisi bilangan — adalah salah satu operasi paling dasar dalam komputasi. Jika dilakukan dengan cara sekolah, biaya mengalikan dua kisi n kali n tumbuh seperti n³. Algoritma Volker Strassen tahun 1969 adalah yang pertama melakukannya lebih baik — “subkubik”, dalam istilah makalah ini — dan sejak itu para matematikawan mengukur kemajuan dengan satu bilangan: eksponen ω (omega), pangkat terkecil dari n yang mencukupi saat kisi-kisi itu membesar.

Strassen menurunkannya ke bawah 2,81. Puluhan tahun kerja, yang didaftar dalam makalah ini, telah mendorongnya hingga sekitar 2,37, dengan langkah yang makin kecil. Pada 2026, Emilien Dupont dan rekan-rekan mencapai 2,371177. Reza Zadeh, dari perusahaan Matroid, Inc., kini membuktikan ω < 2,37115924.

Tabel berisi tahun, penulis, dan batas atas eksponen perkalian matriks, dari 2,807 pada 1969 hingga 2,37115924 pada 2026.

Sejumlah perbaikan batas atas ω, dari Strassen pada 1969 hingga makalah ini. — Tabel 1, Zadeh (2026), arXiv:2610.10593, CC BY 4.0.

Resep dengan 212.820 pengaturan

Rekor-rekor ini tidak berasal dari trik yang lebih cerdik untuk kisi kecil. Rekor itu berasal dari sebuah objek aljabar yang disebut tensor Coppersmith–Winograd, yang dapat dipotong dan digabungkan kembali, secara rekursif, menjadi banyak perkalian matriks yang saling independen. Cara memotongnya diatur oleh kumpulan pilihan yang sangat besar: distribusi probabilitas, penalti entropi, dan ukuran matriks yang ditetapkan tingkat demi tingkat. Setiap kumpulan pilihan yang sah menghasilkan batas yang sah; seninya adalah menemukan kumpulan yang baik.

Berdasarkan kerangka kerja Josh Alman dan rekan-rekan serta formulasi Dupont dan rekan-rekan, Zadeh menyetel 212.820 bilangan sekaligus, dengan tiga penyempurnaan:

Penskalaan ulang menurut kepentingan. Beberapa bagian konstruksi hanya jarang muncul, sehingga pengaruhnya pada hasil sangat kecil dan pengoptimal nyaris tidak menggesernya. Setiap bilangan diskalakan ulang sesuai bobot yang dipikul bagiannya.
Enam kenop untuk titik hambatan. Eksponen akhir ditentukan oleh yang terlemah dari tiga besaran yang saling bersaing pada tiga tahap. Sebuah koreksi terpisah hanya menggunakan enam pengendali untuk menjaga ketiganya seimbang.
Ekspor eksak. Resep akhir diubah menjadi pecahan eksak dengan penyebut 2⁹⁶.

Bukti melalui pemeriksaan

Batas ini adalah bukti berbantuan komputer. Sebuah program pendek, yang hanya memakai pustaka standar Python — tanpa jaringan, tanpa model, tanpa paket tambahan — membangun ulang setiap distribusi dari pecahan-pecahan eksak dan mengevaluasi hasilnya dengan pembulatan yang terjamin. Program itu mendapati bahwa besaran kunci bernilai positif, sekitar 8,5 per miliar, yang membuktikan batas tersebut. Penulis menegaskan apa yang tidak dicakupnya: program itu adalah kode yang dapat diaudit, bukan formalisasi seluruh teori dalam asisten pembuktian, dan pencariannya bersifat lokal, tanpa klaim bahwa resep itu yang terbaik.

Penulis juga menyebutkan bahwa perangkat AI generatif, yang tidak disebutkan namanya, membantu eksplorasi numerik, perangkat lunak, dan naskah, serta bahwa kode awal memanfaatkan catatan komputasi yang dibagikan secara publik oleh Eric Naslund. Sebuah sertifikat komputer publik yang terpisah, dirilis pada 5 Oktober 2026, telah mencapai 2,371169353; nilai baru ini lebih rendah lagi.

Lebih cepat, secara teori

Peningkatan dibandingkan Dupont dan rekan-rekan adalah 0,00001776 pada eksponen. Seperti semua batas yang diperoleh dengan cara ini, jaminannya bersifat asimtotik: eksponen saja tidak memberi tahu mulai ukuran matriks berapa algoritma baru ini benar-benar mengungguli yang sudah ada. Yang diubahnya adalah jawaban terbaik yang diketahui atas pertanyaan yang sudah bergulir sejak 1969 — secepat apa, pada prinsipnya, kisi-kisi bilangan dapat dikalikan?