Multiplicação de polinómios simétricos

No artigo Padrões de software – o iterador, apresentei um iterador para todas as permutações de uma dada lista de elementos. No final referi uma possível aplicação deste iterador relacionada com a multiplicação de polinómios simétricos que passo agora a discutir.
A título de exemplo, considerarei polinómios em três variáveis: x, y e z. Um polinómio simétrico nas variáveis x, y e z mantém-se inalterado aquando da permutação das variáves. Desta forma, se o termo 2xy está presente no polinómio então também 2xz e 2yz o estão. Pode-se escrever o polinómio simétrico dado por 2xy+2xz+2yz com o par ordenado (2,[1,1,0]), onde existe a lista apresentada representa o grau das variáveis e número corresponde ao coeficiente. Nesta representação, assume-se que o polinómio está escrito na forma canónica. O polinómio constante pode ser dado por (const,[0,0,0]) e o polinómio
pol_exemplo 
pode ser escrito como (1,[2,2,1]).
O número de elementos condensados na representação (1,[1,1,1]) é apenas de 1, o elemento xyz. No entanto, o número aumenta para 6 no caso do simétrico (1,[3,2,1]). É fácil de ver que o número de elementos é dado pelo número total das permutações das variáveis a dividir pelo produto das permutações dos graus que se repetem. Por exemplo, no caso de 6 variáveis, a representação (2,[3,2,2,1,1,1]) condensa 6! a dividir por 2!x3! elementos, o que corresponde a uma combinação multinomial.
Suponhamos que pretendemos multiplicar os termos (2,[3,2,1]) e (3,[2,2,1]). Os coeficientes são multiplicados no resultado como é evidente. O primeiro tem n=3!=6 elementos e o outro tem m=3!/2!=3 elementos. Para obter a respectiva multiplicação, teríamos de percorrer todas as permutações de cada uma das listas e somar os graus. No entanto, devido á propriedade comutativa da multiplicação, tal não é necessário. Escolhe-se o termo que condensa o menor número de elementos possíveis, que neste caso é (3,[2,2,1]). As permutações dos graus desta lista (que representam cada elemento) são [2,2,1], [2,1,2] e [1,2,2]. Somando os graus, obtém-se

[2,2,1]+[3,2,1]=[5,4,2] (o resultado tem 6 termos)
[2,1,2]+[3,2,1]=[5,3,3] (o resultado tem 3 termos)
[1,2,2]+[3,2,1]=[4,4,3] (o resultado tem 3 termos)

Como estamos a multiplicar cada termo de (3,[2,2,1]) com a totalidade dos elementos de (2,[3,2,1]), o resultado tem de ter sempre seis elementos. No entanto, as listas [5,3,3] e [4,4,3] apenas representam 3. Por conseguinte, têm um factor de 2 associado.
Desta forma, o resultado da multiplicação simétrica de (3,[2,2,1]) com (2,[3,2,1]) vale (6,[5,4,2])+(12,[5,3,3])+(12,[4,4,3]).
Claramente, o iterador para todas as permutações afigura-se útil neste contexto, para obter todas as permutações da primeira lista considerada.
Outra aplicação consiste mesmo em escrever todos os elementos. Para isso, consideram-se as variáveis em posição fixa e permutam-se os respectivos graus.

No projecto algorexamples, apresento uma representação de polinómios simétricos da pela classe symmetricpolynomial. Nesta classe, qualquer polinómio simétrico é representado por um mapa que, a cada grau, associa um coeficiente. Para construir o polinómio é necessário construir de início o mapa que o vai representar ou então apenas adicionar e multiplicar polinómios. No futuro pretendo construir uma função que permita ler polinómios a partir de uma string com uma sintaxe familiar. Nessa altura, exponho aqui algum código de exemplo para a utilização dessa classe.

Os polinómios simétricos desempenham um papel central na teoria de Galois e a sua importância na resolução de equações polinomiais já havia sido reconhecida por Lagrange. Actualmente ainda se usam essas  técnicas algébricas.

Sobre Sérgio O. Marques

Licenciado em Física/Matemática Aplicada (Astronomia) pela Faculdade de Ciências da Universidade do Porto e Mestre em Matemática Aplicada pela mesma instituição, desenvolvo trabalho no PTC (Porto Technical Centre) - Yazaki como Administrador de bases-de-dados. Dentro o meu leque de interesses encontram-se todos os temas afins às disciplinas de Matemática, Física e Astronomia. Porém, como entusiasta, interesso-me por temas relacionados com electrónica, poesia, música e fotografia.
Esta entrada foi publicada em Computadores e Internet. ligação permanente.

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão / Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão / Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão / Alterar )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s