[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Índice] [ ? ]

53. grobner

/grobner.texi/1.3/Sat Jun 2 00:13:21 2007//


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Índice] [ ? ]

53.1 Introdução a grobner

grobner é um pacote para trabalhos com bases de Groebner no Maxima.

Um tutorial sobre Bases de Groebner pode ser encontrado em

http://www.geocities.com/CapeCanaveral/Hall/3131/

Para usar as seguintes funções você deve primeiramente tornar o pacote `grobner.lisp' disponível para uso:

load(grobner);

Uma demonstração de uso pode ser iniciada com

demo("grobner.demo");

ou com

batch("grobner.demo")

Alguns dos cálculos no arquivo de demonstração irão tomar um pouco de tempo portanto a saída `grobner-demo.output' do arquivo de demonstração pode ser encontrada no mesmo diretório que o arquivo de demonstração.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Índice] [ ? ]

53.1.1 Notas sobre o pacote grobner

O pacote foi escrito por

Marek Rychlik

http://alamos.math.arizona.edu

e foi liberado em 24/05/2002 nos termos da Licença Pública Geral (GPL/GNU/FSF) (veja o arquivo `grobner.lisp'. Essa documentação foi extraída dos arquivos

`README', `grobner.lisp', `grobner.demo', `grobner-demo.output'

por Günter Nowak. Sugestões de melhorias da documentação podem ser discutidas em maxima-mailing-list maxima@math.utexas.edu. O código está um pouco desatualizado atualmente. Implementações modernas utilizam o algorítmo rápido F4 descrito em

 
A new efficient algorithm for computing Gröbner bases (F4) 
Jean-Charles Faugère
LIP6/CNRS Université Paris VI 
January 20, 1999

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Índice] [ ? ]

53.1.2 Implementações de ordem monomial admissível em grobner


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Índice] [ ? ]

53.2 Funções e Variáveis Definidas para grobner


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Índice] [ ? ]

53.2.1 Comutadores globais para grobner

Variável de opção: poly_monomial_order

Valor padrão: lex

Esse comutador globalcontrola qual a ordenação monomial é usada em polinomio e em cálculos com Bases de Groebner. Se não for escolhidat, lex será usada.

Variável de opção: poly_coefficient_ring

Valor padrão: expression_ring

Esse comutador indica o anel de coeficiente dos polinômios que irá ser usado em cálculos de grobner. Se não for escolhido, o anel de expressão geral do maxima's irá ser usado. Essa variável pode ser escolhida para ring_of_integers se for desejado.

Variável de opção: poly_primary_elimination_order

Valor padrão: false

Nome da ordem padrão de eliminação de variáveis em funções de eliminação. Se não for escolhida, lex irá ser usada.

Variável de opção: poly_secondary_elimination_order

Valor padrão: false

Nome da ordem padrão para manter variáveis em funções de eliminação. Se não for escolhida, lex irá ser usada.

Variável de opção: poly_elimination_order

Valor padrão: false

Nome da ordem padrão de funções de eliminação. Se escolhida, irá sobrescrever as escolhas nas variáveis poly_primary_elimination_order e poly_secondary_elimination_order. O usuário deve garantir que essa é uma ordem de eliminação verdadeira válida para o número de variáveis eliminadas.

Variável de opção: poly_return_term_list

Valor padrão: false

Se escolhida para true, todas as funções no pacote grobner irão retornar cada polinômio como uma lista de termos na ordem monomial corrente em lugar de retornar uma expressão geral do maxima.

Variável de opção: poly_grobner_debug

Valor padrão: false

Se escolhida para true, produz saída de depuração e rastros.

Variável de opção: poly_grobner_algorithm

Valor padrão: buchberger

Valores possíveis:

O nome do algorítmo usado para encontrar as bases de Groebner.

Variável de opção: poly_top_reduction_only

Valor padrão: false

Se não for false, usa redução de topo somente se for possível. Redução de topo significa que o algorítmo de divisão para após a primeira redução.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Índice] [ ? ]

53.2.2 Operadores simples em grobner

poly_add, poly_subtract, poly_multiply e poly_expt são as operações aritméticas sobre polinômios. Elas são executadas usando representação interna, mas os resultados são convertidos de volta à forma geral do maxima.

Função: poly_add (poli1, poli2, varlist)

Adiciona dois polinômios poli1 e poli2.

(%i1) poly_add(z+x^2*y,x-z,[x,y,z]);
                                    2
(%o1)                              x  y + x
Função: poly_subtract (poli1, poli2, varlist)

Subtrai o polinômio poli2 do polinômio poli1.

(%i1) poly_subtract(z+x^2*y,x-z,[x,y,z]);
                                      2
(%o1)                          2 z + x  y - x
Função: poly_multiply (poli1, poli2, varlist)

Retorna o produto dos polinômios poli1 e poli2.

