Умножение на матрици

В математиката, умножение на матрици е бинарна операция, при която от две матрици се изчислява нова матрица. Число от реалните или комплексни числа може да бъде умножено според елементарната аритметика. От друга страна, матриците са масиви от числа, така че не съществува един-единствен начин да се дефинира „умножението“ на матрици. Затова терминът „умножение на матрици“ се отнася до различни начини за умножение на матрици. Основните особености на което и да е умножение на матрици включва: броят на редовете и колоните на изходните матрици (наричат се „размер“, „ред“ или „измерение“), и упоменават как клетките на матрицата генерират новата матрица.

Както векторите, матрици с какъвто и да е размер могат да бъдат умножени по скалари, което се свежда до умножаване на всяка една от клетките по едно и също число. Подобно на определението за добавяне или изваждане на матрици, се прави и умножението на две матрици с еднакъв размер на съответните клетки и резултатът се нарича произведение на Адамар. Другият начин е да се получи произведение на Крокенер от две матрици, за да се получи матрица с блочна форма.

Могат да бъдат изведени още много определения. Най-полезната дефиниция може да бъде продиктувана от линейно уравнение и линейна трансформация на вектори, които имат приложение в математиката, физиката, и инженерството. Това определение често се нарича матрично произведение.^[1][2] С други думи, ако A е n × m матрица и B е m × p матрица, тяхното матрично произведение AB еn × p матрица, в която m клетките по редовете A се умножават с m клетките по колоните B.

Тази дефиниция не е комутативна, въпреки че запазва своята асоциативност и дистрибутивност при събирането на матричните клетки. Единичният елемент на матричното произведение (аналогично на умножаване на числа по едно), и квадратна матрица могат да имат обратима матрица (аналогично на реципрочна стойност на число). Последствие от матричното произведение е детерминантна мултипликативност. Получаването на матрично произведение е важна операция в линейните трансформации, матрична група и теорията за групова репрезентация и редуцибилната репрезентация.

Изчисляването на матрични произведения е основна операция в много числови алгоритмии има вероятност да е времеотнемаща, което я прави един от най-изучаваните проблеми в цифровите изчисления. Измислени са различни алгоритми за изчисляване на C = AB, особено за големи матрици.

Тази статия спазва следните конвенции: матриците са представени от главни букви с удебелен шрифт, например A, вектори с малки букви с удебелен шрифт, например a, а клетките на векторите и матриците са с наклонен шрифт (тъй като са скалари), например A и a. Индексната нотация често е най-ясният начин да се изразят определенията, и е приета като стандарт в литературата. Клетката i, j на матрица A се обозначава от(A)_ij или A_ij, докато a цифрово обозначение (не матрична клетка) в колекция от матрици само е подчертано, например: A₁, A₂, и т.н.

Скаларно умножение

 Основна статия: Скаларно умножение

Най-простата форма на умножение на матрици е скаларното умножение, което е частен случай на произведението на Кронекер.

Лявото скаларно умножение на матрица A със скаларен множител λ дава друга матрица λA със същия размер като A. се определя с уравнението λA:

${\displaystyle (\lambda \mathbf {A} )_{ij}=\lambda \left(\mathbf {A} \right)_{ij}\,,}$

подробно:

${\displaystyle \lambda \mathbf {A} =\lambda {\begin{pmatrix}A_{11}&A_{12}&\cdots &A_{1m}\\A_{21}&A_{22}&\cdots &A_{2m}\\\vdots &\vdots &\ddots &\vdots \\A_{n1}&A_{n2}&\cdots &A_{nm}\\\end{pmatrix}}={\begin{pmatrix}\lambda A_{11}&\lambda A_{12}&\cdots &\lambda A_{1m}\\\lambda A_{21}&\lambda A_{22}&\cdots &\lambda A_{2m}\\\vdots &\vdots &\ddots &\vdots \\\lambda A_{n1}&\lambda A_{n2}&\cdots &\lambda A_{nm}\\\end{pmatrix}}\,.}$

По подобен начин, дясното скаларно умножение на матрица A със скаларен множител λ е

${\displaystyle (\mathbf {A} \lambda )_{ij}=\left(\mathbf {A} \right)_{ij}\lambda \,,}$

подробно:

${\displaystyle \mathbf {A} \lambda ={\begin{pmatrix}A_{11}&A_{12}&\cdots &A_{1m}\\A_{21}&A_{22}&\cdots &A_{2m}\\\vdots &\vdots &\ddots &\vdots \\A_{n1}&A_{n2}&\cdots &A_{nm}\\\end{pmatrix}}\lambda ={\begin{pmatrix}A_{11}\lambda &A_{12}\lambda &\cdots &A_{1m}\lambda \\A_{21}\lambda &A_{22}\lambda &\cdots &A_{2m}\lambda \\\vdots &\vdots &\ddots &\vdots \\A_{n1}\lambda &A_{n2}\lambda &\cdots &A_{nm}\lambda \\\end{pmatrix}}\,.}$

Когато подстоящият пръстен е комутативен, например, реално или комплексното число поле, тези две умножения са еквивалентни, и се наричат скаларно умножение. За матрици в по-общ пръстен които не са комутативни, каквито са кватернионите, те може да не са равни.

При реален скаларен множител и матрица:

${\displaystyle \lambda =2,\quad \mathbf {A} ={\begin{pmatrix}a&b\\c&d\\\end{pmatrix}}}$

${\displaystyle 2\mathbf {A} =2{\begin{pmatrix}a&b\\c&d\\\end{pmatrix}}={\begin{pmatrix}2\!\cdot \!a&2\!\cdot \!b\\2\!\cdot \!c&2\!\cdot \!d\\\end{pmatrix}}={\begin{pmatrix}a\!\cdot \!2&b\!\cdot \!2\\c\!\cdot \!2&d\!\cdot \!2\\\end{pmatrix}}={\begin{pmatrix}a&b\\c&d\\\end{pmatrix}}2=\mathbf {A} 2.}$

При скаларен множител кватернион и матрици:

${\displaystyle \lambda =i,\quad \mathbf {A} ={\begin{pmatrix}i&0\\0&j\\\end{pmatrix}}}$

