Множе́ння ма́триць — це бінарна операція, яка використовуючи дві матриці, утворює нову матрицю, яка називається доб́утком ма́триць. Дійсні або комплексні числа множаться відповідно до правил (елементарної арифметики).
Схема праворуч демонструє обчислення добутку двох матриць A і B. Вона показує як перетини в добутку матриць відповідають рядкам матриці A і стовпцям матриці B. Значення на перетинах відмічених кружеяками будуть:
Окрім загально відомого, існують і інші види множення матриць. Ключовими особливостями будь-якого матричного множення є: кількість рядків і стовпців, в початкових матрицях, і правило, як елементи матриць утворюють нову матрицю.
Визначення
Нехай дано дві прямокутні матриці розміру та розміру :
Тоді матриця розмірністю називається їх добутком:
де:
Операція множення двох матриць здійсненна тільки в тому випадку, якщо число стовпців в першому співмножнику дорівнює числу рядків у другому; в цьому випадку говорять, що форма матриць узгоджена. Зокрема, множення завжди здійснимо, якщо обидва множники — квадратні матриці одного і того ж порядку.
Слід зауважити, що з існування добутку зовсім не випливає існування добутку
Приклад
Добуток матриць AB складається з усіх можливих комбінацій скалярних добутків вектор-рядків матриці A і вектор-стовпців матриці B. Елемент матриці AB з індексами i, j є скалярним добутком i-го вектор-рядка матриці A і j-го вектор-стовпця матриці B.
У загальному випадку, добуток матриць не є комутативною операцією. Приміром:
Елемент добутку матриць приведених вище, обчислюється таким чином
Перша координата в позначенні матриці позначає рядок, друга координата — стовпець; цей порядок використовують як при індексації, так і при позначенні розміру. Елемент на перетині рядка та стовпця результуючої матриці є скалярним добутком -го рядка першої матриці і -го стовпця другої матриці. Це пояснює чому ширина і висота множимих матриць повинні збігатися: інакше скалярний добуток не визначено.
Мотивація
Описане правило матричного множення прозоріше всього мотивується, виходячи з множення вектора на матрицю.
Останнє звичайно вводиться виходячи з того, що при розкладанні векторів по базису дію (кожного) лінійного оператора A дає вираз компонент вектора v' = Av:
Тобто лінійний оператор виявляється представлений матрицею, вектори — векторами-стовпцями, а дія оператора на вектор — матричним множенням вектора-стовпця зліва на матрицю оператора (це окремий випадок матричного множення, коли одна з матриць — вектор-стовпець — має розмір 1хn).
(Так само перехід до будь-якого нового базису при зміні координат представляється повністю аналогічним виразом, тільки в цьому випадку вже не компоненти нового вектора в старому базисі, а компоненти старого вектора в новому базисі; при цьому — елементи матриці переходу до нового базису).
Розглянувши послідовну дію на вектор двох операторів: спочатку A, а потім B (або перетворення базису A, а потім перетворення базису B), двічі застосувавши формулу, отримуємо:
звідки видно, що композиції BA дії лінійних операторів A і B (або аналогічної композиції перетворень базису) відповідає матриця, що обчислюється за правилом добутку відповідних матриць:
Визначений таким чином добуток матриць виявляється абсолютно звичайним і очевидно корисним (дає простий і універсальний спосіб обчислення композицій довільної кількості лінійних перетворень).
Властивості
Сполучна властивість, асоціативність:
Розподільна властивість, дистрибутивність щодо додавання:
- .
Добуток матриці на одиничну матрицю того ж порядку дорівнює самій матриці:
Добуток матриці на нульову матрицю тієї ж розмірності дорівнює нульовий матриці:
Якщо і — квадратні матриці одного і того ж порядку, то добуток матриць має ще ряд властивостей.
Множення матриць в загальному випадку є некомутативним:
Якщо , то матриці і називаються перестановочними або комутуючими між собою.
Найпростіші приклади комутуючих матриць:
- будь-яка квадратна матриця — з самою собою: (зведення матриці в квадрат);
- будь-яка квадратна матриця — з одиничною матрицею того ж порядку: ;
- будь-яка квадратна матриця — з нульовою матрицею того ж порядку: ;
- будь-яка невироджена квадратна матриця — зі своєю зворотною матрицею: .
Визначник і слід добутку не залежать від порядку множення матриць:
Обернена матриця
Квадратна матриця називається неособливою(невиродженою), якщо вона має єдину обернену матрицю таку, що виконується умова:
Інакше матриця називається особливою (виродженою).
Матриця порядку є невиродженою в тому і лише в тому випадку, якщо в цьому випадку є квадратна матриця того ж порядку
де — алгебраїчне доповнення елементу у визначнику
Алгоритми швидкого перемноження матриць
Складність обчислення добутку матриць за визначенням становить , однак існують більш ефективні алгоритми, що застосовуються для великих матриць. Питання про граничну швидкість множення великих матриць, також як і питання про побудову найбільш швидких і стійких практичних алгоритмів множення великих матриць залишається однією з невирішених проблем лінійної алгебри.
- Алгоритм Штрассена (1969): Перший алгоритм швидкого множення великих матриць був розроблений Фолькером Штрассеном в 1969. В основі алгоритму лежить рекурсивне розбиття матриць на блоки 2Х2. Штрассен довів, що матриці 2Х2 можна некомутативно перемножити за допомогою семи множень, тому на кожному етапі рекурсії виконується сім множень замість восьми. В результаті асимптотична складність цього алгоритму складає . Недоліком даного методу є велика складність програмування в порівнянні зі стандартним алгоритмом, слабка чисельна стійкість і більший обсяг використовуваної пам'яті. Розроблено ряд алгоритмів на основі методу Штрассена, які покращують чисельну стійкість, швидкість по константі і інші його характеристики. Проте, в силу простоти алгоритм Штрассена залишається одним з практичних алгоритмів множення великих матриць. Штрассен також висунув наступну гіпотезу Штрассена: для як завгодно малого існує алгоритм, що при досить великих натуральних n гарантує перемножування двох матриць розміру за операцій.
- Подальші поліпшення показника ступеня ω для швидкості матричного множення
- Надалі оцінки швидкості множення великих матриць багаторазово поліпшувалися. Однак ці алгоритми носили теоретичний, в основному наближений характер. В силу нестійкості алгоритмів наближеного множення в даний час вони не використовуються на практиці.
- Алгоритм Пана (1978)
- У 1978 Пан запропонував свій метод множення матриць, складність якого склала Θ(n2.78041).
- Алгоритм Біні (1979)
- У 1979 група італійських учених на чолі з Біні розробила алгоритм множення матриць з використанням тензорів. Його складність становить Θ(n2.7799).
- Алгоритми Шенхаге (1981)
- У 1981 Шенхаге представив метод, який працює зі швидкістю Θ(n2.695). Оцінка отримана за допомогою підходу, названого частковим матричним множенням. Пізніше йому вдалося отримати оцінку Θ(n2.6087).
- Потім Шенхаге на базі методу прямих сум отримав оцінку складності Θ(n2.548). Романі зумів понизити оцінку до Θ(n2.5166), а Пан — до Θ(n2.5161).
- У 1990 Копперсміт і [en] опублікували алгоритм, який в модифікації Вильямс Василевської 2011 року перемножує матриці зі швидкістю O(n2.3727). Цей алгоритм використовує ідеї, схожі з алгоритмом Штрассена. На сьогоднішній день модифікації алгоритму Копперсміта-Винограда є найбільш асимптотично швидкими. Але той факт, що отримані поліпшення нікчемні, дозволяє говорити про існування «бар'єру Копперсміта-Винограда» в асимптотичних оцінках швидкості алгоритмів. Алгоритм Копперсміта-Винограда ефективний тільки на матрицях астрономічного розміру і на практиці застосовуватися не може.
- Зв'язок з теорією груп (2003)
- У 2003 Кох та ін. розглянули в своїх роботах алгоритми Штрассена і Копперсміта-Винограда в контексті теорії груп. Вони показали, що гіпотеза Штрассена справедлива, якщо виконується одна з гіпотез теорії груп.
Інші види множення матриць
Джерела
- Гантмахер Ф. Р. Теория матриц. — 5-е. — М: : Физматлит, 2010. — 559 с. — .(рос.)
- Теория матриц. — 2. — Москва : Наука, 1982. — 272 с.(рос.)
- , . Матричный анализ. — М: : Мир, 1989. — 653 с.(рос.)
- , Справочник по математике для научных работников и инженеров. — Москва : Наука, 1973. — 832 с.(рос.)
Примітки
- Кібернетичний збірник. Нова серія. Вип. 25. Сб. статей 1983–1985 рр .: Пер. з англ. — М .: Мир, 1988 — В. Б. Алексєєв. Складність множення матриць. Огляд.
- 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. — 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 [ 26 жовтня 2014 у Wayback Machine.]
- (PDF). Архів оригіналу (PDF) за 6 серпня 2011. Процитовано 26 жовтня 2014.
- (PDF). Архів оригіналу (PDF) за 31 березня 2010. Процитовано 26 жовтня 2014.
Посилання
- Матричний калькулятор
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
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 Shema pravoruch demonstruye obchislennya dobutku dvoh matric A i B Vona pokazuye yak peretini v dobutku matric vidpovidayut ryadkam matrici A i stovpcyam matrici B Znachennya na peretinah vidmichenih kruzheyakami budut x1 2 a1 1 a1 2 b1 2 b2 2 a1 1b1 2 a1 2b2 2x3 3 a3 1 a3 2 b1 3 b2 3 a3 1b1 3 a3 2b2 3 displaystyle begin aligned color Red x 1 2 amp color Olive a 1 1 a 1 2 cdot color Green b 1 2 b 2 2 a 1 1 b 1 2 a 1 2 b 2 2 color Blue x 3 3 amp color Olive a 3 1 a 3 2 cdot color Green b 1 3 b 2 3 a 3 1 b 1 3 a 3 2 b 2 3 end aligned Okrim zagalno vidomogo isnuyut i inshi vidi mnozhennya matric Klyuchovimi osoblivostyami bud yakogo matrichnogo mnozhennya ye kilkist ryadkiv i stovpciv v pochatkovih matricyah i pravilo yak elementi matric utvoryuyut novu matricyu ViznachennyaSumisnist matric dlya mnozhennya Rm n Rn p Rm p displaystyle R m times n times R n times p to R m times p Nehaj dano dvi pryamokutni matrici A displaystyle mathbf A rozmiru m n displaystyle m times n ta B displaystyle mathbf B rozmiru n p displaystyle n times p A a11a12 a1na21a22 a2n am1am2 amn B b11b12 b1pb21b22 b2p bn1bn2 bnp displaystyle mathbf 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 mathbf B begin bmatrix b 11 amp b 12 amp cdots amp b 1p b 21 amp b 22 amp cdots amp b 2p vdots amp vdots amp ddots amp vdots b n1 amp b n2 amp cdots amp b np end bmatrix Mnozhennya i displaystyle i go ryadka na k displaystyle k tij stovpec dlya obchislennya elementa cik displaystyle c ik Todi matricya C displaystyle mathbf C rozmirnistyu m p displaystyle m times p nazivayetsya yih dobutkom C c11c12 c1pc21c22 c2p cm1cm2 cmp displaystyle mathbf C begin bmatrix c 11 amp c 12 amp cdots amp c 1p c 21 amp c 22 amp cdots amp c 2p vdots amp vdots amp ddots amp vdots c m1 amp c m2 amp cdots amp c mp end bmatrix de cik j 1naijbjk i 1 2 m k 1 2 p displaystyle c ik sum j 1 n a ij b jk left i 1 2 ldots m k 1 2 ldots p right 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 AB displaystyle AB zovsim ne viplivaye isnuvannya dobutku BA displaystyle BA PrikladMnozhennya ryadka na stovpecMnozhennya stovpcya na ryadok 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 U zagalnomu vipadku dobutok matric ne ye komutativnoyu operaciyeyu Primirom 1234 3 4 matrix a b c d 4 5 matrix x3 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 Element x3 4 displaystyle x 3 4 dobutku matric privedenih vishe obchislyuyetsya takim chinom x3 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 Persha koordinata v poznachenni matrici poznachaye ryadok druga koordinata stovpec cej poryadok vikoristovuyut yak pri indeksaciyi tak i pri poznachenni rozmiru Element xij displaystyle x color Blue i color Red j na peretini ryadka i displaystyle i ta stovpcya j displaystyle j rezultuyuchoyi matrici ye skalyarnim dobutkom i displaystyle i go ryadka pershoyi matrici i j displaystyle j go stovpcya drugoyi matrici Ce poyasnyuye chomu shirina i visota mnozhimih matric povinni zbigatisya inakshe skalyarnij dobutok ne viznacheno MotivaciyaMnozhennya matrici na stovpecMnozhennya ryadka na matricyu Opisane 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 vi jAijvj displaystyle v i sum limits j A ij v j 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 vi displaystyle v i v comu vipadku vzhe ne komponenti novogo vektora v staromu bazisi a komponenti starogo vektora v novomu bazisi pri comu Aij displaystyle A ij 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 vi jBij kAjkvk j kBijAjkvk k j BijAjk vk 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 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 BA ik jBijAjk displaystyle BA ik sum limits j B ij A jk Viznachenij takim chinom dobutok matric viyavlyayetsya absolyutno zvichajnim i ochevidno korisnim daye prostij i universalnij sposib obchislennya kompozicij dovilnoyi kilkosti linijnih peretvoren VlastivostiSpoluchna vlastivist asociativnist A BC AB C displaystyle mathbf A mathbf BC mathbf AB mathbf C a AB aA B A aB displaystyle alpha mathbf AB alpha mathbf A mathbf B mathbf A alpha mathbf B Rozpodilna vlastivist distributivnist shodo dodavannya A B C AB AC displaystyle mathbf A mathbf B mathbf C mathbf AB mathbf AC A B C AC BC displaystyle mathbf A mathbf B mathbf C mathbf AC mathbf BC Dobutok matrici na odinichnu matricyu E displaystyle mathbf E togo zh poryadku dorivnyuye samij matrici EA A displaystyle mathbf EA mathbf A AE A displaystyle mathbf AE mathbf A Dobutok matrici na nulovu matricyu 0 displaystyle mathbf 0 tiyeyi zh rozmirnosti dorivnyuye nulovij matrici 0A 0 displaystyle mathbf 0A mathbf 0 A0 0 displaystyle mathbf A0 mathbf 0 Yaksho A displaystyle mathbf A i B displaystyle mathbf B kvadratni matrici odnogo i togo zh poryadku to dobutok matric maye she ryad vlastivostej Mnozhennya matric v zagalnomu vipadku ye nekomutativnim AB BA displaystyle mathbf AB neq mathbf BA Yaksho AB BA displaystyle mathbf AB mathbf BA to matrici A displaystyle mathbf A i B displaystyle mathbf B nazivayutsya perestanovochnimi abo komutuyuchimi mizh soboyu Najprostishi prikladi komutuyuchih matric bud yaka kvadratna matricya z samoyu soboyu AA AA A2 displaystyle mathbf AA mathbf AA mathbf A 2 zvedennya matrici v kvadrat bud yaka kvadratna matricya z odinichnoyu matriceyu togo zh poryadku AE EA A displaystyle mathbf AE mathbf EA mathbf A bud yaka kvadratna matricya z nulovoyu matriceyu togo zh poryadku A0 0A 0 displaystyle mathbf A0 mathbf 0A mathbf 0 bud yaka nevirodzhena kvadratna matricya zi svoyeyu zvorotnoyu matriceyu AA 1 A 1A E displaystyle mathbf AA 1 mathbf A 1 A mathbf E Viznachnik i slid dobutku ne zalezhat vid poryadku mnozhennya matric det AB det BA detA detB displaystyle det mathbf AB det mathbf BA det mathbf A cdot det mathbf B tr AB tr BA displaystyle mbox tr mathbf AB mbox tr mathbf BA Obernena matricyaDokladnishe Obernena matricya Kvadratna matricya A displaystyle A nazivayetsya neosoblivoyu nevirodzhenoyu yaksho vona maye yedinu obernenu matricyu A 1 displaystyle A 1 taku sho vikonuyetsya umova AA 1 A 1A E displaystyle AA 1 A 1 A E Inakshe matricya A displaystyle A nazivayetsya osoblivoyu virodzhenoyu Matricya A aik displaystyle A left a ik right poryadku n displaystyle n ye nevirodzhenoyu v tomu i lishe v tomu vipadku yaksho detA det aik 0 displaystyle det A det left a ik right neq 0 v comu vipadku A 1 displaystyle A 1 ye kvadratna matricya togo zh poryadku n displaystyle n A 1 aik 1 AkidetA displaystyle A 1 left a ik right 1 left frac A ki det A right de Aik displaystyle A ik algebrayichne dopovnennya elementu aik displaystyle a ik u viznachniku det aik displaystyle det left a ik right Algoritmi shvidkogo peremnozhennya matricDokladnishe Algoritm peremnozhuvannya matric Skladnist obchislennya dobutku matric za viznachennyam stanovit O n3 displaystyle O n 3 odnak isnuyut bilsh efektivni algoritmi 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 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 nlog2 7 O n2 81 displaystyle O n log 2 7 approx O n 2 81 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 isnuye algoritm sho pri dosit velikih naturalnih n garantuye peremnozhuvannya dvoh matric rozmiru n n displaystyle n times n za O n2 e displaystyle O n 2 varepsilon operacij Podalshi polipshennya pokaznika stupenya w dlya shvidkosti matrichnogo mnozhennyaHronologiya 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 zaproponuvav svij metod mnozhennya matric skladnist yakogo sklala 8 n2 78041 Algoritm Bini 1979 U 1979 grupa italijskih uchenih na choli z Bini rozrobila algoritm mnozhennya matric z vikoristannyam tenzoriv Jogo skladnist stanovit 8 n2 7799 Algoritmi Shenhage 1981 U 1981 Shenhage 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 en opublikuvali algoritm yakij v modifikaciyi Vilyams Vasilevskoyi 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 algoritmi Shtrassena i Koppersmita Vinograda v konteksti teoriyi grup Voni pokazali sho gipoteza Shtrassena spravedliva yaksho vikonuyetsya odna z gipotez teoriyi grup Inshi vidi mnozhennya matricDobutok Adamara Dobutok Kronekera Dobutok Hatri Rao Torcevij dobutokDzherelaGantmaher F R Teoriya matric 5 e M Fizmatlit 2010 559 s ISBN 5 9221 0524 8 ros Teoriya matric 2 Moskva Nauka 1982 272 s ros Matrichnyj analiz M Mir 1989 653 s ros Spravochnik po matematike dlya nauchnyh rabotnikov i inzhenerov Moskva Nauka 1973 832 s ros PrimitkiKibernetichnij 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 n2 7799 displaystyle O n 2 7799 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 26 zhovtnya 2014 u Wayback Machine PDF Arhiv originalu PDF za 6 serpnya 2011 Procitovano 26 zhovtnya 2014 PDF Arhiv originalu PDF za 31 bereznya 2010 Procitovano 26 zhovtnya 2014 PosilannyaMatrichnij kalkulyator