Formalna reprezentacja pierścieni w obliczeniach

Czytając artykuł na temat stosowania metod algebraicznych do wykrywania niektórych indukowanych subgrafów, okazuje się, że ideał krawędzi jest ważnym narzędziem łączącym algebrę komutacyjną i teorię grafów. Skoro nie znam obliczeń obiektów algebraicznych, czy są jakieś dobre odniesienia lub książki na ten temat? Szczególność w reprezentowaniu pierścienia R na maszynie Turinga i złożoność decydowania o podstawowych właściwościach na R (powiedzmy, że wysokość pierwszego ideału w R.)

Twoje pytania są związane z polem (bez słów) o nazwie „Algebra komputerowa”. Sam szukałem obszernych ankiet, kiedy pracowałem nad metodami algebraicznymi do obliczania różnych wskaźników centralności grafów. Nie mogłem znaleźć dobrych ankiet, ale ta książka była częściowo pomocna. Prace badawcze na ten „temat” są rozrzucone po całym świecie i często nie są wyraźnie klasyfikowane jako „algebra komputerowa”. Czytanie prac algorytmicznych na temat izomorfizmu, faktoryzacji (liczby całkowite / wielomiany) i algorytmów grafowych opartych na mnożeniu macierzy może dać ci więcej wglądu.

Według mojej najlepszej wiedzy:

1. Jeśli czytasz o dolnych granicach w jakimś algebraicznym modelu obliczeniowym, zwykle przyjmuje się, że operacje pierścieniowe lub polowe mają stały koszt , to znaczy są podawane jako prymitywy. Jest to założenie przyjęte w jednym z głównych źródeł na ten temat: Burgisser, Clausen, Shokrollahi- Algebraic teoria złożoności (Springer, 1997). (I to jest na przykład modelowane przez obwody algebraiczne.)

2. Kiedy mówi się o górnych granicach , w przypadku standardowych pytań o złożoności algebraicznej, na przykład podczas badania procedur testowania tożsamości wielomianowej, wówczas standardowym założeniem jest to, że operacje pierścieniowe lub polowe mogą być obliczane w czasie polytime. Oznacza to, że działa się na liczbach całkowitych lub liczbach wymiernych i łatwo jest znaleźć schemat kodowania, który umożliwia tak wydajne obliczenia podstawowych operacji.

3. Do innych celów, jakie znam, dotyczących modeli algebraicznych, sposób przedstawienia pierścienia lub pola jest prawdziwym pytaniem i czasami nie ma skutecznego sposobu, aby to zrobić, a nawet mogą istnieć pytania nierozstrzygalne. Odniesienia, które znam na ten temat, obejmują książkę Shiva Kintali, a także: Algebra algorytmiczna , Bhubaneswar Mishra, Springer 1993: Rozdział 3 dotyczy sposobów reprezentowania niektórych pierścieni.

Inne interesujące książki to: Zur Gathen i Jurgen Gerhard, Modern Computer Algebra , Cambridge, 1999. I prawdopodobnie Victor Shoup, Obliczeniowe wprowadzenie do teorii liczb i algebry (dostępne online).

Możesz także mieć szczęście ze słowami kluczowymi „obliczeniowa algebra komutacyjna” i „obliczeniowa geometria algebraiczna”. Spróbuj CLO jako punktu wyjścia i spójrz na J. Symbolic Computation, systemy takie jak Macaulay2 i Singular oraz dokumenty, które się do nich odnoszą. Dużym młotem są obce podstawy Gr \ ", których obliczenie rozwiąże wiele problemów algebraicznych, ale w najgorszym przypadku jest generalnie podwójnie wykładnicze.