Відкрити головне меню

Не плутати з алгоритмом Шьонхаге-Штрассена для множення довгих цілих.

Алгоритм Штрассена призначений для швидкого множення матриць. Він був розроблений Фолькером Штрассеном в 1969 році і є узагальненням методу множення Карацуби на матриці. Цей алгоритм дозволяє швидше за стандартний спосіб множити матриці. На практиці це відчутно на великих матрицях, але існує ще більш швидкий алгоритм Копперсміта-Вінограда для множення дуже великих матриць.

На відміну від традиційного алгоритму множення матриць (за формулою ), який виконується за час , алгоритм Штрассена множить матриці за час , що дає виграш на великих щільних матрицях починаючи, приблизно, з матриць розміру 64 × 64.

Зміст

ІсторіяРедагувати

Фолькер Штрассен опублікував свій алгоритм в 1969 році. Хоча його алгоритм лише трохи швидший, ніж стандартний алгоритм множення матриць, але він був першим, хто вказав на не оптимальність стандартного підходу. Його стаття надихнула на пошук більш швидких алгоритмів. Зокрема, знайдено більш складний алгоритм Копперсміта-Вінограда в 1987 році.

АлгоритмРедагувати

 
У лівій колонці представлення множення матриць 2x2. Наївне множення матриць вимагає одне множення для кожного «1» в лівій колонці. Кожен з решти стовпців являє собою єдине з 7 множень в алгоритмі, і сума стовпців дає повне матричне множення зліва.

Нехай A, B — дві квадратні матриці над кільцем R. Ми можемо обчислити матрицю C, як:

 

Якщо матриці A,B, не типу 2n x 2n заповнюємо відсутні рядки і стовпці нулями. При цьому ми отримуємо зручні для рекурсивного множення розміри, але втрачаємо ефективність за рахунок додаткових непотрібних множень.

Розділимо матриці A,B і C на рівні за розміром блочні матриці

 

де

 

тоді

 
 
 
 

При такій конструкції ми не зменшили кількість операцій множення. Нам, як і раніше, потрібно 8 множень для обчислення Ci, j матриці, як і в звичайному методі.

Зараз важлива частина. Визначаємо нові матриці

 
 
 
 
 
 
 

тільки за допомогою 7 множень (один для кожного Mk) замість 8. Тепер ми можемо висловити Ci,j при умові Mk, ось так:

 
 
 
 

Ми повторюємо рекурсивний процес ділення n раз доти, поки розмір матриць Ci, j не стане досить малим, далі використовують звичайний метод множення матриць.

Асимптотична складністьРедагувати

Стандартне множення матриць займає приблизно 2N3 (де N = 2n) арифметичних операцій (додавання і множення); асимптотична складність O (N3).

Число додавань і множень, необхідних в алгоритмі Штрассена може бути розрахована наступним чином: нехай f(n) число операцій для 2n × 2n матриці. Тоді, за рекурсивним застосуванням алгоритму Штрассена, ми бачимо, що f(n) = 7f(n-1) + L4n, з деякою постійною L, яка залежить від кількості доповнень, виконаних в кожному застосуванні алгоритму. Отже f(n) = (7 + o(1))n, тобто асимптотична складність для множення матриць розміру N = 2n використовуючи алгоритм Штрассена є

 .

Зменшення кількості арифметичних операцій призводить до частково зменшеної числової стабільності,[1] і алгоритм також вимагає значно більше пам'яті, порівняно з наївним алгоритмом. Обидві початкові матриці, розміри яких повинні бути розширені до наступного ступеня двійки, в результаті чого зберігається до чотирьох разів більше елементів, та сім допоміжних матриць, кожна з яких містить в собі чверть елементів.

РангРедагувати

Ранг є важливим поняттям в асимптотичній складності матричного множення. Ранг   над полем F визначається як неправильне позначення.


 

Іншими словами, ранг білінійного відображення - це довжина його найкоротшого білінійного обчислення.[2] Існування алгоритму Штрассена показує, що ранг матриці 2×2 здійснює множення не більше ніж сім разів. Щоб переконатися в цьому, розглянемо цей алгоритм (поряд зі стандартним алгоритмом) в таблиці для обчислення матриць.

Стандартний алгоритм Алгоритм Штрассена
i fi(a) gi(b) wi fi(a) gi(b) wi
1            
2            
3            
4            
5            
6            
7            
8      
   

Питання практичної реалізаціїРедагувати

Наведений вище опис стверджує, що матриці є квадратними, а розмір є ступенем двійки. Це обмеження дозволяє матриці бути розділеною навпіл рекурсивно, поки межа скалярного множення не буде досягнута. Обмеження спрощує пояснення і аналіз складності; і справді, перетворення матриці, як описано, призведе до збільшення часу обчислень і може легко усунути досить невелику економію часу, отриману за допомогою методу.

Подальший розвитокРедагувати

Штрассен був першим, хто показав можливість множення матриць більш ефективним способом, ніж стандартний. Після публікації його роботи в 1969, почалися активні пошуки більш швидкого алгоритму. Асимптотично найшвидшим алгоритмом на сьогоднішній день є алгоритм Копперсміта-Винограда, що дозволяє множити матриці за   операцій[3], запропонований 1987 року і вдосконалений 2011 року до рівня  [3]. Цей алгоритм не має практичного інтересу в оцінці арифметичної складності. Питання про граничну в асимптотиці швидкість множення матриць не вирішене. Існує гіпотеза Штрассена[ru] про те, що для достатньо великих n існує алгоритм множення двох матриць розміру   за   операцій, де   як завгодно мале наперед задане позитивне число. Ця гіпотеза має суто теоретичний інтерес, оскільки розмір матриць для яких   дійсно дуже великий.

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

Алгоритм Винограда-ШтрассенаРедагувати

Існує модифікація алгоритму Штрассена, для якого вимагається 7 множень та 15 додавань (замість18для звичайного алгоритму Штрассена). Матриці A,B і C діляться на блокові підматриці.

Обчислюються проміжні матриціS1S8,P1P7,T1T2

 
 
 
 
 
 
 
 


 
 
 
 
 
 
 


 
 

Елементи матриці C обчислюються за формулами

 
 
 
 

ПриміткиРедагувати

  1. P. D'Alberto and A. Nicolau, "Using recursion to boost ATLAS's performance," Lecture Notes in Computer Science, vol. 4759, pp. 142-151 (2010).
  2. Burgisser, Clausen, and Shokrollahi. Algebraic Complexity Theory. Springer-Verlag 1997.
  3. а б Математики преодолели барьер Копперсмита-Винограда. lenta.ru. 2011-12-12. Архів оригіналу за 2012-02-17. Процитовано 2011-12-12. 

ПосиланняРедагувати