Computational complexity of mathematical operations - Revision history

Tpreu: /* Algebraic functions */ Provided missing references, added multipoint evaluation and clarified the meaning of M(n) as in the cited reference.

2025-06-14T21:45:19Z

Algebraic functions: Provided missing references, added multipoint evaluation and clarified the meaning of M(n) as in the cited reference.

← Previous revision		Revision as of 21:45, 14 June 2025
Line 88:		Line 88:

	== Algebraic functions ==		== Algebraic functions ==
	Here we consider operations over polynomials and {{mvar\|n}} denotes their degree; for the coefficients we use a '''unit-cost''' model, ignoring the number of bits in a number. In practice this means that we assume them to be machine integers.		Here we consider operations over polynomials and {{mvar\|n}} denotes their degree; for the coefficients we use a '''unit-cost''' model, ignoring the number of bits in a number. In practice this means that we assume them to be machine integers. For this section <math>M(n)</math> indicates the time needed for multiplying two polynomials of degree at most <math>n</math>.<ref name="vzG"/>{{rp\|p=242}}
	{\| class="wikitable"		{\| class="wikitable"
	!Operation		!Operation
Line 104:		Line 104:
	\|[[Horner's method]]		\|[[Horner's method]]
	\|<math>\Theta(n)</math>		\|<math>\Theta(n)</math>
			\|-
			\|rowspan=2\|Polynomial multipoint evaluation
			\|rowspan=2\| One polynomial of degree less than <math>n</math> with integer coefficients and <math>n</math> numbers as evaluation points
			\|rowspan=2\| <math>n</math> numbers
			\|Direct evaluation
			\|<math>\Theta(n^2)</math>
			\|-
			\|[[Fast multipoint evaluation]]<ref name="vzG">{{cite book \|first1=J. \|last1=von zur Gathen \|first2=J. \|last2=Gerhard \|title=Modern Computer Algebra \|edition=3rd \|publisher=Cambridge University Press \|date=2013 \|isbn=9781139856065}}</ref>{{rp\|p=295}}
			\|<math>O(M(n) \log n)</math>
	\|-		\|-
	\|rowspan=2\|Polynomial gcd (over <math>\mathbb{Z}[x]</math> or <math>F[x]</math>)		\|rowspan=2\|Polynomial gcd (over <math>\mathbb{Z}[x]</math> or <math>F[x]</math>)
Line 111:		Line 120:
	\|<math>O\mathord\left(n^{2}\right)</math>		\|<math>O\mathord\left(n^{2}\right)</math>
	\|-		\|-
	\|Fast Euclidean algorithm (Lehmer){{~~Citation needed~~\|~~date~~=~~September 2023~~}}		\|Fast Euclidean algorithm<ref name="vzG"/>{{rp\|p=318}} (Lehmer<ref name="vzG"/>{{rp\|p=324}})
	\|<math>O(M(n) \log n)</math>		\|<math>O(M(n) \log n)</math>
	\|}		\|}

Egormanga: /* Matrix algebra */ Grouped Matrix multiplication rows together.

2025-05-26T10:52:17Z

Matrix algebra: Grouped Matrix multiplication rows together.

← Previous revision		Revision as of 10:52, 26 May 2025
Line 301:		Line 301:
	!Complexity		!Complexity
	\|-		\|-
	\|rowspan=4\|[[Matrix multiplication algorithm\|Matrix multiplication]]		\|rowspan=6\|[[Matrix multiplication algorithm\|Matrix multiplication]]
	\|rowspan=4\|Two <math>n \times n</math> matrices		\|rowspan=4\|Two <math>n \times n</math> matrices
	\|rowspan=4\|One <math>n \times n</math> matrix		\|rowspan=4\|One <math>n \times n</math> matrix
Line 330:		Line 330:
	\|<math>O\mathord\left(n^{\psi=2.3728596}\right)</math>		\|<math>O\mathord\left(n^{\psi=2.3728596}\right)</math>
	\|-		\|-
	\|Matrix multiplication
	\|One <math>n \times m</math> matrix, and <br/>one <math>m \times p</math> matrix		\|One <math>n \times m</math> matrix, and <br/>one <math>m \times p</math> matrix
	\|One <math>n \times p</math> matrix		\|One <math>n \times p</math> matrix
