Computational complexity of mathematical operations
Algorithmic runtime requirements for common math procedures
Graphs of functions commonly used in the analysis of algorithms, showing the number of operations
N
{\displaystyle N}
versus input size
n
{\displaystyle n}
for each function
The following tables list the computational complexity of various algorithms for common mathematical operations .
Here, complexity refers to the time complexity of performing computations on a multitape Turing machine .[ 1] See big O notation for an explanation of the notation used.
Note: Due to the variety of multiplication algorithms,
M
(
n
)
{\displaystyle M(n)}
below stands in for the complexity of the chosen multiplication algorithm.
Arithmetic functions
This table lists the complexity of mathematical operations on integers.
Operation
Input
Output
Algorithm
Complexity
Addition
Two
n
{\displaystyle n}
-digit numbers
One
n
+
1
{\displaystyle n+1}
-digit number
Schoolbook addition with carry
Θ Θ -->
(
n
)
{\displaystyle \Theta (n)}
Subtraction
Two
n
{\displaystyle n}
-digit numbers
One
n
+
1
{\displaystyle n+1}
-digit number
Schoolbook subtraction with borrow
Θ Θ -->
(
n
)
{\displaystyle \Theta (n)}
Multiplication
Two
n
{\displaystyle n}
-digit numbers
One
2
n
{\displaystyle 2n}
-digit number
Schoolbook long multiplication
O
(
n
2
)
{\displaystyle O{\mathord {\left(n^{2}\right)}}}
Karatsuba algorithm
O
(
n
1.585
)
{\displaystyle O{\mathord {\left(n^{1.585}\right)}}}
3-way Toom–Cook multiplication
O
(
n
1.465
)
{\displaystyle O{\mathord {\left(n^{1.465}\right)}}}
k
{\displaystyle k}
-way Toom–Cook multiplication
O
(
n
log
-->
(
2
k
− − -->
1
)
log
-->
k
)
{\displaystyle O{\mathord {\left(n^{\frac {\log(2k-1)}{\log k}}\right)}}}
Mixed-level Toom–Cook (Knuth 4.3.3-T)[ 2]
O
(
n
2
2
log
-->
n
log
-->
n
)
{\displaystyle O{\mathord {\left(n\,2^{\sqrt {2\log n}}\,\log n\right)}}}
Schönhage–Strassen algorithm
O
(
n
log
-->
n
log
-->
log
-->
n
)
{\displaystyle O{\mathord {\left(n\log n\log \log n\right)}}}
Harvey-Hoeven algorithm [ 3] [ 4]
O
(
n
log
-->
n
)
{\displaystyle O(n\log n)}
Division
Two
n
{\displaystyle n}
-digit numbers
One
n
{\displaystyle n}
-digit number
Schoolbook long division
O
(
n
2
)
{\displaystyle O{\mathord {\left(n^{2}\right)}}}
Burnikel–Ziegler Divide-and-Conquer Division[ 5]
O
(
M
(
n
)
log
-->
n
)
{\displaystyle O(M(n)\log n)}
Newton–Raphson division
O
(
M
(
n
)
)
{\displaystyle O(M(n))}
Square root
One
n
{\displaystyle n}
-digit number
One
n
{\displaystyle n}
-digit number
Newton's method
O
(
M
(
n
)
)
{\displaystyle O(M(n))}
Modular exponentiation
Two
n
{\displaystyle n}
-digit integers and a
k
{\displaystyle k}
-bit exponent
One
n
{\displaystyle n}
-digit integer
Repeated multiplication and reduction
O
(
M
(
n
)
2
k
)
{\displaystyle O{\mathord {\left(M(n)\,2^{k}\right)}}}
Exponentiation by squaring
O
(
M
(
n
)
k
)
{\displaystyle O(M(n)\,k)}
Exponentiation with Montgomery reduction
O
(
M
(
n
)
k
)
{\displaystyle 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
{\displaystyle n}
with integer coefficients
One number
Direct evaluation
Θ Θ -->
(
n
)
{\displaystyle \Theta (n)}
Horner's method
Θ Θ -->
(
n
)
{\displaystyle \Theta (n)}
Polynomial gcd (over
Z
[
x
]
{\displaystyle \mathbb {Z} [x]}
or
F
[
x
]
{\displaystyle F[x]}
)
Two polynomials of degree
n
{\displaystyle n}
with integer coefficients
One polynomial of degree at most
n
{\displaystyle n}
Euclidean algorithm
O
(
n
2
)
{\displaystyle O{\mathord {\left(n^{2}\right)}}}
Fast Euclidean algorithm (Lehmer)[citation needed ]
O
(
M
(
n
)
log
-->
n
)
{\displaystyle 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
{\displaystyle \exp }
), the natural logarithm (
log
{\displaystyle \log }
), trigonometric functions (
sin
,
cos
{\displaystyle \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
{\displaystyle \exp }
or
log
{\displaystyle \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
{\displaystyle 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
-->
(
2
x
)
=
[
exp
-->
(
x
)
]
2
{\displaystyle \exp(2x)=[\exp(x)]^{2}}
) and direct summation
exp
,
log
,
sin
,
cos
,
arctan
{\displaystyle \exp ,\log ,\sin ,\cos ,\arctan }
O
(
M
(
n
)
n
1
/
2
)
{\displaystyle O{\mathord {\left(M(n)n^{1/2}\right)}}}
Taylor series; FFT -based acceleration
exp
,
log
,
sin
,
cos
,
arctan
{\displaystyle \exp ,\log ,\sin ,\cos ,\arctan }
O
(
M
(
n
)
n
1
/
3
(
log
-->
n
)
2
)
{\displaystyle 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
{\displaystyle \exp ,\log ,\sin ,\cos ,\arctan }
O
(
M
(
n
)
(
log
-->
n
)
2
)
{\displaystyle O{\mathord {\left(M(n)(\log n)^{2}\right)}}}
Arithmetic–geometric mean iteration[ 9]
exp
,
log
,
sin
,
cos
,
arctan
{\displaystyle \exp ,\log ,\sin ,\cos ,\arctan }
O
(
M
(
n
)
log
-->
n
)
{\displaystyle O(M(n)\log n)}
It is not known whether
O
(
M
(
n
)
log
-->
n
)
{\displaystyle O(M(n)\log n)}
is the optimal complexity for elementary functions. The best known lower bound is the trivial bound
Ω Ω -->
{\displaystyle \Omega }
(
M
(
n
)
)
{\displaystyle (M(n))}
.
Non-elementary functions
Function
Input
Algorithm
Complexity
Gamma function
n
{\displaystyle n}
-digit number
Series approximation of the incomplete gamma function
O
(
M
(
n
)
n
1
/
2
(
log
-->
n
)
2
)
{\displaystyle O{\mathord {\left(M(n)n^{1/2}(\log n)^{2}\right)}}}
Fixed rational number
Hypergeometric series
O
(
M
(
n
)
(
log
-->
n
)
2
)
{\displaystyle O{\mathord {\left(M(n)(\log n)^{2}\right)}}}
m
/
24
{\displaystyle m/24}
, for
m
{\displaystyle m}
integer.
Arithmetic-geometric mean iteration
O
(
M
(
n
)
log
-->
n
)
{\displaystyle O(M(n)\log n)}
Hypergeometric function
p
F
q
{\displaystyle {}_{p}\!F_{q}}
n
{\displaystyle n}
-digit number
(As described in Borwein & Borwein)
O
(
M
(
n
)
n
1
/
2
(
log
-->
n
)
2
)
{\displaystyle O{\mathord {\left(M(n)n^{1/2}(\log n)^{2}\right)}}}
Fixed rational number
Hypergeometric series
O
(
M
(
n
)
(
log
-->
n
)
2
)
{\displaystyle 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
{\displaystyle n}
correct digits.
Constant
Algorithm
Complexity
Golden ratio ,
ϕ ϕ -->
{\displaystyle \phi }
Newton's method
O
(
M
(
n
)
)
{\displaystyle O(M(n))}
Square root of 2 ,
2
{\displaystyle {\sqrt {2}}}
Newton's method
O
(
M
(
n
)
)
{\displaystyle O(M(n))}
Euler's number ,
e
{\displaystyle e}
Binary splitting of the Taylor series for the exponential function
O
(
M
(
n
)
log
-->
n
)
{\displaystyle O(M(n)\log n)}
Newton inversion of the natural logarithm
O
(
M
(
n
)
log
-->
n
)
{\displaystyle O(M(n)\log n)}
Pi ,
π π -->
{\displaystyle \pi }
Binary splitting of the arctan series in Machin's formula
O
(
M
(
n
)
(
log
-->
n
)
2
)
{\displaystyle O{\mathord {\left(M(n)(\log n)^{2}\right)}}}
[ 10]
Gauss–Legendre algorithm
O
(
M
(
n
)
log
-->
n
)
{\displaystyle O(M(n)\log n)}
[ 10]
Euler's constant ,
γ γ -->
{\displaystyle \gamma }
Sweeney's method (approximation in terms of the exponential integral )
O
(
M
(
n
)
(
log
-->
n
)
2
)
{\displaystyle 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
{\displaystyle n}
-digit integers
One integer with at most
n
{\displaystyle n}
digits
Euclidean algorithm
O
(
n
2
)
{\displaystyle O{\mathord {\left(n^{2}\right)}}}
Binary GCD algorithm
O
(
n
2
)
{\displaystyle O{\mathord {\left(n^{2}\right)}}}
Left/right k -ary binary GCD algorithm[ 11]
O
(
n
2
log
-->
n
)
{\displaystyle O{\mathord {\left({\frac {n^{2}}{\log n}}\right)}}}
Stehlé–Zimmermann algorithm [ 12]
O
(
M
(
n
)
log
-->
n
)
{\displaystyle O(M(n)\log n)}
Schönhage controlled Euclidean descent algorithm [ 13]
O
(
M
(
n
)
log
-->
n
)
{\displaystyle O(M(n)\log n)}
Jacobi symbol
Two
n
{\displaystyle n}
-digit integers
0
{\displaystyle 0}
,
− − -->
1
{\displaystyle -1}
or
1
{\displaystyle 1}
Schönhage controlled Euclidean descent algorithm[ 14]
O
(
M
(
n
)
log
-->
n
)
{\displaystyle O(M(n)\log n)}
Stehlé–Zimmermann algorithm[ 15]
O
(
M
(
n
)
log
-->
n
)
{\displaystyle O(M(n)\log n)}
Factorial
A positive integer less than
m
{\displaystyle m}
One
O
(
m
log
-->
m
)
{\displaystyle O(m\log m)}
-digit integer
Bottom-up multiplication
O
(
M
(
m
2
)
log
-->
m
)
{\displaystyle O{\mathord {\left(M\left(m^{2}\right)\log m\right)}}}
Binary splitting
O
(
M
(
m
log
-->
m
)
log
-->
m
)
{\displaystyle O(M(m\log m)\log m)}
Exponentiation of the prime factors of
m
{\displaystyle m}
O
(
M
(
m
log
-->
m
)
log
-->
log
-->
m
)
{\displaystyle O(M(m\log m)\log \log m)}
,[ 16]
O
(
M
(
m
log
-->
m
)
)
{\displaystyle O(M(m\log m))}
[ 1]
Primality test
A
n
{\displaystyle n}
-digit integer
True or false
AKS primality test
O
(
n
6
+
o
(
1
)
)
{\displaystyle O{\mathord {\left(n^{6+o(1)}\right)}}}
[ 17] [ 18]
O
(
n
3
)
{\displaystyle O(n^{3})}
, assuming Agrawal's conjecture
Elliptic curve primality proving
O
(
n
4
+
ε ε -->
)
{\displaystyle O{\mathord {\left(n^{4+\varepsilon }\right)}}}
heuristically[ 19]
Baillie–PSW primality test
O
(
n
2
+
ε ε -->
)
{\displaystyle O{\mathord {\left(n^{2+\varepsilon }\right)}}}
[ 20] [ 21]
Miller–Rabin primality test
O
(
k
n
2
+
ε ε -->
)
{\displaystyle O{\mathord {\left(kn^{2+\varepsilon }\right)}}}
[ 22]
Solovay–Strassen primality test
O
(
k
n
2
+
ε ε -->
)
{\displaystyle O{\mathord {\left(kn^{2+\varepsilon }\right)}}}
[ 22]
Integer factorization
A
b
{\displaystyle b}
-bit input integer
A set of factors
General number field sieve
O
(
(
1
+
ε ε -->
)
b
)
{\displaystyle O{\mathord {\left((1+\varepsilon )^{b}\right)}}}
[ nb 1]
Shor's algorithm
O
(
M
(
b
)
b
)
{\displaystyle 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
× × -->
n
{\displaystyle n\times n}
matrices
One
n
× × -->
n
{\displaystyle n\times n}
matrix
Schoolbook matrix multiplication
O
(
n
3
)
{\displaystyle O(n^{3})}
Strassen algorithm
O
(
n
2.807
)
{\displaystyle O{\mathord {\left(n^{2.807}\right)}}}
Coppersmith–Winograd algorithm (galactic algorithm )
O
(
n
2.376
)
{\displaystyle O{\mathord {\left(n^{2.376}\right)}}}
Optimized CW-like algorithms [ 23] [ 24] [ 25] [ 26] (galactic algorithms )
O
(
n
ψ ψ -->
=
2.3728596
)
{\displaystyle O{\mathord {\left(n^{\psi =2.3728596}\right)}}}
Matrix multiplication
One
n
× × -->
m
{\displaystyle n\times m}
matrix, and one
m
× × -->
p
{\displaystyle m\times p}
matrix
One
n
× × -->
p
{\displaystyle n\times p}
matrix
Schoolbook matrix multiplication
O
(
n
m
p
)
{\displaystyle O(nmp)}
Matrix multiplication
One
n
× × -->
⌈
n
k
⌉
{\displaystyle n\times \left\lceil n^{k}\right\rceil }
matrix, and one
⌈
n
k
⌉
× × -->
n
{\displaystyle \left\lceil n^{k}\right\rceil \times n}
matrix, for some
k
≥ ≥ -->
0
{\displaystyle k\geq 0}
One
n
× × -->
n
{\displaystyle n\times n}
matrix
Algorithms given in [ 27]
O
(
n
ω ω -->
(
k
)
+
ϵ ϵ -->
)
{\displaystyle O(n^{\omega (k)+\epsilon })}
, where upper bounds on
ω ω -->
(
k
)
{\displaystyle \omega (k)}
are given in [ 27]
Matrix inversion
One
n
× × -->
n
{\displaystyle n\times n}
matrix
One
n
× × -->
n
{\displaystyle n\times n}
matrix
Gauss–Jordan elimination
O
(
n
3
)
{\displaystyle O{\mathord {\left(n^{3}\right)}}}
Strassen algorithm
O
(
n
2.807
)
{\displaystyle O{\mathord {\left(n^{2.807}\right)}}}
Coppersmith–Winograd algorithm
O
(
n
2.376
)
{\displaystyle O{\mathord {\left(n^{2.376}\right)}}}
Optimized CW-like algorithms
O
(
n
ψ ψ -->
)
{\displaystyle O{\mathord {\left(n^{\psi }\right)}}}
Singular value decomposition
One
m
× × -->
n
{\displaystyle m\times n}
matrix
One
m
× × -->
m
{\displaystyle m\times m}
matrix, one
m
× × -->
n
{\displaystyle m\times n}
matrix, & one
n
× × -->
n
{\displaystyle n\times n}
matrix
Bidiagonalization and QR algorithm
O
(
m
2
n
)
{\displaystyle O{\mathord {\left(m^{2}n\right)}}}
(
m
≥ ≥ -->
n
{\displaystyle m\geq n}
)
One
m
× × -->
n
{\displaystyle m\times n}
matrix, one
n
× × -->
n
{\displaystyle n\times n}
matrix, & one
n
× × -->
n
{\displaystyle n\times n}
matrix
Bidiagonalization and QR algorithm
O
(
m
n
2
)
{\displaystyle O{\mathord {\left(mn^{2}\right)}}}
(
m
≤ ≤ -->
n
{\displaystyle m\leq n}
)
QR decomposition
One
m
× × -->
n
{\displaystyle m\times n}
matrix
One
m
× × -->
n
{\displaystyle m\times n}
matrix, & one
n
× × -->
n
{\displaystyle n\times n}
matrix
Algorithms in [ 28]
O
(
m
n
1
+
1
4
− − -->
ω ω -->
)
{\displaystyle O{\mathord {\left(mn^{1+{\frac {1}{4-\omega }}}\right)}}}
(
m
≥ ≥ -->
n
{\displaystyle m\geq n}
)
Determinant
One
n
× × -->
n
{\displaystyle n\times n}
matrix
One number
Laplace expansion
O
(
n
!
)
{\displaystyle O(n!)}
Division-free algorithm[ 29]
O
(
n
4
)
{\displaystyle O{\mathord {\left(n^{4}\right)}}}
LU decomposition
O
(
n
3
)
{\displaystyle O(n^{3})}
Bareiss algorithm
O
(
n
3
)
{\displaystyle O{\mathord {\left(n^{3}\right)}}}
Fast matrix multiplication[ 30]
O
(
n
ψ ψ -->
)
{\displaystyle O{\mathord {\left(n^{\psi }\right)}}}
Back substitution
Triangular matrix
n
{\displaystyle n}
solutions
Back substitution[ 31]
O
(
n
2
)
{\displaystyle O{\mathord {\left(n^{2}\right)}}}
Characteristic polynomial
One
n
× × -->
n
{\displaystyle n\times n}
matrix
One degree-
n
{\displaystyle n}
polynomial
Faddeev-LeVerrier algorithm
O
(
n
ψ ψ -->
+
1
)
{\displaystyle O(n^{\psi +1})}
Samuelson-Berkowitz algorithm
O
(
n
ψ ψ -->
+
1
)
{\displaystyle O(n^{\psi +1})}
(smaller constant factor)
Preparata-Sarwate algorithm [ 32] [ 33]
O
(
n
ψ ψ -->
+
1
/
2
+
n
3
)
{\displaystyle 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]
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
{\displaystyle n}
Set of complex numbers
Schoolbook
O
(
n
2
)
{\displaystyle O(n^{2})}
Fast Fourier transform
O
(
n
log
-->
n
)
{\displaystyle O(n\log n)}
Notes
^ This form of sub-exponential time is valid for all
ε ε -->
>
0
{\displaystyle \varepsilon >0}
. A more precise form of the complexity can be given as
O
(
exp
-->
64
9
b
(
log
-->
b
)
2
3
)
.
{\displaystyle O{\mathord {\left(\exp {\sqrt[{3}]{{\frac {64}{9}}b(\log b)^{2}}}\right)}}.}
References
^ a b 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 .
^ a b 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
)
{\displaystyle 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·109 " (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 .
^ a b 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(n2.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
^ a b 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
)
{\displaystyle 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 .
Further reading