${\displaystyle i{\begin{pmatrix}i&0\\0&j\\\end{pmatrix}}={\begin{pmatrix}i^{2}&0\\0&ij\\\end{pmatrix}}={\begin{pmatrix}-1&0\\0&k\\\end{pmatrix}}\neq {\begin{pmatrix}-1&0\\0&-k\\\end{pmatrix}}={\begin{pmatrix}i^{2}&0\\0&ji\\\end{pmatrix}}={\begin{pmatrix}i&0\\0&j\\\end{pmatrix}}i\,,}$

където i, j, k са кватернионите. Некомутативността на умножението на кватерниони не позволява прехода на ij = +k към ji = −k.

Произведение на матрици (две матрици)

Да допуснем че две матрици ще бъдат умножени (по-долу се разглежда случай, сведен до каквото и да е число).

Обща дефиниция на матрично произведение

Arithmetic process of multiplying numbers (solid lines) in row i in matrix A and column j in matrix B, then adding the terms (dashed lines) to obtain entry ij in the final matrix.

Ако A е n × m матрица и B е m × p матрица,

${\displaystyle \mathbf {A} ={\begin{pmatrix}A_{11}&A_{12}&\cdots &A_{1m}\\A_{21}&A_{22}&\cdots &A_{2m}\\\vdots &\vdots &\ddots &\vdots \\A_{n1}&A_{n2}&\cdots &A_{nm}\\\end{pmatrix}},\quad \mathbf {B} ={\begin{pmatrix}B_{11}&B_{12}&\cdots &B_{1p}\\B_{21}&B_{22}&\cdots &B_{2p}\\\vdots &\vdots &\ddots &\vdots \\B_{m1}&B_{m2}&\cdots &B_{mp}\\\end{pmatrix}}}$

матричното произведение AB (обозначено без знаци за умножение или точки) представлява n × p матрица^[3][4][5][6]

${\displaystyle \mathbf {A} \mathbf {B} ={\begin{pmatrix}\left(\mathbf {AB} \right)_{11}&\left(\mathbf {AB} \right)_{12}&\cdots &\left(\mathbf {AB} \right)_{1p}\\\left(\mathbf {AB} \right)_{21}&\left(\mathbf {AB} \right)_{22}&\cdots &\left(\mathbf {AB} \right)_{2p}\\\vdots &\vdots &\ddots &\vdots \\\left(\mathbf {AB} \right)_{n1}&\left(\mathbf {AB} \right)_{n2}&\cdots &\left(\mathbf {AB} \right)_{np}\\\end{pmatrix}}}$

където всяка i, j клетка се получава при умножаването на клетките A_ik (хоризонтален ред i на A) по клетките B_kj (вертикална колона j на B), за k = 1, 2, ..., m, и сумирането на резултатите в k:

${\displaystyle (\mathbf {A} \mathbf {B} )_{ij}=\sum _{k=1}^{m}A_{ik}B_{kj}\,.}$

По този начин произведението AB се определя само ако броят на колоните в A е равен на броя на редовете в B, в този случай m. Клетките могат да бъдат изчислявани една по една. Понякога, конвенцията за сумиране на Айнщайн се използва, за да се разбере сумата на повтарящия се индекс k. За да се избегне двусмислие, конвенцията няма да бъде засегната в тази статия.

Обикновено клетките са цифри или изрази, но могат самите те да бъдат матрици (виж блок матрици). И в този случай матричното произведение пак се изчислява по същия начин. Може да се види подробно по-долу как матричното произведение може да бъде изчислено на базата на блокове, които приемат формата на редове и колони.

Илюстриране

Фигурата отдясно илюстрира чрез диаграма произведението на две матрици A and B, и показва как всеки отрязък в матричното произведение отговаря на ред от A и колона от B.

${\displaystyle {\overset {4\times 2{\text{ matrix}}}{\begin{bmatrix}{\color {Brown}{a_{11}}}&{\color {Brown}{a_{12}}}\\\cdot &\cdot \\{\color {Orange}{a_{31}}}&{\color {Orange}{a_{32}}}\\\cdot &\cdot \\\end{bmatrix}}}{\overset {2\times 3{\text{ matrix}}}{\begin{bmatrix}\cdot &{\color {Plum}{b_{12}}}&{\color {Violet}{b_{13}}}\\\cdot &{\color {Plum}{b_{22}}}&{\color {Violet}{b_{23}}}\\\end{bmatrix}}}={\overset {4\times 3{\text{ matrix}}}{\begin{bmatrix}\cdot &x_{12}&x_{13}\\\cdot &\cdot &\cdot \\\cdot &x_{32}&x_{33}\\\cdot &\cdot &\cdot \\\end{bmatrix}}}}$

Стойностите на отрязъците обозначени с кръгове са:

${\displaystyle {\begin{aligned}x_{12}&={\color {Brown}{a_{11}}}{\color {Plum}{b_{12}}}+{\color {Brown}{a_{12}}}{\color {Plum}{b_{22}}}\\x_{13}&={\color {Brown}{a_{11}}}{\color {Violet}{b_{13}}}+{\color {Brown}{a_{12}}}{\color {Violet}{b_{23}}}\\x_{32}&={\color {Orange}{a_{31}}}{\color {Plum}{b_{12}}}+{\color {Orange}{a_{32}}}{\color {Plum}{b_{22}}}\\x_{33}&={\color {Orange}{a_{31}}}{\color {Violet}{b_{13}}}+{\color {Orange}{a_{32}}}{\color {Violet}{b_{23}}}\end{aligned}}}$

Примери за произведение на матрици

Вектор ред и вектор колона

Ако

${\displaystyle \mathbf {A} ={\begin{pmatrix}a&b&c\end{pmatrix}}\,,\quad \mathbf {B} ={\begin{pmatrix}x\\y\\z\end{pmatrix}}\,,}$

техните матрични произведения са:

${\displaystyle \mathbf {AB} ={\begin{pmatrix}a&b&c\end{pmatrix}}{\begin{pmatrix}x\\y\\z\end{pmatrix}}=ax+by+cz\,,}$

и

${\displaystyle \mathbf {BA} ={\begin{pmatrix}x\\y\\z\end{pmatrix}}{\begin{pmatrix}a&b&c\end{pmatrix}}={\begin{pmatrix}xa&xb&xc\\ya&yb&yc\\za&zb&zc\end{pmatrix}}\,.}$

