Английская Википедия:Computational complexity of matrix multiplication

Шаблон:Short description Шаблон:Unsolved In theoretical computer science, the computational complexity of matrix multiplication dictates how quickly the operation of matrix multiplication can be performed. Matrix multiplication algorithms are a central subroutine in theoretical and numerical algorithms for numerical linear algebra and optimization, so finding the fastest algorithm for matrix multiplication is of major practical relevance.

Directly applying the mathematical definition of matrix multiplication gives an algorithm that requires Шаблон:Math field operations to multiply two Шаблон:Math matrices over that field (Шаблон:Math in big O notation). Surprisingly, algorithms exist that provide better running times than this straightforward "schoolbook algorithm". The first to be discovered was Strassen's algorithm, devised by Volker Strassen in 1969 and often referred to as "fast matrix multiplication".^[1] The optimal number of field operations needed to multiply two square Шаблон:Math matrices up to constant factors is still unknown. This is a major open question in theoretical computer science.

Шаблон:As of, the best announced bound on the asymptotic complexity of a matrix multiplication algorithm is Шаблон:Math time, given by Williams, Xu, Xu, and Zhou,^[2] announced in a preprint. This improves on the bound of Шаблон:Math given by a preprint of Duan, Wu and Zhou.^[3] However, this and similar improvements to Strassen are not used in practice, because they are galactic algorithms: the constant coefficient hidden by the big O notation is so large that they are only worthwhile for matrices that are too large to handle on present-day computers.^[4]^[5] The best time-bound confirmed by peer review is Шаблон:Math.^[6]

Simple algorithms

If A, B are Шаблон:Math matrices over a field, then their product AB is also an Шаблон:Math matrix over that field, defined entrywise as

<math>

(AB)_{ij} = \sum_{k = 1}^n A_{ik} B_{kj}. </math>

Schoolbook algorithm

Шаблон:For

The simplest approach to computing the product of two Шаблон:Math matrices A and B is to compute the arithmetic expressions coming from the definition of matrix multiplication. In pseudocode:

input A and B, both n by n matrices
initialize C to be an n by n matrix of all zeros
for i from 1 to n:
    for j from 1 to n:
        for k from 1 to n:
            C[i][j] = C[i][j] + A[i][k]*B[k][j]
output C (as A*B)

This algorithm requires, in the worst case, Шаблон:Tmath multiplications of scalars and Шаблон:Tmath additions for computing the product of two square Шаблон:Math matrices. Its computational complexity is therefore Шаблон:Tmath, in a model of computation where field operations (addition and multiplication) take constant time (in practice, this is the case for floating point numbers, but not necessarily for integers).

Strassen's algorithm

Шаблон:Main Strassen's algorithm improves on naive matrix multiplication through a divide-and-conquer approach. The key observation is that multiplying two Шаблон:Math matrices can be done with only 7 multiplications, instead of the usual 8 (at the expense of 11 additional addition and subtraction operations). This means that, treating the input Шаблон:Math matrices as block Шаблон:Math matrices, the task of multiplying Шаблон:Math matrices can be reduced to 7 subproblems of multiplying Шаблон:Math matrices. Applying this recursively gives an algorithm needing <math>O( n^{\log_{2}7}) \approx O(n^{2.807})</math> field operations.

Unlike algorithms with faster asymptotic complexity, Strassen's algorithm is used in practice. The numerical stability is reduced compared to the naive algorithm,^[7] but it is faster in cases where Шаблон:Math or so^[8] and appears in several libraries, such as BLAS.^[9] Fast matrix multiplication algorithms cannot achieve component-wise stability, but some can be shown to exhibit norm-wise stability.^[10] It is very useful for large matrices over exact domains such as finite fields, where numerical stability is not an issue.

Matrix multiplication exponent

Файл:MatrixMultComplexity svg.svg

Improvement of estimates of exponent Шаблон:Math over time for the computational complexity of matrix multiplication <math>O(n^\omega)</math>

Файл:MatrixMultComplexity1990 svg.svg

Closeup of 1990–2023

Timeline of matrix multiplication exponent
Year	Bound on omega	Authors
1969	2.8074	Strassen^[1]
1978	2.796	Pan^[11]
1979	2.780	Bini, Шаблон:Ill, Romani^[12]
1981	2.522	Schönhage^[13]
1981	2.517	Romani^[14]
1981	2.496	Coppersmith, Winograd^[15]
1986	2.479	Strassen^[16]
1990	2.3755	Coppersmith, Winograd^[17]
2010	2.3737	Stothers^[18]
2012	2.3729	Williams^[19]^[20]
2014	2.3728639	Le Gall^[21]
2020	2.3728596	Alman, Williams^[6]^[22]
2022	2.371866	Duan, Wu, Zhou^[3]
2023	2.371552	Williams, Xu, Xu, and Zhou^[2]

