www.wikidata.uk-ua.nina.az

Множення матриць Множе ння ма триць це бінарна операція яка використовуючи дві матриці утворює нову матрицю яка називаєт

Множення матриць

Множе́ння ма́триць — це бінарна операція, яка використовуючи дві матриці, утворює нову матрицю, яка називається доб́утком ма́триць. Дійсні або комплексні числа множаться відповідно до правил елементарної арифметики. З іншого боку, матриці є масивами чисел, тому існують різні способи визначити добуток матриць. Таким чином, загалом термін «матричне множення» означає різні способи перемноження матриць. Ключовими особливостями будь-якого матричного множення є: кількість рядків і стовпців, в початкових матрицях, і правило, як елементи матриць утворюють нову матрицю.

Визначення Редагувати

Нехай дано дві прямокутні матриці і розмірності і відповідно:

Тоді матриця розмірністю називається їх добутком:

де:

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

Слід зауважити, що з існування добутку зовсім не випливає існування добутку

Ілюстрація Редагувати

Добуток матриць AB складається з усіх можливих комбінацій скалярних добутків вектор-рядків матриці A і вектор-стовпців матриці B. Елемент матриці AB з індексами i, j є скалярним добутком i-го вектор-рядка матриці A і j-го вектор-стовпця матриці B.

Ілюстрація праворуч демонструє обчислення добутку двох матриць A і B. Вона показує як перетини в добутку матриць відповідають рядкам матриці A і стовпцям матриці B. Розмір результуючої матриці завжди максимально можливий, тобто для кожного рядка матриці A і стовпця матриці B є завжди відповідний перетин в добутку матриць.

Значення на перетинах відмічених кружечками будуть:

У загальному випадку, добуток матриць не є комутативною операцією. Приміром:

Елемент добутку матриць приведених вище, обчислюється таким чином

Перша координата в позначенні матриці позначає рядок, друга координата — стовпець; цей порядок використовують як при індексації, так і при позначенні розміру. Елемент на перетині рядка та стовпця результуючої матриці є скалярним добутком -го рядка першої матриці і -го стовпця другої матриці. Це пояснює чому ширина і висота множимих матриць повинні збігатися: інакше скалярний твір не визначено.

Мотивація Редагувати

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

Останнє звичайно вводиться виходячи з того, що при розкладанні векторів по базису дію (кожного) лінійного оператора A дає вираз компонент вектора v' = Av:

Тобто лінійний оператор виявляється представлений матрицею, вектори — векторами-стовпцями, а дія оператора на вектор — матричним множенням вектора-стовпця зліва на матрицю оператора (це окремий випадок матричного множення, коли одна з матриць — вектор-стовпець — має розмір 1хn).

(Так само перехід до будь-якого нового базису при зміні координат представляється повністю аналогічним виразом, тільки в цьому випадку вже не компоненти нового вектора в старому базисі, а компоненти старого вектора в новому базисі; при цьому  — елементи матриці переходу до нового базису).

Розглянувши послідовну дію на вектор двох операторів: спочатку A, а потім B (або перетворення базису A, а потім перетворення базису B), двічі застосувавши формулу, отримуємо:

звідки видно, що композиції BA дії лінійних операторів A і B (або аналогічної композиції перетворень базису) відповідає матриця, що обчислюється за правилом добутку відповідних матриць:

Визначений таким чином добуток матриць виявляється абсолютно звичайним і очевидно корисним (дає простий і універсальний спосіб обчислення композицій довільної кількості лінійних перетворень).

Властивості Редагувати

Сполучна властивість, асоціативність:

Розподільна властивість, дистрибутивність щодо додавання:

Добуток матриці на одиничну матрицю того ж порядку дорівнює самій матриці:

Добуток матриці на нульову матрицю тієї ж розмірності дорівнює нульовий матриці:

Якщо і  — квадратні матриці одного і того ж порядку, то добуток матриць має ще ряд властивостей.

Множення матриць в загальному випадку є некомутативним:

Якщо , то матриці і називаються перестановочними або комутуючими між собою.