Обърнете внимание, че AB и BA са две различни матрици: първата е 1 × 1 матрица докато втората е 3 × 3 матрица. Такива изрази се срещат при реални стойности в Евклидови вектори в Декартова координатна системаи, представени като матрици с редове и колони, при което AB е матричната форма на тяхното скаларно произведение, докато BA е матричната форма на тяхното диадно или тензорно произведение.

Квадратна матрица и вектор колона

Ако

${\displaystyle \mathbf {A} ={\begin{pmatrix}a&b&c\\p&q&r\\u&v&w\end{pmatrix}},\quad \mathbf {B} ={\begin{pmatrix}x\\y\\z\end{pmatrix}}\,,}$

матричното произведение е:

${\displaystyle \mathbf {AB} ={\begin{pmatrix}a&b&c\\p&q&r\\u&v&w\end{pmatrix}}{\begin{pmatrix}x\\y\\z\end{pmatrix}}={\begin{pmatrix}ax+by+cz\\px+qy+rz\\ux+vy+wz\end{pmatrix}}\,,}$

при което BA не е определено.

До произведението на квадратна матрица умножена по матрица от колона се достига естествено в линейната алгебра; за решаване на линейни уравнения и представянето им като линейни трансформации.

Квадратни матрици

Ако

${\displaystyle \mathbf {A} ={\begin{pmatrix}a&b&c\\p&q&r\\u&v&w\end{pmatrix}},\quad \mathbf {B} ={\begin{pmatrix}\alpha &\beta &\gamma \\\lambda &\mu &\nu \\\rho &\sigma &\tau \\\end{pmatrix}}\,,}$

техните матрични произведения са:

${\displaystyle \mathbf {AB} ={\begin{pmatrix}a&b&c\\p&q&r\\u&v&w\end{pmatrix}}{\begin{pmatrix}\alpha &\beta &\gamma \\\lambda &\mu &\nu \\\rho &\sigma &\tau \\\end{pmatrix}}={\begin{pmatrix}a\alpha +b\lambda +c\rho &a\beta +b\mu +c\sigma &a\gamma +b\nu +c\tau \\p\alpha +q\lambda +r\rho &p\beta +q\mu +r\sigma &p\gamma +q\nu +r\tau \\u\alpha +v\lambda +w\rho &u\beta +v\mu +w\sigma &u\gamma +v\nu +w\tau \end{pmatrix}}\,,}$

и

${\displaystyle \mathbf {BA} ={\begin{pmatrix}\alpha &\beta &\gamma \\\lambda &\mu &\nu \\\rho &\sigma &\tau \\\end{pmatrix}}{\begin{pmatrix}a&b&c\\p&q&r\\u&v&w\end{pmatrix}}={\begin{pmatrix}\alpha a+\beta p+\gamma u&\alpha b+\beta q+\gamma v&\alpha c+\beta r+\gamma w\\\lambda a+\mu p+\nu u&\lambda b+\mu q+\nu v&\lambda c+\mu r+\nu w\\\rho a+\sigma p+\tau u&\rho b+\sigma q+\tau v&\rho c+\sigma r+\tau w\end{pmatrix}}\,.}$

В този случай, и двете произведения AB and BA са дефинирани, и клетките показват, че AB и BA по принцип не са равни.

Умножението на квадратни матрици, които представят линейни transformations отговаря на composite transformation (за детайли виж по-долу).

Вектор ред, квадратна матрица, и вектор колона

Ако

${\displaystyle \mathbf {A} ={\begin{pmatrix}a&b&c\end{pmatrix}}\,,\quad \mathbf {B} ={\begin{pmatrix}\alpha &\beta &\gamma \\\lambda &\mu &\nu \\\rho &\sigma &\tau \\\end{pmatrix}}\,,\quad \mathbf {C} ={\begin{pmatrix}x\\y\\z\end{pmatrix}}\,,}$

тяхното матрично произведение е:

${\displaystyle {\begin{aligned}\mathbf {ABC} &={\begin{pmatrix}a&b&c\end{pmatrix}}\left[{\begin{pmatrix}\alpha &\beta &\gamma \\\lambda &\mu &\nu \\\rho &\sigma &\tau \\\end{pmatrix}}{\begin{pmatrix}x\\y\\z\end{pmatrix}}\right]=\left[{\begin{pmatrix}a&b&c\end{pmatrix}}{\begin{pmatrix}\alpha &\beta &\gamma \\\lambda &\mu &\nu \\\rho &\sigma &\tau \\\end{pmatrix}}\right]{\begin{pmatrix}x\\y\\z\end{pmatrix}}\\&={\begin{pmatrix}a&b&c\end{pmatrix}}{\begin{pmatrix}\alpha x+\beta y+\gamma z\\\lambda x+\mu y+\nu z\\\rho x+\sigma y+\tau z\\\end{pmatrix}}={\begin{pmatrix}a\alpha +b\lambda +c\rho &a\beta +b\mu +c\sigma &a\gamma +b\nu +c\tau \end{pmatrix}}{\begin{pmatrix}x\\y\\z\end{pmatrix}}\\&=a\alpha x+b\lambda x+c\rho x+a\beta y+b\mu y+c\sigma y+a\gamma z+b\nu z+c\tau z\,,\end{aligned}}}$

CBA не е дефинирано. Обърнете внимание, че A(BC) = (AB)C, това е едно от мнгото общи свойства, които са описани по-долу. Изрази като ABC се срещат когато се изчислява вътрешното произведение на два вектора, представени като вектор ред и вектор колона в произволна координатна система, и метричен тензор в тези координати обозначени като квадратна матрица.

Четириъгълни матрици

Ако

${\displaystyle \mathbf {A} ={\begin{pmatrix}a&b&c\\x&y&z\end{pmatrix}}\,,\quad \mathbf {B} ={\begin{pmatrix}\alpha &\rho \\\beta &\sigma \\\gamma &\tau \\\end{pmatrix}}\,,}$

техните матрични произведения са:

${\displaystyle \mathbf {A} \mathbf {B} ={\begin{pmatrix}a&b&c\\x&y&z\end{pmatrix}}{\begin{pmatrix}\alpha &\rho \\\beta &\sigma \\\gamma &\tau \\\end{pmatrix}}={\begin{pmatrix}a\alpha +b\beta +c\gamma &a\rho +b\sigma +c\tau \\x\alpha +y\beta +z\gamma &x\rho +y\sigma +z\tau \\\end{pmatrix}}\,,}$

