Álgebra computacional

Dado que el software numérico es altamente eficiente para el cálculo numérico aproximado , en álgebra computacional es común enfatizar el cálculo exacto con datos representados con precisión. Esta representación exacta implica que, incluso cuando el tamaño de la salida es pequeño, los datos intermedios generados durante un cálculo pueden crecer de forma impredecible. Este comportamiento se denomina expansión de la expresión . ^{[ 7 ]} Para mitigar este problema, se utilizan diversos métodos en la representación de los datos, así como en los algoritmos que los manipulan. ^{[ 8 ]}

Expresiones

Excepto en el caso de números y variables , toda expresión matemática puede considerarse como el símbolo de un operador seguido de una secuencia de operandos. En el software de álgebra computacional, las expresiones suelen representarse de esta forma. Esta representación es muy flexible, y muchas cosas que a primera vista no parecen expresiones matemáticas pueden representarse y manipularse como tales. Por ejemplo, una ecuación puede considerarse como una expresión con el operador principal "=", y una matriz puede representarse como una expresión con "matriz" como operador y sus filas como operandos.

Incluso los programas pueden considerarse y representarse como expresiones con el operador "procedimiento" y, al menos, dos operandos: la lista de parámetros y el cuerpo, que a su vez es una expresión con "cuerpo" como operador y una secuencia de instrucciones como operandos. A la inversa, cualquier expresión matemática puede considerarse un programa. Por ejemplo, la expresión a + b puede considerarse un programa para la suma, con a y b como parámetros. La ejecución de este programa consiste en evaluar la expresión para valores dados de a y b ; si no se les proporciona ningún valor, el resultado de la evaluación es simplemente su entrada.

Este proceso de evaluación diferida es fundamental en el álgebra computacional. Por ejemplo, el operador "=" de ecuación también es, en la mayoría de los sistemas de álgebra computacional, el nombre del programa de la prueba de igualdad: normalmente, la evaluación de una ecuación da como resultado una ecuación, pero, cuando se necesita una prueba de igualdad, ya sea solicitada explícitamente por el usuario a través de un comando "evaluación a un booleano", o iniciada automáticamente por el sistema en el caso de una prueba dentro de un programa, entonces se ejecuta la evaluación a un resultado booleano.

Como el tamaño de los operandos de una expresión es impredecible y puede cambiar durante una sesión de trabajo, la secuencia de los operandos se suele representar como una secuencia de punteros (como en Macsyma ) ^{[ 13 ]} o entradas en una tabla hash (como en Maple ).

La aplicación directa de las reglas básicas de diferenciación con respecto a x en la expresión a ^x da como resultado

${\displaystyle x\cdot a^{x-1}\cdot 0+a^{x}\cdot \left(1\cdot \log a+x\cdot {\frac {0}{a}}\right).}$

Generalmente se busca una expresión más simple, y la simplificación es necesaria al trabajar con expresiones generales. Esta simplificación se realiza normalmente mediante reglas de reescritura . ^{[ 14 ]} Existen varias clases de reglas de reescritura que se pueden considerar. Las más simples son las reglas que siempre reducen el tamaño de la expresión, como E − E → 0 o sin(0) → 0. Se aplican sistemáticamente en sistemas de álgebra computacional.

Una dificultad surge con las operaciones asociativas como la suma y la multiplicación. La forma estándar de abordar la asociatividad es considerar que la suma y la multiplicación tienen un número arbitrario de operandos; es decir, que a + b + c se representa como "+"( a , b , c ) . Así, a + ( b + c ) y ( a + b ) + c se simplifican a "+"( a , b , c ) , que se muestra como a + b + c . En el caso de expresiones como a − b + c , la forma más sencilla es reescribir sistemáticamente − E , E − F , E / F como, respectivamente, ( − 1)⋅ E , E + ( − 1)⋅ F , E ⋅ F ^{− 1} . En otras palabras, en la representación interna de las expresiones, no hay resta ni división ni menos unario, fuera de la representación de los números.

Otra dificultad surge con la conmutatividad de la suma y la multiplicación. El problema radica en reconocer rápidamente los términos semejantes para combinarlos o cancelarlos. Comprobar cada par de términos resulta costoso con sumas y productos muy largos. Para solucionar esto, Macsyma ordena los operandos de sumas y productos de forma que los términos semejantes se colocan en posiciones consecutivas, lo que facilita su detección. En Maple , se utiliza una función hash para generar colisiones al introducir términos semejantes, permitiendo combinarlos inmediatamente. Esto permite reconocer y almacenar solo una vez las subexpresiones que aparecen varias veces en un cálculo. De esta forma, se ahorra memoria y se acelera el cálculo al evitar la repetición de las mismas operaciones en expresiones idénticas.

