Computational complexity of mathematical operations

Last updated December 02, 2024

The following tables list the computational complexity of various algorithms for common mathematical operations.

Arithmetic functions

This table lists the complexity of mathematical operations on integers.

Operation	Input	Output	Algorithm	Complexity
Addition	Two $n$ -digit numbers	One $n+1$ -digit number	Schoolbook addition with carry	$\Theta (n)$
Subtraction	Two $n$ -digit numbers	One $n+1$ -digit number	Schoolbook subtraction with borrow	$\Theta (n)$
Multiplication	Two $n$ -digit numbers	One $2n$ -digit number	Schoolbook long multiplication	$O{\mathord {\left(n^{2}\right)}}$
			Karatsuba algorithm	$O{\mathord {\left(n^{1.585}\right)}}$
			3-way Toom–Cook multiplication	$O{\mathord {\left(n^{1.465}\right)}}$
			$k$ -way Toom–Cook multiplication	$O{\mathord {\left(n^{\frac {\log(2k-1)}{\log k}}\right)}}$
			Mixed-level Toom–Cook (Knuth 4.3.3-T)^[2]	$O{\mathord {\left(n\,2^{\sqrt {2\log n}}\,\log n\right)}}$
			Schönhage–Strassen algorithm	$O{\mathord {\left(n\log n\log \log n\right)}}$
			Harvey-Hoeven algorithm ^[3]^[4]	$O(n\log n)$
Division	Two $n$ -digit numbers	One $n$ -digit number	Schoolbook long division	$O{\mathord {\left(n^{2}\right)}}$
			Burnikel–Ziegler Divide-and-Conquer Division^[5]	$O(M(n)\log n)$
			Newton–Raphson division	$O(M(n))$
Square root	One $n$ -digit number	One $n$ -digit number	Newton's method	$O(M(n))$
Modular exponentiation	Two $n$ -digit integers and a $k$ -bit exponent	One $n$ -digit integer	Repeated multiplication and reduction	$O{\mathord {\left(M(n)\,2^{k}\right)}}$
			Exponentiation by squaring	$O(M(n)\,k)$
			Exponentiation with Montgomery reduction	$O(M(n)\,k)$

On stronger computational models, specifically a pointer machine and consequently also a unit-cost random-access machine it is possible to multiply two $n$ -bit numbers in time O(n).^[6]

Algebraic functions

Here we consider operations over polynomials and $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.

Operation	Input	Output	Algorithm	Complexity
Polynomial evaluation	One polynomial of degree $n$ with integer coefficients	One number	Direct evaluation	$\Theta (n)$
Polynomial evaluation	One polynomial of degree $n$ with integer coefficients	One number	Horner's method	$\Theta (n)$
Polynomial gcd (over $\mathbb {Z} [x]$ or $F[x]$ )	Two polynomials of degree $n$ with integer coefficients	One polynomial of degree at most $n$	Euclidean algorithm	$O{\mathord {\left(n^{2}\right)}}$
Polynomial gcd (over $\mathbb {Z} [x]$ or $F[x]$ )	Two polynomials of degree $n$ with integer coefficients	One polynomial of degree at most $n$	Fast Euclidean algorithm (Lehmer)^{[ citation needed ]}	$O(M(n)\log n)$

Special functions

Many of the methods in this section are given in Borwein & Borwein.^[7]

Elementary functions

The elementary functions are constructed by composing arithmetic operations, the exponential function ( $\exp$ ), the natural logarithm ( $\log$ ), trigonometric functions ( $\sin ,\cos$ ), and their inverses. The complexity of an elementary function is equivalent to that of its inverse, since all elementary functions are analytic and hence invertible by means of Newton's method. In particular, if either $\exp$ or $\log$ in the complex domain can be computed with some complexity, then that complexity is attainable for all other elementary functions.

Below, the size $n$ refers to the number of digits of precision at which the function is to be evaluated.