и

${\displaystyle \mathbf {B} \mathbf {A} ={\begin{pmatrix}\alpha &\rho \\\beta &\sigma \\\gamma &\tau \\\end{pmatrix}}{\begin{pmatrix}a&b&c\\x&y&z\end{pmatrix}}={\begin{pmatrix}\alpha a+\rho x&\alpha b+\rho y&\alpha c+\rho z\\\beta a+\sigma x&\beta b+\sigma y&\beta c+\sigma z\\\gamma a+\tau x&\gamma b+\tau y&\gamma c+\tau z\end{pmatrix}}\,.}$

Свойства на матричното произведение (две матрици)

Подобно на числоа (елементи на поле), матриците отговарят на следните общи свойства general properties, въпреки че съществува една особеност, която се дължи на природата на умножението на матрици.^[7][8]

Всички матрици

Шаблон:Ordered list

Шаблон:For

Само квадратни матрици

 Основна статия: квадратна матрица

Шаблон:Ordered list

Произведение на матрици (произволен брой)

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

Произведението на n матрици A₁, A₂, ..., A_n с резмерности s₀ × s₁, s₁ × s₂, ..., s_{n × 1} × s_n (където s₀, s₁, s₂, ..., s_n са положителни числа, като индексите съответстват на тези на матриците), матрицата с размерност s₀ × s_n :

${\displaystyle \prod _{i=1}^{n}\mathbf {A} _{i}=\mathbf {A} _{1}\mathbf {A} _{2}\cdots \mathbf {A} _{n}\,}$

Разписано с индекси:

${\displaystyle \left(\mathbf {A} _{1}\mathbf {A} _{2}\cdots \mathbf {A} _{n}\right)_{i_{0}i_{n}}=\sum _{i_{1}=1}^{s_{1}}\sum _{i_{2}=1}^{s_{2}}\cdots \sum _{i_{n-1}=1}^{s_{n-1}}\left(\mathbf {A} _{1}\right)_{i_{0}i_{1}}\left(\mathbf {A} _{2}\right)_{i_{1}i_{2}}\left(\mathbf {A} _{3}\right)_{i_{2}i_{3}}\cdots \left(\mathbf {A} _{n-1}\right)_{i_{n-2}i_{n-1}}\left(\mathbf {A} _{n}\right)_{i_{n-1}i_{n}}}$

Свойства на матричното произведение (произволен брой)

Свойствата са в сила, докато редът на матриците не е променен. Някои от предишните свойства, валидни за две матрици, могат да бъдат обобщени както следва.

Шаблон:Ordered list

Операции, произлизащи от умножението на матрици

Повечето операции върху квадратни матрици могат да бъдат дефинирани посредством умножението на матрици. Например степенуването и коренуването на матрица могат да бъдат представени чрез многократно прилагане на умножението на матрици, матричната експонента може да бъде дефинирана чрез степенни редове, матричния логаритъм е обратната операция на матричната експоненто и т.н.

Степенуване на матрица

Квадратните матрици могат да бъдат умножени една с друга многократно по подобие на числата, защото те винаги запазват своя брой на редове и колони. Това многократно умножение може да се представи като степенуване на матрица, специален случай на умножението на матрици. От друга страна, правоъгълните матрици нямат същия брой на редове и колони и поради тази причина те никога не могат да бъдат повдигнати на степен. Матрица A с размерност n × n, повдигната на степен k цяло число, се дефинира по следния начин

${\displaystyle \mathbf {A} ^{k}={\underset {k\mathrm {\,times} }{\mathbf {A} \mathbf {A} \cdots \mathbf {A} }}}$

и следните свойства са в сила, където λ е скалар:

1. Нулева степен:

${\displaystyle \mathbf {A} ^{0}=\mathbf {I} }$

където I е единичната матрица. Това е съпоставимо с повдигането на степен нула на кое и да е число, което е равно на единица.

2. Умножение със скалар:

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

3. Детерминанта:

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

Наивният подход при степенуване на матрица е матрицата A да се умножи k пъти. Този метод б могъл да бъде оптимизиран чрез използване на алгоритъм за бързо пресмятане на степен – метод предимно използван за скалари. За матрици, които са подобни на диагоналните, още по-добър вариант е да се използва спектралната декомпозиция на A. Друг метод, базиран на теоремата на Хамилтон-Кейли намира по-ефективно уравнение за A^k, в което даден скалар се повдига на нужната степен отколкото цялата матрица.

Специален случай е степенуването на диагонална матрица. Понеже умножаването на диагонални матрици се състои просто в умножение на съответните диагонални елементи, диагоналната матрица A на степен 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}}}$

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

Приложения на умножението на матрици

Линейни трансформации

 Основна статия: Linear transformations

Матриците предоставят сбит начин на представяне на линейни изображения между векторни пространства и умножението на матрици съответства на композицията на линейни изображения. Произведението на две матрици може да бъде дефинирано, когато елементите им принадлежат на същия пръстен пръстен и следователно може да бъде добавян и умножаван.

Нека U, V, и W са линейни пространства над едно и също поле с дадени базиси, S: V > W и T: U > V са линейни изображения и ST: U > W е тяхната композиция.

Да предположим, че A, B, и C са матриците, представящи изображенията S, T, и ST спрямо дадените базиси.

Тогава матрицата AB = C, композицията (или произведението) на линейни изображения е произведението на техните матрици спрямо дадените базиси.

Система линейни уравнения

Система линейни уравнения с еднакъв брой уравнения и неизвестни може да бъде решена чрез съставянето на матрица от коефициентите на уравненията.

Сходна процедура може да бъде използвана при решаването на линейни диференциални уравнения.

Векторно и диадно произведение

При дадени два вектор стълба a и b, скаларното произведение и диадното произведение са най-простите случаи на матрично произведение.

Скаларно произведение

Скаларното произведение на два вектора в матричен вид е еквивалентно на вектор стълб, умножен от лявата си страна с вектор ред:

${\displaystyle {\begin{aligned}\mathbf {a} \cdot \mathbf {b} &=\mathbf {a} ^{\mathrm {T} }\mathbf {b} \\&={\begin{pmatrix}a_{1}&a_{2}&\cdots &a_{n}\end{pmatrix}}{\begin{pmatrix}b_{1}\\b_{2}\\\vdots \\b_{n}\end{pmatrix}}\\&=a_{1}b_{1}+a_{2}b_{2}+\cdots +a_{n}b_{n}\\&=\sum _{i=1}^{n}a_{i}b_{i},\end{aligned}}}$

