He empezado a trabajar en un paquete (escrito en matlab por ahora) que entre otras cosas debe ser capaz de representar y manipular (comparar, sumar, multiplicar, diferencia, etc) polinomios en varias variables. Hasta el momento, mi enfoque ha sido el siguiente
- Tengo una clase de cada uno de los objetos de los cuales representa un polinomio.
- En cada polinomio objeto, yo almacenar los símbolos de las variables que aparecen en el polinomio (decir $x$$y$), el número de componentes de cada una de estas variables (decir $3$ $2$ si $x\in\mathbb{R}^3$$y\in\mathbb{R}^2$).
- También tengo un modo fijo (algunas de función $r$) de la generación de todos los multi-índices de alguna dimensión y un poco de orden. Por ejemplo, le digo a esta función que la dimensión de la base de que el espacio es $2$, y el orden de la monomials estoy interesado en el es $3$ y devuelve
$$r(2,3)=\left(\begin{bmatrix}3\\ 0\end{bmatrix},\begin{bmatrix}2\\ 1\end{bmatrix},\begin{bmatrix}1\\ 2\end{bmatrix},\begin{bmatrix}0\\ 3\end{bmatrix}\right)$$
Using $r$ I can systematically construct on the go the monomial basis for the space of polynomials of some degree in some variables (just identify the monomial $x_1^3$ with $[3,0]^T$, etc). Furthermore, once I fix how I order the variables (for example, first $x$ then $s$), and the number of components each has, then the order in which $r$ escupe los vectores de la base es fija.
Yo uso el orden en que $r$ devuelve a cabo los vectores para representar el polinomio de interés como el vector de los coeficientes de dicho polinomio con respecto a la monomio base, en el que el $i^{th}$ entrada del vector a es el coeficiente de la $i^{th}$ polinomio devuelto por $r$.
Por ejemplo, para representar
$$q(x)=2x_1^2+x_1x_2-3x_2+1$$
$r$ gives us
$$r(2,0)=\left(\begin{bmatrix}0\\ 0\end{bmatrix}\right),\quad r(2,1) =\left(\begin{bmatrix}1\\ 0\end{bmatrix},\begin{bmatrix}0\\ 1\end{bmatrix}\right),\quad r(2,2) =\left(\begin{bmatrix}2\\ 0\end{bmatrix},\begin{bmatrix}1\\ 1\end{bmatrix},\begin{bmatrix}0\\ 2\end{bmatrix}\right).$$
and thus I end up representing $q$ as
q.symbols = x
q.varnumber = 2
q.coefs = [1,0,-3,2,1]
However, I this seems to me as a poor way of doing things. In particular, I end up having to do a lot of searching through the results returned by $r$. For example, if I'd like to combine a polynomial $p$ in $x$ and another $q$ in $y$ (say add them together), I end up doing something along the lines as
Use $r$ to generate a basis of monomials of sufficiently high degree (in the case of adding of degree $\max\{\deg(p),\deg(q)\}$) in both $x\in\mathbb{R}^3$ and $y\in\mathbb{R}^2$.
Buscar y comparar los componentes apropiados de la ($5$-dimensional) vectores de la base para $p+q$ ($3$- dimensional) vectores de la base de $p$ y por separado el ($2$-dimensional) de $q$. Una vez que identificar cuál de los vectores de la base de $p+q$ corresponden a cual de $p$ y que de $q$, entonces sé que los coeficientes para sumar y donde almacenarlos. En realidad, en este ejemplo, no hay coeficientes se suman porque $p$ $q$ están en diferentes variables, pero en general este no es el caso...
Ahora muchos de estos problemas se resolverían si hubo un bijection que era barato para calcular e invertir de $\mathbb{N}$ y el conjunto de monomials en varias variables. Por ejemplo, uno en el que tenemos una fórmula analítica para (sin embargo, yo no podía pensar en uno, y estoy seguro de que hay uno). También he mirado en línea y he visto menciones de diferentes formas de ordenar los polinomios (lexicográfica, clasificados lexicográfica, ponderado, etc), con propiedades diferentes.
Sin embargo, es claro para mí que uno a utilizar y por qué (yo también sé nada de nada acerca de álgebra computacional). Así que mis preguntas son:
- Alguna sugerencia sobre cómo mejorar el anterior, reducir el coste computacional en su mayoría, pero consideraciones acerca de la memoria también sería genial (estoy abierto a cambiar por completo la manera en la que he estado en representación de polinomios).
- ¿Cómo es esto generalmente se hace en álgebra computacional paquetes?
- Y/o sugerencias para referencias donde puedo encontrar las respuestas a estas preguntas.
PD: me importa sobre todo la manipulación arbitraria, reales, polinomios en $\mathbb{R}^n$, y no aquellas que se encuentran algunos de módulo, ideales, etc. Así las cosas así que de manera eficiente puede calcular la mínima generación de conjuntos de estos, Grobner base, etc, no es probablemente muy importante para mí (puedo estar equivocado, en cuyo caso, por favor me corrija). Tampoco estoy muy preocupado acerca de la aplicación de algoritmos para la división de polinomios y factorización.
Edit: Gracias a todos por las respuestas. Han sido útiles en la mejora de (mucho) de la aplicación. En caso de que alguien curioso, un (siendo muy duro, pero funciona), la versión de el código se puede encontrar aquí.
Edit 2: En caso de que alguien esté interesado, actualmente estoy almacenar los polinomios mediante el almacenamiento de su no-cero de los coeficientes en una matriz junto con su clasificación en la gradual lexicográfica del orden (la matriz ordenados por el orden). Para multiplicar y agregar voy de ida y vuelta desde las filas de la monomials el uso de alguna función recursiva he cocinado.
