Complejidad computacional de operaciones matemáticas

Requisitos de ejecución algorítmica para procedimientos matemáticos comunes

Gráficos de funciones comúnmente utilizadas en el análisis de algoritmos, que muestran el número de operaciones versus el tamaño de entrada para cada función. ${\displaystyle N}$ ${\displaystyle n}$

Las siguientes tablas enumeran la complejidad computacional de varios algoritmos para operaciones matemáticas comunes .

Aquí, la complejidad se refiere a la complejidad temporal de realizar cálculos en una máquina de Turing multicinta . ^[1] Consulte la notación O grande para obtener una explicación de la notación utilizada.

Nota: Debido a la variedad de algoritmos de multiplicación, a continuación se indica la complejidad del algoritmo de multiplicación elegido. ${\displaystyle M(n)}$

Funciones aritméticas

Esta tabla enumera la complejidad de las operaciones matemáticas con números enteros.

En modelos computacionales más fuertes, específicamente una máquina de punteros y en consecuencia también una máquina de acceso aleatorio de costo unitario, es posible multiplicar dos números de n bits en un tiempo O ( n ). ^[6]

Funciones algebraicas

Aquí consideramos operaciones sobre polinomios y n denota su grado; para los coeficientes utilizamos un modelo de costo unitario , ignorando la cantidad de bits de un número. En la práctica, esto significa que asumimos que son números enteros de máquina.

Funciones especiales

Muchos de los métodos de esta sección se dan en Borwein & Borwein. ^[7]

Funciones elementales

Las funciones elementales se construyen mediante la composición de operaciones aritméticas, la función exponencial ( ), el logaritmo natural ( ), las funciones trigonométricas ( ) y sus inversas. La complejidad de una función elemental es equivalente a la de su inversa, ya que todas las funciones elementales son analíticas y, por lo tanto, invertibles mediante el método de Newton. En particular, si o en el dominio complejo se pueden calcular con cierta complejidad, entonces esa complejidad es alcanzable para todas las demás funciones elementales. ${\displaystyle \exp }$ ${\displaystyle \log }$ ${\displaystyle \sin ,\cos }$ ${\displaystyle \exp }$ ${\displaystyle \log }$

A continuación, el tamaño se refiere al número de dígitos de precisión con el que se debe evaluar la función. ${\displaystyle n}$

No se sabe si es la complejidad óptima para funciones elementales. El límite inferior más conocido es el límite trivial . ${\displaystyle O(M(n)\log n)}$ ${\displaystyle \Omega }$ ${\displaystyle (M(n))}$

Funciones no elementales

Constantes matemáticas

Esta tabla muestra la complejidad de calcular aproximaciones a las constantes dadas para corregir dígitos. ${\displaystyle n}$

Teoría de números

Los algoritmos para cálculos teóricos de números se estudian en la teoría de números computacionales .

Álgebra matricial

Las siguientes cifras de complejidad suponen que la aritmética con elementos individuales tiene complejidad O (1), como es el caso de la aritmética de punto flotante de precisión fija o las operaciones en un campo finito .

En 2005, Henry Cohn , Robert Kleinberg , Balázs Szegedy y Chris Umans demostraron que cualquiera de dos conjeturas diferentes implicaría que el exponente de la multiplicación de matrices es 2. ^[32]

Transforma

Los algoritmos para calcular transformadas de funciones (en particular, transformadas integrales ) se utilizan ampliamente en todas las áreas de las matemáticas, particularmente en el análisis y el procesamiento de señales .

Notas

1. Esta forma de tiempo subexponencial es válida para todos los . Una forma más precisa de la complejidad se puede dar como ${\displaystyle \varepsilon >0}$ ${\displaystyle O{\mathord {\left(\exp {\sqrt[{3}]{{\frac {64}{9}}b(\log b)^{2}}}\right)}}.}$

Referencias