The matrix multiplication exponent, usually denoted Шаблон:Math, is the smallest real number for which any two <math>n\times n</math> matrices over a field can be multiplied together using <math>n^{\omega + o(1)}</math> field operations. This notation is commonly used in algorithms research, so that algorithms using matrix multiplication as a subroutine have bounds on running time that can update as bounds on Шаблон:Math improve.

Using a naive lower bound and schoolbook matrix multiplication for the upper bound, one can straightforwardly conclude that Шаблон:Math. Whether Шаблон:Math is a major open question in theoretical computer science, and there is a line of research developing matrix multiplication algorithms to get improved bounds on Шаблон:Math.

All recent algorithms in this line of research use the laser method, a generalization of the Coppersmith–Winograd algorithm, which was given by Don Coppersmith and Shmuel Winograd in 1990 and was the best matrix multiplication algorithm until 2010.^[23] The conceptual idea of these algorithms is similar to Strassen's algorithm: a way is devised for multiplying two Шаблон:Math-matrices with fewer than Шаблон:Math multiplications, and this technique is applied recursively. The laser method has limitations to its power, and cannot be used to show that Шаблон:Math.^[24] Duan, Wu and Zhou identify a source of potential optimization in the laser method termed combination loss.^[3] They find a way to exploit this to devise a variant of the laser method which they use to show Шаблон:Math, breaking the barrier for any conventional laser method algorithm. With this newer approach another bound^[24] applies according to Duan, Wu and Zhou and showing Шаблон:Math will not be possible only addressing combination loss in the laser method.

Group theory reformulation of matrix multiplication algorithms

Henry Cohn, Robert Kleinberg, Balázs Szegedy and Chris Umans put methods such as the Strassen and Coppersmith–Winograd algorithms in an entirely different group-theoretic context, by utilising triples of subsets of finite groups which satisfy a disjointness property called the triple product property (TPP). They also give conjectures that, if true, would imply that there are matrix multiplication algorithms with essentially quadratic complexity. This implies that the optimal exponent of matrix multiplication is 2, which most researchers believe is indeed the case.^[5] One such conjecture is that families of wreath products of Abelian groups with symmetric groups realise families of subset triples with a simultaneous version of the TPP.^[25]^[26] Several of their conjectures have since been disproven by Blasiak, Cohn, Church, Grochow, Naslund, Sawin, and Umans using the Slice Rank method.^[27] Further, Alon, Shpilka and Chris Umans have recently shown that some of these conjectures implying fast matrix multiplication are incompatible with another plausible conjecture, the sunflower conjecture,^[28] which in turn is related to the cap set problem.^[27]

Lower bounds for ω

There is a trivial lower bound of Шаблон:Tmath. Since any algorithm for multiplying two Шаблон:Math-matrices has to process all Шаблон:Math entries, there is a trivial asymptotic lower bound of Шаблон:Math operations for any matrix multiplication algorithm. Thus Шаблон:Tmath. It is unknown whether Шаблон:Tmath. The best known lower bound for matrix-multiplication complexity is Шаблон:Math, for bounded coefficient arithmetic circuits over the real or complex numbers, and is due to Ran Raz.^[29]

The exponent ω is defined to be a limit point, in that it is the infimum of the exponent over all matrix multiplication algorithms. It is known that this limit point is not achieved. In other words, under the model of computation typically studied, there is no matrix multiplication algorithm that uses precisely Шаблон:Math operations; there must be an additional factor of Шаблон:Math.^[15]

Rectangular matrix multiplication

Similar techniques also apply to rectangular matrix multiplication. The central object of study is <math>\omega(k)</math>, which is the smallest <math>c</math> such that one can multiply a matrix of size <math>n\times \lceil n^k\rceil</math> with a matrix of size <math>\lceil n^k\rceil \times n</math> with <math>O(n^{c + o(1)})</math> arithmetic operations. A result in algebraic complexity states that multiplying matrices of size <math>n\times \lceil n^k\rceil</math> and <math>\lceil n^k\rceil \times n</math> requires the same number of arithmetic operations as multiplying matrices of size <math>n\times \lceil n^k\rceil</math> and <math>n \times n</math> and of size <math>n \times n</math> and <math>n\times \lceil n^k\rceil</math>, so this encompasses the complexity of rectangular matrix multiplication.^[30] This generalizes the square matrix multiplication exponent, since <math>\omega(1) = \omega</math>.