Algorithm	Applicability	Complexity
Taylor series; repeated argument reduction (e.g. $\exp(2x)=[\exp(x)]^{2}$ ) and direct summation	$\exp ,\log ,\sin ,\cos ,\arctan$	$O{\mathord {\left(M(n)n^{1/2}\right)}}$
Taylor series; FFT-based acceleration	$\exp ,\log ,\sin ,\cos ,\arctan$	$O{\mathord {\left(M(n)n^{1/3}(\log n)^{2}\right)}}$
Taylor series; binary splitting + bit-burst algorithm ^[8]	$\exp ,\log ,\sin ,\cos ,\arctan$	$O{\mathord {\left(M(n)(\log n)^{2}\right)}}$
Arithmetic–geometric mean iteration^[9]	$\exp ,\log ,\sin ,\cos ,\arctan$	$O(M(n)\log n)$

It is not known whether $O(M(n)\log n)$ is the optimal complexity for elementary functions. The best known lower bound is the trivial bound $\Omega$ $(M(n))$ .

Non-elementary functions

Function	Input	Algorithm	Complexity
Gamma function	$n$ -digit number	Series approximation of the incomplete gamma function	$O{\mathord {\left(M(n)n^{1/2}(\log n)^{2}\right)}}$
	Fixed rational number	Hypergeometric series	$O{\mathord {\left(M(n)(\log n)^{2}\right)}}$
	$m/24$ , for $m$ integer.	Arithmetic-geometric mean iteration	$O(M(n)\log n)$
Hypergeometric function ${}_{p}\!F_{q}$	$n$ -digit number	(As described in Borwein & Borwein)	$O{\mathord {\left(M(n)n^{1/2}(\log n)^{2}\right)}}$
Hypergeometric function ${}_{p}\!F_{q}$	Fixed rational number	Hypergeometric series	$O{\mathord {\left(M(n)(\log n)^{2}\right)}}$

Mathematical constants

This table gives the complexity of computing approximations to the given constants to $n$ correct digits.

Constant	Algorithm	Complexity
Golden ratio, $\phi$	Newton's method	$O(M(n))$
Square root of 2, ${\sqrt {2}}$	Newton's method	$O(M(n))$
Euler's number, $e$	Binary splitting of the Taylor series for the exponential function	$O(M(n)\log n)$
Euler's number, $e$	Newton inversion of the natural logarithm	$O(M(n)\log n)$
Pi, $\pi$	Binary splitting of the arctan series in Machin's formula	$O{\mathord {\left(M(n)(\log n)^{2}\right)}}$ ^[10]
Pi, $\pi$	Gauss–Legendre algorithm	$O(M(n)\log n)$ ^[10]
Euler's constant, $\gamma$	Sweeney's method (approximation in terms of the exponential integral)	$O{\mathord {\left(M(n)(\log n)^{2}\right)}}$

Number theory

Algorithms for number theoretical calculations are studied in computational number theory.

Operation	Input	Output	Algorithm	Complexity
Greatest common divisor	Two $n$ -digit integers	One integer with at most $n$ digits	Euclidean algorithm	$O{\mathord {\left(n^{2}\right)}}$
			Binary GCD algorithm	$O{\mathord {\left(n^{2}\right)}}$
			Left/right k-ary binary GCD algorithm^[11]	$O{\mathord {\left({\frac {n^{2}}{\log n}}\right)}}$
			Stehlé–Zimmermann algorithm ^[12]	$O(M(n)\log n)$
			Schönhage controlled Euclidean descent algorithm ^[13]	$O(M(n)\log n)$
Jacobi symbol	Two $n$ -digit integers	$0$ , $-1$ or $1$	Schönhage controlled Euclidean descent algorithm^[14]	$O(M(n)\log n)$
Jacobi symbol	Two $n$ -digit integers	$0$ , $-1$ or $1$	Stehlé–Zimmermann algorithm^[15]	$O(M(n)\log n)$
Factorial	A positive integer less than $m$	One $O(m\log m)$ -digit integer	Bottom-up multiplication	$O{\mathord {\left(M\left(m^{2}\right)\log m\right)}}$
			Binary splitting	$O(M(m\log m)\log m)$
			Exponentiation of the prime factors of $m$	$O(M(m\log m)\log \log m)$ ,^[16] $O(M(m\log m))$ ^[1]
