Simplificación de polinomios

Question

Supongamos que tengo un (multivariante) polinomio con coeficientes en $\mathbb Z$ o $\mathbb Q$, dado completamente en forma expandida. ¿Cómo puedo simplificar este fin de reducir el número de operaciones elementales (suma, resta, multiplicación) que se utilizan en su representación (y por lo tanto la evaluación una vez que se sustituye los valores de la indeterminates)? Yo no estoy interesado en el caso de que el polinomio como un todo factorizes, sino que estoy buscando una forma inteligente para factorizar partes de la misma.

Ejemplo: ¿cómo se puede activar

$$x^{2} y - x y^{2} - 2 y^{3} + x^{2} - x y - 2 y^{2} - x + 2 y + 1$$

en

$$((x+y)(1+y)-1)(x-2y)+1$$

o algo relativamente sencilla? La primera forma tiene 20 elementales operaciones, 12 multiplicaciones, 3 adiciones y 5 sustracciones. La segunda forma tiene 3 multiplicaciones, 3 adiciones y 2 sustracciones, para un total de 8 de las operaciones. No estoy seguro de que esta es la óptima, pero sin duda es mucho mejor que el totalmente la forma expandida. Factorización de todo polinomio no ayuda, ya que es irreducible sobre $\mathbb Q$.

Una solución ideal sería encontrar una representación con la garantía de un mínimo número de operaciones en el polinomio de tiempo. Pero no estoy seguro de si esto es posible, así que yo también estoy interesado en las soluciones de los cuales no garantizan minimality, o no garantizan el polinomio de tiempo de ejecución, siempre que funcionan razonablemente bien para el uso práctico de los casos.

Answer 1

Dado multivariante, polinomio, un buen lugar para comenzar sería factor $x$ de todos los términos con $x$, entonces el factor de $y$ de todos los términos que están a la izquierda con $y$, y así sucesivamente. Dado un azar multivariante polinomio de grado $n$ $m$ variables, en promedio, $O(n^m)$ términos tendrán un $x$, es decir, sólo la factorización de un $x$ va a reducir el número de multiplicaciones por $O(n^m)$. Del mismo modo, teniendo un $y$ de lo que queda va a reducir el número de multiplicaciones por $O(n^{m-1})$, y así sucesivamente. El polinomio resultante de estos pasos se tiene el formulario, $x*P(x,y,z,...)+y*Q(x,y,z,...)+...+k$. Este consta de $m$ multiplicaciones y $m$ ganancia ($m-1$ si no hay ningún término constante), además de las operaciones necesarias para los polinomios, $P(x,y,z,...)$, $Q(x,y,z,...),$ y así sucesivamente. Estos polinomios son de grado $n-1$ (ya que al menos una variable ha sido un factor fuera de cada plazo) y si la misma operación se aplica a ellos, ceder a otro la reducción en el número de operaciones por $O(m*(n-1)^m)$. Continuando de esta forma recursiva de los rendimientos de un polinomio con cerca de $O(n^m)$ multiplicaciones y $O(n^m)$ adiciones, como contraposición a la $O(n^{m+1})$ multiplicaciones y $O(n^m)$ adiciones del polinomio original.

Esta idea es una adaptación del Método de Horner para polinomios de una sola variable.