Since the output of the matrix multiplication problem is size <math>n^2</math>, we have <math>\omega(k) \geq 2</math> for all values of <math>k</math>. If one can prove for some values of <math>k</math> between 0 and 1 that <math>\omega(k) \leq 2</math>, then such a result shows that <math>\omega(k) = 2</math> for those <math>k</math>. The largest k such that <math>\omega(k) = 2</math> is known as the dual matrix multiplication exponent, usually denoted α. α is referred to as the "dual" because showing that <math>\alpha = 1</math> is equivalent to showing that <math>\omega = 2</math>. Like the matrix multiplication exponent, the dual matrix multiplication exponent sometimes appears in the complexity of algorithms in numerical linear algebra and optimization.^[31]

The first bound on α is by Coppersmith in 1982, who showed that <math>\alpha > 0.17227</math>.^[32] The current best peer-reviewed bound on α is <math>\alpha > 0.31389</math>, given by Le Gall and Urrutia.^[33] This paper also contains bounds on <math>\omega(k)</math>. In July 2023 Williams, Xu, Xu, and Zhou claim to show <math>\alpha \geq 0.321334</math> in a preprint.^[2]

Related problems

Шаблон:Further

Problems that have the same asymptotic complexity as matrix multiplication include determinant, matrix inversion, Gaussian elimination (see next section). Problems with complexity that is expressible in terms of <math>\omega</math> include characteristic polynomial, eigenvalues (but not eigenvectors), Hermite normal form, and Smith normal form.Шаблон:Citation needed

Matrix inversion, determinant and Gaussian elimination

In his 1969 paper, where he proved the complexity <math>O(n^{\log_2 7}) \approx O(n^{2.807})</math> for matrix computation, Strassen proved also that matrix inversion, determinant and Gaussian elimination have, up to a multiplicative constant, the same computational complexity as matrix multiplication. The proof does not make any assumptions on matrix multiplication that is used, except that its complexity is <math>O(n^\omega)</math> for some <math>\omega \ge 2</math>

The starting point of Strassen's proof is using block matrix multiplication. Specifically, a matrix of even dimension Шаблон:Math may be partitioned in four Шаблон:Math blocks

<math>\begin{bmatrix} {A} & {B} \\{C} & {D} \end{bmatrix}.</math>

Under this form, its inverse is

<math>

\begin{bmatrix} {A} & {B} \\ {C} & {D} \end{bmatrix}^{-1} = \begin{bmatrix} {A}^{-1}+{A}^{-1}{B}({D}-{CA}^{-1}{B})^{-1}{CA}^{-1} & -{A}^{-1}{B}({D}-{CA}^{-1}{B})^{-1} \\ -({D}-{CA}^{-1}{B})^{-1}{CA}^{-1} & ({D}-{CA}^{-1}{B})^{-1} \end{bmatrix}, </math> provided that Шаблон:Mvar and <math>{D}-{CA}^{-1}{B}</math> are invertible.

Thus, the inverse of a Шаблон:Math matrix may be computed with two inversions, six multiplications and four additions or additive inverses of Шаблон:Math matrices. It follows that, denoting respectively by Шаблон:Math, Шаблон:Math and Шаблон:Math the number of operations needed for inverting, multiplying and adding Шаблон:Math matrices, one has

If <math>n=2^k,</math> one may apply this formula recursively:

<math>\begin{align}

I(2^k) &\le 2I(2^{k-1}) + 6M(2^{k-1})+ 4 A(2^{k-1})\\ &\le 2^2I(2^{k-2}) + 6(M(2^{k-1})+2M(2^{k-2})) + 4(A(2^{k-1}) + 2A(2^{k-2}))\\ &\,\,\,\vdots \end{align}</math> If <math>M(n)\le cn^\omega,</math> and <math>\alpha=2^\omega\ge 4,</math> one gets eventually

<math>\begin{align}

I(2^k) &\le 2^k I(1) + 6c(\alpha^{k-1}+2\alpha^{k-2} + \cdots +2^{k-1}\alpha^0) + k 2^{k+1}\\ &\le 2^k + 6c\frac{\alpha^k-2^k}{\alpha-2} + k 2^{k+1}\\ &\le d(2^k)^\omega \end{align}</math> for some constant Шаблон:Mvar.