(%i2) poly_multiply(z+x^2*y,x-z,[x,y,z])-(z+x^2*y)*(x-z),expand;
(%o1)                                  0
Função: poly_s_polynomial (poli1, poli2, varlist)

Retorna o polinômio syzygy (S-polinomial) de dois polinômios poli1 e poli2.

Função: poly_primitive_part (poli1, varlist)

Retorna o polinômio poli dividido pelo MDC entre seus coeficientes.

(%i1) poly_primitive_part(35*y+21*x,[x,y]);
(%o1)                              5 y + 3 x
Função: poly_normalize (poli, varlist)

Retorna o polinômio poli dividido pelo coeficiente lider. poly_normalize assume que a divisão é possível, o que nem sempre ocorre em anéis que não são corpos (fields).


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Índice] [ ? ]

53.2.3 Outras funções em grobner

Função: poly_expand (poli, varlist)

Essa função transforma polinômios para a forma interna e da forma interna para a forma geral. poly_expand é equivalente a expand(poly) se poli passa corretamente para um polinômio. Se a representação não for compatível com um polinômio nas variáveis varlist, o resultado é um erro. Esse resultado em erro pode ser usado para testar se uma expressão transforma-se corretamente para a representação interna. Os seguintes exemplos ilustra que variáveis de funções indexadas e transcendentes são permitidas.

(%i1) poly_expand((x-y)*(y+x),[x,y]);
                                     2    2
(%o1)                               x  - y
(%i2) poly_expand((y+x)^2,[x,y]);
                                2            2
(%o2)                          y  + 2 x y + x
(%i3) poly_expand((y+x)^5,[x,y]);
                  5      4         2  3       3  2      4      5
(%o3)            y  + 5 x y  + 10 x  y  + 10 x  y  + 5 x  y + x
(%i4) poly_expand(-1-x*exp(y)+x^2/sqrt(y),[x]);
                                          2
                                  y      x
(%o4)                       - x %e  + ------- - 1
                                       sqrt(y)

(%i5) poly_expand(-1-sin(x)^2+sin(x),[sin(x)]);
                                2
(%o5)                      - sin (x) + sin(x) - 1

Função: poly_expt (poli, número, varlist)

eleva poli a um inteiro positivo número. If número não for um inteiro positivo um erro irá ser mostrado.

(%i1) poly_expt(x-y,3,[x,y])-(x-y)^3,expand;
(%o1)                                  0
Função: poly_content (poli. varlist)

poly_content extrai o MDC entre seus coeficientes

(%i1) poly_content(35*y+21*x,[x,y]);
(%o1)                                  7
Função: poly_pseudo_divide (poli, polilist, varlist)

Realiza a divisão falsa do polinômio poli pela lista de n polinômios polilist. Retorna multiplos valores. O primeiro valor é uma lista de quocientes a. O segundo valor é o resto r. O terceiro argumento é um coeficiente escalar c, tal que c*poli pode ser dividido porpolilist dentro do anel dos coeficientes, que não é necessáriamente corpo. Finalmente, o quarto valor é um contador inteiro do número de reduções realizadas. O objetos resultantes satisfazem à equação:

c*poly=sum(a[i]*polylist[i],i=1...n)+r.

Função: poly_exact_divide (poli1, poli2, varlist)

Divide um polinômio poli1 por outro polinômio poli2. Assume que a divisão exata (sem resto) é possível. Retorna o quociente.

Função: poly_normal_form (poli, polilist, varlist)

poly_normal_form encontra a forma normal de um polinômio poli com relação a um conjunto de polinômios polilist.

Função: poly_buchberger_criterion (polilist, varlist)

Returns true if polilist is a Groebner basis with respect to the current term order, by using the Buchberger criterion: for every two polynomials h1 and h2 in polilist the S-polynomial S(h1,h2) reduces to 0 modulo polilist.

Função: poly_buchberger (polilist_fl varlist)

poly_buchberger realiza o algorítmo de Buchberger sobre uma lista de polinômios e retorna a base de Grobner resultante.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Índice] [ ? ]

53.2.4 Pósprocessamento padão de bases de Groebner

O k-ésimo ideal de eliminação I_k de uma Ideal I sobre K[ x[1],...,x[n] ] é o ideal intersecção(I, K[ x[k+1],...,x[n] ]).
O ideal quociente I:J é o ideal {h|for all w em J: w*h em I}.
O ideal I:p^inf é o ideal {h| existe um n em N: p^n*h em I}.
O ideal I:J^inf é o ideal {h| existe um n em N \and a p em J: p^n*h em I}.
O ideal radical sqrt(I) é o ideal {h| existe um n em N : h^n em I }.

Função: poly_reduction (polilist, varlist)

poly_reduction reduz uma lista de polinômios polilist, de forma que cada poinômio é completametne reduzido com relação a outros polinômios.

