Strassen algorithm - Revision history

2603:8001:8C00:55E0:6126:567A:6DBC:B337: Original improved Strassen algorithm missed the basis change described in the 2023 paper, and therefore yielded incorrect results. Basis change has been added to the algorithm description.

2025-05-31T23:26:28Z

Original improved Strassen algorithm missed the basis change described in the 2023 paper, and therefore yielded incorrect results. Basis change has been added to the algorithm description.

← Previous revision		Revision as of 23:26, 31 May 2025
Line 107:		Line 107:
	This reduces the number of matrix additions and subtractions from 18 to 15. The number of matrix multiplications is still 7, and the asymptotic complexity is the same.{{sfnp\|Knuth\|1997\|p=500}}		This reduces the number of matrix additions and subtractions from 18 to 15. The number of matrix multiplications is still 7, and the asymptotic complexity is the same.{{sfnp\|Knuth\|1997\|p=500}}

	The algorithm was further optimised in 2017,<ref>{{Cite book \|last1=Karstadt \|first1=Elaye \|last2=Schwartz \|first2=Oded \|chapter=Matrix Multiplication, a Little Faster \|date=2017-07-24 \|title=Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures \|chapter-url=https://dl.acm.org/doi/10.1145/3087556.3087579 \|language=en \|publisher=ACM \|pages=101–110 \|doi=10.1145/3087556.3087579 \|isbn=978-1-4503-4593-4}}</ref> reducing the number of matrix additions per step to 12 while maintaining the number of matrix multiplications, and again in 2023:<ref>{{Cite journal \|last1=Schwartz \|first1=Oded \|last2=Vaknin \|first2=Noa \|date=2023-12-31 \|title=Pebbling Game and Alternative Basis for High Performance Matrix Multiplication \|url=https://epubs.siam.org/doi/10.1137/22M1502719 \|journal=SIAM Journal on Scientific Computing \|language=en \|volume=45 \|issue=6 \|pages=C277–C303 \|doi=10.1137/22M1502719 \|bibcode=2023SJSC...45C.277S \|issn=1064-8275\|url-access=subscription }}</ref>		The algorithm was further optimised in 2017 using an alternative basis,<ref>{{Cite book \|last1=Karstadt \|first1=Elaye \|last2=Schwartz \|first2=Oded \|chapter=Matrix Multiplication, a Little Faster \|date=2017-07-24 \|title=Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures \|chapter-url=https://dl.acm.org/doi/10.1145/3087556.3087579 \|language=en \|publisher=ACM \|pages=101–110 \|doi=10.1145/3087556.3087579 \|isbn=978-1-4503-4593-4}}</ref> reducing the number of matrix additions per bilinear step to 12 while maintaining the number of matrix multiplications, and again in 2023:<ref>{{Cite journal \|last1=Schwartz \|first1=Oded \|last2=Vaknin \|first2=Noa \|date=2023-12-31 \|title=Pebbling Game and Alternative Basis for High Performance Matrix Multiplication \|url=https://epubs.siam.org/doi/10.1137/22M1502719 \|journal=SIAM Journal on Scientific Computing \|language=en \|volume=45 \|issue=6 \|pages=C277–C303 \|doi=10.1137/22M1502719 \|bibcode=2023SJSC...45C.277S \|issn=1064-8275\|url-access=subscription }}</ref>

			<math>
			\begin{align}
			A_{22} &= A_{12} - A_{21} + A_{22}; \\
			B_{22} &= B_{12} - B_{21} + B_{22},
			\end{align}
			</math>

	{{col-begin}}		{{col-begin}}
Line 143:		Line 150:
	</math>		</math>
	{{col-end}}		{{col-end}}
			<math>
			\begin{align}
			C_{12} &= C_{12} - C_{22}; \\
			C_{21} &= C_{22} - C_{21},
			\end{align}
			</math>

	== Asymptotic complexity ==		== Asymptotic complexity ==

OAbot: Open access bot: url-access updated in citation with #oabot.

2025-05-26T00:01:23Z

Open access bot: url-access updated in citation with #oabot.

← Previous revision		Revision as of 00:01, 26 May 2025
Line 107:		Line 107:
	This reduces the number of matrix additions and subtractions from 18 to 15. The number of matrix multiplications is still 7, and the asymptotic complexity is the same.{{sfnp\|Knuth\|1997\|p=500}}		This reduces the number of matrix additions and subtractions from 18 to 15. The number of matrix multiplications is still 7, and the asymptotic complexity is the same.{{sfnp\|Knuth\|1997\|p=500}}

	The algorithm was further optimised in 2017,<ref>{{Cite book \|last1=Karstadt \|first1=Elaye \|last2=Schwartz \|first2=Oded \|chapter=Matrix Multiplication, a Little Faster \|date=2017-07-24 \|title=Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures \|chapter-url=https://dl.acm.org/doi/10.1145/3087556.3087579 \|language=en \|publisher=ACM \|pages=101–110 \|doi=10.1145/3087556.3087579 \|isbn=978-1-4503-4593-4}}</ref> reducing the number of matrix additions per step to 12 while maintaining the number of matrix multiplications, and again in 2023:<ref>{{Cite journal \|last1=Schwartz \|first1=Oded \|last2=Vaknin \|first2=Noa \|date=2023-12-31 \|title=Pebbling Game and Alternative Basis for High Performance Matrix Multiplication \|url=https://epubs.siam.org/doi/10.1137/22M1502719 \|journal=SIAM Journal on Scientific Computing \|language=en \|volume=45 \|issue=6 \|pages=C277–C303 \|doi=10.1137/22M1502719 \|bibcode=2023SJSC...45C.277S \|issn=1064-8275}}</ref>		The algorithm was further optimised in 2017,<ref>{{Cite book \|last1=Karstadt \|first1=Elaye \|last2=Schwartz \|first2=Oded \|chapter=Matrix Multiplication, a Little Faster \|date=2017-07-24 \|title=Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures \|chapter-url=https://dl.acm.org/doi/10.1145/3087556.3087579 \|language=en \|publisher=ACM \|pages=101–110 \|doi=10.1145/3087556.3087579 \|isbn=978-1-4503-4593-4}}</ref> reducing the number of matrix additions per step to 12 while maintaining the number of matrix multiplications, and again in 2023:<ref>{{Cite journal \|last1=Schwartz \|first1=Oded \|last2=Vaknin \|first2=Noa \|date=2023-12-31 \|title=Pebbling Game and Alternative Basis for High Performance Matrix Multiplication \|url=https://epubs.siam.org/doi/10.1137/22M1502719 \|journal=SIAM Journal on Scientific Computing \|language=en \|volume=45 \|issue=6 \|pages=C277–C303 \|doi=10.1137/22M1502719 \|bibcode=2023SJSC...45C.277S \|issn=1064-8275\|url-access=subscription }}</ref>

	{{col-begin}}		{{col-begin}}

DDavo: /* Improvements to Strassen algorithm */

2025-01-13T16:05:19Z

Improvements to Strassen algorithm

← Previous revision		Revision as of 16:05, 13 January 2025
Line 107:		Line 107:
	This reduces the number of matrix additions and subtractions from 18 to 15. The number of matrix multiplications is still 7, and the asymptotic complexity is the same.{{sfnp\|Knuth\|1997\|p=500}}		This reduces the number of matrix additions and subtractions from 18 to 15. The number of matrix multiplications is still 7, and the asymptotic complexity is the same.{{sfnp\|Knuth\|1997\|p=500}}

	The algorithm was further optimised in 2017,<ref>{{Cite book \|last1=Karstadt \|first1=Elaye \|last2=Schwartz \|first2=Oded \|chapter=Matrix Multiplication, a Little Faster \|date=2017-07-24 \|title=Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures \|chapter-url=https://dl.acm.org/doi/10.1145/3087556.3087579 \|language=en \|publisher=ACM \|pages=101–110 \|doi=10.1145/3087556.3087579 \|isbn=978-1-4503-4593-4}}</ref> reducing the number of matrix additions per step to 12 while maintaining the number of matrix multiplications, and again in 2023.<ref>{{Cite journal \|last1=Schwartz \|first1=Oded \|last2=Vaknin \|first2=Noa \|date=2023-12-31 \|title=Pebbling Game and Alternative Basis for High Performance Matrix Multiplication \|url=https://epubs.siam.org/doi/10.1137/22M1502719 \|journal=SIAM Journal on Scientific Computing \|language=en \|volume=45 \|issue=6 \|pages=C277–C303 \|doi=10.1137/22M1502719 \|bibcode=2023SJSC...45C.277S \|issn=1064-8275}}</ref>		The algorithm was further optimised in 2017,<ref>{{Cite book \|last1=Karstadt \|first1=Elaye \|last2=Schwartz \|first2=Oded \|chapter=Matrix Multiplication, a Little Faster \|date=2017-07-24 \|title=Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures \|chapter-url=https://dl.acm.org/doi/10.1145/3087556.3087579 \|language=en \|publisher=ACM \|pages=101–110 \|doi=10.1145/3087556.3087579 \|isbn=978-1-4503-4593-4}}</ref> reducing the number of matrix additions per step to 12 while maintaining the number of matrix multiplications, and again in 2023:<ref>{{Cite journal \|last1=Schwartz \|first1=Oded \|last2=Vaknin \|first2=Noa \|date=2023-12-31 \|title=Pebbling Game and Alternative Basis for High Performance Matrix Multiplication \|url=https://epubs.siam.org/doi/10.1137/22M1502719 \|journal=SIAM Journal on Scientific Computing \|language=en \|volume=45 \|issue=6 \|pages=C277–C303 \|doi=10.1137/22M1502719 \|bibcode=2023SJSC...45C.277S \|issn=1064-8275}}</ref>

	{{col-begin}}		{{col-begin}}

DDavo: Added formulas for Schwartz's 12 sums algorithm

2025-01-13T16:03:27Z

Added formulas for Schwartz's 12 sums algorithm

@@ Line 53: / Line 53: @@
 The Strassen algorithm defines instead new values:
-: <math>
+: <math>\begin{align}
 M_1 &= (A_{11} + A_{22}) {\color{red}\times} (B_{11} + B_{22}); \\
 M_2 &= (A_{21} + A_{22}) {\color{red}\times} B_{11}; \\
@@ Line 62: / Line 61: @@
 M_6 &= (A_{21} - A_{11}) {\color{red}\times} (B_{11} + B_{12}); \\
 M_7 &= (A_{12} - A_{22}) {\color{red}\times} (B_{21} + B_{22}), \\
-\end{align}
+\end{align}</math>
 using only 7 multiplications (one for each <math>M_k</math>) instead of 8. We may now express the <math>C_{ij}</math> in terms of <math>M_k</math>:
@@ Line 110: / Line 108: @@
 The algorithm was further optimised in 2017,<ref>{{Cite book |last1=Karstadt |first1=Elaye |last2=Schwartz |first2=Oded |chapter=Matrix Multiplication, a Little Faster |date=2017-07-24 |title=Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures |chapter-url=https://dl.acm.org/doi/10.1145/3087556.3087579 |language=en |publisher=ACM |pages=101–110 |doi=10.1145/3087556.3087579 |isbn=978-1-4503-4593-4}}</ref> reducing the number of matrix additions per step to 12 while maintaining the number of matrix multiplications, and again in 2023.<ref>{{Cite journal |last1=Schwartz |first1=Oded |last2=Vaknin |first2=Noa |date=2023-12-31 |title=Pebbling Game and Alternative Basis for High Performance Matrix Multiplication |url=https://epubs.siam.org/doi/10.1137/22M1502719 |journal=SIAM Journal on Scientific Computing |language=en |volume=45 |issue=6 |pages=C277–C303 |doi=10.1137/22M1502719 |bibcode=2023SJSC...45C.277S |issn=1064-8275}}</ref>
 == Asymptotic complexity ==

2601:249:4200:718:43AB:8395:EB68:E366: /* Improvements to Strassen algorithm */Fixed two typos.

2024-12-19T23:27:59Z

Improvements to Strassen algorithm: Fixed two typos.

← Previous revision		Revision as of 23:27, 19 December 2024
Line 109:		Line 109:
	This reduces the number of matrix additions and subtractions from 18 to 15. The number of matrix multiplications is still 7, and the asymptotic complexity is the same.{{sfnp\|Knuth\|1997\|p=500}}		This reduces the number of matrix additions and subtractions from 18 to 15. The number of matrix multiplications is still 7, and the asymptotic complexity is the same.{{sfnp\|Knuth\|1997\|p=500}}

	The algorithm was further optimised in 2017,<ref>{{Cite book \|last1=Karstadt \|first1=Elaye \|last2=Schwartz \|first2=Oded \|chapter=Matrix Multiplication, a Little Faster \|date=2017-07-24 \|title=Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures \|chapter-url=https://dl.acm.org/doi/10.1145/3087556.3087579 \|language=en \|publisher=ACM \|pages=101–110 \|doi=10.1145/3087556.3087579 \|isbn=978-1-4503-4593-4}}</ref> reducing the number of matrix additions per step to 12 while ~~maintainging~~ the ~~numer~~ of matrix multiplications, and again in 2023.<ref>{{Cite journal \|last1=Schwartz \|first1=Oded \|last2=Vaknin \|first2=Noa \|date=2023-12-31 \|title=Pebbling Game and Alternative Basis for High Performance Matrix Multiplication \|url=https://epubs.siam.org/doi/10.1137/22M1502719 \|journal=SIAM Journal on Scientific Computing \|language=en \|volume=45 \|issue=6 \|pages=C277–C303 \|doi=10.1137/22M1502719 \|bibcode=2023SJSC...45C.277S \|issn=1064-8275}}</ref>		The algorithm was further optimised in 2017,<ref>{{Cite book \|last1=Karstadt \|first1=Elaye \|last2=Schwartz \|first2=Oded \|chapter=Matrix Multiplication, a Little Faster \|date=2017-07-24 \|title=Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures \|chapter-url=https://dl.acm.org/doi/10.1145/3087556.3087579 \|language=en \|publisher=ACM \|pages=101–110 \|doi=10.1145/3087556.3087579 \|isbn=978-1-4503-4593-4}}</ref> reducing the number of matrix additions per step to 12 while maintaining the number of matrix multiplications, and again in 2023.<ref>{{Cite journal \|last1=Schwartz \|first1=Oded \|last2=Vaknin \|first2=Noa \|date=2023-12-31 \|title=Pebbling Game and Alternative Basis for High Performance Matrix Multiplication \|url=https://epubs.siam.org/doi/10.1137/22M1502719 \|journal=SIAM Journal on Scientific Computing \|language=en \|volume=45 \|issue=6 \|pages=C277–C303 \|doi=10.1137/22M1502719 \|bibcode=2023SJSC...45C.277S \|issn=1064-8275}}</ref>

	== Asymptotic complexity ==		== Asymptotic complexity ==

Citation bot: Alter: journal, title, template type. Add: bibcode, chapter-url, chapter, authors 1-1. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox2 | #UCB_webform_linked 254/332

2024-12-13T01:31:54Z

Alter: journal, title, template type. Add: bibcode, chapter-url, chapter, authors 1-1. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox2 | #UCB_webform_linked 254/332

← Previous revision		Revision as of 01:31, 13 December 2024
Line 87:		Line 87:
	== Improvements to Strassen algorithm ==		== Improvements to Strassen algorithm ==
	{{Further information\|Matrix multiplication algorithm#Sub-cubic algorithms\|Computational complexity of matrix multiplication}}		{{Further information\|Matrix multiplication algorithm#Sub-cubic algorithms\|Computational complexity of matrix multiplication}}
	It is possible to reduce the number of matrix additions by instead using the following form discovered by Winograd in 1971:<ref>{{Cite journal \|last=Winograd \|first=S. \|date=October 1971 \|title=On multiplication of 2 × 2 matrices \|url=https://linkinghub.elsevier.com/retrieve/pii/0024379571900097 \|journal=Linear Algebra and ~~its~~ Applications \|language=en \|volume=4 \|issue=4 \|pages=381–388 \|doi=10.1016/0024-3795(71)90009-7}}</ref>		It is possible to reduce the number of matrix additions by instead using the following form discovered by Winograd in 1971:<ref>{{Cite journal \|last=Winograd \|first=S. \|date=October 1971 \|title=On multiplication of 2 × 2 matrices \|url=https://linkinghub.elsevier.com/retrieve/pii/0024379571900097 \|journal=Linear Algebra and Its Applications \|language=en \|volume=4 \|issue=4 \|pages=381–388 \|doi=10.1016/0024-3795(71)90009-7}}</ref>

	<math>		<math>
Line 109:		Line 109:
	This reduces the number of matrix additions and subtractions from 18 to 15. The number of matrix multiplications is still 7, and the asymptotic complexity is the same.{{sfnp\|Knuth\|1997\|p=500}}		This reduces the number of matrix additions and subtractions from 18 to 15. The number of matrix multiplications is still 7, and the asymptotic complexity is the same.{{sfnp\|Knuth\|1997\|p=500}}

	The algorithm was further optimised in 2017,<ref>{{Cite ~~journal~~ \|~~last~~=Karstadt \|~~first~~=Elaye \|last2=Schwartz \|first2=Oded \|~~date=2017-07-24 \|title~~=Matrix Multiplication, a Little Faster \|~~url~~=~~https://dl.acm.org/doi/10.1145/3087556.3087579~~ \|~~journal~~=In Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures ~~(SPAA '17)~~ \|language=en \|publisher=ACM \|pages=101–110 \|doi=10.1145/3087556.3087579 \|isbn=978-1-4503-4593-4}}</ref> reducing the number of matrix additions per step to 12 while maintainging the numer of matrix multiplications, and again in 2023.<ref>{{Cite journal \|~~last~~=Schwartz \|~~first~~=Oded \|last2=Vaknin \|first2=Noa \|date=2023-12-31 \|title=Pebbling Game and Alternative Basis for High Performance Matrix Multiplication \|url=https://epubs.siam.org/doi/10.1137/22M1502719 \|journal=SIAM Journal on Scientific Computing \|language=en \|volume=45 \|issue=6 \|pages=C277–C303 \|doi=10.1137/22M1502719 \|issn=1064-8275}}</ref>		The algorithm was further optimised in 2017,<ref>{{Cite book \|last1=Karstadt \|first1=Elaye \|last2=Schwartz \|first2=Oded \|chapter=Matrix Multiplication, a Little Faster \|date=2017-07-24 \|title=Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures \|chapter-url=https://dl.acm.org/doi/10.1145/3087556.3087579 \|language=en \|publisher=ACM \|pages=101–110 \|doi=10.1145/3087556.3087579 \|isbn=978-1-4503-4593-4}}</ref> reducing the number of matrix additions per step to 12 while maintainging the numer of matrix multiplications, and again in 2023.<ref>{{Cite journal \|last1=Schwartz \|first1=Oded \|last2=Vaknin \|first2=Noa \|date=2023-12-31 \|title=Pebbling Game and Alternative Basis for High Performance Matrix Multiplication \|url=https://epubs.siam.org/doi/10.1137/22M1502719 \|journal=SIAM Journal on Scientific Computing \|language=en \|volume=45 \|issue=6 \|pages=C277–C303 \|doi=10.1137/22M1502719 \|bibcode=2023SJSC...45C.277S \|issn=1064-8275}}</ref>

	== Asymptotic complexity ==		== Asymptotic complexity ==

GoingBatty: General fixes, replaced: 1971 → 1971 (3)

2024-12-02T15:19:12Z

General fixes, replaced: 1971 → 1971 (3)

← Previous revision		Revision as of 15:19, 2 December 2024
Line 2:		Line 2:
	{{distinguish\|text=the [[Schönhage–Strassen algorithm]] for multiplication of polynomials}}		{{distinguish\|text=the [[Schönhage–Strassen algorithm]] for multiplication of polynomials}}

	In [[linear algebra]], the '''Strassen algorithm''', named after [[Volker Strassen]], is an [[Matrix multiplication algorithm\|algorithm for matrix multiplication]]. It is faster than the standard matrix multiplication algorithm for large matrices, with a better [[asymptotic complexity]], although the naive algorithm is often better for smaller matrices. The Strassen algorithm is slower than [[Computational complexity of matrix multiplication\|the fastest known algorithms]] for extremely large matrices, but such [[~~Galactic~~ algorithm~~\|galactic algorithms~~]] are not useful in practice, as they are much slower for matrices of practical size. For small matrices even faster algorithms exist.		In [[linear algebra]], the '''Strassen algorithm''', named after [[Volker Strassen]], is an [[Matrix multiplication algorithm\|algorithm for matrix multiplication]]. It is faster than the standard matrix multiplication algorithm for large matrices, with a better [[asymptotic complexity]], although the naive algorithm is often better for smaller matrices. The Strassen algorithm is slower than [[Computational complexity of matrix multiplication\|the fastest known algorithms]] for extremely large matrices, but such [[galactic algorithm]]s are not useful in practice, as they are much slower for matrices of practical size. For small matrices even faster algorithms exist.

	Strassen's algorithm works for any [[ring (mathematics)\|ring]], such as plus/multiply, but not all [[semirings]], such as [[Min-plus matrix multiplication\|min-plus]] or [[boolean algebra]], where the naive algorithm still works, and so called [[combinatorial matrix multiplication]].		Strassen's algorithm works for any [[ring (mathematics)\|ring]], such as plus/multiply, but not all [[semirings]], such as [[Min-plus matrix multiplication\|min-plus]] or [[boolean algebra]], where the naive algorithm still works, and so called [[combinatorial matrix multiplication]].
Line 87:		Line 87:
	== Improvements to Strassen algorithm ==		== Improvements to Strassen algorithm ==
	{{Further information\|Matrix multiplication algorithm#Sub-cubic algorithms\|Computational complexity of matrix multiplication}}		{{Further information\|Matrix multiplication algorithm#Sub-cubic algorithms\|Computational complexity of matrix multiplication}}
	It is possible to reduce the number of matrix additions by instead using the following form discovered by Winograd in [[1971]]:<ref>{{Cite journal \|last=Winograd \|first=S. \|date=October 1971 \|title=On multiplication of 2 × 2 matrices \|url=https://linkinghub.elsevier.com/retrieve/pii/0024379571900097 \|journal=Linear Algebra and its Applications \|language=en \|volume=4 \|issue=4 \|pages=381–388 \|doi=10.1016/0024-3795(71)90009-7}}</ref>		It is possible to reduce the number of matrix additions by instead using the following form discovered by Winograd in 1971:<ref>{{Cite journal \|last=Winograd \|first=S. \|date=October 1971 \|title=On multiplication of 2 × 2 matrices \|url=https://linkinghub.elsevier.com/retrieve/pii/0024379571900097 \|journal=Linear Algebra and its Applications \|language=en \|volume=4 \|issue=4 \|pages=381–388 \|doi=10.1016/0024-3795(71)90009-7}}</ref>

	<math>		<math>
Line 105:		Line 105:
	</math>		</math>

	where <math>t = a{\color{red}\times}A, \; u = (c - a){\color{red}\times}(C - D), \; v = (c + d){\color{red}\times}(C - A), \; w = t + (c + d - a){\color{red}\times}(A + D - C)</math>.		where <math>t = a{\color{red}\times}A, \; u = (c - a){\color{red}\times}(C - D), \; v = (c + d){\color{red}\times}(C - A), \; w = t + (c + d - a){\color{red}\times}(A + D - C)</math>.

	This reduces the number of matrix additions and subtractions from 18 to 15. The number of matrix multiplications is still 7, and the asymptotic complexity is the same.{{sfnp\|Knuth\|1997\|p=500}}		This reduces the number of matrix additions and subtractions from 18 to 15. The number of matrix multiplications is still 7, and the asymptotic complexity is the same.{{sfnp\|Knuth\|1997\|p=500}}

	The algorithm was further optimised in [[2017]]<ref>{{Cite journal \|last=Karstadt \|first=Elaye \|last2=Schwartz \|first2=Oded \|date=2017-07-24 \|title=Matrix Multiplication, a Little Faster \|url=https://dl.acm.org/doi/10.1145/3087556.3087579 \|journal=In Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '17) \|language=en \|publisher=ACM \|pages=101–110 \|doi=10.1145/3087556.3087579 \|isbn=978-1-4503-4593-4}}</ref>, reducing the number of matrix additions per step to 12 while maintainging the numer of matrix multiplications, and again in [[2023]]<ref>{{Cite journal \|last=Schwartz \|first=Oded \|last2=Vaknin \|first2=Noa \|date=2023-12-31 \|title=Pebbling Game and Alternative Basis for High Performance Matrix Multiplication \|url=https://epubs.siam.org/doi/10.1137/22M1502719 \|journal=SIAM Journal on Scientific Computing \|language=en \|volume=45 \|issue=6 \|pages=C277–C303 \|doi=10.1137/22M1502719 \|issn=1064-8275}}</ref>.		The algorithm was further optimised in 2017,<ref>{{Cite journal \|last=Karstadt \|first=Elaye \|last2=Schwartz \|first2=Oded \|date=2017-07-24 \|title=Matrix Multiplication, a Little Faster \|url=https://dl.acm.org/doi/10.1145/3087556.3087579 \|journal=In Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '17) \|language=en \|publisher=ACM \|pages=101–110 \|doi=10.1145/3087556.3087579 \|isbn=978-1-4503-4593-4}}</ref> reducing the number of matrix additions per step to 12 while maintainging the numer of matrix multiplications, and again in 2023.<ref>{{Cite journal \|last=Schwartz \|first=Oded \|last2=Vaknin \|first2=Noa \|date=2023-12-31 \|title=Pebbling Game and Alternative Basis for High Performance Matrix Multiplication \|url=https://epubs.siam.org/doi/10.1137/22M1502719 \|journal=SIAM Journal on Scientific Computing \|language=en \|volume=45 \|issue=6 \|pages=C277–C303 \|doi=10.1137/22M1502719 \|issn=1064-8275}}</ref>

	== Asymptotic complexity ==		== Asymptotic complexity ==
Line 215:		Line 215:

	== Implementation considerations ==		== Implementation considerations ==
	{{~~refimprove~~ section\|date=January 2015}}		{{more citations needed section\|date=January 2015}}
	The description above states that the matrices are square, and the size is a power of two, and that padding should be used if needed. This restriction allows the matrices to be split in half, recursively, until limit of scalar multiplication is reached. The restriction simplifies the explanation, and analysis of complexity, but is not actually necessary;<ref>{{cite journal \|last=Higham \|first=Nicholas J. \|title=Exploiting fast matrix multiplication within the level 3 BLAS \|journal=ACM Transactions on Mathematical Software \|volume=16 \|issue=4 \|year=1990 \|pages=352–368 \|url=http://www.maths.manchester.ac.uk/~higham/papers/high90s.pdf \|doi=10.1145/98267.98290\|hdl=1813/6900 \|s2cid=5715053 \|hdl-access=free }}</ref>		The description above states that the matrices are square, and the size is a power of two, and that padding should be used if needed. This restriction allows the matrices to be split in half, recursively, until limit of scalar multiplication is reached. The restriction simplifies the explanation, and analysis of complexity, but is not actually necessary;<ref>{{cite journal \|last=Higham \|first=Nicholas J. \|title=Exploiting fast matrix multiplication within the level 3 BLAS \|journal=ACM Transactions on Mathematical Software \|volume=16 \|issue=4 \|year=1990 \|pages=352–368 \|url=http://www.maths.manchester.ac.uk/~higham/papers/high90s.pdf \|doi=10.1145/98267.98290\|hdl=1813/6900 \|s2cid=5715053 \|hdl-access=free }}</ref>
	and in fact, padding the matrix as described will increase the computation time and can easily eliminate the fairly narrow time savings obtained by using the method in the first place.		and in fact, padding the matrix as described will increase the computation time and can easily eliminate the fairly narrow time savings obtained by using the method in the first place.
Line 239:		Line 239:
	* [[Z-order curve]]		* [[Z-order curve]]
	* [[Karatsuba algorithm]], for multiplying ''n''-digit integers in <math>O(n^{\log_2 3})</math> instead of in <math>O(n^2)</math> time		* [[Karatsuba algorithm]], for multiplying ''n''-digit integers in <math>O(n^{\log_2 3})</math> instead of in <math>O(n^2)</math> time
	** A similar [[Multiplication algorithm#~~Complex_number_multiplication~~\|complex multiplication algorithm]] multiplies two complex numbers using 3 real multiplications instead of 4		** A similar [[Multiplication algorithm#Complex number multiplication\|complex multiplication algorithm]] multiplies two complex numbers using 3 real multiplications instead of 4
	* [[Toom–Cook multiplication\|Toom-Cook algorithm]], a faster generalization of the Karatsuba algorithm that permits recursive divide-and-conquer decomposition into more than 2 blocks at a time		* [[Toom–Cook multiplication\|Toom-Cook algorithm]], a faster generalization of the Karatsuba algorithm that permits recursive divide-and-conquer decomposition into more than 2 blocks at a time

TheBooker66: Expanding article: /* Winograd form / --> / Improvements to Strassen algorithm */

2024-11-28T14:42:34Z

Expanding article: Winograd form: --> Improvements to Strassen algorithm

← Previous revision		Revision as of 14:42, 28 November 2024
Line 85:		Line 85:
	Practical implementations of Strassen's algorithm switch to standard methods of matrix multiplication for small enough submatrices, for which those algorithms are more efficient. The particular crossover point for which Strassen's algorithm is more efficient depends on the specific implementation and hardware. Earlier authors had estimated that Strassen's algorithm is faster for matrices with widths from 32 to 128 for optimized implementations.<ref>{{Citation \| last1=Skiena \| first1=Steven S. \| title=The Algorithm Design Manual \| publisher=[[Springer-Verlag]] \| location=Berlin, New York \| isbn=978-0-387-94860-7 \| year=1998 \| chapter=§8.2.3 Matrix multiplication}}.</ref> However, it has been observed that this crossover point has been increasing in recent years, and a 2010 study found that even a single step of Strassen's algorithm is often not beneficial on current architectures, compared to a highly optimized traditional multiplication, until matrix sizes exceed 1000 or more, and even for matrix sizes of several thousand the benefit is typically marginal at best (around 10% or less).<ref name="dalberto"/> A more recent study (2016) observed benefits for matrices as small as 512 and a benefit around 20%.<ref name="huang et al."/>		Practical implementations of Strassen's algorithm switch to standard methods of matrix multiplication for small enough submatrices, for which those algorithms are more efficient. The particular crossover point for which Strassen's algorithm is more efficient depends on the specific implementation and hardware. Earlier authors had estimated that Strassen's algorithm is faster for matrices with widths from 32 to 128 for optimized implementations.<ref>{{Citation \| last1=Skiena \| first1=Steven S. \| title=The Algorithm Design Manual \| publisher=[[Springer-Verlag]] \| location=Berlin, New York \| isbn=978-0-387-94860-7 \| year=1998 \| chapter=§8.2.3 Matrix multiplication}}.</ref> However, it has been observed that this crossover point has been increasing in recent years, and a 2010 study found that even a single step of Strassen's algorithm is often not beneficial on current architectures, compared to a highly optimized traditional multiplication, until matrix sizes exceed 1000 or more, and even for matrix sizes of several thousand the benefit is typically marginal at best (around 10% or less).<ref name="dalberto"/> A more recent study (2016) observed benefits for matrices as small as 512 and a benefit around 20%.<ref name="huang et al."/>

			== Improvements to Strassen algorithm ==
	== Winograd form ==
			{{Further information\|Matrix multiplication algorithm#Sub-cubic algorithms\|Computational complexity of matrix multiplication}}

	It is possible to reduce the number of matrix additions by instead using the following form discovered by Winograd:		It is possible to reduce the number of matrix additions by instead using the following form discovered by Winograd in [[1971]]:<ref>{{Cite journal \|last=Winograd \|first=S. \|date=October 1971 \|title=On multiplication of 2 × 2 matrices \|url=https://linkinghub.elsevier.com/retrieve/pii/0024379571900097 \|journal=Linear Algebra and its Applications \|language=en \|volume=4 \|issue=4 \|pages=381–388 \|doi=10.1016/0024-3795(71)90009-7}}</ref>

	<math>		<math>
Line 108:		Line 108:

	This reduces the number of matrix additions and subtractions from 18 to 15. The number of matrix multiplications is still 7, and the asymptotic complexity is the same.{{sfnp\|Knuth\|1997\|p=500}}		This reduces the number of matrix additions and subtractions from 18 to 15. The number of matrix multiplications is still 7, and the asymptotic complexity is the same.{{sfnp\|Knuth\|1997\|p=500}}

			The algorithm was further optimised in [[2017]]<ref>{{Cite journal \|last=Karstadt \|first=Elaye \|last2=Schwartz \|first2=Oded \|date=2017-07-24 \|title=Matrix Multiplication, a Little Faster \|url=https://dl.acm.org/doi/10.1145/3087556.3087579 \|journal=In Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '17) \|language=en \|publisher=ACM \|pages=101–110 \|doi=10.1145/3087556.3087579 \|isbn=978-1-4503-4593-4}}</ref>, reducing the number of matrix additions per step to 12 while maintainging the numer of matrix multiplications, and again in [[2023]]<ref>{{Cite journal \|last=Schwartz \|first=Oded \|last2=Vaknin \|first2=Noa \|date=2023-12-31 \|title=Pebbling Game and Alternative Basis for High Performance Matrix Multiplication \|url=https://epubs.siam.org/doi/10.1137/22M1502719 \|journal=SIAM Journal on Scientific Computing \|language=en \|volume=45 \|issue=6 \|pages=C277–C303 \|doi=10.1137/22M1502719 \|issn=1064-8275}}</ref>.

	== Asymptotic complexity ==		== Asymptotic complexity ==

Cmglee: /* Winograd form */ Highlight multiplications and merge identical multiplication

2023-12-06T11:32:36Z

Winograd form: Highlight multiplications and merge identical multiplication

← Previous revision		Revision as of 11:32, 6 December 2023
Line 100:		Line 100:
	=		=
	\begin{bmatrix}		\begin{bmatrix}
	aA + bB & w + v + (a + b - c - d)D \\		t + b{\color{red}\times}B & w + v + (a + b - c - d){\color{red}\times}D \\
	w + u + d(B + C - A - D) & w + u + v		w + u + d{\color{red}\times}(B + C - A - D) & w + u + v
	\end{bmatrix}		\end{bmatrix}
	</math>		</math>

	where <math>u = (c - a)(C - D), \; v = (c + d)(C - A), \; w = aA + (c + d - a)(A + D - C)</math>.		where <math>t = a{\color{red}\times}A, \; u = (c - a){\color{red}\times}(C - D), \; v = (c + d){\color{red}\times}(C - A), \; w = t + (c + d - a){\color{red}\times}(A + D - C)</math>.

	This reduces the number of matrix additions and subtractions from 18 to 15. The number of matrix multiplications is still 7, and the asymptotic complexity is the same.{{sfnp\|Knuth\|1997\|p=500}}		This reduces the number of matrix additions and subtractions from 18 to 15. The number of matrix multiplications is still 7, and the asymptotic complexity is the same.{{sfnp\|Knuth\|1997\|p=500}}

Cmglee: /* Algorithm */ Highlight multiplications, separate columns and note Ms are scalars not matrices

2023-12-06T11:26:51Z

Algorithm: Highlight multiplications, separate columns and note Ms are scalars not matrices

← Previous revision		Revision as of 11:26, 6 December 2023
Line 42:		Line 42:
	=		=
	\begin{bmatrix}		\begin{bmatrix}
	A_{11} B_{11} + A_{12} B_{21} &		A_{11} {\color{red}\times} B_{11} + A_{12} {\color{red}\times} B_{21} \quad &
	A_{11} B_{12} + A_{12} B_{22} \\		A_{11} {\color{red}\times} B_{12} + A_{12} {\color{red}\times} B_{22} \\
	A_{21} B_{11} + A_{22} B_{21} &		A_{21} {\color{red}\times} B_{11} + A_{22} {\color{red}\times} B_{21} \quad &
	A_{21} B_{12} + A_{22} B_{22}		A_{21} {\color{red}\times} B_{12} + A_{22} {\color{red}\times} B_{22}
	\end{bmatrix}.		\end{bmatrix}.
	</math>		</math>
Line 51:		Line 51:
	This construction does not reduce the number of multiplications: 8 multiplications of matrix blocks are still needed to calculate the <math>C_{ij}</math> matrices, the same number of multiplications needed when using standard matrix multiplication.		This construction does not reduce the number of multiplications: 8 multiplications of matrix blocks are still needed to calculate the <math>C_{ij}</math> matrices, the same number of multiplications needed when using standard matrix multiplication.

	The Strassen algorithm defines instead new ~~matrices~~:		The Strassen algorithm defines instead new values:

	: <math>		: <math>
	\begin{align}		\begin{align}
	M_1 &= (A_{11} + A_{22}) (B_{11} + B_{22}); \\		M_1 &= (A_{11} + A_{22}) {\color{red}\times} (B_{11} + B_{22}); \\
	M_2 &= (A_{21} + A_{22}) B_{11}; \\		M_2 &= (A_{21} + A_{22}) {\color{red}\times} B_{11}; \\
	M_3 &= A_{11} (B_{12} - B_{22}); \\		M_3 &= A_{11} {\color{red}\times} (B_{12} - B_{22}); \\
	M_4 &= A_{22} (B_{21} - B_{11}); \\		M_4 &= A_{22} {\color{red}\times} (B_{21} - B_{11}); \\
	M_5 &= (A_{11} + A_{12}) B_{22}; \\		M_5 &= (A_{11} + A_{12}) {\color{red}\times} B_{22}; \\
	M_6 &= (A_{21} - A_{11}) (B_{11} + B_{12}); \\		M_6 &= (A_{21} - A_{11}) {\color{red}\times} (B_{11} + B_{12}); \\
	M_7 &= (A_{12} - A_{22}) (B_{21} + B_{22}), \\		M_7 &= (A_{12} - A_{22}) {\color{red}\times} (B_{21} + B_{22}), \\
	\end{align}		\end{align}
	</math>		</math>
Line 74:		Line 74:
	=		=
	\begin{bmatrix}		\begin{bmatrix}
	M_1 + M_4 - M_5 + M_7 &		M_1 + M_4 - M_5 + M_7 \quad &
	M_3 + M_5 \\		M_3 + M_5 \\
	M_2 + M_4 &		M_2 + M_4 \quad &
	M_1 - M_2 + M_3 + M_6		M_1 - M_2 + M_3 + M_6
	\end{bmatrix}.		\end{bmatrix}.