където a^T е транспонираната матрица на a.

Матричното произведение може да се представи под форма на скаларно произведение. Да предположим, че матрицата A с размерност n × m е представена чрез вектор редовете a_i, а матрицата B с размерност m × p е представена чрез вектор стълбовете b_i:

${\displaystyle \mathbf {A} ={\begin{pmatrix}A_{11}&A_{12}&\cdots &A_{1m}\\A_{21}&A_{22}&\cdots &A_{2m}\\\vdots &\vdots &\ddots &\vdots \\A_{n1}&A_{n2}&\cdots &A_{nm}\end{pmatrix}}={\begin{pmatrix}\mathbf {a} _{1}\\\mathbf {a} _{2}\\\vdots \\\mathbf {a} _{n}\end{pmatrix}},}$

${\displaystyle \mathbf {B} ={\begin{pmatrix}B_{11}&B_{12}&\cdots &B_{1p}\\B_{21}&B_{22}&\cdots &B_{2p}\\\vdots &\vdots &\ddots &\vdots \\B_{m1}&B_{m2}&\cdots &B_{mp}\end{pmatrix}}={\begin{pmatrix}\mathbf {b} _{1}&\mathbf {b} _{2}&\cdots &\mathbf {b} _{p}\end{pmatrix}}}$

където

${\displaystyle \mathbf {a} _{i}={\begin{pmatrix}A_{i1}&A_{i2}&\cdots &A_{im}\end{pmatrix}}\,,\quad \mathbf {b} _{i}={\begin{pmatrix}B_{1i}\\B_{2i}\\\vdots \\B_{mi}\end{pmatrix}}}$

Тогава:

${\displaystyle \mathbf {AB} ={\begin{pmatrix}\mathbf {a} _{1}\\\mathbf {a} _{2}\\\vdots \\\mathbf {a} _{n}\end{pmatrix}}{\begin{pmatrix}\mathbf {b} _{1}&\mathbf {b} _{2}&\dots &\mathbf {b} _{p}\end{pmatrix}}={\begin{pmatrix}(\mathbf {a} _{1}\cdot \mathbf {b} _{1})&(\mathbf {a} _{1}\cdot \mathbf {b} _{2})&\dots &(\mathbf {a} _{1}\cdot \mathbf {b} _{p})\\(\mathbf {a} _{2}\cdot \mathbf {b} _{1})&(\mathbf {a} _{2}\cdot \mathbf {b} _{2})&\dots &(\mathbf {a} _{2}\cdot \mathbf {b} _{p})\\\vdots &\vdots &\ddots &\vdots \\(\mathbf {a} _{n}\cdot \mathbf {b} _{1})&(\mathbf {a} _{n}\cdot \mathbf {b} _{2})&\dots &(\mathbf {a} _{n}\cdot \mathbf {b} _{p})\end{pmatrix}}}$

Също така е възможно дадено матрично произведение да се изрази под формата на произведение на матрици и вектор ред или стълб.:

${\displaystyle \mathbf {AB} ={\begin{pmatrix}\mathbf {A} \mathbf {b} _{1}&\mathbf {A} \mathbf {b} _{2}&\dots &\mathbf {A} \mathbf {b} _{p}\end{pmatrix}}={\begin{pmatrix}\mathbf {a} _{1}\mathbf {B} \\\mathbf {a} _{2}\mathbf {B} \\\vdots \\\mathbf {a} _{n}\mathbf {B} \end{pmatrix}}}$

Тези преобразувания са особено полезни за матрици, които са представени като конкатенации на различни типове вектор редове или вектор колони. Например ортогоналните матрици (чиито редове са ортогонални един на друг) и матриците на Марков (при които сумата от редовете или колоните е равна на единица).

Диадно произведение

Диадното произведение (също познато като тензорно произведение) на два вектора в матричен вид е еквивалентно на вектор ред, умножен от ляво с вектор стълб:

${\displaystyle {\begin{aligned}\mathbf {a} \otimes \mathbf {b} &=\mathbf {a} \mathbf {b} ^{\mathrm {T} }\\&={\begin{pmatrix}a_{1}\\a_{2}\\\vdots \\a_{n}\end{pmatrix}}{\begin{pmatrix}b_{1}&b_{2}&\cdots &b_{n}\end{pmatrix}}\\&={\begin{pmatrix}a_{1}b_{1}&a_{1}b_{2}&\cdots &a_{1}b_{n}\\a_{2}b_{1}&a_{2}b_{2}&\cdots &a_{2}b_{n}\\\vdots &\vdots &\ddots &\vdots \\a_{n}b_{1}&a_{n}b_{2}&\cdots &a_{n}b_{n}\\\end{pmatrix}}.\end{aligned}}}$

Умножението на матрици може да се представи под форма на диадно произведение. Матрицата A е представена чрез вектор стълбовете a_i, а матрицата B – чрез вектор редовете b_i:

${\displaystyle {\begin{aligned}\mathbf {AB} &={\begin{pmatrix}\mathbf {\bar {a}} _{1}&\mathbf {\bar {a}} _{2}&\cdots &\mathbf {\bar {a}} _{m}\end{pmatrix}}{\begin{pmatrix}\mathbf {\bar {b}} _{1}\\\mathbf {\bar {b}} _{2}\\\vdots \\\mathbf {\bar {b}} _{m}\end{pmatrix}}\\&=\mathbf {\bar {a}} _{1}\otimes \mathbf {\bar {b}} _{1}+\mathbf {\bar {a}} _{2}\otimes \mathbf {\bar {b}} _{2}+\cdots +\mathbf {\bar {a}} _{m}\otimes \mathbf {\bar {b}} _{m}\\&=\sum _{i=1}^{m}\mathbf {\bar {a}} _{i}\otimes \mathbf {\bar {b}} _{i}\end{aligned}}}$

където този път

${\displaystyle \mathbf {\bar {a}} _{i}={\begin{pmatrix}A_{1i}\\A_{2i}\\\vdots \\A_{ni}\end{pmatrix}}\,,\quad \mathbf {\bar {b}} _{i}={\begin{pmatrix}B_{i1}&B_{i2}&\cdots &B_{ip}\end{pmatrix}}\,.}$