Função: poly_minimization (polilist, varlist)

Retorna uma sublista da lista de polinômios polilist gerando o mesmo ideal de monômio que polilist mas minimo, i.e. nenhum monômio líder de um polinômio na sublista divide o monômio líder de outro polinômio.

Função: poly_normalize_list (polilist, varlist)

poly_normalize_list aplica poly_normalize a cada polinômio na lista. Que significa que poly_normalize_list divide todo polinômio em uma lista polilist por seu coeficiente líder.

Função: poly_grobner (polilist, varlist)

Retorna uma base de Groebner do ideal gerado pelos polinômios polilist. Afetado pelos sinalizadores globais.

Função: poly_reduced_grobner (polilist, varlist)

Retorna uma base de Groebner reduzida do ideal gerado pelos polinômios polilist. Afetado pelos sinalizadores globais.

Função: poly_depends_p (poli, var, varlist)

poly_depends testa se um polinômio depende da variável var.

Função: poly_elimination_ideal (polilist, num, varlist)

poly_elimination_ideal retorna a base de grobner do num-ésimo ideal de eliminação de um ideal especificado como uma lista de polinômios geradores (não necessáriamente base de Groebner)

Função: poly_colon_ideal (polilist1, polilist2, varlist)

Retorna a base reduzida de Groebner do ideal quociente

I(polilist1):I(polilist2)

onde polilist1 e polilist2 são duas listas de polinômios.

Função: poly_ideal_intersection (polilist1, polilist2, varlist)

poly_ideal_intersection retorna a intersecção entre dois ideais.

Função: poly_lcm (poli1, poli2, varlist)

Retorna o mínimo múltiplo comum entre poli1 e poli2.

Função: poly_gcd (poli1, poli2, varlist)

Retorna máximo divisor comum de poli1 e poli2.

Função: poly_grobner_equal (polilist1, polilist2, varlist)

poly_grobner_equal testa se duas bases de Groebner geram o mesmo ideal. Retorna true se as duas listas de polinômios polilist1 e polilist2, assumidas serem bases de Groebner, geram o mesmo ideal, e false de outra forma. Isso é equivalente a verificar que todo polinômio da primeira base é reduzido a 0 módulo a segunda base e vice-versa. Note que no exemplo abaixo a primeira lista não é uma base de Groebner, e dessa forma o resultado é false.

(%i1) poly_grobner_equal([y+x,x-y],[x,y],[x,y]);
(%o1)                         false
Função: poly_grobner_subsetp (polilist1, polilist2, varlist)

poly_grobner_subsetp testa se um ideal gerado pela polilist1 está contido em um ideal gerado pela polilist2. Para esse teste sempre tenha sucesso, polilist2 deve ser uma base de Groebner.

Função: poly_grobner_member (poli, polilist, varlist)

Retorna true se um polinômio poli pertence ao ideal gerado pela lista polinomial polilist, que é assumida como sendouma base de Groebner. Retorna false de outra forma.

poly_grobner_member testa se um polinômio pertence a um ideal gerado por uma lista de polinômios, que é assumida ser uma base de Groebner. Equivale a normal_form sendo 0.

Função: poly_ideal_saturation1 (polilist, poli, varlist)

Retorna abase de Groebner reduzida da saturação do ideal

I(polylist):poly^inf

Geometricamente, sobre um corpo algebricamente fechado, esse é um conjunto de polinmios no ideal gerado por polilist que não tende identicamente a zero sobre a variação de poli.

Função: poly_ideal_saturation (polilist1, polilist2, varlist)

Retorna a base de Groebner reduzida da saturação do ideal

I(polylist1):I(polylist2)^inf

Geometricamente, sobre um corpo algebricamente fechado, esse é um conjunto de polinmios no ideal gerado por polilist1 que não tende identicamente a zero sobre a variação de polilist2.

Função: poly_ideal_polysaturation1 (polilist1, polilist2, varlist)

polilist2 ist a list of n polynomials [poly1,...,polyn]. Retorna a base de Groebner reduzida do ideal

I(polylist):poly1^inf:...:polyn^inf

obtido por uma seqüência de sucessivas saturações nos polinômios da lista polinômial polilist2 do ideal gerado pela lista polinomial polilist1.

Função: poly_ideal_polysaturation (polilist, polilistlist, varlist)

polilistlist is a list of n list of polynomials [polylist1,...,polylistn]. Retorna a base reduzida de Groebner da saturação do ideal

I(polylist):I(polylist_1)^inf:...:I(polylist_n)^inf

Função: poly_saturation_extension (poli, polilist, varlist1, varlist2)

poly_saturation_extension implementa o famoso artifício de Rabinowitz.


[ << ] [ >> ]           [Top] [Contents] [Índice] [ ? ]

This document was generated by Robert Dodier on Dezembro, 22 2007 using texi2html 1.76.