1. Алгоритми швидкого множення матриць [ правити | правити код ]

Множення матриць - одна з основних операцій над матрицями . Матриця, що отримується в результаті операції множення, називається твором матриць.

Нехай дано дві прямокутні матриці A {\ displaystyle A} і B {\ displaystyle B} розмірності l × m {\ displaystyle l \ times m} і m × n {\ displaystyle m \ times n} відповідно:

A = [a 11 a 12 ⋯ a 1 ma 21 a 22 ⋯ a 2 m ⋮ ⋮ ⋱ ⋮ al 1 al 2 ⋯ alm], B = [b 11 b 12 ⋯ b 1 nb 21 b 22 ⋯ b 2 n ⋮ ⋮ ⋱ ⋮ bm 1 bm 2 ⋯ bmn]. {\ Displaystyle A = {\ begin {bmatrix} a_ {11} & a_ {12} & \ cdots & a_ {1m} \\ a_ {21} & a_ {22} & \ cdots & a_ {2m} \\\ vdots & \ vdots & \ ddots & \ vdots \\ a_ {l1} & a_ {l2} & \ cdots & a_ {lm} \ end {bmatrix}}, \; \; \; B = {\ begin {bmatrix} b_ {11} & b_ { 12} & \ cdots & b_ {1n} \\ b_ {21} & b_ {22} & \ cdots & b_ {2n} \\\ vdots & \ vdots & \ ddots & \ vdots \\ b_ {m1} & b_ {m2} & \ cdots & b_ {mn} \ end {bmatrix}}.}

Тоді матриця C {\ displaystyle C} розмірністю l × n {\ displaystyle l \ times n} :

C = [c 11 c 12 ⋯ c 1 nc 21 c 22 ⋯ c 2 n ⋮ ⋮ ⋱ ⋮ cl 1 cl 2 ⋯ cln], {\ displaystyle C = {\ begin {bmatrix} c_ {11} & c_ {12} & \ cdots & c_ {1n} \\ c_ {21} & c_ {22} & \ cdots & c_ {2n} \\\ vdots & \ vdots & \ ddots & \ vdots \\ c_ {l1} & c_ {l2} & \ cdots & c_ {ln} \ end {bmatrix}},}

в якій:

c i j = Σ r = 1 m a i r b r j (i = 1, 2, ... l; j = 1, 2, ... n). {\ Displaystyle c_ {ij} = \ sum _ {r = 1} ^ {m} a_ {ir} b_ {rj} \; \; \; \ left (i = 1,2, \ ldots l; \; j = 1,2, \ ldots n \ right).}

називається їх твором.

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

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

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

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

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}} & = (a_ {1,1}, a_ {1,2}) \ cdot (b_ {1,2}, b_ {2,2}) \\ & = a_ {1,1} b_ {1,2} + a_ {1,2} b_ {2,2} \\ {\ color {Blue} x_ {3,3}} & = (a_ {3,1 }, a_ {3,2}) \ cdot (b_ {1,3}, b_ {2,3}) \\ & = a_ {3,1} b_ {1,3} + a_ {3,2} b_ {2,3} \ end {aligned}}}

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

[⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 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 & \ cdot & \ cdot & \ cdot \\\ cdot & \ cdot & \ cdot & \ cdot \\\ color {Blue} 1 & \ color {Blue} 2 & \ color {Blue} 3 & \ color {Blue} 4 \\\ end {bmatrix }}} {\ overset {4 \ times 5 {\ text {matrix}}} {\ begin {bmatrix} \ cdot & \ cdot & \ cdot & \ color {Red} a & \ cdot \\\ cdot & \ cdot & \ cdot & \ color {Red} b & \ cdot \\\ cdot & \ cdot & \ cdot & \ color {Red} c & \ cdot \\\ cdot & \ cdot & \ cdot & \ color {Red} d & \ cdot \ \\ end {bmatrix}}} = {\ overset {3 \ times 5 {\ text {matrix}}} {\ begin {bmatrix} \ cdot & \ cdot & \ cdot & \ cdot & \ cdot \\\ cdot & \ cdot & \ cdot & \ cdot & \ cdot \\\ cdot & \ cdot & \ cdot & x_ {3,4} & \ cdot \\\ end {bmatrix}}}}

Елемент x 3, 4 {\ displaystyle x_ {3,4}} твори матриць, наведених вище, обчислюється таким чином

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}}