Този метод подчертава ефекта от отделните стълб/ред двойки в резултата.

${\displaystyle {\begin{aligned}{\begin{pmatrix}{\color {Brown}1}&{\color {Orange}2}&{\color {Violet}3}\\{\color {Brown}4}&{\color {Orange}5}&{\color {Violet}6}\\{\color {Brown}7}&{\color {Orange}8}&{\color {Violet}9}\\\end{pmatrix}}{\begin{pmatrix}{\color {Brown}a}&{\color {Brown}d}\\{\color {Orange}b}&{\color {Orange}e}\\{\color {Violet}c}&{\color {Violet}f}\\\end{pmatrix}}&={\begin{pmatrix}{\color {Brown}1}\\{\color {Brown}4}\\{\color {Brown}7}\\\end{pmatrix}}{\begin{pmatrix}{\color {Brown}{a}}&{\color {Brown}{d}}\\\end{pmatrix}}+{\begin{pmatrix}{\color {Orange}2}\\{\color {Orange}5}\\{\color {Orange}8}\\\end{pmatrix}}{\begin{pmatrix}{\color {Orange}{b}}&{\color {Orange}{e}}\\\end{pmatrix}}+{\begin{pmatrix}{\color {Violet}3}\\{\color {Violet}6}\\{\color {Violet}9}\\\end{pmatrix}}{\begin{pmatrix}{\color {Violet}c}&{\color {Violet}f}\\\end{pmatrix}}\\&={\begin{pmatrix}{\color {Brown}{1a}}&{\color {Brown}{1d}}\\{\color {Brown}{4a}}&{\color {Brown}{4d}}\\{\color {Brown}{7a}}&{\color {Brown}{7d}}\\\end{pmatrix}}+{\begin{pmatrix}{\color {Orange}{2b}}&{\color {Orange}{2e}}\\{\color {Orange}{5b}}&{\color {Orange}{5e}}\\{\color {Orange}{8b}}&{\color {Orange}{8e}}\\\end{pmatrix}}+{\begin{pmatrix}{\color {Violet}{3c}}&{\color {Violet}{3f}}\\{\color {Violet}{6c}}&{\color {Violet}{6f}}\\{\color {Violet}{9c}}&{\color {Violet}{9f}}\\\end{pmatrix}}\\&={\begin{pmatrix}{\color {Brown}{1a}}+{\color {Orange}{2b}}+{\color {Violet}{3c}}&{\color {Brown}{1d}}+{\color {Orange}{2e}}+{\color {Violet}{3f}}\\{\color {Brown}{4a}}+{\color {Orange}{5b}}+{\color {Violet}{6c}}&{\color {Brown}{4d}}+{\color {Orange}{5e}}+{\color {Violet}{6f}}\\{\color {Brown}{7a}}+{\color {Orange}{8b}}+{\color {Violet}{9c}}&{\color {Brown}{7d}}+{\color {Orange}{8e}}+{\color {Violet}{9f}}\\\end{pmatrix}}.\end{aligned}}}$

Алгоритми за ефективно умножение на матрици

 Основна статия: Matrix multiplication algorithm

Граници на ω във времето.

Времето за умножение на квадратни матрици с наивен алгоритъм е O(n³). Времето за умножение на правоъгълни матрици (една m × p-матрица с една p × n-матрица) е O(mnp), Все пак съществуват и по-ефективни алгоритми за целта, например алгоритъм на Страсен, разработен през 1969 г. от Volker Strassen и често срещан под името „бързо умножение на матрици“. Той се базира на определен начин на умножение на две 2 × 2-матрици, изискващ само 7 умножения (вместо обичайните 8) за сметка на няколко допълнителни операции по събиране и изваждане. Използването на това чрез рекурсия дава като резултат сложност ${\displaystyle O(n^{\log _{2}7})\approx O(n^{2.807})}$. Алгоритъмът на Страсен е по-сложен, а неговата числена стабилност е по-ниска в сравнение с тази на наивния алгоритъм.^[9] Въпреки това, последния е включен в няколко библиотеки като BLAS, където той е чувствително по-ефективен за матрици с размери над 100,^[10] и освен това е много полезен за големи матрици над точните области като крайни полета, където числената стабилност не е проблем.

Настоящият O(n^k) алгоритъм с възможно най-ниската експонента k е обобщение на алгоритъм на Копърсмит-Виноград с асимптотична сложност O(n^2.3728639), създаден от Франсоа Ле Гал.^[11] Този алгоритъм, заедно с алгоритъм на Копърсмит-Виноград на който е базиран, са близки до алгоритъма на Страсен: намерен е начин за умножение на две k ? k-матрици с по-малко от k³ умножения, и след това тази техника е приложена рекурсивно. Въпреки това, константния коефициент, скрит зад голямата О нотация, е толкова голям, че тези алгоритми си струва да бъдат прилагани само за матрици, които са твърде големи за обработка със съвременната изчислителна техника.^[12][13]

Тъй като всеки алгоритъм за умножение на две n × n-матрици трябва да обработи 2 × n²-елемента, има асимптотична долна граница от Ω(n²) операции. През 2002 г. Раз доказва че стойността на долната граница за аритметични вериги със свързани коефициенти е по-ниска Ω(n² log(n)) от тази при реални или сложни числа.

През 2003 – 2005 г. Коун и други слагат методиките на алгоритмите на Страсен и Копърсмит-Виноград в напълно различен, групово-теоретичен контекст. Това става чрез употребата на тройки от подмножества на крайни групи, които нямат общи елементи, наречено още свойство на тройното произведение (TPP). Те показват, че ако семействата на кръглите произведения на Абелови групи със симетрични групи дава семейства от тройки подмножества с еднаква версия на тяхното TPP, това значи че има алгоритми за умножение на матрици с приблизително квадратична сложност. Повечето изследователи вярват в че това е вярно.^[14] Въпреки това, Алон, Шпилка и Крис Уманс доказват, че при някои от тези предположения бързото умножението на матрици е несъвместимо с друго предположение – това на слънчогледа.^[15]

Алгоритъмът на Фрайвалдс е обикновен Монте Карло алгоритъм, който, при дадени матрици A, B, C се изпълнява за Θ(n²) време, ако AB = C.

