Новий прорив наближає множення матриць до ідеального | Журнал Quanta

Комп’ютерники — вимоглива група. Для них недостатньо отримати правильну відповідь на проблему — ціль, майже завжди, полягає в тому, щоб отримати відповідь якомога ефективніше.

Візьмемо акт множення матриць або масивів чисел. У 1812 році французький математик Жак Філіп Марі Біне запропонував базовий набір правил, яким ми досі навчаємо студентів. Це працює чудово, але інші математики знайшли способи спростити та прискорити процес. Тепер завдання прискорення процесу Матричне множення лежить на перетині математики та інформатики, де дослідники продовжують удосконалювати процес донині, хоча за останні десятиліття успіхи були досить скромними. Починаючи з 1987 року, чисельні вдосконалення в множенні матриць були «невеликими і... надзвичайно важко досягнутими», сказав Франсуа Ле Галль, фахівець з інформатики в університеті Нагоя.

Тепер троє дослідників — Рань Дуань і Реньфей Чжоу з Університету Цінхуа та Хунсюнь Ву з Каліфорнійського університету в Берклі — зробили серйозний крок вперед у боротьбі з цією одвічною проблемою. їх нові результати, представлений у листопаді минулого року на конференції «Основи комп’ютерних наук», походить від несподіваної нової методики, сказав Ле Галл. Хоча саме вдосконалення було відносно невеликим, Ле Галл назвав його «концептуально більшим, ніж інші попередні».

Техніка відкриває раніше невідоме і, отже, невикористане джерело потенційних покращень, і вона вже принесла свої плоди: Другий папір, опублікований у січні, спирається на перший, щоб показати, як матричне множення можна ще більше підвищити.

«Це великий технічний прорив», — сказав він Вільям Кушмаул, вчений-теоретик у Гарвардському університеті. «Це найбільше вдосконалення множення матриць, яке ми бачили за понад десять років».

Увійдіть в Матрицю

Це може здатися незрозумілою проблемою, але множення матриці є фундаментальною обчислювальною операцією. Він включений у велику частину алгоритмів, які люди використовують щодня для різноманітних завдань, від відображення чіткішої комп’ютерної графіки до вирішення логістичних проблем у теорії мереж. І, як і в інших сферах обчислень, швидкість має першорядне значення. Навіть незначні покращення можуть призвести до значної економії часу, обчислювальної потужності та грошей. Але на даний момент теоретики в основному зацікавлені в тому, щоб з'ясувати, наскільки швидким може бути цей процес.

Традиційний спосіб множення на два n-за-n матриці — шляхом множення чисел з кожного рядка в першій матриці на числа в стовпцях у другій — вимагає n³ роздільні множення. Для матриць 2 на 2 це означає 2³ або 8 множень.

У 1969 році математик Фолькер Штрассен відкрив більш складну процедуру, за допомогою якої можна було помножити матриці 2 на 2 лише за сім кроків множення та 18 додавання. Через два роки комп’ютерний науковець Шмуель Віноград продемонстрував, що сім – це справді абсолютний мінімум для матриць 2 на 2.

Штрассен використав ту саму ідею, щоб показати, що все більше n-за-n матриці також можна множити менш ніж n³ кроки. Ключовим елементом цієї стратегії є процедура, яка називається декомпозицією — розбиття великої матриці на послідовні менші підматриці, які в кінцевому підсумку можуть бути такими маленькими, як 2 на 2 або навіть 1 на 1 (це лише окремі числа).

За словами, обґрунтування поділу гігантського масиву на крихітні частини досить просте Вірджинія Василевська Вільямс, фахівець з інформатики в Массачусетському технологічному інституті та співавтор однієї з нових статей. «Людині важко дивитися на велику матрицю (скажімо, порядку 100 на 100) і думати про найкращий можливий алгоритм», — сказала Василевська Вільямс. Навіть матриці 3 на 3 ще не повністю розкриті. «Тим не менш, можна використовувати швидкий алгоритм, який вже розроблено для малих матриць, щоб також отримати швидкий алгоритм для великих матриць».

Дослідники визначили, що ключ до швидкості полягає в тому, щоб зменшити кількість кроків множення, зменшивши цей показник n³ (для стандартного методу) стільки, скільки можуть. Найменше можливе значення, n², в основному стільки, скільки потрібно, щоб написати відповідь. Інформатики називають цей показник як омега, ω, с n^ω це найменша кількість кроків, необхідних для успішного множення двох n-за-n матриці як n виростає дуже великим. «Мета цієї роботи, — сказав Чжоу, який також є співавтором статті за січень 2024 року, — полягає в тому, щоб побачити, наскільки близько ви можете підійти до 2 і чи можна цього досягти теоретично».

Лазерний фокус

У 1986 році Штрассен зробив ще один великий прорив, коли він введені так званий лазерний метод множення матриць. Штрассен використовував його, щоб встановити верхнє значення омеги 2.48. Хоча цей метод є лише одним із кроків у великому матричному множенні, він є одним із найважливіших, оскільки дослідники продовжують його вдосконалювати.

Через рік Віноград і Дон Копперсміт представили новий алгоритм, який чудово доповнював лазерний метод. Ця комбінація інструментів використовувалася практично у всіх наступних спробах прискорити множення матриць.