Line 336:		Line 335:
	\|<math>O(nmp)</math>		\|<math>O(nmp)</math>
	\|-		\|-
	\|Matrix multiplication
	\|One <math>n \times \left\lceil n^k \right\rceil</math> matrix, and <br/>one <math>\left\lceil n^k \right\rceil \times n</math> matrix, for some <math>k \geq 0</math>		\|One <math>n \times \left\lceil n^k \right\rceil</math> matrix, and <br/>one <math>\left\lceil n^k \right\rceil \times n</math> matrix, for some <math>k \geq 0</math>
	\|One <math>n \times n</math> matrix		\|One <math>n \times n</math> matrix

94.175.200.195: sqrt gives n/2 digits, not sure what to do about division (m digits / n digits = m-n digits)

2025-05-06T17:24:26Z

sqrt gives n/2 digits, not sure what to do about division (m digits / n digits = m-n digits)

← Previous revision		Revision as of 17:24, 6 May 2025
Line 68:		Line 68:
	\|[[Square root]]		\|[[Square root]]
	\|One <math>n</math>-digit number		\|One <math>n</math>-digit number
	\|One <math>n</math>-digit number		\|One <math>n/2</math>-digit number
	\|[[Newton's method]]		\|[[Newton's method]]
	\|<math>O(M(n))</math>		\|<math>O(M(n))</math>

94.175.200.195: Subtraction produces n-digit number, not n+1

2025-05-06T17:20:49Z

Subtraction produces n-digit number, not n+1

← Previous revision		Revision as of 17:20, 6 May 2025
Line 26:		Line 26:
	\|[[Subtraction]]		\|[[Subtraction]]
	\|Two <math>n</math>-digit numbers		\|Two <math>n</math>-digit numbers
	\|One <math>n+1</math>-digit number		\|One <math>n</math>-digit number
	\|Schoolbook subtraction with borrow		\|Schoolbook subtraction with borrow
	\|<math>\Theta(n)</math>		\|<math>\Theta(n)</math>

Giftlite: /* Matrix algebra */ −sp

2024-12-01T17:01:48Z

Matrix algebra: −sp

← Previous revision		Revision as of 17:01, 1 December 2024
Line 411:		Line 411:

	In 2005, [[Henry Cohn]], [[Robert Kleinberg]], [[Balázs Szegedy]], and [[Chris Umans]] showed that either of two different conjectures would imply that the exponent of matrix multiplication is 2.<ref>{{cite book \|first1=Henry \|last1=Cohn \|first2=Robert \|last2=Kleinberg \|first3=Balazs \|last3=Szegedy \|first4=Chris \|last4=Umans \|arxiv=math.GR/0511460 \|chapter=Group-theoretic Algorithms for Matrix Multiplication \|chapter-url= \|title=Proceedings of the 46th Annual Symposium on Foundations of Computer Science \|year=2005 \|publisher=IEEE \|isbn=0-7695-2468-0 \|pages=379–388 \|doi=10.1109/SFCS.2005.39\|s2cid=6429088 }}</ref>		In 2005, [[Henry Cohn]], [[Robert Kleinberg]], [[Balázs Szegedy]], and [[Chris Umans]] showed that either of two different conjectures would imply that the exponent of matrix multiplication is 2.<ref>{{cite book \|first1=Henry \|last1=Cohn \|first2=Robert \|last2=Kleinberg \|first3=Balazs \|last3=Szegedy \|first4=Chris \|last4=Umans \|arxiv=math.GR/0511460 \|chapter=Group-theoretic Algorithms for Matrix Multiplication \|chapter-url= \|title=Proceedings of the 46th Annual Symposium on Foundations of Computer Science \|year=2005 \|publisher=IEEE \|isbn=0-7695-2468-0 \|pages=379–388 \|doi=10.1109/SFCS.2005.39\|s2cid=6429088 }}</ref>


	== Transforms ==		== Transforms ==

