Алгоритм Штрассена

Вступ та постановка задачі

Розмноження матриць за визначенням, вбудована функція

matmul та оптимізація

1 Вступ та постановка задачі

Одне з основних завдань цієї роботи - реалізувати алгоритм Штрассена. Це рекурсивний алгоритм множення матриць, що дозволяє значно прискорити процес множення. Слід зазначити, що цей алгоритм ефективний лише матриць досить великого розміру. Визначити розмір матриць, з якого є сенс починати множити за алгоритмом Штрассена, можна експериментальним шляхом. Крім того, я вже згадувала, що алгоритм є рекурсивним. У нерекурсивної галузі алгоритму використовується "просте" множення матриць, тобто. множення за визначенням. Зробити нерекурсивну гілку найефективнішою та організувати вихід із рекурсії у потрібний момент – ще одне завдання моєї роботи.

Отже, намітимо цілі роботи:

реалізувати алгоритм Штрассена;

Експериментально визначити розмір матриці, котрій слід переходити на множення по алгоритму;

Організувати вихід із рекурсії у потрібний момент;

Зробити не рекурсивну гілку найефективнішою.

2 Алгоритм Штрассена

Найвитратніша за часом операція - множення. Тобто. щоб прискорити процес, потрібно скоротити їхнє число. Штрассен вигадав алгоритм [1, 2, 3], який дозволяє уникнути одного множення. Чудово, що формули вимагають комутативності складання, тобто. вони застосовні і для матриць, що дозволяє застосовувати алгоритм рекурсивно.

Алгоритм працює з квадратними матрицями розміру 2 n. Зауважимо, що для множення матриць такого розміру потрібно 2 3n множень. Якщо ж матриці не квадратні, то можна розширити їх до потрібного розміру, заповнивши рядки, що відсутні, і стовпці нулями. Припустимо, є двіматриці A і B розміру 2 n які потрібно перемножити: C = AB. Розіб'ємо кожну матрицю на чотири підматриці:

---