Ось спрощений спосіб уявлення про те, як ці різні елементи поєднуються разом. Почнемо з двох великих матриць, A і B, які потрібно помножити. Спочатку ви розкладаєте їх на безліч менших підматриць або блоків, як їх іноді називають. Далі ви можете використати алгоритм Копперсміта та Вінограда, щоб він слугував своєрідним посібником з обробки та, зрештою, складання блоків. «Він говорить мені, що множити, що додавати і які записи куди йдуть» у матриці продукту C, сказала Василевська Вільямс. «Це просто рецепт створення C з A і B».

Однак є підступ: інколи ви отримуєте блоки, які мають спільні записи. Залишити їх у продукті було б схоже на двічі підрахувати ці записи, тому в певний момент вам потрібно буде позбутися цих дубльованих термінів, які називаються перекриттями. Дослідники роблять це, «вбиваючи» блоки, в яких вони знаходяться, встановлюючи їхні компоненти рівними нулю, щоб видалити їх з розрахунку.

Ось тут, нарешті, вступає в дію лазерний метод Штрассена. «Лазерний метод зазвичай працює дуже добре і, як правило, знаходить хороший спосіб знищити підмножину блоків, щоб усунути перекриття», — сказав Ле Галл. Після того, як лазер усуне або «спалить» усі перекриття, ви можете побудувати матрицю кінцевого продукту, C.

Поєднання цих різних методів разом призводить до алгоритму множення двох матриць із навмисно скупою загальною кількістю множень — принаймні теоретично. Лазерний метод не є практичним; це просто спосіб подумати про ідеальний спосіб множення матриць. «Ми ніколи не запускаємо цей метод [на комп’ютері], — сказав Чжоу. «Ми це аналізуємо».

І цей аналіз призвів до найбільшого покращення омеги за більш ніж десятиліття.

Знайдено втрату

Дослідження минулого літа Дуаня, Чжоу та Ву показало, що процес Штрассена все ще можна значно прискорити. Це все через концепцію, яку вони назвали прихованою втратою, глибоко заховану в попередніх аналізах — «результат ненавмисного знищення занадто великої кількості блоків», — сказав Чжоу.

Лазерний метод працює шляхом маркування блоків з нахлестом як сміття, призначеного для утилізації; інші блоки вважаються гідними та будуть збережені. Однак процес відбору є дещо рандомізованим. Блок, оцінений як сміття, насправді може виявитися корисним. Це не було абсолютною несподіванкою, але, вивчивши багато з цих випадкових виборів, команда Дуана визначила, що лазерний метод систематично занижував вартість блоків: більше блоків слід зберігати, а менше викидати. І, як зазвичай буває, менше відходів означає більшу ефективність.

«Таким чином, можливість зберігати більше блоків без перекриття призводить до … швидшого алгоритму множення матриці», — сказав Ле Галл.

Довівши існування цієї втрати, команда Дуаня змінила спосіб, за допомогою якого лазерний метод позначав блоки, суттєво зменшивши відходи. У результаті вони встановили нову верхню межу для омеги на рівні близько 2.371866 — покращення в порівнянні з попередньою верхньою межею 2.3728596, встановлений у 2020 році Джош Алман і Василевська Вільямс. Це може здатися скромною зміною, знижуючи межу приблизно на 0.001. Але це найбільше покращення, яке вчені бачили з 2010 року. Для порівняння, результат Василевської Вільямс і Альмана у 2020 році покращився порівняно з попередником лише на 0.00001.

Але найцікавішим для дослідників є не лише сам новий рекорд, який проіснував недовго. Це також той факт, що газета розкрила новий шлях для вдосконалення, який до того часу залишався абсолютно непоміченим. Майже чотири десятиліття всі покладаються на той самий лазерний метод, сказав Ле Галл. «Тоді вони виявили, що ми можемо зробити краще».

Документ від січня 2024 року вдосконалив цей новий підхід, дозволивши Василевській Вільямс, Чжоу та їхнім співавторам ще більше зменшити приховані втрати. Це призвело до додаткового покращення верхньої межі омеги, зменшивши її до 2.371552. Автори також узагальнили ту саму техніку для покращення процесу множення для прямокутних (n-за-m) матриці — процедура, яка має застосування в теорії графів, машинному навчанні та інших областях.

Певний подальший прогрес у цьому напрямі майже безперечний, але є межі. У 2015 році Ле Гал і двоє його співробітників доведений що нинішній підхід — лазерний метод у поєднанні з рецептом Копперсміта-Вінограда — не може дати омегу нижче 2.3078. Щоб зробити будь-які подальші вдосконалення, сказав Ле Галл, «вам потрібно вдосконалити оригінальний [підхід] Coppersmith і Winograd, який насправді не змінився з 1987 року.». Але поки що кращого способу ніхто не придумав. Може навіть не бути жодного.

«Поліпшення омеги насправді є частиною розуміння цієї проблеми», — сказав Чжоу. «Якщо ми зможемо добре зрозуміти проблему, то зможемо розробити для неї кращі алгоритми. [І] люди все ще перебувають на дуже ранніх стадіях розуміння цієї давньої проблеми».