Найпростіші приклади комутуючих матриць:

  • будь-яка квадратна матриця — з самою собою: (зведення матриці в квадрат);
  • будь-яка квадратна матриця — з одиничною матрицею того ж порядку: ;
  • будь-яка квадратна матриця — з нульовою матрицею того ж порядку: ;
  • будь-яка невироджена квадратна матриця — зі своєю зворотною матрицею: .

Визначник і слід добутку не залежать від порядку множення матриць:

Обернена матриця Редагувати

Квадратна матриця називається неособливою(невиродженою), якщо вона має єдину обернену матрицю таку, що виконується умова:

Інакше матриця називається особливою (виродженою).

Матриця порядку є невиродженою в тому і лише в тому випадку, якщо в цьому випадку є квадратна матриця того ж порядку

де  — алгебраїчне доповнення елементу у визначнику

Алгоритми швидкого перемноження матриць Редагувати

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

  • Алгоритм Штрассена (1969): Перший алгоритм швидкого множення великих матриць був розроблений Фолькером Штрассеном в 1969. В основі алгоритму лежить рекурсивне розбиття матриць на блоки 2Х2. Штрассен довів, що матриці 2Х2 можна некомутативно перемножити за допомогою семи множень, тому на кожному етапі рекурсії виконується сім множень замість восьми. В результаті асимптотична складність цього алгоритму складає . Недоліком даного методу є велика складність програмування в порівнянні зі стандартним алгоритмом, слабка чисельна стійкість і більший обсяг використовуваної пам'яті. Розроблено ряд алгоритмів на основі методу Штрассена, які покращують чисельну стійкість, швидкість по константі і інші його характеристики. Проте, в силу простоти алгоритм Штрассена залишається одним з практичних алгоритмів множення великих матриць. Штрассен також висунув наступну гіпотезу Штрассена: для як завгодно малого існує алгоритм, що при досить великих натуральних n гарантує перемножування двох матриць розміру за операцій.
  • Подальші поліпшення показника ступеня ω для швидкості матричного множення
Хронологія поліпшення оцінок показника ступеня ω для швидкості матричного множення.
  • Алгоритм Біні (1979)
  • Алгоритми Шенхаге (1981)
  • Зв'язок з теорією груп (2003)

Див. також Редагувати