Primality test	A $n$ -digit integer	True or false	AKS primality test	$O{\mathord {\left(n^{6+o(1)}\right)}}$ ^[17]^[18] $O(n^{3})$ , assuming Agrawal's conjecture
			Elliptic curve primality proving	$O{\mathord {\left(n^{4+\varepsilon }\right)}}$ heuristically^[19]
			Baillie–PSW primality test	$O{\mathord {\left(n^{2+\varepsilon }\right)}}$ ^[20]^[21]
			Miller–Rabin primality test	$O{\mathord {\left(kn^{2+\varepsilon }\right)}}$ ^[22]
			Solovay–Strassen primality test	$O{\mathord {\left(kn^{2+\varepsilon }\right)}}$ ^[22]
Integer factorization	A $b$ -bit input integer	A set of factors	General number field sieve	$O{\mathord {\left((1+\varepsilon )^{b}\right)}}$ ^{[nb 1]}
Integer factorization	A $b$ -bit input integer	A set of factors	Shor's algorithm	$O(M(b)b)$ , on a quantum computer

Matrix algebra

The following complexity figures assume that arithmetic with individual elements has complexity O(1), as is the case with fixed-precision floating-point arithmetic or operations on a finite field.

Operation	Input	Output	Algorithm	Complexity
Matrix multiplication	Two $n\times n$ matrices	One $n\times n$ matrix	Schoolbook matrix multiplication	$O(n^{3})$
			Strassen algorithm	$O{\mathord {\left(n^{2.807}\right)}}$
			Coppersmith–Winograd algorithm (galactic algorithm)	$O{\mathord {\left(n^{2.376}\right)}}$
			Optimized CW-like algorithms ^[23]^[24]^[25]^[26] (galactic algorithms)	$O{\mathord {\left(n^{\psi =2.3728596}\right)}}$
Matrix multiplication	One $n\times m$ matrix, and one $m\times p$ matrix	One $n\times p$ matrix	Schoolbook matrix multiplication	$O(nmp)$
Matrix multiplication	One $n\times \left\lceil n^{k}\right\rceil$ matrix, and one $\left\lceil n^{k}\right\rceil \times n$ matrix, for some $k\geq 0$	One $n\times n$ matrix	Algorithms given in ^[27]	$O(n^{\omega (k)+\epsilon })$ , where upper bounds on $\omega (k)$ are given in ^[27]
Matrix inversion	One $n\times n$ matrix	One $n\times n$ matrix	Gauss–Jordan elimination	$O{\mathord {\left(n^{3}\right)}}$
			Strassen algorithm	$O{\mathord {\left(n^{2.807}\right)}}$
			Coppersmith–Winograd algorithm	$O{\mathord {\left(n^{2.376}\right)}}$
			Optimized CW-like algorithms	$O{\mathord {\left(n^{\psi }\right)}}$
Singular value decomposition	One $m\times n$ matrix	One $m\times m$ matrix, one $m\times n$ matrix, & one $n\times n$ matrix	Bidiagonalization and QR algorithm	$O{\mathord {\left(m^{2}n\right)}}$ ( $m\geq n$ )
Singular value decomposition	One $m\times n$ matrix	One $m\times n$ matrix, one $n\times n$ matrix, & one $n\times n$ matrix	Bidiagonalization and QR algorithm	$O{\mathord {\left(mn^{2}\right)}}$ ( $m\leq n$ )
QR decomposition	One $m\times n$ matrix	One $m\times n$ matrix, & one $n\times n$ matrix	Algorithms in ^[28]	$O{\mathord {\left(mn^{1+{\frac {1}{4-\omega }}}\right)}}$ ( $m\geq n$ )
Determinant	One $n\times n$ matrix	One number	Laplace expansion	$O(n!)$
			Division-free algorithm^[29]	$O{\mathord {\left(n^{4}\right)}}$
			LU decomposition	$O(n^{3})$
			Bareiss algorithm	$O{\mathord {\left(n^{3}\right)}}$
			Fast matrix multiplication^[30]	$O{\mathord {\left(n^{\psi }\right)}}$