1. Schönhage, A.; Grotefeld, AFW; Vetter, E. (1994). Algoritmos rápidos: implementación de una máquina de Turing multicinta . BI Wissenschafts-Verlag. ISBN 978-3-411-16891-0.OCLC 897602049  .
2. Knuth 1997
3. Harvey, D.; Van Der Hoeven, J. (2021). "Multiplicación de enteros en tiempo O (n log n)" (PDF) . Anales de Matemáticas . 193 (2): 563–617. doi :10.4007/annals.2021.193.2.4. S2CID  109934776.
4. Klarreich, Erica (diciembre de 2019). "La multiplicación alcanza el límite de velocidad". Commun. ACM . 63 (1): 11–13. doi :10.1145/3371387. S2CID  209450552.
5. Burnikel, Christoph; Ziegler, Joaquín (1998). División recursiva rápida . Forschungsberichte des Max-Planck-Instituts für Informatik. Sarrebruck: MPI Informatik Bibliothek & Dokumentation. OCLC  246319574. MPII-98-1-022.
6. Schönhage, Arnold (1980). "Máquinas de modificación de almacenamiento". Revista SIAM de Computación . 9 (3): 490–508. doi :10.1137/0209036.
7. Borwein, J.; Borwein, P. (1987). Pi y el AGM: un estudio sobre teoría analítica de números y complejidad computacional . Wiley. ISBN 978-0-471-83138-9.OCLC 755165897  .
8. Chudnovsky, David; Chudnovsky, Gregory (1988). "Aproximaciones y multiplicación compleja según Ramanujan". Ramanujan revisitado: Actas de la Conferencia del Centenario . Academic Press. págs. 375–472. ISBN 978-0-01-205856-5.
9. Brent, Richard P. (2014) [1975]. "Métodos de búsqueda de cero de precisión múltiple y la complejidad de la evaluación de funciones elementales". En Traub, JF (ed.). Complejidad computacional analítica . Elsevier. págs. 151–176. arXiv : 1004.3412 . ISBN 978-1-4832-5789-1.
10. Richard P. Brent (2020), Los hermanos Borwein, Pi y la 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, Número de identificación del sujeto  214742997
11. Sorenson, J. (1994). "Dos algoritmos rápidos de MCD". Revista de algoritmos . 16 (1): 110–144. doi :10.1006/jagm.1994.1006.
12. Crandall, R.; Pomerance, C. (2005). "Algoritmo 9.4.7 (mcd binario recursivo de Stehlé-Zimmerman)". Números primos: una perspectiva computacional (2.ª ed.). Springer. págs. 471-473. ISBN 978-0-387-28979-3.
13. Möller N (2008). "Sobre el algoritmo de Schönhage y el cálculo del mcd entero subcuadrático" (PDF) . Matemáticas de la computación . 77 (261): 589–607. Bibcode :2008MaCom..77..589M. doi : 10.1090/S0025-5718-07-02017-0 .
14. Bernstein, DJ "Algoritmos más rápidos para encontrar números enteros no cuadrados módulo en el peor de los casos".
15. Brent, Richard P.; Zimmermann, Paul (2010). "Un algoritmo O ( M ( n ) log ⁡ n ) {\displaystyle O(M(n)\log n)} para el símbolo de Jacobi". Simposio Internacional de Teoría Algorítmica de Números . Springer. págs. 83–95. arXiv : 1004.2091 . doi :10.1007/978-3-642-14518-6_10. ISBN. 978-3-642-14518-6.S2CID 7632655  .
16. Borwein, P. (1985). "Sobre la complejidad del cálculo de factoriales". Journal of Algorithms . 6 (3): 376–380. doi :10.1016/0196-6774(85)90006-9.
17. Lenstra jr., HW ; Pomerance, Carl (2019). "Pruebas de primalidad con periodos gaussianos" (PDF) . Revista de la Sociedad Matemática Europea . 21 (4): 1229–69. doi :10.4171/JEMS/861. hdl :21.11116/0000-0005-717D-0.
18. Tao, Terence (2010). "1.11 La prueba de primalidad AKS". Un épsilon de la habitación, II: Páginas del tercer año de un blog matemático . Estudios de posgrado en matemáticas. Vol. 117. Sociedad Matemática Americana. págs. 82–86. doi :10.1090/gsm/117. ISBN 978-0-8218-5280-4.Señor 2780010  .
19. Morain, F. (2007). "Implementación de la versión asintóticamente rápida del algoritmo de demostración de primalidad de curva elíptica". Matemáticas de la computación . 76 (257): 493–505. arXiv : math/0502097 . Bibcode :2007MaCom..76..493M. doi :10.1090/S0025-5718-06-01890-4. MR  2261033. S2CID  133193.
20. Pomerance, Carl ; Selfridge, John L. ; Wagstaff, Jr., Samuel S. (julio de 1980). "Los pseudoprimos hasta 25·109" (PDF) . Matemáticas de la computación . 35 (151): 1003–26. doi : 10.1090/S0025-5718-1980-0572872-7 . JSTOR  2006210.
21. Baillie, Robert; Wagstaff, Jr., Samuel S. (octubre de 1980). "Lucas Pseudoprimes" (PDF) . Matemáticas de la computación . 35 (152): 1391–1417. doi : 10.1090/S0025-5718-1980-0583518-6 . JSTOR  2006406. MR  0583518.
22. Monier, Louis (1980). "Evaluación y comparación de dos algoritmos de prueba de primalidad probabilística eficientes". Ciencias de la Computación Teórica . 12 (1): 97–108. doi : 10.1016/0304-3975(80)90007-9 . MR  0582244.
23. Alman, Josh; Williams, Virginia Vassilevska (2020), "Un método láser refinado y una multiplicación de matrices más rápida", 32.º Simposio anual ACM-SIAM sobre algoritmos discretos (SODA 2021), arXiv : 2010.05846 , doi : 10.1137/1.9781611976465.32, S2CID  222290442
24. Davie, AM; Stothers, AJ (2013), "Límite mejorado para la complejidad de la multiplicación de matrices", Actas de la Royal Society of Edinburgh , 143A (2): 351–370, doi :10.1017/S0308210511001648, S2CID  113401430
25. Vassilevska Williams, Virginia (2014), Rompiendo la barrera Coppersmith-Winograd: multiplicación de matrices en tiempo O(n2.373)
26. Le Gall, François (2014), "Potencias de tensores y multiplicación rápida de matrices", Actas del 39.° Simposio Internacional sobre Computación Simbólica y Algebraica — ISSAC '14 , pág. 23, arXiv : 1401.7714 , Bibcode :2014arXiv1401.7714L, doi :10.1145/2608628.2627493, ISBN 9781450325011, S2CID353236 ​
27. Le Gall, François; Urrutia, Floren (2018). "Multiplicación de matrices rectangulares mejorada usando potencias del tensor Coppersmith-Winograd". En Czumaj, Artur (ed.). Actas del vigésimo noveno simposio anual ACM-SIAM sobre algoritmos discretos . Sociedad de Matemáticas Industriales y Aplicadas. doi :10.1137/1.9781611975031.67. ISBN . 978-1-61197-503-1.S2CID33396059  .​
28. Knight, Philip A. (mayo de 1995). "Multiplicación rápida de matrices rectangulares y descomposición QR". Álgebra lineal y sus aplicaciones . 221 : 69–81. doi : 10.1016/0024-3795(93)00230-w . ISSN  0024-3795.
29. Rote, G. (2001). "Algoritmos sin división para el determinante y el pfaffiano: enfoques algebraicos y combinatorios" (PDF) . Matemáticas discretas computacionales . Springer. pp. 119–135. ISBN 3-540-45506-X.
30. Aho, Alfred V. ; Hopcroft, John E. ; Ullman, Jeffrey D. (1974). "Teorema 6.6". El diseño y análisis de algoritmos informáticos . Addison-Wesley. pág. 241. ISBN 978-0-201-00029-0.
31. Fraleigh, JB; Beauregard, RA (1987). Álgebra lineal (3ª ed.). Addison-Wesley. pag. 95.ISBN​ 978-0-201-15459-7.
32. Cohn, Henry; Kleinberg, Robert; Szegedy, Balazs; Umans, Chris (2005). "Algoritmos de teoría de grupos para la multiplicación de matrices". Actas del 46.º Simposio anual sobre fundamentos de la informática . IEEE. págs. 379–388. arXiv : math.GR/0511460 . doi :10.1109/SFCS.2005.39. ISBN . 0-7695-2468-0.S2CID6429088  .​

Lectura adicional

• Brent, Richard P .; Zimmermann, Paul (2010). Aritmética informática moderna . Cambridge University Press. ISBN 978-0-521-19469-3.
• Knuth, Donald Ervin (1997). Algoritmos seminuméricos . El arte de la programación informática . Vol. 2 (3.ª ed.). Addison-Wesley. ISBN 978-0-201-89684-8.