Algunas reglas de reescritura a veces aumentan y a veces disminuyen el tamaño de las expresiones a las que se aplican. Este es el caso de la ley distributiva o las identidades trigonométricas . Por ejemplo, la ley distributiva permite reescribir${\displaystyle (x+1)^{4}\rightarrow x^{4}+4x^{3}+6x^{2}+4x+1}$y${\displaystyle (x-1)(x^{4}+x^{3}+x^{2}+x+1)\rightarrow x^{5}-1.}$Dado que no existe una forma de elegir de manera general si aplicar o no dicha regla de reescritura, esta solo se realiza cuando el usuario la solicita explícitamente. Para la propiedad distributiva, la función informática que aplica esta regla de reescritura se denomina normalmente "expandir". La regla de reescritura inversa, denominada "factorizar", requiere un algoritmo complejo, que constituye una función clave en los sistemas de álgebra computacional (véase Factorización de polinomios ).

Hay dos nociones de igualdad para las expresiones matemáticas . La igualdad sintáctica es la igualdad de su representación en una computadora. Esto es fácil de probar en un programa. La igualdad semántica se da cuando dos expresiones representan el mismo objeto matemático, como en

${\displaystyle (x+y)^{2}=x^{2}+2xy+y^{2}.}$

Según el teorema de Richardson , es posible que no exista un algoritmo que determine si dos expresiones numéricas son semánticamente iguales si se permiten exponenciales y logaritmos en dichas expresiones. Por consiguiente, la igualdad (semántica) solo puede comprobarse en ciertas clases de expresiones, como los polinomios y las fracciones racionales .

Para comprobar la igualdad de dos expresiones, en lugar de diseñar algoritmos específicos, lo habitual es expresar las expresiones en una forma canónica o expresar su diferencia en una forma normal , y comprobar la igualdad sintáctica del resultado.

En álgebra computacional, "forma canónica" y "forma normal" no son sinónimos. ^{[ 15 ]} Una forma canónica es tal que dos expresiones en forma canónica son semánticamente iguales si y solo si son sintácticamente iguales, mientras que una forma normal es tal que una expresión en forma normal es semánticamente cero solo si es sintácticamente cero. En otras palabras, el cero tiene una representación única como expresión en forma normal.

En álgebra computacional, las formas normales suelen preferirse por varias razones. En primer lugar, las formas canónicas pueden ser más costosas de calcular que las formas normales. Por ejemplo, para expresar un polinomio en forma canónica, es necesario desarrollar cada producto mediante la propiedad distributiva , mientras que esto no es necesario con una forma normal (véase más adelante). En segundo lugar, como en el caso de expresiones con radicales, una forma canónica, si existe, puede depender de ciertas elecciones arbitrarias, y estas elecciones pueden ser diferentes para dos expresiones calculadas independientemente. Esto puede hacer que el uso de una forma canónica resulte poco práctico.

Los primeros sistemas de álgebra computacional, como el ENIAC de la Universidad de Pensilvania , dependían de programadores humanos para reprogramarlo entre cálculos, manipular sus numerosos módulos físicos (o paneles) y alimentar su lector de tarjetas IBM. ^{[ 16 ]} Las matemáticas se encargaron de la mayor parte de la programación del ENIAC guiada por humanos: Jean Jennings , Marlyn Wescoff , Ruth Lichterman , Betty Snyder , Frances Bilas y Kay McNulty lideraron dichos esfuerzos. ^{[ 17 ]}

En 1960, John McCarthy exploró una extensión de las funciones recursivas primitivas para calcular expresiones simbólicas a través del lenguaje de programación Lisp mientras estaba en el Instituto Tecnológico de Massachusetts . ^{[ 18 ]} Aunque su serie sobre "Funciones recursivas de expresiones simbólicas y su cálculo por máquina" quedó incompleta, ^{[ 19 ]} McCarthy y sus contribuciones a la programación de inteligencia artificial y al álgebra computacional a través de Lisp ayudaron a establecer el Proyecto MAC en el Instituto Tecnológico de Massachusetts y la organización que más tarde se convirtió en el Laboratorio de IA de Stanford (SAIL) en la Universidad de Stanford , cuya competencia facilitó un desarrollo significativo en el álgebra computacional a lo largo de finales del siglo XX.

Los primeros intentos de computación simbólica, en las décadas de 1960 y 1970, enfrentaron desafíos relacionados con la ineficiencia de algoritmos conocidos desde hace mucho tiempo al ser adaptados a sistemas de álgebra computacional. ^{[ 20 ]} Los predecesores del Proyecto MAC, como ALTRAN , buscaron superar las limitaciones algorítmicas mediante avances en hardware e intérpretes, mientras que los esfuerzos posteriores se centraron en la optimización del software. ^{[ 21 ]}

Gran parte del trabajo de los investigadores en este campo consistió en revisar el álgebra clásica para aumentar su efectividad , al tiempo que desarrollaban algoritmos eficientes para su uso en álgebra computacional. Un ejemplo de este tipo de trabajo es el cálculo del máximo común divisor de polinomios , una tarea necesaria para simplificar fracciones y un componente esencial del álgebra computacional. Los algoritmos clásicos para este cálculo, como el algoritmo de Euclides , resultaron ineficientes en campos infinitos; los algoritmos del álgebra lineal enfrentaron dificultades similares. ^{[ 22 ]} Por lo tanto, los investigadores recurrieron al descubrimiento de métodos para reducir polinomios (como aquellos sobre un anillo de enteros o un dominio de factorización única ) a una variante computable eficientemente mediante un algoritmo euclidiano.