Back substitution	Triangular matrix	$n$ solutions	Back substitution^[31]	$O{\mathord {\left(n^{2}\right)}}$
Characteristic polynomial	One $n\times n$ matrix	One degree- $n$ polynomial	Faddeev-LeVerrier algorithm	$O(n^{\psi +1})$
			Samuelson-Berkowitz algorithm	$O(n^{\psi +1})$ (smaller constant factor)
			Preparata-Sarwate algorithm ^[32]^[33]	$O(n^{\psi +1/2}+n^{3})$

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.^[34]

Transforms

Algorithms for computing transforms of functions (particularly integral transforms) are widely used in all areas of mathematics, particularly analysis and signal processing.

Operation	Input	Output	Algorithm	Complexity
Discrete Fourier transform	Finite data sequence of size $n$	Set of complex numbers	Schoolbook	$O(n^{2})$
Discrete Fourier transform	Finite data sequence of size $n$	Set of complex numbers	Fast Fourier transform	$O(n\log n)$

Notes

↑ This form of sub-exponential time is valid for all $\varepsilon >0$ . A more precise form of the complexity can be given as $O{\mathord {\left(\exp {\sqrt[{3}]{{\frac {64}{9}}b(\log b)^{2}}}\right)}}.$

Related Research Articles

<span class="mw-page-title-main">Carmichael number</span> Composite number in number theory

In number theory, a Carmichael number is a composite number ⁠ $⁠$ which in modular arithmetic satisfies the congruence relation:

In mathematics and computer programming, exponentiating by squaring is a general method for fast computation of large positive integer powers of a number, or more generally of an element of a semigroup, like a polynomial or a square matrix. Some variants are commonly referred to as square-and-multiply algorithms or binary exponentiation. These can be of quite general use, for example in modular arithmetic or powering of matrices. For semigroups for which additive notation is commonly used, like elliptic curves used in cryptography, this method is also referred to as double-and-add.

In mathematics, the factorial of a non-negative integer $,$ denoted by $,$ is the product of all positive integers less than or equal to $.$ The factorial of also equals the product of $with the next smaller factorial: For example, The value of 0! is 1, according to the convention for an empty product.$

<span class="mw-page-title-main">Fast Fourier transform</span> O(N log N) discrete Fourier transform algorithm

A fast Fourier transform (FFT) is an algorithm that computes the Discrete Fourier Transform (DFT) of a sequence, or its inverse (IDFT). Fourier analysis converts a signal from its original domain to a representation in the frequency domain and vice versa. The DFT is obtained by decomposing a sequence of values into components of different frequencies. This operation is useful in many fields, but computing it directly from the definition is often too slow to be practical. An FFT rapidly computes such transformations by factorizing the DFT matrix into a product of sparse factors. As a result, it manages to reduce the complexity of computing the DFT from $, which arises if one simply applies the definition of DFT, to, where n is the data size. The difference in speed can be enormous, especially for long data sets where n may be in the thousands or millions. In the presence of round-off error, many FFT algorithms are much more accurate than evaluating the DFT definition directly or indirectly. There are many different FFT algorithms based on a wide range of published theories, from simple complex-number arithmetic to group theory and number theory.$

In mathematics, integer factorization is the decomposition of a positive integer into a product of integers. Every positive integer greater than 1 is either the product of two or more integer factors greater than 1, in which case it is called a composite number, or it is not, in which case it is called a prime number. For example, $15$ is a composite number because $15 = 3 \cdot 5$ , but $7$ is a prime number because it cannot be decomposed in this way. If one of the factors is composite, it can in turn be written as a product of smaller factors, for example $60 = 3 \cdot 20 = 3 \cdot (5 \cdot 4)$ . Continuing this process until every factor is prime is called prime factorization; the result is always unique up to the order of the factors by the prime factorization theorem.

A multiplication algorithm is an algorithm to multiply two numbers. Depending on the size of the numbers, different algorithms are more efficient than others. Numerous algorithms are known and there has been much research into the topic.

