Descomposición polinómica

En matemáticas, unha descomposición polinómica expresa un polinomio f como a composición funcional  dos polinomios g e h, onde g e h teñen grao superior a 1; é unha descomposición funcional alxébrica. Son coñecidos algoritmos para descompoñer polinomios univariados en tempo polinómico.

Os polinomios que se descompoñen deste xeito son polinomios compostos; os que non o son son polinomios non compostos ou ás veces polinomios primos (non se deben confundir cos polinomios irredutíbeis, que non se poden factorizar en produtos de polinomios). O grao dun polinomio composto é sempre un número composto, o produto dos graos dos polinomios compostos.

O resto deste artigo trata só de polinomios univariados; tamén existen algoritmos para polinomios multivariados de grao arbitrario.Jean-Charles Faugère, Ludovic Perret, "An efficient algorithm for decomposing multivariate polynomials and its applications to cryptography", Journal of Symbolic Computation, 44:1676-1689 (2009), 

 Exemplos 
No caso máis sinxelo, un dos polinomios é un monomio. Por exemplo,



descompónse en



xa que



usando o símbolo do operador de anel ∘ para indicar a composición da función.

Menos trivialmente,



 Unicidade 
Un polinomio pode ter distintas descomposicións en polinomios non compostos onde  onde  para algúns . A restrición na definición a polinomios de grao superior a 1 exclúe as infinitas descomposicións posíbeis con polinomios lineares.

 Aplicacións 
Unha descomposición polinómica pode permitir unha avaliación máis eficiente dun polinomio. Por exemplo,



pódese calcular con 3 multiplicacións e 3 sumas usando a descomposición, mentres que o método de Horner requiriría 7 multiplicacións e 8 sumas.

Unha descomposición polinómica permite o cálculo de raíces simbólicas usando radicais, mesmo para algúns polinomios irredutíbeis. Esta técnica úsase en moitos sistemaa alxébricos computacionais. Por exemplo, usando a descomposición



as raíces deste polinomio irredutíbel pódense calcular como 



Mesmo no caso dos polinomios cuárticos, onde hai unha fórmula explícita para as raíces, a resolución mediante a descomposición adoita dar unha forma máis sinxela. Por exemplo, a descomposición



dá as raíces 



pero a aplicación directa da fórmula cuártica dá resultados equivalentes mais nunha forma difícil de simplificar e difícil de entender; unha das catro raíces é:



 Algoritmos 
O primeiro algoritmo para a descomposición polinómica foi publicado en 1985, aínda que fora descuberto en 1976,  e implementado no sistema alxébrico computacional Macsyma/Maxima. Ese algoritmo leva un tempo exponencial no peor dos casos, mais funciona independentemente da característica do corpo subxacente.

Un algoritmo de 1989 execútase en tempo polinómico pero con restricións na característica.

Un algoritmo de 2014 calcula unha descomposición en tempo polinómico e sen restricións sobre a característica.

 Notas 


 Véxase tamén 

 Bibliografía 


 Outros artigos 
 Polinomio.

Categoría:Polinomios
Categoría:Wikipedia:Páxinas con traducións non revisadas