Перша координата в позначенні матриці позначає рядок, друга координата - стовпець; цей порядок використовують як при індексації, так і при позначенні розміру. Елемент x i j {\ displaystyle x _ {{\ color {Blue} i} {\ color {Red} j}}} на перетині рядка i {\ displaystyle i} і стовпці j {\ displaystyle j} результуючої матриці є скалярним твором i {\ displaystyle i} го рядка першої матриці і j {\ displaystyle j} -го стовпця другого матриці. Це пояснює чому ширина і висота множимо матриць повинні збігатися: в іншому випадку скалярний твір не визначено.

Побачити причини описаного правила матричного множення найлегше, розглянувши множення вектора на матрицю.

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

v i '= Σ j A i j v j {\ displaystyle v' _ {i} = \ sum \ limits _ {j} A_ {ij} v_ {j}}

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

(Так само перехід до будь-якого нового базису при зміні координат представляється повністю аналогічним виразом, тільки v i '{\ displaystyle v' _ {i}} в цьому випадку вже не компоненти нового вектора в старому базисі, а компоненти старого вектора в новому базисі; при цьому A i j {\ displaystyle A_ {ij}} - елементи матриці переходу до нового базису).

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

vi "= Σ j B ij Σ k A jkvk = Σ j Σ k B ij A jkvk = Σ k Σ j (B ij A jk) 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},}

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

(B A) i k = Σ j B i j A j k. {\ Displaystyle (BA) _ {ik} = \ sum \ limits _ {j} B_ {ij} A_ {jk}.}

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

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

A (B C) = (A B) C; {\ Displaystyle \ mathbf {A} (\ mathbf {BC}) = (\ mathbf {AB}) \ mathbf {C};} α (A B) = (α A) B = A (α B). {\ Displaystyle \ alpha (\ mathbf {AB}) = (\ alpha \ mathbf {A}) \ mathbf {B} = \ mathbf {A} (\ alpha \ mathbf {B}).}

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

A (B + C) = A B + A C; {\ Displaystyle \ mathbf {A} (\ mathbf {B} + \ mathbf {C}) = \ mathbf {AB} + \ mathbf {AC};} (A + B) C = A C + B C. {\ Displaystyle (\ mathbf {A} + \ mathbf {B}) \ mathbf {C} = \ mathbf {AC} + \ mathbf {BC}.} .

Твір матриці на одиничну матрицю E {\ displaystyle \ mathbf {E}} відповідного порядку дорівнює самій матриці:

E A = A; {\ Displaystyle \ mathbf {EA} = \ mathbf {A};} A E = A. {\ Displaystyle \ mathbf {AE} = \ mathbf {A}.}

Твір матриці на нульову матрицю 0 {\ displaystyle \ mathbf {0}} підходящої розмірності одно нульовий матриці:

0 A = 0; {\ Displaystyle \ mathbf {0A} = \ mathbf {0};} A 0 = 0. {\ Displaystyle \ mathbf {A0} = \ mathbf {0}.}

Якщо A {\ displaystyle \ mathbf {A}} і B {\ displaystyle \ mathbf {B}} - квадратні матриці одного і того ж порядку, то твір матриць має ще ряд властивостей.

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

A B ≠ B A. {\ Displaystyle \ mathbf {AB} \ neq \ mathbf {BA}.}

Якщо A B = B A {\ displaystyle \ mathbf {AB} = \ mathbf {BA}} , То матриці A {\ displaystyle \ mathbf {A}} і B {\ displaystyle \ mathbf {B}} називаються коммутирующими між собою.

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

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

det (A B) = det (B A) = det A ⋅ det B; {\ Displaystyle \ det (\ mathbf {AB}) = \ det (\ mathbf {BA}) = \ det \ mathbf {A} \ cdot \ det \ mathbf {B};} tr (A B) = tr (B A). {\ Displaystyle {\ mbox {tr}} (\ mathbf {AB}) = {\ mbox {tr}} (\ mathbf {BA}).}

квадратна матриця A {\ displaystyle A} називається неособенной (невироджених) , Якщо вона має єдину зворотний матрицю A - 1 {\ displaystyle A ^ {- 1}} таку, що виконується умова:

A A - 1 = A - 1 A = E. {\ Displaystyle AA ^ {- 1} = A ^ {- 1} A = E.}

В іншому випадку матриця A {\ displaystyle A} називається особливою (виродженої) .

