Complejidad computacional de las operaciones matemáticas.

Requisitos de tiempo de ejecución algorítmico 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 representa 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 potentes, específicamente una máquina de puntero y, en consecuencia, también una máquina de acceso aleatorio de costo unitario, es posible multiplicar dos números de n bits en el 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 en un número. En la práctica, esto significa que los asumimos como números enteros de máquina.

Funciones especiales

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

Funciones elementales

Las funciones elementales se construyen componiendo operaciones aritméticas, la función exponencial ( ), el logaritmo natural ( ), 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 tanto invertibles mediante el método de Newton. En particular, si uno o en el dominio complejo se puede 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 los que se evaluará la función. ${\displaystyle n}$

No se sabe si cuál 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 los dígitos. ${\displaystyle n}$

Teoría de los números

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

Álgebra matricial

Las siguientes cifras de complejidad suponen que la aritmética con elementos individuales tiene una complejidad O (1), como es el caso de la aritmética de coma 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 (particularmente transformaciones integrales ) se usan 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 . 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: una implementación de la 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 el tiempo O (n log n)» (PDF) . Anales de Matemáticas . 193 (2): 563–617. doi : 10.4007/anales.2021.193.2.4. S2CID  109934776.
4. Klarreich, Erica (diciembre de 2019). "La multiplicación alcanza el límite de velocidad". Comunitario. 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 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, Gregorio (1988). "Aproximaciones y multiplicación compleja según Ramanujan". Ramanujan revisitado: Actas de la Conferencia del Centenario . Prensa académica. págs. 375–472. ISBN 978-0-01-205856-5.
9. Brent, Richard P. (2014) [1975]. "Métodos de búsqueda de ceros 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, S2CID  214742997
11. Sorenson, J. (1994). "Dos algoritmos GCD rápidos". Revista de algoritmos . 16 (1): 110-144. doi :10.1006/jagm.1994.1006.
12. Crandall, R.; Pomerancia, C. (2005). "Algoritmo 9.4.7 (Stehlé-Zimmerman binario-recursivo-gcd)". Números primos: una perspectiva computacional (2ª ed.). Saltador. págs. 471–3. ISBN 978-0-387-28979-3.
13. Möller N (2008). "Sobre el algoritmo de Schönhage y el cálculo del mcd de enteros subcuadráticos" (PDF) . Matemáticas de la Computación . 77 (261): 589–607. Código Bib : 2008MaCom..77..589M. doi : 10.1090/S0025-5718-07-02017-0 .
14. Bernstein, DJ "Algoritmos más rápidos para encontrar enteros en el peor de los casos en módulo no cuadrado".
15. Brent, Richard P.; Zimmerman, 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 . Saltador. 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". Revista de algoritmos . 6 (3): 376–380. doi :10.1016/0196-6774(85)90006-9.
17. Lenstra hijo., HW ; Pomerancia, Carl (2019). "Prueba de primalidad con períodos 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 de AKS". Una épsilon de 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 Estadounidense. 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 prueba de primalidad de la curva elíptica". Matemáticas de la Computación . 76 (257): 493–505. arXiv : matemáticas/0502097 . Código Bib : 2007MaCom..76..493M. doi :10.1090/S0025-5718-06-01890-4. SEÑOR  2261033. S2CID  133193.
20. Pomerancia, Carl ; Selfridge, John L .; Wagstaff, Jr., Samuel S. (julio de 1980). "Los pseudoprimos a 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 Pseudoprimos» (PDF) . Matemáticas de la Computación . 35 (152): 1391-1417. doi : 10.1090/S0025-5718-1980-0583518-6 . JSTOR  2006406. SEÑOR  0583518.
22. Monier, Louis (1980). "Evaluación y comparación de dos algoritmos eficientes de prueba de primalidad probabilística". Informática Teórica . 12 (1): 97-108. doi : 10.1016/0304-3975(80)90007-9 . SEÑOR  0582244.
23. Alma, 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, soy; 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 calderero-Winograd: multiplicación de matrices en tiempo O (n2.373)
26. Le Gall, François (2014), "Poderes de tensores y multiplicación rápida de matrices", Actas del 39º Simposio Internacional sobre Computación Simbólica y Algebraica - ISSAC '14 , p. 23, arXiv : 1401.7714 , Bibcode : 2014arXiv1401.7714L, doi : 10.1145/2608628.2627493, ISBN 9781450325011, S2CID  353236
27. Le Gall, François; Urrutia, Floren (2018). "Multiplicación de matrices rectangulares mejorada utilizando potencias del tensor de calderero-Winograd". En Czumaj, Artur (ed.). Actas del vigésimo noveno simposio anual ACM-SIAM sobre algoritmos discretos . Sociedad de Matemática Industrial y Aplicada. doi :10.1137/1.9781611975031.67. ISBN 978-1-61197-503-1. S2CID  33396059.
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. De memoria, G. (2001). "Algoritmos sin división para el determinante y el pfaffiano: enfoques algebraicos y combinatorios" (PDF) . Matemáticas discretas computacionales . Saltador. págs. 119-135. ISBN 3-540-45506-X.
30. Ah, Alfred V .; Hopcroft, John E .; Ullman, Jeffrey D. (1974). "Teorema 6.6". El diseño y análisis de algoritmos informáticos . Addison-Wesley. pag. 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, Enrique; 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. S2CID  6429088.

Otras lecturas

• Brent, Richard P .; Zimmerman, Paul (2010). Aritmética informática moderna . Prensa de la Universidad de Cambridge. 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.