Формальное представление колец в вычислениях

17

Читая статью об использовании алгебраических методов для обнаружения некоторых индуцированных подграфов, кажется, что реберный идеал является важным инструментом, соединяющим коммутативную алгебру и теорию графов. Поскольку я не знаком с вычислениями алгебраических объектов, есть ли хорошие ссылки или книги на эту тему? Особенности представления кольца R на машине Тьюринга и сложность определения основных свойств на R (скажем, высоты простого идеала в R.)

Сянь-Чжи Чан 張顯 之
источник
Извините, если вопрос слишком элементарный или широкий ...
Сянь-Чи Чанг 之 之
это хороший вопрос
Суреш Венкат
4
Хотя я сам не очень разбираюсь в этой теме, я бы порекомендовал проверить Кайяла и Саксену о проблемах изоморфизма и автоморфизма кольца . Это очень сложная теоретическая статья, так что это должно помочь. Я полагаю, что они представляют собой конечные кольца, сначала указав аддитивную группу (по ее генераторам), а затем приведя список попарных произведений всех этих генераторов.
Робин Котари

Ответы:

14

Ваши вопросы связаны с областью (без каламбура), которая называется «Компьютерная алгебра». Я сам искал всесторонние обзоры, когда работал над алгебраическими методами для вычисления различных метрик центральности графа. Я не мог найти хорошие обзоры, но эта книга была частично полезна. Исследовательские работы по этой «теме» разбросаны повсеместно и часто явно не классифицируются как «компьютерная алгебра». Чтение алгоритмических работ по изоморфизму, факторизации (целые числа / полиномы) и алгоритмов графов, основанных на умножении матриц, может дать вам более глубокое понимание.

Шива Кинтали
источник
«Поле» под названием «Компьютер», «Алгебра» ... Хм ... В любом случае, спасибо за книгу и ключевое слово, теперь я могу сделать еще несколько поисков !!
Сянь-Чи Чан 之 之
14

Насколько я знаю:

  1. Если вы читаете о нижних границах в некоторой алгебраической вычислительной модели, то обычное предположение состоит в том, что кольцевые или полевые операции имеют постоянную стоимость , то есть они задаются как примитивы. Это предположение сделано в одном из основных источников по теме: Burgisser, Clausen, Shokrollahi - алгебраическая теория сложности (Springer, 1997). (И это то, что моделируется алгебраическими схемами, например.)

  2. Когда говорят о верхних границах для стандартных вопросов алгебраической сложности, как, например, при изучении процедур проверки полиномиального тождества, тогда стандартное предположение состоит в том, что кольцевые или полевые операции могут быть вычислены в многопоточности. Это означает, что каждый работает над целыми числами или над рациональными числами, и легко найти схему кодирования, которая позволяет такие эффективные вычисления основных операций.

  3. Для других целей, которые я знаю, относительно алгебраических моделей, способ представления кольца или поля является реальным вопросом, и иногда нет эффективного способа сделать это, и могут даже возникнуть вопросы неразрешимости. Ссылки, которые я знаю об этом типе вопросов, охватывают книгу Шивы Кинтали, а также: Алгоритмическая алгебра , Бхубанешвар Мишра, Спрингер 1993: Глава 3 посвящена способам представления определенных колец.

Другие интересные книги могут быть: Zur Gathen и Jurgen Gerhard, Modern Computer Algebra , Cambridge, 1999. И, возможно, Victor Shoup, Вычислительное введение в теорию чисел и алгебру (доступно онлайн).

Иддо Цамерет
источник
Книга онлайн действительно помогает!
Сянь-Чи Чанг 之 之
8

Вам также может повезти с ключевыми словами «вычислительная коммутативная алгебра» и «вычислительная алгебраическая геометрия». Попробуйте CLO в качестве отправной точки и посмотрите на J. Символические вычисления, а также системы, такие как Macaulay2 и Singular, и документы, которые на них ссылаются. Большим молотом являются базисы Грена Обнера, вычисление которых решит многие алгебраические задачи, но в худшем случае это двойная экспоненциальная зависимость в целом.

Джейсон Мортон
источник