www.wikidata.uk-ua.nina.az

Алгоритм Штрассена Не плутати з алгоритмом Шьонхаге Штрассена для множення довгих цілих чисел алгоритм який в 1969 році

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

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

Алгоритм Штрассена — алгоритм, який в 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 використовуючи алгоритм Штрассена є

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

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

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


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

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

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

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

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

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

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

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

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

Обчислюються проміжні матриціS1 —S8,P1 —P7,T1 —T2



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

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

  1. P. D'Alberto and A. Nicolau, "Using recursion to boost ATLAS's performance [ 8 квітня 2016 у Wayback Machine.], " 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. 12 грудня 2011. Архів оригіналу за 17 лютого 2012. Процитовано 12 грудня 2011. 

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

  • Weisstein, Eric W. Strassen's Formulas(англ.) на сайті Wolfram MathWorld. (також включені формули для швидкого пошуку зворотньої матриці)
  • Tyler J. Earnest,
  • (легко для освітніх цілей)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Ne plutati z algoritmom Shonhage Shtrassena dlya mnozhennya dovgih cilih chisel Algoritm Shtrassena algoritm yakij v 1969 roci rozrobiv Folker Shtrassen Priznachenij dlya shvidkogo mnozhennya matric ye uzagalnennyam metodu mnozhennya Karacubi na matrici Cej algoritm dozvolyaye shvidshe za standartnij sposib mnozhiti matrici Na praktici ce vidchutno na velikih matricyah ale isnuye she bilsh shvidkij algoritm Koppersmita Vinograda dlya mnozhennya duzhe velikih matric Na vidminu vid tradicijnogo algoritmu mnozhennya matric za formuloyu c i k a i j b j k displaystyle c ik sum a ij b jk yakij vikonuyetsya za chas O N 3 O N log 2 8 displaystyle O N 3 O N log 2 8 algoritm Shtrassena mnozhit matrici za chas O N log 2 7 o 1 O N 2 8074 displaystyle O N log 2 7 o 1 approx O N 2 8074 sho daye vigrash na velikih shilnih matricyah pochinayuchi priblizno z matric rozmiru 64 64 Zmist 1 Istoriya 2 Algoritm 3 Asimptotichna skladnist 3 1 Rang 4 Pitannya praktichnoyi realizaciyi 5 Podalshij rozvitok 6 Algoritm Vinograda Shtrassena 7 Primitki 8 PosilannyaIstoriya RedaguvatiFolker Shtrassen opublikuvav svij algoritm v 1969 roci Hocha jogo algoritm lishe trohi shvidshij nizh standartnij algoritm mnozhennya matric ale vin buv pershim hto vkazav na ne optimalnist standartnogo pidhodu Jogo stattya nadihnula na poshuk bilsh shvidkih algoritmiv Zokrema znajdeno bilsh skladnij algoritm Koppersmita Vinograda v 1987 roci Algoritm Redaguvati nbsp U livij kolonci predstavlennya mnozhennya matric 2x2 Nayivne mnozhennya matric vimagaye odne mnozhennya dlya kozhnogo 1 v livij kolonci Kozhen z reshti stovpciv yavlyaye soboyu yedine z 7 mnozhen v algoritmi i suma stovpciv daye povne matrichne mnozhennya zliva Nehaj A B dvi kvadratni matrici nad kilcem R Mi mozhemo obchisliti matricyu C yak C A B A B C R 2 n 2 n displaystyle mathbf C mathbf A mathbf B qquad mathbf A mathbf B mathbf C in R 2 n times 2 n nbsp Yaksho matrici A B ne tipu 2n x 2n zapovnyuyemo vidsutni ryadki i stovpci nulyami Pri comu mi otrimuyemo zruchni dlya rekursivnogo mnozhennya rozmiri ale vtrachayemo efektivnist za rahunok dodatkovih nepotribnih mnozhen Rozdilimo matrici A B i C na rivni za rozmirom blochni matrici A A 1 1 A 1 2 A 2 1 A 2 2 B B 1 1 B 1 2 B 2 1 B 2 2 C C 1 1 C 1 2 C 2 1 C 2 2 displaystyle mathbf A begin bmatrix mathbf A 1 1 amp mathbf A 1 2 mathbf A 2 1 amp mathbf A 2 2 end bmatrix mbox mathbf B begin bmatrix mathbf B 1 1 amp mathbf B 1 2 mathbf B 2 1 amp mathbf B 2 2 end bmatrix mbox mathbf C begin bmatrix mathbf C 1 1 amp mathbf C 1 2 mathbf C 2 1 amp mathbf C 2 2 end bmatrix nbsp de A i j B i j C i j R 2 n 1 2 n 1 displaystyle mathbf A i j mathbf B i j mathbf C i j in R 2 n 1 times 2 n 1 nbsp todi C 1 1 A 1 1 B 1 1 A 1 2 B 2 1 displaystyle mathbf C 1 1 mathbf A 1 1 mathbf B 1 1 mathbf A 1 2 mathbf B 2 1 nbsp C 1 2 A 1 1 B 1 2 A 1 2 B 2 2 displaystyle mathbf C 1 2 mathbf A 1 1 mathbf B 1 2 mathbf A 1 2 mathbf B 2 2 nbsp C 2 1 A 2 1 B 1 1 A 2 2 B 2 1 displaystyle mathbf C 2 1 mathbf A 2 1 mathbf B 1 1 mathbf A 2 2 mathbf B 2 1 nbsp C 2 2 A 2 1 B 1 2 A 2 2 B 2 2 displaystyle mathbf C 2 2 mathbf A 2 1 mathbf B 1 2 mathbf A 2 2 mathbf B 2 2 nbsp Pri takij konstrukciyi mi ne zmenshili kilkist operacij mnozhennya Nam yak i ranishe potribno 8 mnozhen dlya obchislennya Ci j matrici yak i v zvichajnomu metodi Zaraz vazhliva chastina Viznachayemo novi matrici M 1 A 1 1 A 2 2 B 1 1 B 2 2 displaystyle mathbf M 1 mathbf A 1 1 mathbf A 2 2 mathbf B 1 1 mathbf B 2 2 nbsp M 2 A 2 1 A 2 2 B 1 1 displaystyle mathbf M 2 mathbf A 2 1 mathbf A 2 2 mathbf B 1 1 nbsp M 3 A 1 1 B 1 2 B 2 2 displaystyle mathbf M 3 mathbf A 1 1 mathbf B 1 2 mathbf B 2 2 nbsp M 4 A 2 2 B 2 1 B 1 1 displaystyle mathbf M 4 mathbf A 2 2 mathbf B 2 1 mathbf B 1 1 nbsp M 5 A 1 1 A 1 2 B 2 2 displaystyle mathbf M 5 mathbf A 1 1 mathbf A 1 2 mathbf B 2 2 nbsp M 6 A 2 1 A 1 1 B 1 1 B 1 2 displaystyle mathbf M 6 mathbf A 2 1 mathbf A 1 1 mathbf B 1 1 mathbf B 1 2 nbsp M 7 A 1 2 A 2 2 B 2 1 B 2 2 displaystyle mathbf M 7 mathbf A 1 2 mathbf A 2 2 mathbf B 2 1 mathbf B 2 2 nbsp tilki za dopomogoyu 7 mnozhen odin dlya kozhnogo Mk zamist 8 Teper mi mozhemo visloviti Ci j pri umovi Mk os tak C 1 1 M 1 M 4 M 5 M 7 displaystyle mathbf C 1 1 mathbf M 1 mathbf M 4 mathbf M 5 mathbf M 7 nbsp C 1 2 M 3 M 5 displaystyle mathbf C 1 2 mathbf M 3 mathbf M 5 nbsp C 2 1 M 2 M 4 displaystyle mathbf C 2 1 mathbf M 2 mathbf M 4 nbsp C 2 2 M 1 M 2 M 3 M 6 displaystyle mathbf C 2 2 mathbf M 1 mathbf M 2 mathbf M 3 mathbf M 6 nbsp Mi povtoryuyemo rekursivnij proces dilennya n raz doti poki rozmir matric Ci j ne stane dosit malim dali vikoristovuyut zvichajnij metod mnozhennya matric Asimptotichna skladnist RedaguvatiStandartne mnozhennya matric zajmaye priblizno 2N3 de N 2n arifmetichnih operacij dodavannya i mnozhennya asimptotichna skladnist O N3 Chislo dodavan i mnozhen neobhidnih v algoritmi Shtrassena mozhe buti rozrahovana nastupnim chinom nehaj f n chislo operacij dlya 2n 2n matrici Todi za rekursivnim zastosuvannyam algoritmu Shtrassena mi bachimo sho f n 7f n 1 L4n z deyakoyu postijnoyu L yaka zalezhit vid kilkosti dopovnen vikonanih v kozhnomu zastosuvanni algoritmu Otzhe f n 7 o 1 n tobto asimptotichna skladnist dlya mnozhennya matric rozmiru N 2n vikoristovuyuchi algoritm Shtrassena ye O 7 o 1 n O N log 2 7 o 1 O N 2 8074 displaystyle O 7 o 1 n O N log 2 7 o 1 approx O N 2 8074 nbsp Zmenshennya kilkosti arifmetichnih operacij prizvodit do chastkovo zmenshenoyi chislovoyi stabilnosti 1 i algoritm takozh vimagaye znachno bilshe pam yati porivnyano z nayivnim algoritmom Obidvi pochatkovi matrici rozmiri yakih povinni buti rozshireni do nastupnogo stupenya dvijki v rezultati chogo zberigayetsya do chotiroh raziv bilshe elementiv ta sim dopomizhnih matric kozhna z yakih mistit v sobi chvert elementiv Rang Redaguvati Rang ye vazhlivim ponyattyam v asimptotichnij skladnosti matrichnogo mnozhennya Rang ϕ A B C displaystyle phi mathbf A times mathbf B rightarrow mathbf C nbsp nad polem F viznachayetsya yak nepravilne poznachennya R ϕ F min r f i A g i B w i C a A b B ϕ a b i 1 r f i a g i b w i displaystyle R phi mathbf F min left r left exists f i in mathbf A g i in mathbf B w i in mathbf C forall mathbf a in mathbf A mathbf b in mathbf B phi mathbf a mathbf b sum i 1 r f i mathbf a g i mathbf b w i right right nbsp Inshimi slovami rang bilinijnogo vidobrazhennya ce dovzhina jogo najkorotshogo bilinijnogo obchislennya 2 Isnuvannya algoritmu Shtrassena pokazuye sho rang matrici 2 2 zdijsnyuye mnozhennya ne bilshe nizh sim raziv Shob perekonatisya v comu rozglyanemo cej algoritm poryad zi standartnim algoritmom v tablici dlya obchislennya matric Standartnij algoritm Algoritm Shtrassenai fi a gi b wi fi a gi b wi1 1 0 0 0 a displaystyle begin bmatrix 1 amp 0 0 amp 0 end bmatrix mathbf a nbsp 1 0 0 0 b displaystyle begin bmatrix 1 amp 0 0 amp 0 end bmatrix mathbf b nbsp 1 0 0 0 displaystyle begin bmatrix 1 amp 0 0 amp 0 end bmatrix nbsp 1 0 0 1 a displaystyle begin bmatrix 1 amp 0 0 amp 1 end bmatrix mathbf a nbsp 1 0 0 1 b displaystyle begin bmatrix 1 amp 0 0 amp 1 end bmatrix mathbf b nbsp 1 0 0 1 displaystyle begin bmatrix 1 amp 0 0 amp 1 end bmatrix nbsp 2 0 1 0 0 a displaystyle begin bmatrix 0 amp 1 0 amp 0 end bmatrix mathbf a nbsp 0 0 1 0 b displaystyle begin bmatrix 0 amp 0 1 amp 0 end bmatrix mathbf b nbsp 1 0 0 0 displaystyle begin bmatrix 1 amp 0 0 amp 0 end bmatrix nbsp 0 0 1 1 a displaystyle begin bmatrix 0 amp 0 1 amp 1 end bmatrix mathbf a nbsp 1 0 0 0 b displaystyle begin bmatrix 1 amp 0 0 amp 0 end bmatrix mathbf b nbsp 0 0 1 1 displaystyle begin bmatrix 0 amp 0 1 amp 1 end bmatrix nbsp 3 1 0 0 0 a displaystyle begin bmatrix 1 amp 0 0 amp 0 end bmatrix mathbf a nbsp 0 1 0 0 b displaystyle begin bmatrix 0 amp 1 0 amp 0 end bmatrix mathbf b nbsp 0 1 0 0 displaystyle begin bmatrix 0 amp 1 0 amp 0 end bmatrix nbsp 1 0 0 0 a displaystyle begin bmatrix 1 amp 0 0 amp 0 end bmatrix mathbf a nbsp 0 1 0 1 b displaystyle begin bmatrix 0 amp 1 0 amp 1 end bmatrix mathbf b nbsp 0 1 0 1 displaystyle begin bmatrix 0 amp 1 0 amp 1 end bmatrix nbsp 4 0 1 0 0 a displaystyle begin bmatrix 0 amp 1 0 amp 0 end bmatrix mathbf a nbsp 0 0 0 1 b displaystyle begin bmatrix 0 amp 0 0 amp 1 end bmatrix mathbf b nbsp 0 1 0 0 displaystyle begin bmatrix 0 amp 1 0 amp 0 end bmatrix nbsp 0 0 0 1 a displaystyle begin bmatrix 0 amp 0 0 amp 1 end bmatrix mathbf a nbsp 1 0 1 0 b displaystyle begin bmatrix 1 amp 0 1 amp 0 end bmatrix mathbf b nbsp 1 0 1 0 displaystyle begin bmatrix 1 amp 0 1 amp 0 end bmatrix nbsp 5 0 0 1 0 a displaystyle begin bmatrix 0 amp 0 1 amp 0 end bmatrix mathbf a nbsp 1 0 0 0 b displaystyle begin bmatrix 1 amp 0 0 amp 0 end bmatrix mathbf b nbsp 0 0 1 0 displaystyle begin bmatrix 0 amp 0 1 amp 0 end bmatrix nbsp 1 1 0 0 a displaystyle begin bmatrix 1 amp 1 0 amp 0 end bmatrix mathbf a nbsp 0 0 0 1 b displaystyle begin bmatrix 0 amp 0 0 amp 1 end bmatrix mathbf b nbsp 1 1 0 0 displaystyle begin bmatrix 1 amp 1 0 amp 0 end bmatrix nbsp 6 0 0 0 1 a displaystyle begin bmatrix 0 amp 0 0 amp 1 end bmatrix mathbf a nbsp 0 0 1 0 b displaystyle begin bmatrix 0 amp 0 1 amp 0 end bmatrix mathbf b nbsp 0 0 1 0 displaystyle begin bmatrix 0 amp 0 1 amp 0 end bmatrix nbsp 1 0 1 0 a displaystyle begin bmatrix 1 amp 0 1 amp 0 end bmatrix mathbf a nbsp 1 1 0 0 b displaystyle begin bmatrix 1 amp 1 0 amp 0 end bmatrix mathbf b nbsp 0 0 0 1 displaystyle begin bmatrix 0 amp 0 0 amp 1 end bmatrix nbsp 7 0 0 1 0 a displaystyle begin bmatrix 0 amp 0 1 amp 0 end bmatrix mathbf a nbsp 0 1 0 0 b displaystyle begin bmatrix 0 amp 1 0 amp 0 end bmatrix mathbf b nbsp 0 0 0 1 displaystyle begin bmatrix 0 amp 0 0 amp 1 end bmatrix nbsp 0 1 0 1 a displaystyle begin bmatrix 0 amp 1 0 amp 1 end bmatrix mathbf a nbsp 0 0 1 1 b displaystyle begin bmatrix 0 amp 0 1 amp 1 end bmatrix mathbf b nbsp 1 0 0 0 displaystyle begin bmatrix 1 amp 0 0 amp 0 end bmatrix nbsp 8 0 0 0 1 a displaystyle begin bmatrix 0 amp 0 0 amp 1 end bmatrix mathbf a nbsp 0 0 0 1 b displaystyle begin bmatrix 0 amp 0 0 amp 1 end bmatrix mathbf b nbsp 0 0 0 1 displaystyle begin bmatrix 0 amp 0 0 amp 1 end bmatrix nbsp a b i 1 8 f i a g i b w i displaystyle mathbf a mathbf b sum i 1 8 f i mathbf a g i mathbf b w i nbsp a b i 1 7 f i a g i b w i displaystyle mathbf a mathbf b sum i 1 7 f i mathbf a g i mathbf b w i nbsp Pitannya praktichnoyi realizaciyi RedaguvatiNavedenij vishe opis stverdzhuye sho matrici ye kvadratnimi a rozmir ye stupenem dvijki Ce obmezhennya dozvolyaye matrici buti rozdilenoyu navpil rekursivno poki mezha skalyarnogo mnozhennya ne bude dosyagnuta Obmezhennya sproshuye poyasnennya i analiz skladnosti i spravdi peretvorennya matrici yak opisano prizvede do zbilshennya chasu obchislen i mozhe legko usunuti dosit neveliku ekonomiyu chasu otrimanu za dopomogoyu metodu Podalshij rozvitok RedaguvatiShtrassen buv pershim hto pokazav mozhlivist mnozhennya matric bilsh efektivnim sposobom nizh standartnij Pislya publikaciyi jogo roboti v 1969 pochalisya aktivni poshuki bilsh shvidkogo algoritmu Asimptotichno najshvidshim algoritmom na sogodnishnij den ye algoritm Koppersmita Vinograda sho dozvolyaye mnozhiti matrici za O n 2 376 displaystyle rm O n 2 376 nbsp operacij 3 zaproponovanij 1987 roku i vdoskonalenij 2011 roku do rivnya O n 2 3727 displaystyle rm O n 2 3727 nbsp 3 Cej algoritm ne maye praktichnogo interesu v ocinci arifmetichnoyi skladnosti Pitannya pro granichnu v asimptotici shvidkist mnozhennya matric ne virishene Isnuye gipoteza Shtrassena ru pro te sho dlya dostatno velikih n isnuye algoritm mnozhennya dvoh matric rozmiru n n displaystyle n times n nbsp za O n 2 e displaystyle rm O n 2 varepsilon nbsp operacij de e displaystyle varepsilon nbsp yak zavgodno male napered zadane pozitivne chislo Cya gipoteza maye suto teoretichnij interes oskilki rozmir matric dlya yakih e displaystyle varepsilon nbsp dijsno duzhe velikij Pitannya pro pobudovu najbilsh shvidkogo ta stijkogo praktichnogo algoritmu mnozhennya velikih matric takozh zalishayetsya nevirishenim Algoritm Vinograda Shtrassena RedaguvatiIsnuye modifikaciya algoritmu Shtrassena dlya yakogo vimagayetsya 7 mnozhen ta 15 dodavan zamist18dlya zvichajnogo algoritmu Shtrassena Matrici A B i C dilyatsya na blokovi pidmatrici Obchislyuyutsya promizhni matriciS1 S8 P1 P7 T1 T2 S 1 A 2 1 A 2 2 displaystyle mathbf S 1 mathbf A 2 1 mathbf A 2 2 nbsp S 2 S 1 A 1 1 displaystyle mathbf S 2 mathbf S 1 mathbf A 1 1 nbsp S 3 A 1 1 A 2 1 displaystyle mathbf S 3 mathbf A 1 1 mathbf A 2 1 nbsp S 4 A 1 2 S 2 displaystyle mathbf S 4 mathbf A 1 2 mathbf S 2 nbsp S 5 B 1 2 B 1 1 displaystyle mathbf S 5 mathbf B 1 2 mathbf B 1 1 nbsp S 6 B 2 2 S 5 displaystyle mathbf S 6 mathbf B 2 2 mathbf S 5 nbsp S 7 B 2 2 B 1 2 displaystyle mathbf S 7 mathbf B 2 2 mathbf B 1 2 nbsp S 8 S 6 B 2 1 displaystyle mathbf S 8 mathbf S 6 mathbf B 2 1 nbsp P 1 S 2 S 6 displaystyle mathbf P 1 mathbf S 2 mathbf S 6 nbsp P 2 A 1 1 B 1 1 displaystyle mathbf P 2 mathbf A 1 1 mathbf B 1 1 nbsp P 3 A 1 2 B 2 1 displaystyle mathbf P 3 mathbf A 1 2 mathbf B 2 1 nbsp P 4 S 3 S 7 displaystyle mathbf P 4 mathbf S 3 mathbf S 7 nbsp P 5 S 1 S 5 displaystyle mathbf P 5 mathbf S 1 mathbf S 5 nbsp P 6 S 4 B 2 2 displaystyle mathbf P 6 mathbf S 4 mathbf B 2 2 nbsp P 7 A 2 2 S 8 displaystyle mathbf P 7 mathbf A 2 2 mathbf S 8 nbsp T 1 P 1 P 2 displaystyle mathbf T 1 mathbf P 1 mathbf P 2 nbsp T 2 T 1 P 4 displaystyle mathbf T 2 mathbf T 1 mathbf P 4 nbsp Elementi matrici C obchislyuyutsya za formulami C 1 1 P 2 P 3 displaystyle mathbf C 1 1 mathbf P 2 mathbf P 3 nbsp C 1 2 T 1 P 5 P 6 displaystyle mathbf C 1 2 mathbf T 1 mathbf P 5 mathbf P 6 nbsp C 2 1 T 2 P 7 displaystyle mathbf C 2 1 mathbf T 2 mathbf P 7 nbsp C 2 2 T 2 P 5 displaystyle mathbf C 2 2 mathbf T 2 mathbf P 5 nbsp Primitki Redaguvati P D Alberto and A Nicolau Using recursion to boost ATLAS s performance Arhivovano 8 kvitnya 2016 u Wayback Machine Lecture Notes in Computer Science vol 4759 pp 142 151 2010 Burgisser Clausen and Shokrollahi Algebraic Complexity Theory Springer Verlag 1997 a b Matematiki preodoleli barer Koppersmita Vinograda lenta ru 12 grudnya 2011 Arhiv originalu za 17 lyutogo 2012 Procitovano 12 grudnya 2011 Posilannya RedaguvatiWeisstein Eric W Strassen s Formulas angl na sajti Wolfram MathWorld takozh vklyucheni formuli dlya shvidkogo poshuku zvorotnoyi matrici Tyler J Earnest Strassen s Algorithm on the Cell Broadband EngineSimple Strassen s algorithms implementation in C legko dlya osvitnih cilej Simple Strassen s algorithms implementation in Java Arhivovano 20 bereznya 2012 u Wayback Machine Otrimano z https uk wikipedia org w index php title Algoritm Shtrassena amp oldid 39593078