Nowy przełom zbliża mnożenie macierzy do ideału | Magazyn Quanta

Informatycy to wymagająca grupa. Dla nich nie wystarczy znaleźć właściwą odpowiedź na problem — celem prawie zawsze jest uzyskanie odpowiedzi tak skutecznie, jak to możliwe.

Wykonaj czynność mnożenia macierzy lub tablic liczb. W 1812 roku francuski matematyk Jacques Philippe Marie Binet opracował podstawowy zbiór zasad, których nadal uczymy uczniów. Działa to doskonale, ale inni matematycy znaleźli sposoby na uproszczenie i przyspieszenie tego procesu. Teraz zadanie przyspieszenie procesu mnożenia macierzy leży na styku matematyki i informatyki, gdzie badacze do dziś udoskonalają ten proces, choć w ostatnich dziesięcioleciach postęp był dość skromny. Od 1987 r. postępy numeryczne w mnożeniu macierzy są „małe i… niezwykle trudne do uzyskania” – stwierdził François Le Galla, informatyk na Uniwersytecie w Nagoya.

Teraz trzech badaczy — Ran Duan i Renfei Zhou z Uniwersytetu Tsinghua oraz Hongxun Wu z Uniwersytetu Kalifornijskiego w Berkeley — zrobiło duży krok naprzód w walce z tym odwiecznym problemem. Ich nowe wyniki, zaprezentowane w listopadzie ubiegłego roku na konferencji Podstawy informatyki, wynikają z nieoczekiwanej nowej techniki, powiedział Le Gall. Chociaż samo ulepszenie było stosunkowo niewielkie, Le Gall nazwał je „koncepcyjnie większymi niż inne poprzednie”.

Technika ta odkrywa nieznane wcześniej i tym samym niewykorzystane źródło potencjalnych ulepszeń i już przyniosła owoce: Drugi papier, opublikowany w styczniu, opiera się na pierwszym, aby pokazać, w jaki sposób można jeszcze bardziej przyspieszyć mnożenie macierzy.

„To poważny przełom techniczny” – stwierdził Williama Kuszmaula, informatyk teoretyczny na Uniwersytecie Harvarda. „To największa poprawa mnożenia macierzy, jaką widzieliśmy od ponad dekady”.

Wprowadź Matrix

Może się to wydawać niejasnym problemem, ale mnożenie macierzy jest podstawową operacją obliczeniową. Jest częścią dużej części algorytmów, których ludzie używają na co dzień do różnych zadań, od wyświetlania ostrzejszej grafiki komputerowej po rozwiązywanie problemów logistycznych w teorii sieci. Podobnie jak w innych obszarach obliczeń, szybkość jest najważniejsza. Nawet niewielkie ulepszenia mogą ostatecznie doprowadzić do znacznych oszczędności czasu, mocy obliczeniowej i pieniędzy. Na razie jednak teoretyków interesuje głównie ustalenie, jak szybki może być ten proces.

Tradycyjny sposób mnożenia przez dwa n-przez-n macierze — poprzez pomnożenie liczb z każdego wiersza pierwszej macierzy przez liczby z kolumn drugiej — wymaga n³ oddzielne mnożenia. W przypadku macierzy 2 na 2 oznacza to 2³ lub 8 mnożeń.

W 1969 roku matematyk Volker Strassen odkrył bardziej skomplikowaną procedurę, która umożliwia pomnożenie macierzy 2 na 2 w zaledwie siedmiu krokach multiplikatywnych i 18 dodawaniach. Dwa lata później informatyk Shmuel Winograd wykazał, że siedem to rzeczywiście absolutne minimum dla macierzy 2 na 2.

Strassen wykorzystał ten sam pomysł, aby pokazać, że wszystko jest większe n-przez-n macierze można również pomnożyć przez mniej niż n³ kroki. Kluczowym elementem tej strategii jest procedura zwana dekompozycją — rozbicie dużej macierzy na kolejne mniejsze podmacierze, które mogą ostatecznie mieć rozmiary zaledwie 2 na 2 lub nawet 1 na 1 (są to tylko pojedyncze liczby).