In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor.

In computational number theory, a variety of algorithms make it possible to generate prime numbers efficiently. These are used in various applications, for example hashing, public-key cryptography, and search of prime factors in large numbers.

<span class="mw-page-title-main">Gene H. Golub</span> American mathematician (1932–2007)

Gene Howard Golub, was an American numerical analyst who taught at Stanford University as Fletcher Jones Professor of Computer Science and held a courtesy appointment in electrical engineering.

In analytic number theory, the Dickman function or Dickman–de Bruijn functionρ is a special function used to estimate the proportion of smooth numbers up to a given bound. It was first studied by actuary Karl Dickman, who defined it in his only mathematical publication, which is not easily available, and later studied by the Dutch mathematician Nicolaas Govert de Bruijn.

In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally independent graphs.

In mathematics, a Cauchy matrix, named after Augustin-Louis Cauchy, is an m×n matrix with elements a_ij in the form

In mathematics, the Riemann hypothesis is the conjecture that the Riemann zeta function has its zeros only at the negative even integers and complex numbers with real part ⁠1/2⁠. Many consider it to be the most important unsolved problem in pure mathematics. It is of great interest in number theory because it implies results about the distribution of prime numbers. It was proposed by Bernhard Riemann, after whom it is named.

Because matrix multiplication is such a central operation in many numerical algorithms, much work has been invested in making matrix multiplication algorithms efficient. Applications of matrix multiplication in computational problems are found in many fields including scientific computing and pattern recognition and in seemingly unrelated problems such as counting the paths through a graph. Many different algorithms have been designed for multiplying matrices on different types of hardware, including parallel and distributed systems, where the computational work is spread over multiple processors.

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.

In numerical mathematics, hierarchical matrices (H-matrices) are used as data-sparse approximations of non-sparse matrices. While a sparse matrix of dimension $can be represented efficiently in units of storage by storing only its non-zero entries, a non-sparse matrix would require units of storage, and using this type of matrices for large problems would therefore be prohibitively expensive in terms of storage and computing time. Hierarchical matrices provide an approximation requiring only units of storage, where is a parameter controlling the accuracy of the approximation. In typical applications, e.g., when discretizing integral equations, preconditioning the resulting systems of linear equations, or solving elliptic partial differential equations, a rank proportional to with a small constant is sufficient to ensure an accuracy of . Compared to many other data-sparse representations of non-sparse matrices, hierarchical matrices offer a major advantage: the results of matrix arithmetic operations like matrix multiplication, factorization or inversion can be approximated in operations, where$

The Rybicki–Press algorithm is a fast algorithm for inverting a matrix whose entries are given by $, where and where the are sorted in order. The key observation behind the Rybicki-Press observation is that the matrix inverse of such a matrix is always a tridiagonal matrix, and tridiagonal systems of equations can be solved efficiently. It is a computational optimization of a general set of statistical methods developed to determine whether two noisy, irregularly sampled data sets are, in fact, dimensionally shifted representations of the same underlying function. The most common use of the algorithm is in the detection of periodicity in astronomical observations, such as for detecting quasars.$

Virginia Vassilevska Williams is a theoretical computer scientist and mathematician known for her research in computational complexity theory and algorithms. She is currently the Steven and Renee Finn Career Development Associate Professor of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology. She is notable for her breakthrough results in fast matrix multiplication, for her work on dynamic algorithms, and for helping to develop the field of fine-grained complexity.

Beresford Neill Parlett is an English applied mathematician, specializing in numerical analysis and scientific computation.

In mathematics and computer science, polynomial evaluation refers to computation of the value of a polynomial when its indeterminates are substituted for some values. In other words, evaluating the polynomial $at consists of computing See also Polynomial ring § Polynomial evaluation$

References