Умножение на блокове матрици. При 2D алгоритъмът всеки процесор отговаря за една подматрица C. При 3D алгоритъмът, умножението на всеки чифт подматрици от A и B се подава на един процесор..

Паралелно умножение на матрици

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

${\displaystyle \mathbf {C} ={\begin{pmatrix}\mathbf {C} _{11}&\mathbf {C} _{12}\\\mathbf {C} _{21}&\mathbf {C} _{22}\\\end{pmatrix}}={\begin{pmatrix}\mathbf {A} _{11}&\mathbf {A} _{12}\\\mathbf {A} _{21}&\mathbf {A} _{22}\\\end{pmatrix}}{\begin{pmatrix}\mathbf {B} _{11}&\mathbf {B} _{12}\\\mathbf {B} _{21}&\mathbf {B} _{22}\\\end{pmatrix}}=\mathbf {A} \mathbf {B} }$

които лежат и в основата на алгоритъма на Страсен. Тук A, B и C вземат за квадратни n by n матрици, а C₁₁ и т.н. са n/2 by n/2 подматрици. От това разлагане се получава^[16]

${\displaystyle {\begin{pmatrix}\mathbf {A} _{11}&\mathbf {A} _{12}\\\mathbf {A} _{21}&\mathbf {A} _{22}\\\end{pmatrix}}{\begin{pmatrix}\mathbf {B} _{11}&\mathbf {B} _{12}\\\mathbf {B} _{21}&\mathbf {B} _{22}\\\end{pmatrix}}={\begin{pmatrix}\mathbf {A} _{11}\mathbf {B} _{11}+\mathbf {A} _{12}\mathbf {B} _{21}&\mathbf {A} _{11}\mathbf {B} _{12}+\mathbf {A} _{12}\mathbf {B} _{22}\\\mathbf {A} _{21}\mathbf {B} _{11}+\mathbf {A} _{22}\mathbf {B} _{21}&\mathbf {A} _{21}\mathbf {B} _{12}+\mathbf {A} _{22}\mathbf {B} _{22}\\\end{pmatrix}}}$

което се състои от осем умножения на деойки подматрици, всички от които могат да бъдат изпълнявани паралелно, последвани от допълнителна стъпка. Ако това се приложи рекурсивно и събиранията се изпълнят отново паралелно, получения алгоритъм отнема Θ(log² n) време на идеална машина с безкраен брой процесори, и има максимална възможна скорост Θ(n³/(log² n)) на всички реални компютри (въпреки че алгоритъма не е практичен, негов по-практичен вариант постига Θ(n²) скорост).^[16]

Трябва да бъде отбелязано това, че някои алгоритми с по-ниска времева сложност на хартия, може да имат индиректно добавена допълнителна сложност по време при работа на реални машини.

Разпределени алгоритми и алгоритми избягващи комуникация

При модерните архитектури с йерархична памет, цената на зареджане и съхранение на данните от матричните елементи е по=висока от тази на изчисленията. За една машина това е количеството данни, пренасяно между RAM паметта и кеша, докато при многовъзловите машини с разпределена памет това е количеството данни, премасяно междъ отделните възли. И в двата случая това се нарича ширина на потока за комуникация. Наивните алгоритми, ползващи три вложени цикъла използват Ω(n³) широчина на комуникационния поток.

Алгоритъма на Канон, познат още като 2D алгоритъм, разделя всяка входна матрица на блокове чиито елементи са подматрици с големина √M/3 by √M/3, където M е размера на бързата памет.^[17] След това за блоковете от матрици се прилага наивния алгоритъм, който изчислява произведенията на подматриците изцяло в бързата памет. Това намалява широчината на комуникационния канал до O(n³/√M), което е асимптотично оптимално (за алгоритми с изчислителна производителност Ω(n³)).^[18][19]

В разпределена среда с p процесора подредени в √p на √p 2D мрежа, към всеки процесор може да бъде зачислена една подматрица, а произведението – да бъде изчислено с всеки процесор, предавайки O(n²/√p) думи. Това е асимптотично оптимално, ако се предположи че всеки изчислителен възел съхранява минимум O(n²/p) елементи.^[19] Това може да бъде подобрено от 3D алгоритъм, който подрежда процесорите в 3D мрежа с форма на куб, давайки всяко произведение на две подматрици на един процесор. Получените в резултат подматрици след това се генерират посредством изваждане на всеки ред.^[20] Този алгоритъм предава O(n²/p^2/3) думи на процесор, което е асимптотично оптимално.^[19] Все пак, това изисква репликиране на всеки елемент от входящите матрици p^1/3 пъти, и следователно изисква фактор от p^1/3 пъти повече памет, в сравнение с нужната за съхранението на входните данни. Този алгоритъм може да се комбинира с алгоритъма на Страсен с цел да се намали още повече времето за изпълнение.^[20] „2.5D“ алгоритмите предоставят баланс между ползването на памет и широчината на комуникационния канал.^[21] За съвременните разпределени компютърни среди като MapReduce са създадени специализирани алгоритми за умножение.^[22]

Други форми на умножение

По-долу са представени няколко други начина за умножение на матрици. Всъщност, някои от тях са по-прости от дефиницията по-горе.

Произведение на Адамар

 Основна статия: Hadamard product (matrices)

Произведението на Адамар е предназначено за две матрици с еднакви размерности. За две матрици A и B с еднакви размерности произведението на Адамар A ○ B е матрица от същата размерност, като i, j-тия елемент на A е умножен с i, j-тия елемент на B, което изглежда по следния начин:

${\displaystyle \left(\mathbf {A} \circ \mathbf {B} \right)_{ij}=A_{ij}B_{ij}\,,}$

разписано пълно:

${\displaystyle \mathbf {A} \circ \mathbf {B} ={\begin{pmatrix}A_{11}&A_{12}&\cdots &A_{1m}\\A_{21}&A_{22}&\cdots &A_{2m}\\\vdots &\vdots &\ddots &\vdots \\A_{n1}&A_{n2}&\cdots &A_{nm}\\\end{pmatrix}}\circ {\begin{pmatrix}B_{11}&B_{12}&\cdots &B_{1m}\\B_{21}&B_{22}&\cdots &B_{2m}\\\vdots &\vdots &\ddots &\vdots \\B_{n1}&B_{n2}&\cdots &B_{nm}\\\end{pmatrix}}={\begin{pmatrix}A_{11}B_{11}&A_{12}B_{12}&\cdots &A_{1m}B_{1m}\\A_{21}B_{21}&A_{22}B_{22}&\cdots &A_{2m}B_{2m}\\\vdots &\vdots &\ddots &\vdots \\A_{n1}B_{n1}&A_{n2}B_{n2}&\cdots &A_{nm}B_{nm}\\\end{pmatrix}}}$

