Computational complexity of mathematical operations

Last updated
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 Comparison computational complexity.svg
Graphs of functions commonly used in the analysis of algorithms, showing the number of operations versus input size for each function

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

Contents

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, below stands in for the complexity of the chosen multiplication algorithm.

Arithmetic functions

This table lists the complexity of mathematical operations on integers.

OperationInputOutputAlgorithmComplexity
Addition Two -digit numbersOne -digit numberSchoolbook addition with carry
Subtraction Two -digit numbersOne -digit numberSchoolbook subtraction with borrow
Multiplication Two -digit numbers
One -digit number Schoolbook long multiplication
Karatsuba algorithm
3-way Toom–Cook multiplication
-way Toom–Cook multiplication
Mixed-level Toom–Cook (Knuth 4.3.3-T) [2]
Schönhage–Strassen algorithm
Harvey-Hoeven algorithm [3] [4]
Division Two -digit numbersOne -digit number Schoolbook long division
Burnikel–Ziegler Divide-and-Conquer Division [5]
Newton–Raphson division
Square root One -digit numberOne -digit number Newton's method
Modular exponentiation Two -digit integers and a -bit exponentOne -digit integerRepeated multiplication and reduction
Exponentiation by squaring
Exponentiation with Montgomery reduction

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. For this section indicates the time needed for multiplying two polynomials of degree at most . [7] :242

OperationInputOutputAlgorithmComplexity
Polynomial evaluationOne polynomial of degree with integer coefficientsOne numberDirect evaluation
Horner's method
Polynomial multipoint evaluationOne polynomial of degree less than with integer coefficients and numbers as evaluation points numbersDirect evaluation
Fast multipoint evaluation [7] :295
Polynomial gcd (over or )Two polynomials of degree with integer coefficientsOne polynomial of degree at most Euclidean algorithm
Fast Euclidean algorithm [7] :318 (Lehmer [7] :324)

Special functions

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

Elementary functions

The elementary functions are constructed by composing arithmetic operations, the exponential function (), the natural logarithm (), trigonometric functions (), 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 or in the complex domain can be computed with some complexity, then that complexity is attainable for all other elementary functions.

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

AlgorithmApplicabilityComplexity
Taylor series; repeated argument reduction (e.g. ) and direct summation
Taylor series; FFT-based acceleration
Taylor series; binary splitting + bit-burst algorithm [9]
Arithmetic–geometric mean iteration [10]

It is not known whether is the optimal complexity for elementary functions. The best known lower bound is the trivial bound .

Non-elementary functions

FunctionInputAlgorithmComplexity
Gamma function -digit numberSeries approximation of the incomplete gamma function
Fixed rational numberHypergeometric series
, for integer. Arithmetic-geometric mean iteration
Hypergeometric function -digit number(As described in Borwein & Borwein)
Fixed rational numberHypergeometric series

Mathematical constants

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

ConstantAlgorithmComplexity
Golden ratio, Newton's method
Square root of 2, Newton's method
Euler's number, Binary splitting of the Taylor series for the exponential function
Newton inversion of the natural logarithm
Pi, Binary splitting of the arctan series in Machin's formula [11]
Gauss–Legendre algorithm [11]
Euler's constant, Sweeney's method (approximation in terms of the exponential integral)

Number theory

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

OperationInputOutputAlgorithmComplexity
Greatest common divisor Two -digit integersOne integer with at most digits Euclidean algorithm
Binary GCD algorithm
Left/right k-ary binary GCD algorithm [12]
Stehlé–Zimmermann algorithm [13]
Schönhage controlled Euclidean descent algorithm [14]
Jacobi symbol Two -digit integers, or Schönhage controlled Euclidean descent algorithm [15]
Stehlé–Zimmermann algorithm [16]
Factorial A positive integer less than One -digit integerBottom-up multiplication
Binary splitting
Exponentiation of the prime factors of , [17]
[1]
Primality test A -digit integerTrue or false AKS primality test [18] [19]
, assuming Agrawal's conjecture
Elliptic curve primality proving heuristically [20]
Baillie–PSW primality test [21] [22]
Miller–Rabin primality test [23]
Solovay–Strassen primality test [23]
Integer factorization A -bit input integerA set of factors General number field sieve [nb 1]
Shor's algorithm , 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.