1 2 Schönhage, A.; Grotefeld, A.F.W.; Vetter, E. (1994). Fast Algorithms—A Multitape Turing Machine Implementation. BI Wissenschafts-Verlag. ISBN 978-3-411-16891-0. OCLC 897602049.
↑ Knuth 1997
↑ Harvey, D.; Van Der Hoeven, J. (2021). "Integer multiplication in time O (n log n)" (PDF). Annals of Mathematics. 193 (2): 563–617. doi:10.4007/annals.2021.193.2.4. S2CID 109934776.
↑ Klarreich, Erica (December 2019). "Multiplication hits the speed limit". Commun. ACM. 63 (1): 11–13. doi:10.1145/3371387. S2CID 209450552.
↑ Burnikel, Christoph; Ziegler, Joachim (1998). Fast Recursive Division. Forschungsberichte des Max-Planck-Instituts für Informatik. Saarbrücken: MPI Informatik Bibliothek & Dokumentation. OCLC 246319574. MPII-98-1-022.
↑ Schönhage, Arnold (1980). "Storage Modification Machines". SIAM Journal on Computing. 9 (3): 490–508. doi:10.1137/0209036.
↑ Borwein, J.; Borwein, P. (1987). Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity. Wiley. ISBN 978-0-471-83138-9. OCLC 755165897.
↑ Chudnovsky, David; Chudnovsky, Gregory (1988). "Approximations and complex multiplication according to Ramanujan". Ramanujan revisited: Proceedings of the Centenary Conference. Academic Press. pp. 375–472. ISBN 978-0-01-205856-5.
↑ Brent, Richard P. (2014) [1975]. "Multiple-precision zero-finding methods and the complexity of elementary function evaluation". In Traub, J.F. (ed.). Analytic Computational Complexity. Elsevier. pp. 151–176. arXiv: 1004.3412 . ISBN 978-1-4832-5789-1.
1 2 Richard P. Brent (2020), The Borwein Brothers, Pi and the AGM, Springer Proceedings in Mathematics & Statistics, vol. 313, arXiv: 1802.07558 , doi:10.1007/978-3-030-36568-4, ISBN 978-3-030-36567-7, S2CID 214742997
↑ Sorenson, J. (1994). "Two Fast GCD Algorithms". Journal of Algorithms. 16 (1): 110–144. doi:10.1006/jagm.1994.1006.
↑ Crandall, R.; Pomerance, C. (2005). "Algorithm 9.4.7 (Stehlé-Zimmerman binary-recursive-gcd)". Prime Numbers – A Computational Perspective (2nd ed.). Springer. pp. 471–3. ISBN 978-0-387-28979-3.
↑ Möller N (2008). "On Schönhage's algorithm and subquadratic integer gcd computation" (PDF). Mathematics of Computation. 77 (261): 589–607. Bibcode:2008MaCom..77..589M. doi: 10.1090/S0025-5718-07-02017-0 .
↑ Bernstein, D.J. "Faster Algorithms to Find Non-squares Modulo Worst-case Integers".
↑ Brent, Richard P.; Zimmermann, Paul (2010). "An $O(M(n)\log n)$ algorithm for the Jacobi symbol". International Algorithmic Number Theory Symposium. Springer. pp. 83–95. arXiv: 1004.2091 . doi:10.1007/978-3-642-14518-6_10. ISBN 978-3-642-14518-6. S2CID 7632655.
↑ Borwein, P. (1985). "On the complexity of calculating factorials". Journal of Algorithms. 6 (3): 376–380. doi:10.1016/0196-6774(85)90006-9.
↑ Lenstra jr., H.W.; Pomerance, Carl (2019). "Primality testing with Gaussian periods" (PDF). Journal of the European Mathematical Society . 21 (4): 1229–69. doi:10.4171/JEMS/861. hdl:21.11116/0000-0005-717D-0.
↑ Tao, Terence (2010). "1.11 The AKS primality test". An epsilon of room, II: Pages from year three of a mathematical blog. Graduate Studies in Mathematics. Vol. 117. American Mathematical Society. pp. 82–86. doi:10.1090/gsm/117. ISBN 978-0-8218-5280-4. MR 2780010.
↑ Morain, F. (2007). "Implementing the asymptotically fast version of the elliptic curve primality proving algorithm". Mathematics of Computation . 76 (257): 493–505. arXiv: math/0502097 . Bibcode:2007MaCom..76..493M. doi:10.1090/S0025-5718-06-01890-4. MR 2261033. S2CID 133193.
↑ Pomerance, Carl; Selfridge, John L.; Wagstaff, Jr., Samuel S. (July 1980). "The pseudoprimes to 25·10⁹" (PDF). Mathematics of Computation. 35 (151): 1003–26. doi: 10.1090/S0025-5718-1980-0572872-7 . JSTOR 2006210.
↑ Baillie, Robert; Wagstaff, Jr., Samuel S. (October 1980). "Lucas Pseudoprimes" (PDF). Mathematics of Computation. 35 (152): 1391–1417. doi: 10.1090/S0025-5718-1980-0583518-6 . JSTOR 2006406. MR 0583518.
1 2 Monier, Louis (1980). "Evaluation and comparison of two efficient probabilistic primality testing algorithms". Theoretical Computer Science . 12 (1): 97–108. doi: 10.1016/0304-3975(80)90007-9 . MR 0582244.
↑ Alman, Josh; Williams, Virginia Vassilevska (2020), "A Refined Laser Method and Faster Matrix Multiplication", 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), pp. 522–539, arXiv: 2010.05846 , doi:10.1137/1.9781611976465.32, ISBN 978-1-61197-646-5, S2CID 222290442
↑ Davie, A.M.; Stothers, A.J. (2013), "Improved bound for complexity of matrix multiplication", Proceedings of the Royal Society of Edinburgh, 143A (2): 351–370, doi:10.1017/S0308210511001648, S2CID 113401430
↑ Vassilevska Williams, Virginia (2014), Breaking the Coppersmith-Winograd barrier: Multiplying matrices in O(n^2.373) time
↑ Le Gall, François (2014), "Powers of tensors and fast matrix multiplication", Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation — ISSAC '14, p. 23, arXiv: 1401.7714 , Bibcode:2014arXiv1401.7714L, doi:10.1145/2608628.2627493, ISBN 9781450325011, S2CID 353236
1 2 Le Gall, François; Urrutia, Floren (2018). "Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor". In Czumaj, Artur (ed.). Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611975031.67. ISBN 978-1-61197-503-1. S2CID 33396059.
↑ Knight, Philip A. (May 1995). "Fast rectangular matrix multiplication and QR decomposition". Linear Algebra and Its Applications. 221: 69–81. doi: 10.1016/0024-3795(93)00230-w . ISSN 0024-3795.
↑ Rote, G. (2001). "Division-free algorithms for the determinant and the pfaffian: algebraic and combinatorial approaches" (PDF). Computational discrete mathematics. Springer. pp. 119–135. ISBN 3-540-45506-X.
↑ Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974). "Theorem 6.6". The Design and Analysis of Computer Algorithms. Addison-Wesley. p. 241. ISBN 978-0-201-00029-0.
↑ Fraleigh, J.B.; Beauregard, R.A. (1987). Linear Algebra (3rd ed.). Addison-Wesley. p. 95. ISBN 978-0-201-15459-7.
↑ Preparata, F.P.; Sarwate, D.V. (April 1978). "An improved parallel processor bound in fast matrix inversion". Information Processing Letters. 7 (3): 148–150. doi: 10.1016/0020-0190(78)90079-0 .
↑ Galil, Zvi; Pan, Victor (January 16, 1989). "Parallel evaluation of the determinant and of the inverse of a matrix". Information Processing Letters. 30 (1): 148–150. doi: 10.1016/0020-0190(89)90173-7 ., in which the $O(n^{3})$ term is reduced
↑ Cohn, Henry; Kleinberg, Robert; Szegedy, Balazs; Umans, Chris (2005). "Group-theoretic Algorithms for Matrix Multiplication". Proceedings of the 46th Annual Symposium on Foundations of Computer Science. IEEE. pp. 379–388. arXiv: math.GR/0511460 . doi:10.1109/SFCS.2005.39. ISBN 0-7695-2468-0. S2CID 6429088.