Тази операция е идентична с това да се умножат много числа едновременно. Следователно произведението Адамар e комутативно, асоциативно и дистрибутивно. Също така е основна подматрица от произведението на Крьонекер. Съдържа се в алгоритми за компресия като JPEG.

Произведение на Фробениус

Произведението на Фробениус, понякога отбелязвано като A : B, е произведение на две матрици. То също така представлява сумата от елементите от произведението на Адамар. Подробно,

${\displaystyle \mathbf {A} :\mathbf {B} =\sum _{i,j}A_{ij}B_{ij}=\mathrm {vec} (\mathbf {A} )^{\mathsf {T}}\mathrm {vec} (\mathbf {B} )=\mathrm {tr} (\mathbf {A} ^{\mathsf {T}}\mathbf {B} )=\mathrm {tr} (\mathbf {A} \mathbf {B} ^{\mathsf {T}}),}$

където „tr“ означава следата на матрица, а vec означава векторизацията.

Произведение на Крьонекер

 Основна статия: Kronecker product

За две матрици A и B с произволни размерности съответно m × n и p × q (без каквито и да е било изисквания върху размерността на матриците), произведението на Крьоникер е матрицата

${\displaystyle \mathbf {A} \otimes \mathbf {B} ={\begin{pmatrix}A_{11}\mathbf {B} &A_{12}\mathbf {B} &\cdots &A_{1n}\mathbf {B} \\A_{21}\mathbf {B} &A_{22}\mathbf {B} &\cdots &A_{2n}\mathbf {B} \\\vdots &\vdots &\ddots &\vdots \\A_{m1}\mathbf {B} &A_{m2}\mathbf {B} &\cdots &A_{mn}\mathbf {B} \\\end{pmatrix}}.}$

с размерност mp × nq. Това е приложението на най-общото тензорно произведение върху матрици.

Бележки

1. Lerner, R. G., Trigg, G. L. Encyclopaedia of Physics. 2nd. VHC publishers, 1991. ISBN 3-527-26954-1.
2. Parker, C. B. McGraw Hill Encyclopaedia of Physics. 2nd. 1994. ISBN 0-07-051400-3.
3. Lipschutz, S., Lipson, M. Linear Algebra. 4th. McGraw Hill (USA), 2009. ISBN 978-0-07-154352-1. с. 30 – 31.
4. Riley, K. F., Hobson, M. P., Bence, S. J. Mathematical methods for physics and engineering. Cambridge University Press, 2010. ISBN 978-0-521-86153-3.
5. Adams, R. A. Calculus, A Complete Course. 3rd. Addison Wesley, 1995. ISBN 0 201 82823 5. с. 627.
6. Horn, Johnson. Matrix Analysis. 2nd. Cambridge University Press, 2013. ISBN 978 0 521 54823 6. с. 6.
7. 2 // Linear Algebra. 4th. McGraw Hill (USA), 2009. ISBN 978-0-07-154352-1.
8. Horn, Johnson. 0 // Matrix Analysis. 2nd. Cambridge University Press, 2013. ISBN 978 0 521 54823 6.
9. Miller, Webb. Computational complexity and numerical stability // SIAM News 4. 1975. DOI:10.1137/0204009. 10.1.1.148.9947. с. 97 – 107.
10. Press 2007, p. 108.
11. Powers of tensors and fast matrix multiplication // Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC 2014). 2014.. Оригиналния алгоритъм е представен от Дон Копърсмит и Шмуел Виноград през 1990 г. и има асимптотична сложност O(n^2.376). Подобрен е през 2013 г. до O(n^2.3729) от Виргиния Василевска Уилиамс, като времето за изпълнение е малко по-високо от подобрението на Ле Гал: Williams, Virginia Vassilevska. Multiplying matrices faster than Coppersmith-Winograd // Архивиран от оригинала на 2013-10-08. Посетен на 2015-09-29.
12. Iliopoulos, Costas S. Worst-case complexity bounds on algorithms for computing the canonical structure of finite abelian groups and the Hermite and Smith normal forms of an integer matrix // SIAM Journal on Computing 18 (4). 1989. DOI:10.1137/0218045. с. 658 – 669. Архивиран от оригинала на 2014-03-05. Посетен на 2015-09-29. The Coppersmith–Winograd algorithm is not practical, due to the very large hidden constant in the upper bound on the number of multiplications required.
13. Robinson, Sara. Toward an Optimal Algorithm for Matrix Multiplication // SIAM News 38 (9). 2005.
14. Robinson, 2005.
15. Alon, Shpilka, Umans, On Sunflowers and Matrix Multiplication
16. Ph.D. Keith H. Randall. Cilk: Efficient Multithreaded Computing. Massachusetts Institute of Technology, 1998. с. 54 – 57.
17. Lynn Elliot Cannon, A cellular computer to implement the Kalman Filter Algorithm, Technical report, Ph.D. Thesis, Montana State University, 14 юли 1969.
18. Hong, J.W. и др. I/O complexity: The red-blue pebble game // STOC ’81: Proceedings of the thirteenth annual ACM symposium on Theory of computing. 1981. с. 326 – 333.
19. Irony, Dror и др. Communication lower bounds for distributed-memory matrix multiplication // J. Parallel Distrib. Comput. 64 (9). September 2004. DOI:10.1016/j.jpdc.2004.03.021. с. 1017 – 1026.
20. Agarwal, R.C. и др. A three-dimensional approach to parallel matrix multiplication // IBM J. Res. Dev. 39 (5). September 1995. DOI:10.1147/rd.395.0575. с. 575 – 582.
21. Solomonik, Edgar и др. Communication-optimal parallel 2.5D matrix multiplication and LU factorization algorithms // Proceedings of the 17th international conference on Parallel processing Part II. 2011. DOI:10.1007/978-3-642-23397-5_10. с. 90 – 109.
22. Bosagh Zadeh, Reza, Carlsson, Gunnar. Dimension Independent Matrix Square Using MapReduce. Посетен на 12 юли 2014.