Каковы известные эффективные алгоритмы вычисления определителя целочисленной матрицы с коэффициентами в , кольца вычетов по модулю m . Число m может быть не простым, а составным (поэтому вычисления выполняются в кольце, а не в поле).
Насколько я знаю (читайте ниже), большинство алгоритмов являются модификациями исключения Гаусса. Вопрос в вычислительной эффективности этих процедур.
Если так получилось, что есть какой-то другой подход, мне тоже интересно.
Заранее спасибо.
Обновить:
Позвольте мне объяснить источник этого вопроса. Предположим, что простое число. Так что Z m это поле. И в этом случае мы можем выполнить все вычисления, используя числа, меньшие m , поэтому у нас есть хорошая верхняя граница для всех операций над числами: сложение, умножение и инверсия - все необходимые операции для запуска исключения по Гауссу.
С другой стороны, мы не можем выполнить инверсию для некоторых чисел, если не простое число. Поэтому нам нужны некоторые хитрости для вычисления определителя.
И теперь мне любопытно, каковы известные уловки, чтобы сделать работу и можно ли найти такие уловки и бумаги книг.
источник
Ответы:
Если вам известна факторизация вы можете вычислить по модулю каждый p e i i отдельно, а затем объединить результаты с использованием китайского остатка. Если е я = 1 , то вычисления по модулю р е I я легко, так как это поле. Для большего e i , вы можете использовать подъем Hensel.m=pe11⋯penn peii ei=1 peii ei
источник
Существует комбинаторный алгоритм Махаджана и Виная, который работает над коммутативными кольцами: http://cjtcs.cs.uchicago.edu/articles/1997/5/contents.html
источник
Для решения этой проблемы существует быстрый детерминированный алгоритм, основанный на нормальных формах Смита , сложность которого в худшем случае ограничена сверху стоимостью умножения матриц по целым числам по модулю . Для любой матрицы A алгоритм выводит свою нормальную форму Смита, откуда легко вычислить det ( A ) .m A det(A)
Более конкретно, определяют , так что два п × п матриц с коэффициентами , взятых из Z м может быть умножено с помощью O ( п ω ) основные арифметические операции над Z м (целое сложение, умножение, возведение в степень, и т.д.). Потом,ω n×n Zm O(nω) Zm
Когда это было написано в 1996 году, не было асимптотически более быстрой альтернативы (в статье упоминается о существовании ранее существовавших алгоритмов с той же границей, но я не знаю, какие из них, или являются ли они вероятностными).
Обновление (17 июля 2013 г.): приятная бонусная особенность этого алгоритма заключается в том, что он работает за полиномиальное время для произвольного составного не зная факторизации простого числа m ! Это хорошо, поскольку не существует известных эффективных (классических) алгоритмов факторинга (конечно, если у вас был квантовый компьютер, вы могли бы применить алгоритм Шора ). Если вы делаете есть разложение , то алгоритм Маркус предложил способ кажется проще реализовать.m m
Примечания: в статье сложность «основных арифметических операций» равна если вы используете стандартную целочисленную арифметику, но вы можете достичь O ( MO(log2m) с помощью более быстрых методов. M ( t ) ограничивает стоимость умножения двух t- битных целых чисел. Текущая запись для ω -2.3727.O(M(logm)loglogm) M(t) t ω
источник