OperationInputOutputAlgorithmComplexity
Matrix multiplication Two matricesOne matrix Schoolbook matrix multiplication
Strassen algorithm
Coppersmith–Winograd algorithm (galactic algorithm)
Optimized CW-like algorithms [24] [25] [26] [27] (galactic algorithms)
One matrix, and
one matrix
One matrixSchoolbook matrix multiplication
One matrix, and
one matrix, for some
One matrixAlgorithms given in [28] , where upper bounds on are given in [28]
Matrix inversion One matrixOne matrix Gauss–Jordan elimination
Strassen algorithm
Coppersmith–Winograd algorithm
Optimized CW-like algorithms
Singular value decomposition One matrixOne matrix,
one matrix, &
one matrix
Bidiagonalization and QR algorithm
()
One matrix,
one matrix, &
one matrix
Bidiagonalization and QR algorithm
()
QR decomposition One matrixOne matrix, &
one matrix
Algorithms in [29]
()
Determinant One matrixOne number Laplace expansion
Division-free algorithm [30]
LU decomposition
Bareiss algorithm
Fast matrix multiplication [31]
Back substitution Triangular matrix solutionsBack substitution [32]
Characteristic polynomialOne matrixOne degree- polynomial Faddeev-LeVerrier algorithm
Samuelson-Berkowitz algorithm (smaller constant factor)
Preparata-Sarwate algorithm [33] [34]

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. [35]

Transforms

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

OperationInputOutputAlgorithmComplexity
Discrete Fourier transform Finite data sequence of size Set of complex numbersSchoolbook
Fast Fourier transform

Notes

  1. This form of sub-exponential time is valid for all . A more precise form of the complexity can be given as

References

  1. 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.
  2. Knuth 1997
  3. 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.
  4. Klarreich, Erica (December 2019). "Multiplication hits the speed limit". Commun. ACM. 63 (1): 11–13. doi:10.1145/3371387. S2CID   209450552.
  5. 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.
  6. Schönhage, Arnold (1980). "Storage Modification Machines". SIAM Journal on Computing. 9 (3): 490–508. doi:10.1137/0209036.
  7. 1 2 3 4 von zur Gathen, J.; Gerhard, J. (2013). Modern Computer Algebra (3rd ed.). Cambridge University Press. ISBN   9781139856065.
  8. 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.
  9. 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.
  10. 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.
  11. 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
  12. Sorenson, J. (1994). "Two Fast GCD Algorithms". Journal of Algorithms. 16 (1): 110–144. doi:10.1006/jagm.1994.1006.
  13. 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.
  14. 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 .
  15. Bernstein, D.J. "Faster Algorithms to Find Non-squares Modulo Worst-case Integers".
  16. Brent, Richard P.; Zimmermann, Paul (2010). "An 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.
  17. Borwein, P. (1985). "On the complexity of calculating factorials". Journal of Algorithms. 6 (3): 376–380. doi:10.1016/0196-6774(85)90006-9.
  18. 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.
  19. 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.
  20. 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.
  21. 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.
  22. 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.
  23. 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.
  24. 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
  25. 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
  26. Vassilevska Williams, Virginia (2014), Breaking the Coppersmith-Winograd barrier: Multiplying matrices in O(n2.373) time
  27. 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
  28. 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.
  29. 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.
  30. 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.
  31. 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.
  32. Fraleigh, J.B.; Beauregard, R.A. (1987). Linear Algebra (3rd ed.). Addison-Wesley. p. 95. ISBN   978-0-201-15459-7.
  33. 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 .
  34. 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 term is reduced
  35. 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