Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Computational complexity of mathematical operations
open-in-new
<h2 id="arithmetic-functions">Arithmetic functions</h2> <p>This table lists the complexity of mathematical operations on integers. </p> <table><tbody><tr><th>Operation</th><th>Input</th><th>Output</th><th>Algorithm</th><th>Complexity</th></tr><tr><td><a href="/facts/Addition/apFWJBFB">Addition</a></td><td>Two n {\displaystyle n} -digit numbers</td><td>One n + 1 {\displaystyle n+1} -digit number</td><td>Schoolbook addition with carry</td><td> Θ ( n ) {\displaystyle \Theta (n)} </td></tr><tr><td><a href="/facts/Subtraction/dEUrp6k0">Subtraction</a></td><td>Two n {\displaystyle n} -digit numbers</td><td>One n {\displaystyle n} -digit number</td><td>Schoolbook subtraction with borrow</td><td> Θ ( n ) {\displaystyle \Theta (n)} </td></tr><tr><td rowspan="7"><a href="/facts/Multiplication/VtcUjpNv">Multiplication</a></td><td rowspan="7">Two n {\displaystyle n} -digit numbers</td><td rowspan="7">One 2 n {\displaystyle 2n} -digit number</td><td><a href="/facts/Multiplication_algorithm/68xf6EdK">Schoolbook long multiplication</a></td><td> O ( n 2 ) {\displaystyle O{\mathord {\left(n^{2}\right)}}} </td></tr><tr><td><a href="/facts/Karatsuba_algorithm/YFk3dnqX">Karatsuba algorithm</a></td><td> O ( n 1.585 ) {\displaystyle O{\mathord {\left(n^{1.585}\right)}}} </td></tr><tr><td>3-way <a href="/facts/Toom%25E2%2580%2593Cook_multiplication/5AuKo2IJ">Toom–Cook multiplication</a></td><td> O ( n 1.465 ) {\displaystyle O{\mathord {\left(n^{1.465}\right)}}} </td></tr><tr><td> k {\displaystyle k} -way Toom–Cook multiplication</td><td> O ( n log ( 2 k − 1 ) log k ) {\displaystyle O{\mathord {\left(n^{\frac {\log(2k-1)}{\log k}}\right)}}} </td></tr><tr><td>Mixed-level Toom–Cook (Knuth 4.3.3-T)<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a></td><td> O ( n 2 2 log n log n ) {\displaystyle O{\mathord {\left(n\,2^{\sqrt {2\log n}}\,\log n\right)}}} </td></tr><tr><td><a href="/facts/Sch%25C3%25B6nhage%25E2%2580%2593Strassen_algorithm/7dLGaI4d">Schönhage–Strassen algorithm</a></td><td> O ( n log n log log n ) {\displaystyle O{\mathord {\left(n\log n\log \log n\right)}}} </td></tr><tr><td><a href="/facts/Harvey-Hoeven_algorithm/68xf6EdK">Harvey-Hoeven algorithm</a><a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a><a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a></td><td> O ( n log n ) {\displaystyle O(n\log n)} </td></tr><tr><td rowspan="3"><a href="/facts/Division_(mathematics)/FqLKNkmq">Division</a></td><td rowspan="3">Two n {\displaystyle n} -digit numbers</td><td rowspan="3">One n {\displaystyle n} -digit number</td><td><a href="/facts/Long_division/W8Vd90Kw">Schoolbook long division</a></td><td> O ( n 2 ) {\displaystyle O{\mathord {\left(n^{2}\right)}}} </td></tr><tr><td>Burnikel–Ziegler Divide-and-Conquer Division<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a></td><td> O ( M ( n ) log n ) {\displaystyle O(M(n)\log n)} </td></tr><tr><td><a href="/facts/Newton%25E2%2580%2593Raphson_division/8xc3I1sJ">Newton–Raphson division</a></td><td> O ( M ( n ) ) {\displaystyle O(M(n))} </td></tr><tr><td><a href="/facts/Square_root/AfrzfBdQ">Square root</a></td><td>One n {\displaystyle n} -digit number</td><td>One n / 2 {\displaystyle n/2} -digit number</td><td><a href="/facts/Newton%2527s_method/VlRhI2FL">Newton's method</a></td><td> O ( M ( n ) ) {\displaystyle O(M(n))} </td></tr><tr><td rowspan="3"><a href="/facts/Modular_exponentiation/0STECS3P">Modular exponentiation</a></td><td rowspan="3">Two n {\displaystyle n} -digit integers and a k {\displaystyle k} -bit exponent</td><td rowspan="3">One n {\displaystyle n} -digit integer</td><td>Repeated multiplication and reduction</td><td> O ( M ( n ) 2 k ) {\displaystyle O{\mathord {\left(M(n)\,2^{k}\right)}}} </td></tr><tr><td><a href="/facts/Exponentiation_by_squaring/HP8H37AA">Exponentiation by squaring</a></td><td> O ( M ( n ) k ) {\displaystyle O(M(n)\,k)} </td></tr><tr><td>Exponentiation with <a href="/facts/Montgomery_reduction/C1UyVrKJ">Montgomery reduction</a></td><td> O ( M ( n ) k ) {\displaystyle O(M(n)\,k)} </td></tr></tbody></table> <p>On stronger computational models, specifically a <a href="/facts/Pointer_machine/0SdkYhF2">pointer machine</a> and consequently also a <a href="/facts/Random-access_machine/9NrNtVSd">unit-cost random-access machine</a> it is possible to multiply two n-bit numbers in time <i>O</i>(<i>n</i>).<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> </p> <h2 id="algebraic-functions">Algebraic functions</h2> <p>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. </p> <table><tbody><tr><th>Operation</th><th>Input</th><th>Output</th><th>Algorithm</th><th>Complexity</th></tr><tr><td rowspan="2"><a href="/facts/Polynomial/Lzak8VVx">Polynomial</a> evaluation</td><td rowspan="2">One polynomial of degree n {\displaystyle n} with integer coefficients</td><td rowspan="2">One number</td><td>Direct evaluation</td><td> Θ ( n ) {\displaystyle \Theta (n)} </td></tr><tr><td><a href="/facts/Horner%2527s_method/KIBtC85Q">Horner's method</a></td><td> Θ ( n ) {\displaystyle \Theta (n)} </td></tr><tr><td rowspan="2">Polynomial gcd (over Z [ x ] {\displaystyle \mathbb {Z} [x]} or F [ x ] {\displaystyle F[x]} )</td><td rowspan="2">Two polynomials of degree n {\displaystyle n} with integer coefficients</td><td rowspan="2">One polynomial of degree at most n {\displaystyle n} </td><td><a href="/facts/Euclidean_algorithm/wApql29c">Euclidean algorithm</a></td><td> O ( n 2 ) {\displaystyle O{\mathord {\left(n^{2}\right)}}} </td></tr><tr><td>Fast Euclidean algorithm (Lehmer)</td><td> O ( M ( n ) log n ) {\displaystyle O(M(n)\log n)} </td></tr></tbody></table> <h2 id="special-functions">Special functions</h2> <p>Many of the methods in this section are given in Borwein & Borwein.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> </p> <h3>Elementary functions</h3> <p>The <a href="/facts/Elementary_function/wVFyDwu8">elementary functions</a> are constructed by composing arithmetic operations, the <a href="/facts/Exponential_function/ewlYxvR2">exponential function</a> ( exp {\displaystyle \exp } ), the <a href="/facts/Natural_logarithm/PnreKEzI">natural logarithm</a> ( log {\displaystyle \log } ), <a href="/facts/Trigonometric_function/czej7ur0">trigonometric functions</a> ( 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 <a href="/facts/Analytic_function/JhL3z8FP">analytic</a> 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. </p><p>Below, the size n {\displaystyle n} refers to the number of digits of precision at which the function is to be evaluated. </p> <table><tbody><tr><th>Algorithm</th><th>Applicability</th><th>Complexity</th></tr><tr><td><a href="/facts/Taylor_series/M0aTuftH">Taylor series</a>; repeated argument reduction (e.g. exp ( 2 x ) = [ exp ( x ) ] 2 {\displaystyle \exp(2x)=[\exp(x)]^{2}} ) and direct summation</td><td> exp , log , sin , cos , arctan {\displaystyle \exp ,\log ,\sin ,\cos ,\arctan } </td><td> O ( M ( n ) n 1 / 2 ) {\displaystyle O{\mathord {\left(M(n)n^{1/2}\right)}}} </td></tr><tr><td>Taylor series; <a href="/facts/Fast_Fourier_transform/caT7UUCh">FFT</a>-based acceleration</td><td> exp , log , sin , cos , arctan {\displaystyle \exp ,\log ,\sin ,\cos ,\arctan } </td><td> O ( M ( n ) n 1 / 3 ( log n ) 2 ) {\displaystyle O{\mathord {\left(M(n)n^{1/3}(\log n)^{2}\right)}}} </td></tr><tr><td>Taylor series; <a href="/facts/Binary_splitting/yVk20XmE">binary splitting</a> + bit-burst algorithm<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a></td><td> exp , log , sin , cos , arctan {\displaystyle \exp ,\log ,\sin ,\cos ,\arctan } </td><td> O ( M ( n ) ( log n ) 2 ) {\displaystyle O{\mathord {\left(M(n)(\log n)^{2}\right)}}} </td></tr><tr><td><a href="/facts/Arithmetic%25E2%2580%2593geometric_mean/8PRN9UB4">Arithmetic–geometric mean</a> iteration<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a></td><td> exp , log , sin , cos , arctan {\displaystyle \exp ,\log ,\sin ,\cos ,\arctan } </td><td> O ( M ( n ) log n ) {\displaystyle O(M(n)\log n)} </td></tr></tbody></table> <p>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 <a href="/facts/Big_O_notation/weFFjSWg"> Ω {\displaystyle \Omega } </a> ( M ( n ) ) {\displaystyle (M(n))} . </p> <h3>Non-elementary functions</h3> <table><tbody><tr><th>Function</th><th>Input</th><th>Algorithm</th><th>Complexity</th></tr><tr><td rowspan="3"><a href="/facts/Gamma_function/SjGQcnyw">Gamma function</a></td><td> n {\displaystyle n} -digit number</td><td>Series approximation of the <a href="/facts/Incomplete_gamma_function/vojnYSu4">incomplete gamma function</a></td><td> O ( M ( n ) n 1 / 2 ( log n ) 2 ) {\displaystyle O{\mathord {\left(M(n)n^{1/2}(\log n)^{2}\right)}}} </td></tr><tr><td>Fixed rational number</td><td>Hypergeometric series</td><td> O ( M ( n ) ( log n ) 2 ) {\displaystyle O{\mathord {\left(M(n)(\log n)^{2}\right)}}} </td></tr><tr><td> m / 24 {\displaystyle m/24} , for m {\displaystyle m} integer.</td><td><a href="/facts/Arithmetic-geometric_mean/8PRN9UB4">Arithmetic-geometric mean</a> iteration</td><td> O ( M ( n ) log n ) {\displaystyle O(M(n)\log n)} </td></tr><tr><td rowspan="2"><a href="/facts/Hypergeometric_function/yTEC6NBJ">Hypergeometric function</a> p F q {\displaystyle {}_{p}\!F_{q}} </td><td> n {\displaystyle n} -digit number</td><td>(As described in Borwein & Borwein)</td><td> O ( M ( n ) n 1 / 2 ( log n ) 2 ) {\displaystyle O{\mathord {\left(M(n)n^{1/2}(\log n)^{2}\right)}}} </td></tr><tr><td>Fixed rational number</td><td>Hypergeometric series</td><td> O ( M ( n ) ( log n ) 2 ) {\displaystyle O{\mathord {\left(M(n)(\log n)^{2}\right)}}} </td></tr></tbody></table> <h3>Mathematical constants</h3> <p>This table gives the complexity of computing approximations to the given constants to n {\displaystyle n} correct digits. </p> <table><tbody><tr><th>Constant</th><th>Algorithm</th><th>Complexity</th></tr><tr><td><a href="/facts/Golden_ratio/anloSRmD">Golden ratio</a>, ϕ {\displaystyle \phi } </td><td><a href="/facts/Newton%2527s_method/VlRhI2FL">Newton's method</a></td><td> O ( M ( n ) ) {\displaystyle O(M(n))} </td></tr><tr><td><a href="/facts/Square_root_of_2/SD0sag94">Square root of 2</a>, 2 {\displaystyle {\sqrt {2}}} </td><td>Newton's method</td><td> O ( M ( n ) ) {\displaystyle O(M(n))} </td></tr><tr><td rowspan="2"><a href="/facts/E_(mathematical_constant)/coEtSBk8">Euler's number</a>, e {\displaystyle e} </td><td><a href="/facts/Binary_splitting/yVk20XmE">Binary splitting</a> of the Taylor series for the exponential function</td><td> O ( M ( n ) log n ) {\displaystyle O(M(n)\log n)} </td></tr><tr><td>Newton inversion of the natural logarithm</td><td> O ( M ( n ) log n ) {\displaystyle O(M(n)\log n)} </td></tr><tr><td rowspan="2"><a href="/facts/Pi/vC0UBj1q">Pi</a>, π {\displaystyle \pi } </td><td>Binary splitting of the arctan series in <a href="/facts/Machin%2527s_formula/1VPlhmYf">Machin's formula</a></td><td> O ( M ( n ) ( log n ) 2 ) {\displaystyle O{\mathord {\left(M(n)(\log n)^{2}\right)}}} <a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a></td></tr><tr><td><a href="/facts/Gauss%25E2%2580%2593Legendre_algorithm/QqzIk2L6">Gauss–Legendre algorithm</a></td><td> O ( M ( n ) log n ) {\displaystyle O(M(n)\log n)} <a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a></td></tr><tr><td><a href="/facts/Euler%25E2%2580%2593Mascheroni_constant/2kEgRvjC">Euler's constant</a>, γ {\displaystyle \gamma } </td><td>Sweeney's method (approximation in terms of the <a href="/facts/Exponential_integral/JF6aMcmL">exponential integral</a>)</td><td> O ( M ( n ) ( log n ) 2 ) {\displaystyle O{\mathord {\left(M(n)(\log n)^{2}\right)}}} </td></tr></tbody></table> <h2 id="number-theory">Number theory</h2> <p>Algorithms for <a href="/facts/Number_theory/zhoa7zrc">number theoretical</a> calculations are studied in <a href="/facts/Computational_number_theory/7Lu5N57C">computational number theory</a>. </p> <table><tbody><tr><th>Operation</th><th>Input</th><th>Output</th><th>Algorithm</th><th>Complexity</th></tr><tr><td rowspan="5"><a href="/facts/Greatest_common_divisor/kNFvBuKl">Greatest common divisor</a></td><td rowspan="5">Two n {\displaystyle n} -digit integers</td><td rowspan="5">One integer with at most n {\displaystyle n} digits</td><td><a href="/facts/Euclidean_algorithm/wApql29c">Euclidean algorithm</a></td><td> O ( n 2 ) {\displaystyle O{\mathord {\left(n^{2}\right)}}} </td></tr><tr><td><a href="/facts/Binary_GCD_algorithm/AS9LC3NQ">Binary GCD algorithm</a></td><td> O ( n 2 ) {\displaystyle O{\mathord {\left(n^{2}\right)}}} </td></tr><tr><td>Left/right <i>k</i>-ary binary GCD algorithm<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a></td><td> O ( n 2 log n ) {\displaystyle O{\mathord {\left({\frac {n^{2}}{\log n}}\right)}}} </td></tr><tr><td>Stehlé–Zimmermann algorithm<a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a></td><td> O ( M ( n ) log n ) {\displaystyle O(M(n)\log n)} </td></tr><tr><td>Schönhage controlled Euclidean descent algorithm<a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a></td><td> O ( M ( n ) log n ) {\displaystyle O(M(n)\log n)} </td></tr><tr><td rowspan="2"><a href="/facts/Jacobi_symbol/lHlojG0o">Jacobi symbol</a></td><td rowspan="2">Two n {\displaystyle n} -digit integers</td><td rowspan="2"> 0 {\displaystyle 0} , − 1 {\displaystyle -1} or 1 {\displaystyle 1} </td><td>Schönhage controlled Euclidean descent algorithm<a class="footnote-ref" id="fnref:15" href="#fn:15"><sup>15</sup></a></td><td> O ( M ( n ) log n ) {\displaystyle O(M(n)\log n)} </td></tr><tr><td>Stehlé–Zimmermann algorithm<a class="footnote-ref" id="fnref:16" href="#fn:16"><sup>16</sup></a></td><td> O ( M ( n ) log n ) {\displaystyle O(M(n)\log n)} </td></tr><tr><td rowspan="3"><a href="/facts/Factorial/kkfy1Bwe">Factorial</a></td><td rowspan="3">A positive integer less than m {\displaystyle m} </td><td rowspan="3">One O ( m log m ) {\displaystyle O(m\log m)} -digit integer</td><td>Bottom-up multiplication</td><td> O ( M ( m 2 ) log m ) {\displaystyle O{\mathord {\left(M\left(m^{2}\right)\log m\right)}}} </td></tr><tr><td>Binary splitting</td><td> O ( M ( m log m ) log m ) {\displaystyle O(M(m\log m)\log m)} </td></tr><tr><td>Exponentiation of the prime factors of m {\displaystyle m} </td><td> O ( M ( m log m ) log log m ) {\displaystyle O(M(m\log m)\log \log m)} ,<a class="footnote-ref" id="fnref:17" href="#fn:17"><sup>17</sup></a> O ( M ( m log m ) ) {\displaystyle O(M(m\log m))} <a class="footnote-ref" id="fnref:18" href="#fn:18"><sup>18</sup></a></td></tr><tr><td rowspan="5"><a href="/facts/Primality_test/dLMr8E0u">Primality test</a></td><td rowspan="5">A n {\displaystyle n} -digit integer</td><td rowspan="5">True or false</td><td><a href="/facts/AKS_primality_test/VRkvQVeT">AKS primality test</a></td><td> O ( n 6 + o ( 1 ) ) {\displaystyle O{\mathord {\left(n^{6+o(1)}\right)}}} <a class="footnote-ref" id="fnref:19" href="#fn:19"><sup>19</sup></a><a class="footnote-ref" id="fnref:20" href="#fn:20"><sup>20</sup></a> O ( n 3 ) {\displaystyle O(n^{3})} , assuming <a href="/facts/Agrawal%2527s_conjecture/WzpQszey">Agrawal's conjecture</a></td></tr><tr><td><a href="/facts/Elliptic_curve_primality_proving/S7310ePf">Elliptic curve primality proving</a></td><td> O ( n 4 + ε ) {\displaystyle O{\mathord {\left(n^{4+\varepsilon }\right)}}} <i>heuristically<a class="footnote-ref" id="fnref:21" href="#fn:21"><sup>21</sup></a></i></td></tr><tr><td><a href="/facts/Baillie%25E2%2580%2593PSW_primality_test/y2FlVSfx">Baillie–PSW primality test</a></td><td> O ( n 2 + ε ) {\displaystyle O{\mathord {\left(n^{2+\varepsilon }\right)}}} <a class="footnote-ref" id="fnref:22" href="#fn:22"><sup>22</sup></a><a class="footnote-ref" id="fnref:23" href="#fn:23"><sup>23</sup></a></td></tr><tr><td><a href="/facts/Miller%25E2%2580%2593Rabin_primality_test/FWx93kWC">Miller–Rabin primality test</a></td><td> O ( k n 2 + ε ) {\displaystyle O{\mathord {\left(kn^{2+\varepsilon }\right)}}} <a class="footnote-ref" id="fnref:24" href="#fn:24"><sup>24</sup></a></td></tr><tr><td><a href="/facts/Solovay%25E2%2580%2593Strassen_primality_test/83tAxuen">Solovay–Strassen primality test</a></td><td> O ( k n 2 + ε ) {\displaystyle O{\mathord {\left(kn^{2+\varepsilon }\right)}}} <a class="footnote-ref" id="fnref:25" href="#fn:25"><sup>25</sup></a></td></tr><tr><td rowspan="2"><a href="/facts/Integer_factorization/EjMCTz2t">Integer factorization</a></td><td rowspan="2">A b {\displaystyle b} -bit input integer</td><td rowspan="2">A set of factors</td><td><a href="/facts/General_number_field_sieve/elC06ARC">General number field sieve</a></td><td> O ( ( 1 + ε ) b ) {\displaystyle O{\mathord {\left((1+\varepsilon )^{b}\right)}}} <a class="footnote-ref" id="fnref:26" href="#fn:26"><sup>26</sup></a></td></tr><tr><td><a href="/facts/Shor%2527s_algorithm/9JwEtznC">Shor's algorithm</a></td><td> O ( M ( b ) b ) {\displaystyle O(M(b)b)} , on a <a href="/facts/Quantum_computer/nbbcgmvq">quantum computer</a></td></tr></tbody></table> <h2 id="matrix-algebra">Matrix algebra</h2> <p class="note">Main article: <a href="/facts/Computational_complexity_of_matrix_multiplication/KCn5KUzd">Computational complexity of matrix multiplication</a></p> <p>The following complexity figures assume that arithmetic with individual elements has complexity <i>O</i>(1), as is the case with fixed-precision <a href="/facts/Floating-point_arithmetic/eIckahxe">floating-point arithmetic</a> or operations on a <a href="/facts/Finite_field/UkMGJo3m">finite field</a>. </p> <table><tbody><tr><th>Operation</th><th>Input</th><th>Output</th><th>Algorithm</th><th>Complexity</th></tr><tr><td rowspan="4"><a href="/facts/Matrix_multiplication_algorithm/VrYWxfDt">Matrix multiplication</a></td><td rowspan="4">Two n × n {\displaystyle n\times n} matrices</td><td rowspan="4">One n × n {\displaystyle n\times n} matrix</td><td><a href="/facts/Matrix_multiplication_algorithm/VrYWxfDt">Schoolbook matrix multiplication</a></td><td> O ( n 3 ) {\displaystyle O(n^{3})} </td></tr><tr><td><a href="/facts/Strassen_algorithm/rrIGRSNp">Strassen algorithm</a></td><td> O ( n 2.807 ) {\displaystyle O{\mathord {\left(n^{2.807}\right)}}} </td></tr><tr><td><a href="/facts/Coppersmith%25E2%2580%2593Winograd_algorithm/KCn5KUzd">Coppersmith–Winograd algorithm</a> (<a href="/facts/Galactic_algorithm/Q17Y5kP8">galactic algorithm</a>)</td><td> O ( n 2.376 ) {\displaystyle O{\mathord {\left(n^{2.376}\right)}}} </td></tr><tr><td><a href="/facts/Computational_complexity_of_matrix_multiplication/KCn5KUzd">Optimized CW-like algorithms</a><a class="footnote-ref" id="fnref:27" href="#fn:27"><sup>27</sup></a><a class="footnote-ref" id="fnref:28" href="#fn:28"><sup>28</sup></a><a class="footnote-ref" id="fnref:29" href="#fn:29"><sup>29</sup></a><a class="footnote-ref" id="fnref:30" href="#fn:30"><sup>30</sup></a> (<a href="/facts/Galactic_algorithm/Q17Y5kP8">galactic algorithms</a>)</td><td> O ( n ψ = 2.3728596 ) {\displaystyle O{\mathord {\left(n^{\psi =2.3728596}\right)}}} </td></tr><tr><td>Matrix multiplication</td><td>One n × m {\displaystyle n\times m} matrix, and one m × p {\displaystyle m\times p} matrix</td><td>One n × p {\displaystyle n\times p} matrix</td><td>Schoolbook matrix multiplication</td><td> O ( n m p ) {\displaystyle O(nmp)} </td></tr><tr><td>Matrix multiplication</td><td>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} </td><td>One n × n {\displaystyle n\times n} matrix</td><td>Algorithms given in <a class="footnote-ref" id="fnref:31" href="#fn:31"><sup>31</sup></a></td><td> O ( n ω ( k ) + ϵ ) {\displaystyle O(n^{\omega (k)+\epsilon })} , where upper bounds on ω ( k ) {\displaystyle \omega (k)} are given in <a class="footnote-ref" id="fnref:32" href="#fn:32"><sup>32</sup></a></td></tr><tr><td rowspan="4"><a href="/facts/Matrix_inversion/fPqXk3V8">Matrix inversion</a></td><td rowspan="4">One n × n {\displaystyle n\times n} matrix</td><td rowspan="4">One n × n {\displaystyle n\times n} matrix</td><td><a href="/facts/Gauss%25E2%2580%2593Jordan_elimination/23Rvf4ht">Gauss–Jordan elimination</a></td><td> O ( n 3 ) {\displaystyle O{\mathord {\left(n^{3}\right)}}} </td></tr><tr><td>Strassen algorithm</td><td> O ( n 2.807 ) {\displaystyle O{\mathord {\left(n^{2.807}\right)}}} </td></tr><tr><td>Coppersmith–Winograd algorithm</td><td> O ( n 2.376 ) {\displaystyle O{\mathord {\left(n^{2.376}\right)}}} </td></tr><tr><td>Optimized CW-like algorithms</td><td> O ( n ψ ) {\displaystyle O{\mathord {\left(n^{\psi }\right)}}} </td></tr><tr><td rowspan="2"><a href="/facts/Singular_value_decomposition/8t3v6wk3">Singular value decomposition</a></td><td rowspan="2">One m × n {\displaystyle m\times n} matrix</td><td>One m × m {\displaystyle m\times m} matrix, one m × n {\displaystyle m\times n} matrix, & one n × n {\displaystyle n\times n} matrix</td><td>Bidiagonalization and QR algorithm</td><td> O ( m 2 n ) {\displaystyle O{\mathord {\left(m^{2}n\right)}}} ( m ≥ n {\displaystyle m\geq n} )</td></tr><tr><td>One m × n {\displaystyle m\times n} matrix, one n × n {\displaystyle n\times n} matrix, & one n × n {\displaystyle n\times n} matrix</td><td>Bidiagonalization and QR algorithm</td><td> O ( m n 2 ) {\displaystyle O{\mathord {\left(mn^{2}\right)}}} ( m ≤ n {\displaystyle m\leq n} )</td></tr><tr><td><a href="/facts/QR_decomposition/NswfKLGY">QR decomposition</a></td><td>One m × n {\displaystyle m\times n} matrix</td><td>One m × n {\displaystyle m\times n} matrix, & one n × n {\displaystyle n\times n} matrix</td><td>Algorithms in <a class="footnote-ref" id="fnref:33" href="#fn:33"><sup>33</sup></a></td><td> O ( m n 1 + 1 4 − ω ) {\displaystyle O{\mathord {\left(mn^{1+{\frac {1}{4-\omega }}}\right)}}} ( m ≥ n {\displaystyle m\geq n} )</td></tr><tr><td rowspan="5"><a href="/facts/Determinant/eGYqJ2TF">Determinant</a></td><td rowspan="5">One n × n {\displaystyle n\times n} matrix</td><td rowspan="5">One number</td><td><a href="/facts/Laplace_expansion/B4EIjlsp">Laplace expansion</a></td><td> O ( n ! ) {\displaystyle O(n!)} </td></tr><tr><td>Division-free algorithm<a class="footnote-ref" id="fnref:34" href="#fn:34"><sup>34</sup></a></td><td> O ( n 4 ) {\displaystyle O{\mathord {\left(n^{4}\right)}}} </td></tr><tr><td><a href="/facts/LU_decomposition/M13Ew8RD">LU decomposition</a></td><td> O ( n 3 ) {\displaystyle O(n^{3})} </td></tr><tr><td><a href="/facts/Bareiss_algorithm/uUKd5hKv">Bareiss algorithm</a></td><td> O ( n 3 ) {\displaystyle O{\mathord {\left(n^{3}\right)}}} </td></tr><tr><td>Fast matrix multiplication<a class="footnote-ref" id="fnref:35" href="#fn:35"><sup>35</sup></a></td><td> O ( n ψ ) {\displaystyle O{\mathord {\left(n^{\psi }\right)}}} </td></tr><tr><td>Back substitution</td><td><a href="/facts/Triangular_matrix/qjXSFMM3">Triangular matrix</a></td><td> n {\displaystyle n} solutions</td><td>Back substitution<a class="footnote-ref" id="fnref:36" href="#fn:36"><sup>36</sup></a></td><td> O ( n 2 ) {\displaystyle O{\mathord {\left(n^{2}\right)}}} </td></tr><tr><td rowspan="3">Characteristic polynomial</td><td rowspan="3">One n × n {\displaystyle n\times n} matrix</td><td rowspan="3">One degree- n {\displaystyle n} polynomial</td><td><a href="/facts/Faddeev-LeVerrier_algorithm/uuKcU5tn">Faddeev-LeVerrier algorithm</a></td><td> O ( n ψ + 1 ) {\displaystyle O(n^{\psi +1})} </td></tr><tr><td><a href="/facts/Samuelson-Berkowitz_algorithm/SuKF8jw0">Samuelson-Berkowitz algorithm</a></td><td> O ( n ψ + 1 ) {\displaystyle O(n^{\psi +1})} (smaller constant factor)</td></tr><tr><td>Preparata-Sarwate algorithm<a class="footnote-ref" id="fnref:37" href="#fn:37"><sup>37</sup></a><a class="footnote-ref" id="fnref:38" href="#fn:38"><sup>38</sup></a></td><td> O ( n ψ + 1 / 2 + n 3 ) {\displaystyle O(n^{\psi +1/2}+n^{3})} </td></tr></tbody></table> <p>In 2005, <a href="/facts/Henry_Cohn/o0yydD1I">Henry Cohn</a>, <a href="/facts/Robert_Kleinberg/eENou3yD">Robert Kleinberg</a>, <a href="/facts/Bal%25C3%25A1zs_Szegedy/RaFcBaP4">Balázs Szegedy</a>, and <a href="/facts/Chris_Umans/4sCaCG1F">Chris Umans</a> showed that either of two different conjectures would imply that the exponent of matrix multiplication is 2.<a class="footnote-ref" id="fnref:39" href="#fn:39"><sup>39</sup></a> </p> <h2 id="transforms">Transforms</h2> <p>Algorithms for computing <a href="/facts/Transformation_(function)/Yr2J3o8H">transforms</a> of functions (particularly <a href="/facts/Integral_transform/AB2yjHJJ">integral transforms</a>) are widely used in all areas of mathematics, particularly <a href="/facts/Mathematical_analysis/XXeR26Ih">analysis</a> and <a href="/facts/Signal_processing/Npaja6zb">signal processing</a>. </p> <table><tbody><tr><th>Operation</th><th>Input</th><th>Output</th><th>Algorithm</th><th>Complexity</th></tr><tr><td rowspan="2"><a href="/facts/Discrete_Fourier_transform/uK9Tjsbl">Discrete Fourier transform</a></td><td rowspan="2">Finite data sequence of size n {\displaystyle n} </td><td rowspan="2">Set of complex numbers</td><td>Schoolbook</td><td> O ( n 2 ) {\displaystyle O(n^{2})} </td></tr><tr><td><a href="/facts/Fast_Fourier_transform/caT7UUCh">Fast Fourier transform</a></td><td> O ( n log n ) {\displaystyle O(n\log n)} </td></tr></tbody></table> <h2 id="notes">Notes</h2> <h2 id="further-reading">Further reading</h2> <ul><li><a href="/facts/Richard_P._Brent/JYLmuA0M">Brent, Richard P.</a>; <a href="/facts/Paul_Zimmermann_(mathematician)/7CCQSrGj">Zimmermann, Paul</a> (2010). <i>Modern Computer Arithmetic</i>. Cambridge University Press. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-521-19469-3.</li> <li><a href="/facts/Donald_Knuth/GozNzDM6">Knuth, Donald Ervin</a> (1997). <i>Seminumerical Algorithms</i>. <a href="/facts/The_Art_of_Computer_Programming/MR1bMD9e">The Art of Computer Programming</a>. Vol. 2 (3rd ed.). Addison-Wesley. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-201-89684-8.</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>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. <a href="978-3-411-16891-0" target="_blank">978-3-411-16891-0</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Knuth 1997 - Knuth, Donald Ervin (1997). Seminumerical Algorithms. The Art of Computer Programming. Vol. 2 (3rd ed.). Addison-Wesley. ISBN 978-0-201-89684-8. <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>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. <a href="https://hal.archives-ouvertes.fr/hal-02070778v2/file/nlogn.pdf" target="_blank">https://hal.archives-ouvertes.fr/hal-02070778v2/file/nlogn.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Klarreich, Erica (December 2019). "Multiplication hits the speed limit". Commun. ACM. 63 (1): 11–13. doi:10.1145/3371387. S2CID 209450552. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>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. <a href="/wiki/OCLC_(identifier)" target="_blank">/wiki/OCLC_(identifier)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Schönhage, Arnold (1980). "Storage Modification Machines". SIAM Journal on Computing. 9 (3): 490–508. doi:10.1137/0209036. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>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. <a href="978-0-471-83138-9" target="_blank">978-0-471-83138-9</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>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. <a href="978-0-01-205856-5" target="_blank">978-0-01-205856-5</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>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 href="978-1-4832-5789-1" target="_blank">978-1-4832-5789-1</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>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 <a href="978-3-030-36567-7" target="_blank">978-3-030-36567-7</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>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 <a href="978-3-030-36567-7" target="_blank">978-3-030-36567-7</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>Sorenson, J. (1994). "Two Fast GCD Algorithms". Journal of Algorithms. 16 (1): 110–144. doi:10.1006/jagm.1994.1006. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>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. <a href="978-0-387-28979-3" target="_blank">978-0-387-28979-3</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> <li id="fn:14"><p>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. <a href="http://www.lysator.liu.se/~nisse/archive/sgcd.pdf" target="_blank">http://www.lysator.liu.se/~nisse/archive/sgcd.pdf</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li> <li id="fn:15"><p>Bernstein, D.J. "Faster Algorithms to Find Non-squares Modulo Worst-case Integers". <a href="http://cr.yp.to/papers/nonsquare.ps" target="_blank">http://cr.yp.to/papers/nonsquare.ps</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li> <li id="fn:16"><p>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. <a href="978-3-642-14518-6" target="_blank">978-3-642-14518-6</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></p></li> <li id="fn:17"><p>Borwein, P. (1985). "On the complexity of calculating factorials". Journal of Algorithms. 6 (3): 376–380. doi:10.1016/0196-6774(85)90006-9. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></p></li> <li id="fn:18"><p>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. <a href="978-3-411-16891-0" target="_blank">978-3-411-16891-0</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></p></li> <li id="fn:19"><p>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. <a href="/wiki/Hendrik_Lenstra" target="_blank">/wiki/Hendrik_Lenstra</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></p></li> <li id="fn:20"><p>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. <a href="978-0-8218-5280-4" target="_blank">978-0-8218-5280-4</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></p></li> <li id="fn:21"><p>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. <a href="/wiki/Mathematics_of_Computation" target="_blank">/wiki/Mathematics_of_Computation</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></p></li> <li id="fn:22"><p>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. <a href="/wiki/Carl_Pomerance" target="_blank">/wiki/Carl_Pomerance</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></p></li> <li id="fn:23"><p>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 href="/wiki/Samuel_S._Wagstaff,_Jr." target="_blank">/wiki/Samuel_S._Wagstaff,_Jr.</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></p></li> <li id="fn:24"><p>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. <a href="https://doi.org/10.1016%2F0304-3975%2880%2990007-9" target="_blank">https://doi.org/10.1016%2F0304-3975%2880%2990007-9</a> <a href="#fnref:24" class="footnote-back-ref">↩</a></p></li> <li id="fn:25"><p>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. <a href="https://doi.org/10.1016%2F0304-3975%2880%2990007-9" target="_blank">https://doi.org/10.1016%2F0304-3975%2880%2990007-9</a> <a href="#fnref:25" class="footnote-back-ref">↩</a></p></li> <li id="fn:26"><p>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)}}.} <a href="#fnref:26" class="footnote-back-ref">↩</a></p></li> <li id="fn:27"><p>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 <a href="978-1-61197-646-5" target="_blank">978-1-61197-646-5</a> <a href="#fnref:27" class="footnote-back-ref">↩</a></p></li> <li id="fn:28"><p>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 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:28" class="footnote-back-ref">↩</a></p></li> <li id="fn:29"><p>Vassilevska Williams, Virginia (2014), Breaking the Coppersmith-Winograd barrier: Multiplying matrices in O(n2.373) time <a href="/wiki/Virginia_Vassilevska_Williams" target="_blank">/wiki/Virginia_Vassilevska_Williams</a> <a href="#fnref:29" class="footnote-back-ref">↩</a></p></li> <li id="fn:30"><p>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 href="9781450325011" target="_blank">9781450325011</a> <a href="#fnref:30" class="footnote-back-ref">↩</a></p></li> <li id="fn:31"><p>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. <a href="978-1-61197-503-1" target="_blank">978-1-61197-503-1</a> <a href="#fnref:31" class="footnote-back-ref">↩</a></p></li> <li id="fn:32"><p>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. <a href="978-1-61197-503-1" target="_blank">978-1-61197-503-1</a> <a href="#fnref:32" class="footnote-back-ref">↩</a></p></li> <li id="fn:33"><p>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. <a href="https://doi.org/10.1016%2F0024-3795%2893%2900230-w" target="_blank">https://doi.org/10.1016%2F0024-3795%2893%2900230-w</a> <a href="#fnref:33" class="footnote-back-ref">↩</a></p></li> <li id="fn:34"><p>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. <a href="3-540-45506-X" target="_blank">3-540-45506-X</a> <a href="#fnref:34" class="footnote-back-ref">↩</a></p></li> <li id="fn:35"><p>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. <a href="978-0-201-00029-0" target="_blank">978-0-201-00029-0</a> <a href="#fnref:35" class="footnote-back-ref">↩</a></p></li> <li id="fn:36"><p>Fraleigh, J.B.; Beauregard, R.A. (1987). Linear Algebra (3rd ed.). Addison-Wesley. p. 95. ISBN 978-0-201-15459-7. <a href="978-0-201-15459-7" target="_blank">978-0-201-15459-7</a> <a href="#fnref:36" class="footnote-back-ref">↩</a></p></li> <li id="fn:37"><p>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. <a href="https://doi.org/10.1016%2F0020-0190%2878%2990079-0" target="_blank">https://doi.org/10.1016%2F0020-0190%2878%2990079-0</a> <a href="#fnref:37" class="footnote-back-ref">↩</a></p></li> <li id="fn:38"><p>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 <a href="https://doi.org/10.1016%2F0020-0190%2889%2990173-7" target="_blank">https://doi.org/10.1016%2F0020-0190%2889%2990173-7</a> <a href="#fnref:38" class="footnote-back-ref">↩</a></p></li> <li id="fn:39"><p>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. <a href="0-7695-2468-0" target="_blank">0-7695-2468-0</a> <a href="#fnref:39" class="footnote-back-ref">↩</a></p></li> </ol>