Bilgisayar bilimcileri zorlu bir gruptur. Onlar için bir soruna doğru cevabı bulmak yeterli değildir; amaç neredeyse her zaman cevaba mümkün olduğu kadar verimli bir şekilde ulaşmaktır.

Matrisleri veya sayı dizilerini çarpma eylemini ele alalım. 1812'de Fransız matematikçi Jacques Philippe Marie Binet, hâlâ öğrencilere öğrettiğimiz temel kuralları ortaya attı. Mükemmel bir şekilde çalışıyor ancak diğer matematikçiler süreci basitleştirmenin ve hızlandırmanın yollarını buldular. Artık görevi süreci hızlandırmak Matris çarpımının keşfi matematik ve bilgisayar bilimlerinin kesişiminde yer alıyor ve burada araştırmacılar bugüne kadar süreci geliştirmeye devam ediyor; ancak son yıllarda elde edilen kazanımlar oldukça mütevazı. 1987'den bu yana matris çarpımındaki sayısal gelişmelerin "küçük ve elde edilmesi son derece zor" olduğu belirtildi. François Le GallNagoya Üniversitesi'nde bilgisayar bilimcisi.

Şimdi, üç araştırmacı - Tsinghua Üniversitesi'nden Ran Duan ve Renfei Zhou ve Kaliforniya Üniversitesi, Berkeley'den Hongxun Wu - bu daimi sorunla mücadelede ileriye doğru büyük bir adım attı. Onların yeni sonuçlarLe Gall, geçen Kasım ayında Bilgisayar Biliminin Temelleri konferansında sunulan yeni teknolojinin beklenmedik yeni bir teknikten kaynaklandığını söyledi. Gelişmenin kendisi nispeten küçük olsa da Le Gall bunu "kavramsal olarak öncekilerden daha büyük" olarak nitelendirdi.

Teknik, daha önce bilinmeyen ve dolayısıyla kullanılmayan potansiyel iyileştirme kaynağını ortaya çıkardı ve şimdiden meyvesini verdi: İkinci bir makaleOcak ayında yayınlanan, matris çarpımının nasıl daha da artırılabileceğini gösteren ilkine dayanıyor.

"Bu büyük bir teknik atılım" dedi William KuszmaulHarvard Üniversitesi'nde teorik bilgisayar bilimcisi. "Bu, on yılı aşkın süredir matris çarpımında gördüğümüz en büyük gelişme."

Enter the Matrix

Karanlık bir problem gibi görünebilir, ancak matris çarpımı temel bir hesaplama işlemidir. Daha net bilgisayar grafikleri görüntülemekten ağ teorisindeki lojistik sorunları çözmeye kadar, insanların her gün çeşitli görevler için kullandığı algoritmaların büyük bir kısmına dahil edilmiştir. Ve diğer hesaplama alanlarında olduğu gibi hız çok önemlidir. Küçük iyileştirmeler bile sonuçta önemli miktarda zaman, hesaplama gücü ve para tasarrufu sağlayabilir. Ancak şimdilik teorisyenler esas olarak sürecin ne kadar hızlı olabileceğini bulmaya çalışıyor.

İkiyi çarpmanın geleneksel yolu n-By-n matrisler — birinci matristeki her satırdaki sayıları ikinci matristeki sütunlardaki sayılarla çarparak — şunu gerektirir: n³ ayrı çarpımlar. 2'ye 2 matrisler için bu, 2 anlamına gelir³ veya 8 çarpma.

1969'da matematikçi Volker Strassen, 2'ye 2 matrisleri yalnızca yedi çarpım adımında ve 18 toplamayla çarpabilen daha karmaşık bir prosedürü ortaya çıkardı. İki yıl sonra bilgisayar bilimcisi Shmuel Winograd, 2'ye 2'lik matrisler için gerçekten de mutlak minimumun yedi olduğunu gösterdi.

Strassen aynı fikirden yararlanarak her şeyin daha büyük olduğunu gösterdi. n-By-n matrisler aynı zamanda daha az sayıda çarpılabilir n³ adımlar. Bu stratejideki önemli bir unsur, ayrıştırma adı verilen bir prosedürü içerir; büyük bir matrisin, 2'ye 2 veya hatta 1'e 1 kadar küçük olabilen ardışık olarak daha küçük alt matrislere bölünmesi (bunlar yalnızca tek sayılardır).