For matrices whose dimension is not a power of two, the same complexity is reached by increasing the dimension of the matrix to a power of two, by padding the matrix with rows and columns whose entries are 1 on the diagonal and 0 elsewhere.

This proves the asserted complexity for matrices such that all submatrices that have to be inverted are indeed invertible. This complexity is thus proved for almost all matrices, as a matrix with randomly chosen entries is invertible with probability one.

The same argument applies to LU decomposition, as, if the matrix Шаблон:Mvar is invertible, the equality

<math>\begin{bmatrix} {A} & {B} \\{C} & {D} \end{bmatrix}

= \begin{bmatrix}I & 0\\CA^{-1}&I\end{bmatrix}\,\begin{bmatrix}A&B\\0&D-CA^{-1}B\end{bmatrix}</math> defines a block LU decomposition that may be applied recursively to <math>A</math> and <math>D-CA^{-1}B,</math> for getting eventually a true LU decomposition of the original matrix.

The argument applies also for the determinant, since it results from the block LU decomposition that

<math>\det \begin{bmatrix} {A} & {B} \\{C} & {D} \end{bmatrix} =

\det(A)\det(D-CA^{-1}B).</math>

Minimizing number of multiplications

Related to the problem of minimizing the number of arithmetic operations is minimizing the number of multiplications, which is typically a more costly operation than addition. A <math>O(n^\omega)</math> algorithm for matrix multiplication must necessarily only use <math>O(n^\omega)</math> multiplication operations, but these algorithms are impractical. Improving from the naive <math>n^3</math> multiplications for schoolbook multiplication, <math>4\times 4</math> matrices in <math>\mathbb{Z}/2\mathbb{Z}</math> can be done with 47 multiplications,^[34] <math>3\times 3</math> matrix multiplication over a commutative ring can be done in 21 multiplications^[35]^[36] (23 if non-commutative^[37]). The lower bound of multiplications needed is 2mn+2n−m−2 (multiplication of n×m-matrices with m×n-matrices using the substitution method, m⩾n⩾3), which means n=3 case requires at least 19 multiplications and n=4 at least 34.^[38] For n=2 optimal 7 multiplications 15 additions are minimal, compared to only 4 additions for 8 multiplications.^[39]^[40]

References

Шаблон:Reflist

External links

[strassen69-1] 1,0 ^1,1 Шаблон:Cite journal

[wxxz23-2] 2,0 ^2,1 ^2,2 Шаблон:Cite arXiv

[dwz22-3] 3,0 ^3,1 ^3,2 Шаблон:Cite arXiv

[4] Шаблон:Cite journal

[robinson-5] 5,0 ^5,1 Шаблон:Cite journal

[aw20-6] 6,0 ^6,1 Шаблон:Cite book

[7] Шаблон:Cite journal

[skiena-8] Шаблон:Cite book

[9] Шаблон:Cite book

[bdl16-10] Шаблон:Cite journal

[11] Шаблон:Cite book

[12] Шаблон:Cite journal

[13] Шаблон:Cite journal

[14] Шаблон:Cite journal

[CW.81-15] 15,0 ^15,1 Шаблон:Cite book

[16] Шаблон:Cite book

[17] Шаблон:Cite journal

[18] Шаблон:Cite thesis

[19] Шаблон:Cite book

[Williams.2014-20] Шаблон:Cite report

[LeGall2014-21] Шаблон:Cite book

[22] Шаблон:Cite web

[coppersmith-23] Шаблон:Cite journal

[afl14-24] 24,0 ^24,1 Шаблон:Cite book

[25] Шаблон:Cite book

[26] Шаблон:Cite book

[:0-27] 27,0 ^27,1 Шаблон:Cite book

[28] Шаблон:Cite journal

[29] Шаблон:Cite book

[gall18-30] Шаблон:Cite book

[31] Шаблон:Cite journal

[32] Шаблон:Cite journal

[33] Шаблон:Cite book

[34] See Extended Data Fig. 1: Algorithm for multiplying 4 × 4 matrices in modular arithmetic (<math>\mathbb{Z}_{2}</math>)) with 47 multiplications in Шаблон:Cite journal

[35] Шаблон:Cite journal

[36] Шаблон:Cite journal
Also in Шаблон:Cite journal

[37] Шаблон:Cite journal

[38] Шаблон:Cite journal

[39] Шаблон:Cite journal

[40] Шаблон:Cite book

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.

Английская Википедия:Computational complexity of matrix multiplication

Содержание