Według. uzasadnienie dzielenia gigantycznej tablicy na małe części jest dość proste Virginia Wasilewska Williams, informatyk w Massachusetts Institute of Technology i współautor jednego z nowych artykułów. „Człowiekowi trudno jest spojrzeć na dużą matrycę (powiedzmy, rzędu 100 na 100) i wymyślić najlepszy możliwy algorytm” – stwierdziła Vassilevska Williams. Nawet macierze 3 na 3 nie zostały jeszcze w pełni rozwiązane. „Niemniej jednak można zastosować szybki algorytm, który już opracowano dla małych macierzy, aby uzyskać szybki algorytm również dla większych macierzy”.

Naukowcy ustalili, że kluczem do szybkości jest zmniejszenie liczby kroków mnożenia i obniżenie wykładnika n³ (w przypadku metody standardowej) tak dużo, jak tylko mogą. Najniższa możliwa wartość, n², trwa w zasadzie tyle, ile potrzeba na napisanie odpowiedzi. Informatycy nazywają ten wykładnik omega, ω, with n^ω oznacza najmniejszą możliwą liczbę kroków potrzebnych do pomyślnego pomnożenia dwa n-przez-n matryce jako n rośnie bardzo duży. „Celem tej pracy” – powiedział Zhou, który jest także współautorem artykułu ze stycznia 2024 r. – „jest sprawdzenie, jak blisko wartości 2 można się zbliżyć i czy da się to osiągnąć w teorii”.

Laserowe skupienie

W 1986 roku Strassen dokonał kolejnego wielkiego przełomu, kiedy wprowadzono tak zwana laserowa metoda mnożenia macierzy. Strassen na tej podstawie ustalił górną wartość dla omega wynoszącą 2.48. Chociaż metoda ta stanowi tylko jeden etap mnożenia dużych macierzy, jest jednym z najważniejszych, ponieważ badacze stale ją udoskonalają.

Rok później Winograd i Don Coppersmith wprowadzili nowy algorytm, który pięknie uzupełnił metodę laserową. Ta kombinacja narzędzi pojawiała się praktycznie we wszystkich późniejszych próbach przyspieszenia mnożenia macierzy.

Oto uproszczony sposób myślenia o tym, jak te różne elementy pasują do siebie. Zacznijmy od dwóch dużych macierzy, A i B, które chcesz przez siebie pomnożyć. Najpierw rozkładasz je na wiele mniejszych podmacierzy lub bloków, jak się je czasem nazywa. Następnie możesz użyć algorytmu Coppersmitha i Winograda, aby posłużył jako swego rodzaju instrukcja obsługi, a ostatecznie montażu bloków. „Mówi mi, co mam pomnożyć, co dodać i jakie wpisy gdzie umieścić” w macierzy iloczynu C, powiedziała Vassilevska Williams. „To tylko przepis na zbudowanie C z A i B”.

Jest jednak pewien haczyk: czasami powstają bloki, które mają wspólne wpisy. Pozostawienie ich w produkcie byłoby równoznaczne z dwukrotnym policzeniem tych wpisów, dlatego w pewnym momencie trzeba pozbyć się zduplikowanych terminów, zwanych nakładającymi się. Badacze robią to poprzez „zabijanie” bloków, w których się znajdują – ustawiając ich składniki na zero, aby usunąć je z obliczeń.

I tu w końcu pojawia się metoda laserowa Strassena. „Metoda laserowa zazwyczaj działa bardzo dobrze i ogólnie stanowi dobry sposób na zniszczenie podzbioru bloków w celu usunięcia nakładania się” – powiedział Le Gall. Po wyeliminowaniu przez laser lub „wypaleniu” wszystkich zakładek można skonstruować matrycę produktu końcowego, C.

Połączenie tych różnych technik daje w rezultacie algorytm mnożenia dwóch macierzy z celowo skąpą liczbą mnożeń ogółem — przynajmniej w teorii. Metoda laserowa nie jest z założenia praktyczna; to tylko sposób na przemyślenie idealnego sposobu mnożenia macierzy. „Nigdy nie uruchamiamy tej metody [na komputerze]” – powiedział Zhou. „Analizujemy to”.