Матриця A = [a i k] {\ displaystyle A = \ left [a_ {ik} \ right]} порядку n {\ displaystyle n} є невироджених в тому і тільки в тому випадку, якщо det A = det [a i k] ≠ 0; {\ Displaystyle \ det A = \ det \ left [a_ {ik} \ right] \ neq 0;} в цьому випадку A - 1 {\ displaystyle A ^ {- 1}} є квадратна матриця того ж порядку n: {\ displaystyle n}

A - 1 = [aik] - 1 = [A ki det A], {\ displaystyle A ^ {- 1} = \ left [a_ {ik} \ right] ^ {- 1} = \ left [{\ frac { A_ {ki}} {\ det A}} \ right],}

де A i k {\ displaystyle A_ {ik}} - алгебраїчне доповнення елемента a i k {\ displaystyle a_ {ik}} определителе det [a i k]. {\ Displaystyle \ det \ left [a_ {ik} \ right].}

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

Складність обчислення добутку матриць за визначенням становить O (n 3) {\ displaystyle \ O (n ^ {3})} , Однак існують більш ефективні алгоритми [1] , Що застосовуються для великих матриць. Питання про граничній швидкості множення великих матриць, також як і питання про побудову найбільш швидких і стійких практичних алгоритмів множення великих матриць залишається однією з невирішених проблем лінійної алгебри .

Перший алгоритм швидкого множення великих матриць був розроблений Фолькером Штрассені [2] в 1969. В основі алгоритму лежить рекурсивне розбиття матриць на блоки 2Х2. Штрассен довів, що матриці 2Х2 можна некомутативними перемножити за допомогою семи умножений, тому на кожному етапі рекурсії виконується сім множень замість восьми. В результаті асимптотична складність цього алгоритму складає O (n log 2 ⁡ 7) ≈ O (n 2.81) {\ displaystyle O (n ^ {\ log _ {2} 7}) \ approx O (n ^ {2.81})} . Недоліком даного методу є велика складність програмування в порівнянні зі стандартним алгоритмом, слабка чисельна стійкість і більший обсяг використовуваної пам'яті. Розроблено ряд алгоритмів на основі методу Штрассена, які покращують чисельну стійкість, швидкість по константі і інші його характеристики. Проте, в силу простоти алгоритм Штрассена залишається одним з практичних алгоритмів множення великих матриць. Штрассен також висунув наступну гіпотезу Штрассена : Для як завгодно малого ε> 0 {\ displaystyle \ varepsilon> 0} існує алгоритм, при досить великих натуральних n гарантує множення двох матриць розміру n × n {\ displaystyle n \ times n} за O (n 2 + ε) {\ displaystyle O (n ^ {2 + \ varepsilon})} операцій.

• Подальші поліпшення показника ступеня ω для швидкості матричного множення

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

• Алгоритм Пана (1978)

У 1978 Пан [3] запропонував свій метод множення матриць, складність якого склала Θ (n2.78041).

• Алгоритм Біні (1979)

У 1979 група італійських учених на чолі з Біні [4] розробила алгоритм множення матриць з використанням тензорів. Його складність становить Θ (n2.7799).

• Алгоритми Шёнхаге (1981)

У 1981 Шёнхаге [5] представив метод, який працює зі швидкістю Θ (n2.695). Оцінка отримана за допомогою підходу, названого частковим матричних множенням. Пізніше йому вдалося отримати оцінку Θ (n2.6087). Потім Шёнхаге на базі методу прямих сум отримав оцінку складності Θ (n2.548). Романі зумів знизити оцінку до Θ (n2.5166), а Пан - до Θ (n2.5161). У 1990 Копперсміт і Виноград [6] опублікували алгоритм, який в модифікації Вільямс Василевської [7] 2011 року примножує матриці зі швидкістю O (n2.3727). Цей алгоритм використовує ідеї, схожі з алгоритмом Штрассена. На сьогоднішній день модифікації алгоритму Копперсміта-Винограду є найбільш асимптотично швидкими. Але той факт, що отримані поліпшення незначні, дозволяє говорити про існування «бар'єру Копперсміта-Винограду» в асимптотичних оцінках швидкості алгоритмів. Алгоритм Копперсміта-Винограду ефективний тільки на матрицях астрономічного розміру і на практиці застосовуватися не може.

• Зв'язок з теорією груп (2003)