Citation bot: Alter: journal, pages. Add: isbn, pages. Removed URL that duplicated identifier. Formatted dashes. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Computer arithmetic algorithms | #UCB_Category 4/20

2024-11-12T06:33:56Z

Alter: journal, pages. Add: isbn, pages. Removed URL that duplicated identifier. Formatted dashes. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Computer arithmetic algorithms | #UCB_Category 4/20

← Previous revision		Revision as of 06:33, 12 November 2024
Line 323:		Line 323:
	\| arxiv=2010.05846		\| arxiv=2010.05846
	\| title = 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021)		\| title = 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021)
			\| pages=522–539
			\| isbn=978-1-61197-646-5
	\| s2cid=222290442		\| s2cid=222290442
	\|url=https://www.siam.org/conferences/cm/program/accepted-papers/soda21-accepted-papers		\|url=https://www.siam.org/conferences/cm/program/accepted-papers/soda21-accepted-papers
Line 368:		Line 370:
	\|One <math>m \times n</math> matrix		\|One <math>m \times n</math> matrix
	\|One <math>m \times n</math> matrix, & <br /> one <math>n \times n</math> matrix		\|One <math>m \times n</math> matrix, & <br /> one <math>n \times n</math> matrix
	\| Algorithms in <ref>{{Cite journal \|last=Knight \|first=Philip A. \|date=May 1995 \|title=Fast rectangular matrix multiplication and QR decomposition ~~\|url=https://doi.org/10.1016/0024-3795(93)00230-W~~ \|journal=Linear Algebra and ~~its~~ Applications \|volume=221 \|pages=69–81 \|doi=10.1016/0024-3795(93)00230-w \|issn=0024-3795\|doi-access=free }}</ref>		\| Algorithms in <ref>{{Cite journal \|last=Knight \|first=Philip A. \|date=May 1995 \|title=Fast rectangular matrix multiplication and QR decomposition \|journal=Linear Algebra and Its Applications \|volume=221 \|pages=69–81 \|doi=10.1016/0024-3795(93)00230-w \|issn=0024-3795\|doi-access=free }}</ref>
	\|<math>O\mathord\left(mn^{1+\frac{1}{4-\omega}}\right)</math> <br /> (<math>m \geq n</math>)		\|<math>O\mathord\left(mn^{1+\frac{1}{4-\omega}}\right)</math> <br /> (<math>m \geq n</math>)
	\|-		\|-
Line 404:		Line 406:
	\|<math>O(n^{\psi+1})</math> (smaller constant factor)		\|<math>O(n^{\psi+1})</math> (smaller constant factor)
	\|-		\|-
	\|[[Preparata-Sarwate algorithm]]<ref>{{Cite journal\|last1=Preparata\|first1=F.P.\|last2=Sarwate\|first2=D.V.\|date=April 1978\|title=An improved parallel processor bound in fast matrix inversion~~\|url=https://doi.org/10.1016/0020-0190(78)90079-0~~\|journal=Information Processing Letters\|volume=7\|issue=3\|pages=~~148-150~~\|doi=10.1016/0020-0190(78)90079-0\|doi-access=free}}</ref><ref>{{Cite journal\|last1=Galil\|first1=Zvi\|last2=Pan\|first2=Victor\|date=January 16, 1989\|title=Parallel evaluation of the determinant and of the inverse of a matrix~~\|url=https://doi.org/10.1016/0020-0190(89)90173-7~~\|journal=Information Processing Letters\|volume=30\|issue=1\|pages=~~148-150~~\|doi=10.1016/0020-0190(89)90173-7\|doi-access=free}}, in which the <math>O(n^3)</math> term is reduced</ref>		\|[[Preparata-Sarwate algorithm]]<ref>{{Cite journal\|last1=Preparata\|first1=F.P.\|last2=Sarwate\|first2=D.V.\|date=April 1978\|title=An improved parallel processor bound in fast matrix inversion\|journal=Information Processing Letters\|volume=7\|issue=3\|pages=148–150\|doi=10.1016/0020-0190(78)90079-0\|doi-access=free}}</ref><ref>{{Cite journal\|last1=Galil\|first1=Zvi\|last2=Pan\|first2=Victor\|date=January 16, 1989\|title=Parallel evaluation of the determinant and of the inverse of a matrix\|journal=Information Processing Letters\|volume=30\|issue=1\|pages=148–150\|doi=10.1016/0020-0190(89)90173-7\|doi-access=free}}, in which the <math>O(n^3)</math> term is reduced</ref>
	\|<math>O(n^{\psi+1/2}+n^3)</math>		\|<math>O(n^{\psi+1/2}+n^3)</math>
	\|}		\|}

Drone Better: add Samuelson-Berkowitz and Preparata-Sarwate algorithms for computing charpoly

2024-11-06T00:21:38Z

add Samuelson-Berkowitz and Preparata-Sarwate algorithms for computing charpoly

← Previous revision		Revision as of 00:21, 6 November 2024
Line 395:		Line 395:
	\|<math>O\mathord\left(n^2\right)</math>		\|<math>O\mathord\left(n^2\right)</math>
	\|-		\|-
	\|Characteristic polynomial		\|rowspan=3\|Characteristic polynomial
	\|One <math>n \times n</math> matrix		\|rowspan=3\|One <math>n \times n</math> matrix
	\|One degree-<math>n</math> polynomial		\|rowspan=3\|One degree-<math>n</math> polynomial
	\|[[Faddeev-LeVerrier algorithm]]		\|[[Faddeev-LeVerrier algorithm]]
	\|<math>O(n^{\psi+1})</math>		\|<math>O(n^{\psi+1})</math>
			\|-
			\|[[Samuelson-Berkowitz algorithm]]
			\|<math>O(n^{\psi+1})</math> (smaller constant factor)
			\|-
			\|[[Preparata-Sarwate algorithm]]<ref>{{Cite journal\|last1=Preparata\|first1=F.P.\|last2=Sarwate\|first2=D.V.\|date=April 1978\|title=An improved parallel processor bound in fast matrix inversion\|url=https://doi.org/10.1016/0020-0190(78)90079-0\|journal=Information Processing Letters\|volume=7\|issue=3\|pages=148-150\|doi=10.1016/0020-0190(78)90079-0\|doi-access=free}}</ref><ref>{{Cite journal\|last1=Galil\|first1=Zvi\|last2=Pan\|first2=Victor\|date=January 16, 1989\|title=Parallel evaluation of the determinant and of the inverse of a matrix\|url=https://doi.org/10.1016/0020-0190(89)90173-7\|journal=Information Processing Letters\|volume=30\|issue=1\|pages=148-150\|doi=10.1016/0020-0190(89)90173-7\|doi-access=free}}, in which the <math>O(n^3)</math> term is reduced</ref>
			\|<math>O(n^{\psi+1/2}+n^3)</math>
	\|}		\|}

Drone Better: add characteristic polynomial to matrix section, use ψ for matrix multiplication exponent (the Faddeev-LeVerrier algorithm being O(n^{ψ+1} from performing n successive multiplications))

2024-08-13T12:37:18Z

add characteristic polynomial to matrix section, use ψ for matrix multiplication exponent (the Faddeev-LeVerrier algorithm being O(n^{ψ+1} from performing n successive multiplications))

← Previous revision		Revision as of 12:37, 13 August 2024
Line 326:		Line 326:
	\|url=https://www.siam.org/conferences/cm/program/accepted-papers/soda21-accepted-papers		\|url=https://www.siam.org/conferences/cm/program/accepted-papers/soda21-accepted-papers
	}}</ref><ref>{{Citation \| last1=Davie \| first1=A.M. \| last2=Stothers \| first2=A.J. \| title=Improved bound for complexity of matrix multiplication\|journal=Proceedings of the Royal Society of Edinburgh\|volume=143A\| issue=2 \|pages=351–370\|year=2013\|doi=10.1017/S0308210511001648\| s2cid=113401430 }}</ref><ref>{{Citation \| last1=Vassilevska Williams \| first1=Virginia \|author-link= Virginia Vassilevska Williams \| title=Breaking the Coppersmith-Winograd barrier: Multiplying matrices in O(n<sup>2.373</sup>) time \| url=https://www.scribd.com/document/397495001/Breaking-the-Coppersmith-Winograd-Barrier-for-Matrix-Multiplication-Algorithms \| year=2014 }}</ref><ref>{{Citation \| last1=Le Gall \| first1=François \| contribution=Powers of tensors and fast matrix multiplication \| year = 2014 \| arxiv=1401.7714 \| title = Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation — ISSAC '14\| bibcode=2014arXiv1401.7714L \| title-link=ISSAC \| page=23 \| doi=10.1145/2608628.2627493 \| isbn=9781450325011 \| s2cid=353236 }}</ref> ([[galactic algorithm]]s)		}}</ref><ref>{{Citation \| last1=Davie \| first1=A.M. \| last2=Stothers \| first2=A.J. \| title=Improved bound for complexity of matrix multiplication\|journal=Proceedings of the Royal Society of Edinburgh\|volume=143A\| issue=2 \|pages=351–370\|year=2013\|doi=10.1017/S0308210511001648\| s2cid=113401430 }}</ref><ref>{{Citation \| last1=Vassilevska Williams \| first1=Virginia \|author-link= Virginia Vassilevska Williams \| title=Breaking the Coppersmith-Winograd barrier: Multiplying matrices in O(n<sup>2.373</sup>) time \| url=https://www.scribd.com/document/397495001/Breaking-the-Coppersmith-Winograd-Barrier-for-Matrix-Multiplication-Algorithms \| year=2014 }}</ref><ref>{{Citation \| last1=Le Gall \| first1=François \| contribution=Powers of tensors and fast matrix multiplication \| year = 2014 \| arxiv=1401.7714 \| title = Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation — ISSAC '14\| bibcode=2014arXiv1401.7714L \| title-link=ISSAC \| page=23 \| doi=10.1145/2608628.2627493 \| isbn=9781450325011 \| s2cid=353236 }}</ref> ([[galactic algorithm]]s)
	\|<math>O\mathord\left(n^{2.3728596}\right)</math>		\|<math>O\mathord\left(n^{\psi=2.3728596}\right)</math>
	\|-		\|-
	\|Matrix multiplication		\|Matrix multiplication
Line 344:		Line 344:
	\|rowspan=4\|One <math>n \times n</math> matrix		\|rowspan=4\|One <math>n \times n</math> matrix
	\|[[Gauss–Jordan elimination]]		\|[[Gauss–Jordan elimination]]
	\|<math>O\mathord\left(n^{3}\right)</math>		\|<math>O\mathord\left(n^3\right)</math>
	\|-		\|-
	\|Strassen algorithm		\|Strassen algorithm
Line 353:		Line 353:
	\|-		\|-
	\|Optimized CW-like algorithms		\|Optimized CW-like algorithms
	\|<math>O\mathord\left(n^{~~2.373~~}\right)</math>		\|<math>O\mathord\left(n^{\psi}\right)</math>
	\|-		\|-
	\|rowspan=2\|[[Singular value decomposition]]		\|rowspan=2\|[[Singular value decomposition]]
Line 378:		Line 378:
	\|-		\|-
	\|Division-free algorithm<ref>{{cite book \|first=G. \|last=Rote \|chapter=Division-free algorithms for the determinant and the pfaffian: algebraic and combinatorial approaches \|chapter-url=http://page.mi.fu-berlin.de/rote/Papers/pdf/Division-free+algorithms.pdf \|title=Computational discrete mathematics \|publisher=Springer \|date=2001 \|isbn=3-540-45506-X \|pages=119–135 \|url=}}</ref>		\|Division-free algorithm<ref>{{cite book \|first=G. \|last=Rote \|chapter=Division-free algorithms for the determinant and the pfaffian: algebraic and combinatorial approaches \|chapter-url=http://page.mi.fu-berlin.de/rote/Papers/pdf/Division-free+algorithms.pdf \|title=Computational discrete mathematics \|publisher=Springer \|date=2001 \|isbn=3-540-45506-X \|pages=119–135 \|url=}}</ref>
	\|<math>O\mathord\left(n^{4}\right)</math>		\|<math>O\mathord\left(n^4\right)</math>
	\|-		\|-
	\|[[LU decomposition]]		\|[[LU decomposition]]
	\|<math>O(n^{3})</math>		\|<math>O(n^3)</math>
	\|-		\|-
	\|[[Bareiss algorithm]]		\|[[Bareiss algorithm]]
Line 387:		Line 387:
	\|-		\|-
	\|Fast matrix multiplication<ref>{{cite book \|chapter=Theorem 6.6 \|page=241\|title=The Design and Analysis of Computer Algorithms\|first1=Alfred V.\|last1=Aho\|author1-link=Alfred Aho\|first2=John E.\|last2=Hopcroft\|author2-link=John Hopcroft\|first3=Jeffrey D.\|last3=Ullman\|author3-link=Jeffrey Ullman\|publisher=Addison-Wesley\|year=1974 \|isbn=978-0-201-00029-0}}</ref>		\|Fast matrix multiplication<ref>{{cite book \|chapter=Theorem 6.6 \|page=241\|title=The Design and Analysis of Computer Algorithms\|first1=Alfred V.\|last1=Aho\|author1-link=Alfred Aho\|first2=John E.\|last2=Hopcroft\|author2-link=John Hopcroft\|first3=Jeffrey D.\|last3=Ullman\|author3-link=Jeffrey Ullman\|publisher=Addison-Wesley\|year=1974 \|isbn=978-0-201-00029-0}}</ref>
	\|<math>O\mathord\left(n^~~{2.373}~~\right)</math>		\|<math>O\mathord\left(n^\psi\right)</math>
	\|-		\|-

	\|Back substitution		\|Back substitution
	\|[[Triangular matrix]]		\|[[Triangular matrix]]
Line 395:		Line 394:
	\|Back substitution<ref>{{cite book \|first1=J.B. \|last1=Fraleigh \|first2=R.A. \|last2=Beauregard \|title=Linear Algebra \|publisher=Addison-Wesley \|edition=3rd \|date=1987 \|isbn=978-0-201-15459-7 \|pages=95 \|url=}}</ref>		\|Back substitution<ref>{{cite book \|first1=J.B. \|last1=Fraleigh \|first2=R.A. \|last2=Beauregard \|title=Linear Algebra \|publisher=Addison-Wesley \|edition=3rd \|date=1987 \|isbn=978-0-201-15459-7 \|pages=95 \|url=}}</ref>
	\|<math>O\mathord\left(n^2\right)</math>		\|<math>O\mathord\left(n^2\right)</math>
			\|-
			\|Characteristic polynomial
			\|One <math>n \times n</math> matrix
			\|One degree-<math>n</math> polynomial
			\|[[Faddeev-LeVerrier algorithm]]
			\|<math>O(n^{\psi+1})</math>
	\|}		\|}

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

2024-04-22T07:38:47Z

Open access bot: doi updated in citation with #oabot.

← Previous revision		Revision as of 07:38, 22 April 2024
Line 368:		Line 368:
	\|One <math>m \times n</math> matrix		\|One <math>m \times n</math> matrix
	\|One <math>m \times n</math> matrix, & <br /> one <math>n \times n</math> matrix		\|One <math>m \times n</math> matrix, & <br /> one <math>n \times n</math> matrix
	\| Algorithms in <ref>{{Cite journal \|last=Knight \|first=Philip A. \|date=May 1995 \|title=Fast rectangular matrix multiplication and QR decomposition \|url=https://doi.org/10.1016/0024-3795(93)00230-W \|journal=Linear Algebra and its Applications \|volume=221 \|pages=69–81 \|doi=10.1016/0024-3795(93)00230-w \|issn=0024-3795}}</ref>		\| Algorithms in <ref>{{Cite journal \|last=Knight \|first=Philip A. \|date=May 1995 \|title=Fast rectangular matrix multiplication and QR decomposition \|url=https://doi.org/10.1016/0024-3795(93)00230-W \|journal=Linear Algebra and its Applications \|volume=221 \|pages=69–81 \|doi=10.1016/0024-3795(93)00230-w \|issn=0024-3795\|doi-access=free }}</ref>
	\|<math>O\mathord\left(mn^{1+\frac{1}{4-\omega}}\right)</math> <br /> (<math>m \geq n</math>)		\|<math>O\mathord\left(mn^{1+\frac{1}{4-\omega}}\right)</math> <br /> (<math>m \geq n</math>)
	\|-		\|-

Ira Leviton: Fixed a reference. Please see Category:CS1 errors: dates.

2024-04-14T18:14:08Z

Fixed a reference. Please see Category:CS1 errors: dates.

← Previous revision		Revision as of 18:14, 14 April 2024
Line 337:		Line 337:
	\|One <math>n \times \left\lceil n^k \right\rceil</math> matrix, and <br/>one <math>\left\lceil n^k \right\rceil \times n</math> matrix, for some <math>k \geq 0</math>		\|One <math>n \times \left\lceil n^k \right\rceil</math> matrix, and <br/>one <math>\left\lceil n^k \right\rceil \times n</math> matrix, for some <math>k \geq 0</math>
	\|One <math>n \times n</math> matrix		\|One <math>n \times n</math> matrix
	\|Algorithms given in <ref name="Le Gall">{{cite book \|last1=Le Gall \|first1=François \|last2=Urrutia \|first2=Floren \|editor1-last=Czumaj \|editor1-first=Artur \|title=Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms \|date=2018 \|publisher=Society for Industrial and Applied Mathematics ~~(SIAM)~~ \|isbn=978-1-61197-503-1 \|chapter=Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor \|doi=10.1137/1.9781611975031.67\|s2cid=33396059 }}</ref>		\|Algorithms given in <ref name="Le Gall">{{cite book \|last1=Le Gall \|first1=François \|last2=Urrutia \|first2=Floren \|editor1-last=Czumaj \|editor1-first=Artur \|title=Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms \|date=2018 \|publisher=Society for Industrial and Applied Mathematics \|isbn=978-1-61197-503-1 \|chapter=Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor \|doi=10.1137/1.9781611975031.67\|s2cid=33396059 }}</ref>
	\|<math>O(n^{\omega(k)+\epsilon})</math>, where upper bounds on <math>\omega(k)</math> are given in <ref name="Le Gall" />		\|<math>O(n^{\omega(k)+\epsilon})</math>, where upper bounds on <math>\omega(k)</math> are given in <ref name="Le Gall" />
	\|-		\|-
Line 368:		Line 368:
	\|One <math>m \times n</math> matrix		\|One <math>m \times n</math> matrix
	\|One <math>m \times n</math> matrix, & <br /> one <math>n \times n</math> matrix		\|One <math>m \times n</math> matrix, & <br /> one <math>n \times n</math> matrix
	\| Algorithms in <ref>{{Cite journal \|last=Knight \|first=Philip A. \|date=1995~~-05~~ \|title=Fast rectangular matrix multiplication and QR decomposition \|url=https://doi.org/10.1016/0024-3795(93)00230-W \|journal=Linear Algebra and its Applications \|volume=221 \|pages=69–81 \|doi=10.1016/0024-3795(93)00230-w \|issn=0024-3795}}</ref>		\| Algorithms in <ref>{{Cite journal \|last=Knight \|first=Philip A. \|date=May 1995 \|title=Fast rectangular matrix multiplication and QR decomposition \|url=https://doi.org/10.1016/0024-3795(93)00230-W \|journal=Linear Algebra and its Applications \|volume=221 \|pages=69–81 \|doi=10.1016/0024-3795(93)00230-w \|issn=0024-3795}}</ref>
	\|<math>O\mathord\left(mn^{1+\frac{1}{4-\omega}}\right)</math> <br /> (<math>m \geq n</math>)		\|<math>O\mathord\left(mn^{1+\frac{1}{4-\omega}}\right)</math> <br /> (<math>m \geq n</math>)
	\|-		\|-