Определитель по модулю m

18

Каковы известные эффективные алгоритмы вычисления определителя целочисленной матрицы с коэффициентами в , кольца вычетов по модулю m . Число m может быть не простым, а составным (поэтому вычисления выполняются в кольце, а не в поле).Zммм

Насколько я знаю (читайте ниже), большинство алгоритмов являются модификациями исключения Гаусса. Вопрос в вычислительной эффективности этих процедур.

Если так получилось, что есть какой-то другой подход, мне тоже интересно.

Заранее спасибо.

Обновить:

Позвольте мне объяснить источник этого вопроса. Предположим, что простое число. Так что Z m это поле. И в этом случае мы можем выполнить все вычисления, используя числа, меньшие m , поэтому у нас есть хорошая верхняя граница для всех операций над числами: сложение, умножение и инверсия - все необходимые операции для запуска исключения по Гауссу.мZмм

С другой стороны, мы не можем выполнить инверсию для некоторых чисел, если не простое число. Поэтому нам нужны некоторые хитрости для вычисления определителя.м

И теперь мне любопытно, каковы известные уловки, чтобы сделать работу и можно ли найти такие уловки и бумаги книг.

Валерий Соколов
источник
3
Что вы подразумеваете под "эффективным"? Проблема явно в . P
Дэвид
2
Является ли фиксированной константой? Как это дается? m
Михаил Блондин
2
Что вы подразумеваете под маленьким? Могут ли они быть написаны в одинарном?
Михаил Блондин
5
Я до сих пор не понимаю вопроса. Определитель целочисленной матрицы может быть вычислен за полиномиальное время, поэтому вы можете просто принять это значение по модулю . Не нужно выполнять деления на Z m или найти факторизацию m . mZmm
Дэвид
2
@ValeriySokolov: это базовая линейная алгебра. Например, пожалуйста, проверьте проблему 11.5.3 вычислительной сложности Кристоса Х. Пападимитриу.
Цуёси Ито

Ответы:

15

Если вам известна факторизация вы можете вычислить по модулю каждый p e i i отдельно, а затем объединить результаты с использованием китайского остатка. Если е я = 1 , то вычисления по модулю р е I я легко, так как это поле. Для большего e i , вы можете использовать подъем Hensel. m=p1e1pnenpieiei=1pieiei

Маркус Блезер
источник
Спасибо! Это как то, что я искал. Это обычная практика для детерминант? (ссылки приветствуются).
Валерий Соколов
6
Это стандартные методы компьютерной алгебры. Взгляните на Modern Computer Algebra von zur Gathen и Gerhard или любую другую книгу по компьютерной алгебре. Что касается вашей конкретной проблемы, см. Также следующую статью Pan, Yu & Stewart comet.lehman.cuny.edu/vpan/pdf/pan146.pdf
Маркус Блезер,
17

Существует комбинаторный алгоритм Махаджана и Виная, который работает над коммутативными кольцами: http://cjtcs.cs.uchicago.edu/articles/1997/5/contents.html

Сашо Николов
источник
Спасибо за ваш ответ со ссылкой на очень интересную статью.
Валерий Соколов
Также я считаю, что существуют более эффективные алгоритмы, поскольку авторы этой статьи решили более общую задачу (для любого коммутативного кольца).
Валерий Соколов
под «есть» вы подразумеваете «известный» или «существует» (но еще не найдены)? это разумное предположение, но я немного скептически отношусь к тому, что структура кольца зачинщиков по модулю небольшого составного числа может вам все это очень сильно помочь. если я ошибаюсь, я нахожу это интересным.
Сашо Николов
1
@ValeriySokolov, чтобы быть справедливым, так как ответ действительно отвечает на ваш вопрос, вы можете принять его (или если вы хотите подождать, возможно, лучшие ответы, которые не были бы неразумными)
Суреш Венкат
@SashoNikolov Я обнаружил, что Wolfram Mathematica как-то вычисляет это. В «Замечаниях по реализации» они говорят: Det использует модульные методы и сокращение строк, создавая результат, используя китайскую теорему об остатках. Я хотел бы знать, что именно они делают, но быстрый поиск ничего не дал мне. Что касается «небольшого составного », то это только означает, что я хочу считать сложность сложений и умножений в этом кольце O ( 1 ) . То есть все факторы, подобные O ( log m ) , рассматриваются как O ( 1 ) . mO(1)O(logm)O(1)
Валерий Соколов
11

Для решения этой проблемы существует быстрый детерминированный алгоритм, основанный на нормальных формах Смита , сложность которого в худшем случае ограничена сверху стоимостью умножения матриц по целым числам по модулю . Для любой матрицы A алгоритм выводит свою нормальную форму Смита, откуда легко вычислить det ( A ) .mAdet(A)

Более конкретно, определяют , так что два п × п матриц с коэффициентами , взятых из Z м может быть умножено с помощью O ( п ω ) основные арифметические операции над Z м (целое сложение, умножение, возведение в степень, и т.д.). Потом,ωn×nZmO(nω)Zm

Дана матрица существует детерминированный алгоритм, который вычисляетdet(A)с использованиемO(nω)основных арифметических операций надZm[1].AZmn×ndet(A)O(nω)Zm

Когда это было написано в 1996 году, не было асимптотически более быстрой альтернативы (в статье упоминается о существовании ранее существовавших алгоритмов с той же границей, но я не знаю, какие из них, или являются ли они вероятностными).

Обновление (17 июля 2013 г.): приятная бонусная особенность этого алгоритма заключается в том, что он работает за полиномиальное время для произвольного составного не зная факторизации простого числа m ! Это хорошо, поскольку не существует известных эффективных (классических) алгоритмов факторинга (конечно, если у вас был квантовый компьютер, вы могли бы применить алгоритм Шора ). Если вы делаете есть разложение , то алгоритм Маркус предложил способ кажется проще реализовать.mm

Примечания: в статье сложность «основных арифметических операций» равна если вы используете стандартную целочисленную арифметику, но вы можете достичь O ( MO(log2m) с помощью более быстрых методов. M ( t ) ограничивает стоимость умножения двух t- битных целых чисел. Текущая запись для ω -2.3727.O(M(logm)loglogm)M(t)tω

Хуан Бермехо Вега
источник
не что обычно обозначается ω ? θω
Сашо Николов
Может быть, я не знаю наиболее распространенные обозначения для этого.
Хуан Бермехо Вега
Я думаю, что вы правы, я изменю это, чтобы быть "господствующим направлением"
Хуан Бермехо Вега