Джерела Редагувати

  • Гантмахер Ф. Р. Теория матриц. — 5-е. — М: : Физматлит, 2010. — 559 с. — ISBN 5-9221-0524-8.(рос.)
  • Ланкастер П. Теория матриц. — Москва : Наука, 1973. — 280 с.(рос.)
  • Р.Хорн, Ч.Джонсон. Матричный анализ. — М: : Мир, 1989. — 653 с.(рос.)
  • Корн Г., Корн Т. Довідник по математиці. — Москва : Наука, 1978. — С. 392-394.

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

  1. Кібернетичний збірник. Нова серія. Вип. 25. Сб. статей 1983–1985 рр .: Пер. з англ. — М .: Мир, 1988 — В. Б. Алексєєв. Складність множення матриць. Огляд.
  2. Strassen, Volker, Gaussian Elimination is not Optimal, Numer. Math. 13, p. 354–356, 1969
  3. Pan V. Ya, Strassen's algorithm is not optimal — trilinear technique of aggregating uniting and canceling for constructing fast algorithms for matrix operations. — Proc. 19th Annual Symposium on Foundations of Computer Science, Ann Arbor, Mich., 1978
  4. Bini D., Capovani M., Lotti G., Romani F. — complexity for approximate matrix multiplication. — Inform. Process. Lett., 1979
  5. Schonhage A. Partial and total matrix multiplication. — SIAM J. Comput., 1981
  6. Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9:251-280, 1990.
  7. Williams, Virginia (2011), Multiplying matices in O(n2.3727 time [ 26 жовтня 2014 у Wayback Machine.]
  8. . Архів оригіналу за 6 серпня 2011. Процитовано 26 жовтня 2014. 
  9. . Архів оригіналу за 31 березня 2010. Процитовано 26 жовтня 2014. 
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Mnozhe nnya ma tric ce binarna operaciya yaka vikoristovuyuchi dvi matrici utvoryuye novu matricyu yaka nazivayetsya dob utkom ma tric Dijsni abo kompleksni chisla mnozhatsya vidpovidno do pravil elementarnoyi arifmetiki Z inshogo boku matrici ye masivami chisel tomu isnuyut rizni sposobi viznachiti dobutok matric Takim chinom zagalom termin matrichne mnozhennya oznachaye rizni sposobi peremnozhennya matric Klyuchovimi osoblivostyami bud yakogo matrichnogo mnozhennya ye kilkist ryadkiv i stovpciv v pochatkovih matricyah i pravilo yak elementi matric utvoryuyut novu matricyu Zmist 1 Viznachennya 2 Ilyustraciya 3 Motivaciya 4 Vlastivosti 5 Obernena matricya 6 Algoritmi shvidkogo peremnozhennya matric 7 Div takozh 8 Dzherela 9 PrimitkiViznachennya RedaguvatiNehaj dano dvi pryamokutni matrici A displaystyle A nbsp i B displaystyle B nbsp rozmirnosti m n displaystyle m times n nbsp i n q displaystyle n times q nbsp vidpovidno A a 11 a 12 a 1 n a 21 a 22 a 2 n a m 1 a m 2 a m n B b 11 b 12 b 1 q b 21 b 22 b 2 q b n 1 b n 2 b n q displaystyle A begin bmatrix a 11 amp a 12 amp cdots amp a 1n a 21 amp a 22 amp cdots amp a 2n vdots amp vdots amp ddots amp vdots a m1 amp a m2 amp cdots amp a mn end bmatrix B begin bmatrix b 11 amp b 12 amp cdots amp b 1q b 21 amp b 22 amp cdots amp b 2q vdots amp vdots amp ddots amp vdots b n1 amp b n2 amp cdots amp b nq end bmatrix nbsp Todi matricya C displaystyle C nbsp rozmirnistyu m q displaystyle m times q nbsp nazivayetsya yih dobutkom C c 11 c 12 c 1 q c 21 c 22 c 2 q c m 1 c m 2 c m q displaystyle C begin bmatrix c 11 amp c 12 amp cdots amp c 1q c 21 amp c 22 amp cdots amp c 2q vdots amp vdots amp ddots amp vdots c m1 amp c m2 amp cdots amp c mq end bmatrix nbsp de c i j r 1 n a i r b r j i 1 2 m j 1 2 q displaystyle c ij sum r 1 n a ir b rj left i 1 2 ldots m j 1 2 ldots q right nbsp Operaciya mnozhennya dvoh matric zdijsnenna tilki v tomu vipadku yaksho chislo stovpciv v pershomu spivmnozhniku dorivnyuye chislu ryadkiv u drugomu v comu vipadku govoryat sho forma matric uzgodzhena Zokrema mnozhennya zavzhdi zdijsnimo yaksho obidva mnozhniki kvadratni matrici odnogo i togo zh poryadku Slid zauvazhiti sho z isnuvannya dobutku A B displaystyle AB nbsp zovsim ne viplivaye isnuvannya dobutku B A displaystyle BA nbsp Ilyustraciya Redaguvati nbsp Dobutok matric AB skladayetsya z usih mozhlivih kombinacij skalyarnih dobutkiv vektor ryadkiv matrici A i vektor stovpciv matrici B Element matrici AB z indeksami i j ye skalyarnim dobutkom i go vektor ryadka matrici A i j go vektor stovpcya matrici B Ilyustraciya pravoruch demonstruye obchislennya dobutku dvoh matric A i B Vona pokazuye yak peretini v dobutku matric vidpovidayut ryadkam matrici A i stovpcyam matrici B Rozmir rezultuyuchoyi matrici zavzhdi maksimalno mozhlivij tobto dlya kozhnogo ryadka matrici A i stovpcya matrici B ye zavzhdi vidpovidnij peretin v dobutku matric Znachennya na peretinah vidmichenih kruzhechkami budut x 1 2 a 1 1 a 1 2 b 1 2 b 2 2 a 1 1 b 1 2 a 1 2 b 2 2 x 3 3 a 3 1 a 3 2 b 1 3 b 2 3 a 3 1 b 1 3 a 3 2 b 2 3 displaystyle begin aligned color Red x 1 2 amp a 1 1 a 1 2 cdot b 1 2 b 2 2 amp a 1 1 b 1 2 a 1 2 b 2 2 color Blue x 3 3 amp a 3 1 a 3 2 cdot b 1 3 b 2 3 amp a 3 1 b 1 3 a 3 2 b 2 3 end aligned nbsp U zagalnomu vipadku dobutok matric ne ye komutativnoyu operaciyeyu Primirom 1 2 3 4 3 4 matrix a b c d 4 5 matrix x 3 4 3 5 matrix displaystyle overset 3 times 4 text matrix begin bmatrix cdot amp cdot amp cdot amp cdot cdot amp cdot amp cdot amp cdot color Blue 1 amp color Blue 2 amp color Blue 3 amp color Blue 4 end bmatrix overset 4 times 5 text matrix begin bmatrix cdot amp cdot amp cdot amp color Red a amp cdot cdot amp cdot amp cdot amp color Red b amp cdot cdot amp cdot amp cdot amp color Red c amp cdot cdot amp cdot amp cdot amp color Red d amp cdot end bmatrix overset 3 times 5 text matrix begin bmatrix cdot amp cdot amp cdot amp cdot amp cdot cdot amp cdot amp cdot amp cdot amp cdot cdot amp cdot amp cdot amp x 3 4 amp cdot end bmatrix nbsp Element x 3 4 displaystyle x 3 4 nbsp dobutku matric privedenih vishe obchislyuyetsya takim chinom x 3 4 1 2 3 4 a b c d 1 a 2 b 3 c 4 d displaystyle x 3 4 color Blue 1 color Blue 2 color Blue 3 color Blue 4 cdot color Red a color Red b color Red c color Red d color Blue 1 cdot color Red a color Blue 2 cdot color Red b color Blue 3 cdot color Red c color Blue 4 cdot color Red d nbsp Persha koordinata v poznachenni matrici poznachaye ryadok druga koordinata stovpec cej poryadok vikoristovuyut yak pri indeksaciyi tak i pri poznachenni rozmiru Element x i j displaystyle x color Blue i color Red j nbsp na peretini ryadka i displaystyle i nbsp ta stovpcya j displaystyle j nbsp rezultuyuchoyi matrici ye skalyarnim dobutkom i displaystyle i nbsp go ryadka pershoyi matrici i j displaystyle j nbsp go stovpcya drugoyi matrici Ce poyasnyuye chomu shirina i visota mnozhimih matric povinni zbigatisya inakshe skalyarnij tvir ne viznacheno Motivaciya RedaguvatiOpisane pravilo matrichnogo mnozhennya prozorishe vsogo motivuyetsya vihodyachi z mnozhennya vektora na matricyu Ostannye zvichajno vvoditsya vihodyachi z togo sho pri rozkladanni vektoriv po bazisu diyu kozhnogo linijnogo operatora A daye viraz komponent vektora v Av v i j A i j v j displaystyle v i sum limits j A ij v j nbsp Tobto linijnij operator viyavlyayetsya predstavlenij matriceyu vektori vektorami stovpcyami a diya operatora na vektor matrichnim mnozhennyam vektora stovpcya zliva na matricyu operatora ce okremij vipadok matrichnogo mnozhennya koli odna z matric vektor stovpec maye rozmir 1hn Tak samo perehid do bud yakogo novogo bazisu pri zmini koordinat predstavlyayetsya povnistyu analogichnim virazom tilki v i displaystyle v i nbsp v comu vipadku vzhe ne komponenti novogo vektora v staromu bazisi a komponenti starogo vektora v novomu bazisi pri comu A i j displaystyle A ij nbsp elementi matrici perehodu do novogo bazisu Rozglyanuvshi poslidovnu diyu na vektor dvoh operatoriv spochatku A a potim B abo peretvorennya bazisu A a potim peretvorennya bazisu B dvichi zastosuvavshi formulu otrimuyemo v i j B i j k A j k v k j k B i j A j k v k k j B i j A j k v k displaystyle v i sum limits j B ij sum limits k A jk v k sum limits j sum limits k B ij A jk v k sum limits k sum limits j B ij A jk v k nbsp zvidki vidno sho kompoziciyi BA diyi linijnih operatoriv A i B abo analogichnoyi kompoziciyi peretvoren bazisu vidpovidaye matricya sho obchislyuyetsya za pravilom dobutku vidpovidnih matric B A i k j B i j A j k displaystyle BA ik sum limits j B ij A jk nbsp Viznachenij takim chinom dobutok matric viyavlyayetsya absolyutno zvichajnim i ochevidno korisnim daye prostij i universalnij sposib obchislennya kompozicij dovilnoyi kilkosti linijnih peretvoren Vlastivosti RedaguvatiSpoluchna vlastivist asociativnist A B C A B C displaystyle mathbf A mathbf BC mathbf AB mathbf C nbsp a A B a A B A a B displaystyle alpha mathbf AB alpha mathbf A mathbf B mathbf A alpha mathbf B nbsp Rozpodilna vlastivist distributivnist shodo dodavannya A B C A B A C displaystyle mathbf A mathbf B mathbf C mathbf AB mathbf AC nbsp A B C A C B C displaystyle mathbf A mathbf B mathbf C mathbf AC mathbf BC nbsp Dobutok matrici na odinichnu matricyu E displaystyle mathbf E nbsp togo zh poryadku dorivnyuye samij matrici E A A displaystyle mathbf EA mathbf A nbsp A E A displaystyle mathbf AE mathbf A nbsp Dobutok matrici na nulovu matricyu 0 displaystyle mathbf 0 nbsp tiyeyi zh rozmirnosti dorivnyuye nulovij matrici 0 A 0 displaystyle mathbf 0A mathbf 0 nbsp A 0 0 displaystyle mathbf A0 mathbf 0 nbsp Yaksho A displaystyle mathbf A nbsp i B displaystyle mathbf B nbsp kvadratni matrici odnogo i togo zh poryadku to dobutok matric maye she ryad vlastivostej Mnozhennya matric v zagalnomu vipadku ye nekomutativnim A B B A displaystyle mathbf AB neq mathbf BA nbsp Yaksho A B B A displaystyle mathbf AB mathbf BA nbsp to matrici A displaystyle mathbf A nbsp i B displaystyle mathbf B nbsp nazivayutsya perestanovochnimi abo komutuyuchimi mizh soboyu Najprostishi prikladi komutuyuchih matric bud yaka kvadratna matricya z samoyu soboyu A A A A A 2 displaystyle mathbf AA mathbf AA mathbf A 2 nbsp zvedennya matrici v kvadrat bud yaka kvadratna matricya z odinichnoyu matriceyu togo zh poryadku A E E A A displaystyle mathbf AE mathbf EA mathbf A nbsp bud yaka kvadratna matricya z nulovoyu matriceyu togo zh poryadku A 0 0 A 0 displaystyle mathbf A0 mathbf 0A mathbf 0 nbsp bud yaka nevirodzhena kvadratna matricya zi svoyeyu zvorotnoyu matriceyu A A 1 A 1 A E displaystyle mathbf AA 1 mathbf A 1 A mathbf E nbsp Viznachnik i slid dobutku ne zalezhat vid poryadku mnozhennya matric det A B det B A det A det B displaystyle det mathbf AB det mathbf BA det mathbf A cdot det mathbf B nbsp tr A B tr B A displaystyle mbox tr mathbf AB mbox tr mathbf BA nbsp Obernena matricya RedaguvatiDokladnishe Obernena matricyaKvadratna matricya A displaystyle A nbsp nazivayetsya neosoblivoyu nevirodzhenoyu yaksho vona maye yedinu obernenu matricyu A 1 displaystyle A 1 nbsp taku sho vikonuyetsya umova A A 1 A 1 A E displaystyle AA 1 A 1 A E nbsp Inakshe matricya A displaystyle A nbsp nazivayetsya osoblivoyu virodzhenoyu Matricya A a i k displaystyle A left a ik right nbsp poryadku n displaystyle n nbsp ye nevirodzhenoyu v tomu i lishe v tomu vipadku yaksho det A det a i k 0 displaystyle det A det left a ik right neq 0 nbsp v comu vipadku A 1 displaystyle A 1 nbsp ye kvadratna matricya togo zh poryadku n displaystyle n nbsp A 1 a i k 1 A k i det A displaystyle A 1 left a ik right 1 left frac A ki det A right nbsp de A i k displaystyle A ik nbsp algebrayichne dopovnennya elementu a i k displaystyle a ik nbsp u viznachniku det a i k displaystyle det left a ik right nbsp Algoritmi shvidkogo peremnozhennya matric RedaguvatiDokladnishe Algoritm peremnozhuvannya matricSkladnist obchislennya dobutku matric za viznachennyam stanovit O n 3 displaystyle O n 3 nbsp odnak isnuyut bilsh efektivni algoritmi 1 sho zastosovuyutsya dlya velikih matric Pitannya pro granichnu shvidkist mnozhennya velikih matric takozh yak i pitannya pro pobudovu najbilsh shvidkih i stijkih praktichnih algoritmiv mnozhennya velikih matric zalishayetsya odniyeyu z nevirishenih problem linijnoyi algebri Algoritm Shtrassena 1969 Pershij algoritm shvidkogo mnozhennya velikih matric buv rozroblenij Folkerom Shtrassenom 2 v 1969 V osnovi algoritmu lezhit rekursivne rozbittya matric na bloki 2H2 Shtrassen doviv sho matrici 2H2 mozhna nekomutativno peremnozhiti za dopomogoyu semi mnozhen tomu na kozhnomu etapi rekursiyi vikonuyetsya sim mnozhen zamist vosmi V rezultati asimptotichna skladnist cogo algoritmu skladaye O n log 2 7 O n 2 81 displaystyle O n log 2 7 approx O n 2 81 nbsp Nedolikom danogo metodu ye velika skladnist programuvannya v porivnyanni zi standartnim algoritmom slabka chiselna stijkist i bilshij obsyag vikoristovuvanoyi pam yati Rozrobleno ryad algoritmiv na osnovi metodu Shtrassena yaki pokrashuyut chiselnu stijkist shvidkist po konstanti i inshi jogo harakteristiki Prote v silu prostoti algoritm Shtrassena zalishayetsya odnim z praktichnih algoritmiv mnozhennya velikih matric Shtrassen takozh visunuv nastupnu gipotezu Shtrassena dlya yak zavgodno malogo e gt 0 displaystyle varepsilon gt 0 nbsp isnuye algoritm sho pri dosit velikih naturalnih n garantuye peremnozhuvannya dvoh matric rozmiru n n displaystyle n times n nbsp za O n 2 e displaystyle O n 2 varepsilon nbsp operacij Podalshi polipshennya pokaznika stupenya w dlya shvidkosti matrichnogo mnozhennya nbsp Hronologiya polipshennya ocinok pokaznika stupenya w dlya shvidkosti matrichnogo mnozhennya Nadali ocinki shvidkosti mnozhennya velikih matric bagatorazovo polipshuvalisya Odnak ci algoritmi nosili teoretichnij v osnovnomu nablizhenij harakter V silu nestijkosti algoritmiv nablizhenogo mnozhennya v danij chas voni ne vikoristovuyutsya na praktici Algoritm Pana 1978 U 1978 Pan 3 zaproponuvav svij metod mnozhennya matric skladnist yakogo sklala 8 n2 78041 Algoritm Bini 1979 U 1979 grupa italijskih uchenih na choli z Bini 4 rozrobila algoritm mnozhennya matric z vikoristannyam tenzoriv Jogo skladnist stanovit 8 n2 7799 Algoritmi Shenhage 1981 U 1981 Shenhage 5 predstaviv metod yakij pracyuye zi shvidkistyu 8 n2 695 Ocinka otrimana za dopomogoyu pidhodu nazvanogo chastkovim matrichnim mnozhennyam Piznishe jomu vdalosya otrimati ocinku 8 n2 6087 Potim Shenhage na bazi metodu pryamih sum otrimav ocinku skladnosti 8 n2 548 Romani zumiv poniziti ocinku do 8 n2 5166 a Pan do 8 n2 5161 dd Algoritm Koppersmita Vinograda 1990 U 1990 Koppersmit i Vinograd en 6 opublikuvali algoritm yakij v modifikaciyi Vilyams Vasilevskoyi 7 2011 roku peremnozhuye matrici zi shvidkistyu O n2 3727 Cej algoritm vikoristovuye ideyi shozhi z algoritmom Shtrassena Na sogodnishnij den modifikaciyi algoritmu Koppersmita Vinograda ye najbilsh asimptotichno shvidkimi Ale toj fakt sho otrimani polipshennya nikchemni dozvolyaye govoriti pro isnuvannya bar yeru Koppersmita Vinograda v asimptotichnih ocinkah shvidkosti algoritmiv Algoritm Koppersmita Vinograda efektivnij tilki na matricyah astronomichnogo rozmiru i na praktici zastosovuvatisya ne mozhe Zv yazok z teoriyeyu grup 2003 U 2003 Koh ta in rozglyanuli v svoyih robotah 8 algoritmi Shtrassena i Koppersmita Vinograda v konteksti teoriyi grup Voni pokazali sho gipoteza Shtrassena spravedliva yaksho vikonuyetsya odna z gipotez teoriyi grup 9 Div takozh RedaguvatiDobutok Adamara Dobutok Kronekera Basic Linear Algebra Subprograms Dobutok Hatri Rao Torcevij dobutokDzherela RedaguvatiGantmaher F R Teoriya matric 5 e M Fizmatlit 2010 559 s ISBN 5 9221 0524 8 ros Lankaster P Teoriya matric Moskva Nauka 1973 280 s ros R Horn Ch Dzhonson Matrichnyj analiz M Mir 1989 653 s ros Korn G Korn T Dovidnik po matematici Moskva Nauka 1978 S 392 394 Primitki Redaguvati Kibernetichnij zbirnik Nova seriya Vip 25 Sb statej 1983 1985 rr Per z angl M Mir 1988 V B Aleksyeyev Skladnist mnozhennya matric Oglyad Strassen Volker Gaussian Elimination is not Optimal Numer Math 13 p 354 356 1969 Pan V Ya Strassen s algorithm is not optimal trilinear technique of aggregating uniting and canceling for constructing fast algorithms for matrix operations Proc 19th Annual Symposium on Foundations of Computer Science Ann Arbor Mich 1978 Bini D Capovani M Lotti G Romani F O n 2 7799 displaystyle O n 2 7799 nbsp complexity for approximate matrix multiplication Inform Process Lett 1979 Schonhage A Partial and total matrix multiplication SIAM J Comput 1981 Don Coppersmith and Shmuel Winograd Matrix multiplication via arithmetic progressions Journal of Symbolic Computation 9 251 280 1990 Williams Virginia 2011 Multiplying matices in O n2 3727 time Arhivovano 26 zhovtnya 2014 u Wayback Machine Group theoretic Algorithms for Matrix Multiplication Arhiv originalu za 6 serpnya 2011 Procitovano 26 zhovtnya 2014 Toward an Optimal Algorithm for Matrix Multiplication Arhiv originalu za 31 bereznya 2010 Procitovano 26 zhovtnya 2014 Otrimano z https uk wikipedia org w index php title Mnozhennya matric amp oldid 36887293