Representação formal de anéis em cálculos

Ao ler um artigo sobre o uso de métodos algébricos para detectar alguns subgráficos induzidos, parece que o ideal da aresta é uma ferramenta importante que conecta álgebra comutativa e teoria de grafos. Como não estou familiarizado com cálculos de objetos algébricos, existem boas referências ou livros sobre esse assunto? Particularidade em representar um anel R em uma máquina de Turing e a complexidade de decidir propriedades básicas em R (por exemplo, a altura de um ideal primo em R.)

Suas perguntas estão relacionadas a um campo (sem trocadilhos) chamado "Álgebra do computador". Eu próprio estava procurando pesquisas abrangentes quando estava trabalhando em métodos algébricos para calcular várias métricas de centralidade de gráficos. Não consegui encontrar boas pesquisas, mas este livro foi parcialmente útil. Os trabalhos de pesquisa sobre esse "tópico" estão espalhados por todo o lado e geralmente não são explicitamente categorizados como "álgebra computacional". A leitura de artigos algorítmicos sobre isomorfismo, fatoração (números inteiros / polinômios) e algoritmos de gráfico com base na multiplicação de matrizes pode fornecer mais informações.

Que eu saiba:

1. Se você ler sobre limites inferiores em algum modelo computacional algébrico, a suposição usual é que as operações de anel ou campo são de custo constante , ou seja, são dadas como primitivas. Esta é a suposição feita em uma das principais fontes sobre o tema: Burgisser, Clausen, Shokrollahi- Teoria da complexidade algébrica (Springer, 1997). (E é isso que é modelado por circuitos algébricos, por exemplo.)

2. Quando se fala em limites superiores , para perguntas padrão em complexidade algébrica, como ao estudar procedimentos de teste de identidade polinomial, a suposição padrão é que as operações de anel ou campo podem ser computadas em polítime. Isso significa que se trabalha sobre números inteiros ou sobre números racionais, e é fácil encontrar um esquema de codificação que permita cálculos tão eficientes das operações básicas.

3. Para outros fins que conheço, em relação aos modelos algébricos, a maneira de representar o anel ou o campo é uma questão real e, às vezes, não existe uma maneira eficiente de fazê-lo, e pode até haver questões de indecidibilidade. As referências que conheço que cobrem esse tipo de perguntas são o livro que Shiva Kintali deu e também: Álgebra Algorítmica , Bhubaneswar Mishra, Springer 1993: O Capítulo 3 trata de maneiras de representar certos anéis.

Outros livros de interesse podem ser: Zur Gathen e Jurgen Gerhard, Modern Computer Algebra , Cambridge, 1999. E possivelmente Victor Shoup, Uma Introdução Computacional à Teoria dos Números e Álgebra , (Disponível on-line).

Você também pode ter sorte com as palavras-chave 'álgebra comutativa computacional' e 'geometria algébrica computacional'. Tente o CLO como ponto de partida e veja J. Symbolic Computation, sistemas como Macaulay2 e Singular e os documentos que os referenciam. O grande martelo são as bases de Gröner, cujo cálculo resolverá muitos problemas algébricos, mas, no pior dos casos, é duplamente exponencial em geral.