Dev bir diziyi küçük parçalara bölmenin mantığı oldukça basit. Virginia Vasilevska WilliamsMassachusetts Teknoloji Enstitüsü'nde bilgisayar bilimcisi ve yeni makalelerden birinin ortak yazarı. Vassilevska Williams, "Bir insanın büyük bir matrise (örneğin 100'e 100) bakıp mümkün olan en iyi algoritmayı düşünmesi zordur" dedi. 3'e 3'lük matrisler bile henüz tam olarak çözülmedi. "Bununla birlikte, daha büyük matrisler için de hızlı bir algoritma elde etmek amacıyla, küçük matrisler için halihazırda geliştirilmiş olan hızlı bir algoritma kullanılabilir."

Araştırmacılar, hızın anahtarının çarpma adımlarının sayısını azaltarak bu üssün değerini düşürmek olduğunu belirledi. n³ (standart yöntem için) ellerinden geldiğince. Mümkün olan en düşük değer, n², temelde sadece cevabı yazmak için gereken süre kadardır. Bilgisayar bilimcileri bu üsse omega, ω adını verir ve n^ω iki tanesini başarılı bir şekilde çarpmak için gereken mümkün olan en az adımdır n-By-n matrisler n çok büyür. Aynı zamanda Ocak 2024 tarihli makalenin yazarlarından biri olan Zhou, "Bu çalışmanın amacı, 2'ye ne kadar yaklaşabileceğinizi ve teoride bunun başarılabileceğini görmektir" dedi.

Lazer Odaklama

1986 yılında Strassen başka bir büyük atılım daha gerçekleştirdi. tanıttı matris çarpımı için lazer yöntemi denilen şey. Strassen bunu omega için 2.48'lik bir üst değer belirlemek için kullandı. Yöntem, büyük matris çarpımlarında yalnızca bir adım olsa da, en önemlilerinden biridir çünkü araştırmacılar onu geliştirmeye devam etmektedir.

Bir yıl sonra Winograd ve Don Coppersmith, lazer yöntemini güzel bir şekilde tamamlayan yeni bir algoritmayı tanıttılar. Bu araçların kombinasyonu, matris çarpımını hızlandırmaya yönelik neredeyse tüm sonraki çabalarda öne çıktı.

İşte bu farklı unsurların birbirine nasıl uyum sağladığına dair basitleştirilmiş bir düşünme yöntemi. Birlikte çarpmak istediğiniz iki büyük matris olan A ve B ile başlayalım. İlk olarak, bunları bazen adlandırıldığı gibi çok sayıda daha küçük alt matrislere veya bloklara ayrıştırırsınız. Daha sonra, Coppersmith ve Winograd'ın algoritmasını, blokların işlenmesi ve nihai olarak birleştirilmesi için bir tür kullanım kılavuzu görevi görmesi için kullanabilirsiniz. Vassilevska Williams, "Bana C çarpım matrisinde neyin çarpılacağını, neyin ekleneceğini ve hangi girişlerin nereye gideceğini söylüyor" dedi. “Bu sadece A ve B'den C oluşturmanın bir tarifi.”

Ancak bir sorun var: Bazen ortak girişleri olan bloklarla karşılaşıyorsunuz. Bunları üründe bırakmak, bu girişleri iki kez saymaya benzer, dolayısıyla bir noktada çakışma adı verilen bu yinelenen terimlerden kurtulmanız gerekir. Araştırmacılar bunu, içinde bulundukları blokları "öldürerek", bileşenlerini sıfıra eşitleyerek hesaplamadan çıkararak yapıyorlar.

İşte tam bu noktada Strassen'in lazer yöntemi devreye giriyor. Le Gall, "Lazer yöntemi genellikle çok iyi çalışıyor ve genellikle örtüşmeyi ortadan kaldırmak için bir blok alt kümesini öldürmenin iyi bir yolunu buluyor" dedi. Lazer tüm örtüşmeleri ortadan kaldırdıktan veya "yaktıktan" sonra, son ürün matrisi C'yi oluşturabilirsiniz.

Bu çeşitli tekniklerin bir araya getirilmesi, en azından teoride, iki matrisin kasıtlı olarak çok az sayıda çarpma işlemiyle çarpılmasına yönelik bir algoritmayla sonuçlanır. Lazer yönteminin pratik olması amaçlanmamıştır; bu sadece matrisleri çarpmanın ideal yolunu düşünmenin bir yolu. Zhou, "Yöntemi hiçbir zaman bilgisayarda çalıştırmıyoruz" dedi. "Bunu analiz ediyoruz."