У 2003 Кох та ін. Розглянули в своїх роботах [8] алгоритми Штрассена і Копперсміта-Винограду в контексті теорії груп. Вони показали, що гіпотеза Штрассена справедлива, якщо виконується одна з гіпотез теорії груп [9] .

Квадратні матриці можна багаторазово множити самі на себе так само, як звичайні числа, так як у них однакове число рядків і стовпців. Таке послідовне множення можна назвати зведенням матриці в ступінь - це буде окремий випадок звичайного множення декількох матриць. У прямокутних матриць число рядків і стовпців різний, тому їх ніколи не можна підносити до степеня. Матриця A розмірності n × n, зведена в ступінь, визначається формулою

A k = A A ⋯ A ⏟ k {\ displaystyle \ mathbf {A} ^ {k} = \ underbrace {\ mathbf {A} \ mathbf {A} \ cdots \ mathbf {A}} _ {k}}

і має такі властивості (λ - деякий скаляр):

Нульова ступінь:

A 0 = E {\ displaystyle \ mathbf {A} ^ {0} = \ mathbf {E}}

де E - одинична матриця . Це аналог того факту, що нульова ступінь будь-якого числа дорівнює одиниці.

Множення на скаляр:

(Λ A) k = λ k A k {\ displaystyle (\ lambda \ mathbf {A}) ^ {k} = \ lambda ^ {k} \ mathbf {A} ^ {k}}

визначник:

det (A k) = det (A) k {\ displaystyle \ det (\ mathbf {A} ^ {k}) = \ det (\ mathbf {A}) ^ {k}}

Наївний спосіб обчислення ступеня матриці - це множити k раз матрицю A на результат попереднього множення, починаючи з одиничної матриці, як це часто роблять для скалярів. для діагоналізіруемих матриць існує кращий метод, заснований на використанні спектрального розкладання матриці A. Ще один метод, заснований на теоремі Гамільтона - Келі , Будує більш ефективне вираження для A k, в якому в необхідний ступінь зводиться скаляр, а не вся матриця.

Особливий випадок становлять діагональні матриці . Так як твір діагональних матриць зводиться до множення відповідних діагональних елементів, то k -а ступінь діагональної матриці A складається з елементів, зведених в необхідний ступінь:

A k = (a 11 0 ⋯ 0 0 a 22 ⋯ 0 ⋮ ⋮ ⋱ ⋮ 0 0 ⋯ a n n) k = (a 11 k 0 ⋯ 0 0 a 22 k ⋯ 0 ⋮ ⋮ ⋱ ⋮ 0 0 ⋯ a n n k). {\ Displaystyle \ mathbf {A} ^ {k} = {\ begin {pmatrix} a_ {11} & 0 & \ cdots & 0 \\ 0 & a_ {22} & \ cdots & 0 \\\ vdots & \ vdots & \ ddots & \ vdots \\ 0 & 0 & \ cdots & a_ {nn} \ end {pmatrix}} ^ {k} = {\ begin {pmatrix} a_ {11} ^ {k} & 0 & \ cdots & 0 \\ 0 & a_ {22} ^ {k} & \ cdots & 0 \\\ vdots & \ vdots & \ ddots & \ vdots \\ 0 & 0 & \ cdots & a_ {nn} ^ {k} \ end {pmatrix}}.}

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

Використовуючи множення матриць і зведення матриць в ступінь, можна визначити інші операції над матрицями. наприклад, матрична експонента може бути визначена через статечної ряд , матричний логарифм [En] - як зворотна до матричної експоненті функція і так далі.

• Корн Г., Корн Т. Алгебра матриць і матричне числення // Довідник з математики. - 4-е видання. - М: Наука, 1978. - С. 392-394.

1. ↑ Кібернетичний збірник. Нова серія. Вип. 25. Зб. статей 1983 - 1985 рр .: Пер. з англ. - М .: Світ, 1988 - В.Б. Алексс. Складність множення матриць. Огляд.
2. ↑ Strassen V. Gaussian Elimination is not Optimal // Numer. Math - Springer Science + Business Media , 1969. - Vol. 13, Iss. 4. - P. 354-356. - ISSN 0029-599X ; 0945-3245 - doi: 10.1007 / BF02165411
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. - O (n 2.7799) {\ displaystyle O (n ^ {2.7799})} 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
8. ↑ Group-theoretic Algorithms for Matrix Multiplication
9. ↑ Toward an Optimal Algorithm for Matrix Multiplication