I ta analiza doprowadziła do największego ulepszenia omegi od ponad dekady.

Znaleziono stratę

Artykuł z zeszłego lata, napisany przez Duana, Zhou i Wu, pokazał, że proces Strassena można jeszcze znacznie przyspieszyć. Wszystko wynikało z koncepcji, którą nazwali ukrytą stratą, głęboko zakopanej w poprzednich analizach – „wyniku niezamierzonego zabicia zbyt wielu bloków” – powiedział Zhou.

Metoda laserowa polega na oznaczaniu bloków z zakładkami jako śmieci przeznaczonych do utylizacji; inne bloki zostaną uznane za godne i zostaną zapisane. Proces selekcji jest jednak w pewnym stopniu losowy. Blok oceniony jako śmieciowy może jednak okazać się przydatny. Nie było to całkowitą niespodzianką, ale badając wiele z tych przypadkowych wyborów, zespół Duana ustalił, że metoda laserowa systematycznie zaniża wartość bloków: należy oszczędzać więcej bloków, a mniej wyrzucać. I jak to zwykle bywa, mniej odpadów przekłada się na większą wydajność.

„Możliwość zachowania większej liczby bloków bez nakładania się prowadzi zatem do… szybszego algorytmu mnożenia macierzy” – powiedział Le Gall.

Po udowodnieniu istnienia tej straty zespół Duana zmodyfikował sposób znakowania bloków metodą laserową, znacznie zmniejszając ilość odpadów. W rezultacie ustalili nową górną granicę dla omegi na poziomie około 2.371866, co oznacza poprawę w stosunku do poprzedniej górnej granicy wynoszącej 2.3728596, z 2020 roku autorstwa Josha Almana i Vassilevskiej Williams. Może się to wydawać niewielką zmianą, obniżającą granicę o zaledwie około 0.001. Jest to jednak największa poprawa, jaką naukowcy zaobserwowali od 2010 r. Dla porównania wynik Vassilevskiej Williams i Almana z 2020 r. był lepszy w porównaniu z poprzednikiem jedynie o 0.00001.

Ale to, co najbardziej ekscytuje badaczy, to nie tylko sam nowy rekord, który nie trwał długo. Jest to także fakt, że artykuł ujawnił nową drogę ulepszeń, która do tej pory pozostawała całkowicie niezauważona. Le Gall powiedział, że od prawie czterech dekad wszyscy polegają na tej samej metodzie laserowej. „Potem odkryli, że cóż, możemy działać lepiej”.

W artykule ze stycznia 2024 r. udoskonalono to nowe podejście, umożliwiając Vassilevskiej Williams, Zhou i ich współautorom dalsze ograniczenie ukrytych strat. Doprowadziło to do dodatkowej poprawy górnej granicy omegi, obniżając ją do 2.371552. Autorzy uogólnili również tę samą technikę, aby ulepszyć proces mnożenia prostokątów (n-przez-m) macierze — procedura mająca zastosowanie w teorii grafów, uczeniu maszynowym i innych dziedzinach.

Dalszy postęp w tym kierunku jest niemal pewny, istnieją jednak pewne granice. W 2015 r. Le Gall i dwóch współpracowników okazały że obecne podejście — metoda laserowa w połączeniu z recepturą Coppersmitha-Winograda — nie może dać wartości omega poniżej 2.3078. Aby wprowadzić dalsze ulepszenia, stwierdził Le Gall, „należy ulepszyć pierwotne [podejście] Coppersmith i Winograd, które tak naprawdę nie zmieniło się od 1987 r.". Ale jak dotąd nikt nie wpadł na lepszy sposób. Może nawet nie być ani jednego.

„Ulepszanie omega jest w rzeczywistości częścią zrozumienia tego problemu” – powiedział Zhou. „Jeśli dobrze zrozumiemy problem, będziemy mogli zaprojektować dla niego lepsze algorytmy. [I] ludzie wciąż znajdują się na bardzo wczesnym etapie zrozumienia tego odwiecznego problemu”.