Ve bu analiz, Omega'da on yılı aşkın süredir görülen en büyük gelişmeye yol açtı.

Bir Kayıp Bulundu

Geçen yaz Duan, Zhou ve Wu tarafından yazılan makale, Strassen'in sürecinin hala önemli ölçüde hızlandırılabileceğini gösterdi. Zhou, bunların hepsinin önceki analizlerin derinliklerine gömülmüş, gizli kayıp olarak adlandırdıkları bir kavram yüzünden olduğunu söyledi; "kasıtsız olarak çok fazla bloğun öldürülmesinin bir sonucuydu" dedi Zhou.

Lazer yöntemi, üst üste binen blokların imha edilmesi planlanan çöp olarak etiketlenmesiyle çalışır; diğer bloklar layık görülerek kurtarılacaktır. Ancak seçim süreci biraz rastgeledir. Çöp olarak değerlendirilen bir bloğun aslında faydalı olduğu ortaya çıkabilir. Bu tamamen bir sürpriz değildi, ancak Duan'ın ekibi bu rastgele seçimlerin çoğunu inceleyerek lazer yönteminin bloklara sistematik olarak düşük değer biçtiğini belirledi: Daha fazla blok kurtarılmalı ve daha az blok atılmalı. Ve genellikle olduğu gibi, daha az atık daha fazla verimlilik anlamına gelir.

Le Gall, "Daha fazla bloğu örtüşmeden tutabilmek, daha hızlı bir matris çarpım algoritmasına yol açıyor" dedi.

Bu kaybın varlığını kanıtladıktan sonra Duan'ın ekibi, lazer yönteminin blokları etiketleme şeklini değiştirerek israfı önemli ölçüde azalttı. Sonuç olarak, omega için 2.371866 civarında yeni bir üst sınır belirlediler; bu, önceki 2.3728596 üst sınırına göre bir gelişme. 2020'de geçti Josh Alman ve Vassilevska Williams tarafından. Bu, sınırı yaklaşık 0.001 oranında düşüren mütevazı bir değişiklik gibi görünebilir. Ancak bu, bilim adamlarının 2010'dan bu yana gördüğü en büyük gelişme. Vassilevska Williams ve Alman'ın 2020 sonucu, kıyaslandığında selefine göre yalnızca 0.00001 ilerleme kaydetti.

Ancak araştırmacılar için en heyecan verici olan şey, yalnızca uzun sürmeyen yeni rekorun kendisi değil. Aynı zamanda makalenin, o zamana kadar tamamen gözden kaçan yeni bir iyileştirme yolunu ortaya çıkardığı da bir gerçektir. Le Gall, neredeyse kırk yıldır herkesin aynı lazer yöntemine güvendiğini söyledi. “Sonra daha iyisini yapabileceğimizi anladılar.”

Ocak 2024 tarihli makale bu yeni yaklaşımı geliştirerek Vassilevska Williams, Zhou ve ortak yazarlarının gizli kayıpları daha da azaltmalarına olanak tanıdı. Bu, Omega'nın üst sınırında ek bir iyileşmeye yol açarak onu 2.371552'ye düşürdü. Yazarlar aynı tekniği dikdörtgenler için çarpma işlemini geliştirmek amacıyla da genelleştirdiler (n-By-m) matrisler — grafik teorisi, makine öğrenimi ve diğer alanlarda uygulamaları olan bir prosedür.

Bu doğrultuda daha fazla ilerleme kaydedilmesi kesindir ancak bunun da sınırları vardır. 2015 yılında Le Gall ve iki işbirlikçisi kanıtladı Mevcut yaklaşımın (Coppersmith-Winograd tarifiyle birleştirilmiş lazer yöntemi) 2.3078'in altında bir omega elde edemeyeceğini söyledi. Le Gall, daha fazla iyileştirme yapmak için şunları söyledi: "Bakırcılık ve Winograd'ın 1987'den bu yana pek değişmeyen orijinal yaklaşımını geliştirmeniz gerekiyor."". Ancak şu ana kadar kimse daha iyi bir yol bulamadı. Hatta hiç olmayabilir.

Zhou, "Omega'yı geliştirmek aslında bu sorunu anlamanın bir parçası" dedi. “Sorunu iyi anlayabilirsek, onun için daha iyi algoritmalar tasarlayabiliriz. [Ve] insanlar bu asırlık sorunu anlamanın hâlâ çok erken aşamalarındalar."