Матрица Мура похожа на матрицу Вандермонда, но имеет слегка измененное определение. http://en.wikipedia.org/wiki/Moore_matrix
Какова сложность вычисления определителя заданной матрицы Мура полного ранга по модулю некоторого целого числа?
Можно ли уменьшить определитель Мура с с использованием методов БПФ до для некоторого ?
Является ли сложность Moore det по модулю целым числом, а Vandermonde - то же самое? Сложность определителя Вандермонда равна (Страница 644 в Справочнике по теоретической информатике: алгоритмы и сложность Яна Леувена)
Пост похож на текущий: определитель по модулю м
Ответы:
В общем, существует теоретический алгоритм времени для нахождения LU-разложения произвольной матрицы с использованием алгоритма Копперсмита-Винограда , который затем, очевидно, дает определитель (добавляя время O ( n ) ). Однако существует проблема, заключающаяся в том, что алгоритм Копперсмита – Винограда на практике не считается пригодным для использования. На самом деле, люди в основном используют алгоритм Штрассена времени O ( n 2,807 ) . Разве Boost UBLAS не использует lu_factorize ?O ( n2,376) O ( n ) O ( n2,807)
В вашем случае матрица Мура должна допускать значительную оптимизацию, потому что в принципе любая процедура, подобная гауссовскому исключению, такая как разложение LU, может быть сделана абстрактно. В самом деле, вы найдете хорошую формулу для вычисления детерминанта Мура, на который ссылается википедия , что, по-видимому, доказывается простой разработкой декомпозиции LU в целом.O ( n )
источник
Важно, чтобы в приведенном вами определении матрица находилась в конечном поле, скажем, где m простое число. Это позволяет использовать теорему Эйлера для вычисления двойных экспонент a q eZm m которые появляются в матрице за время O ( log ( m n )aqemodm .
a q i ≡ a q iO(log(mn)M(logm))
В противном случае кажется сложным даже вычислить матричные коэффициенты без факторизации m .
Если простое или может быть эффективно разложено, в наихудшей сложности преобладает количество шагов, необходимых для умножения матрицы O ( n ω ) . Например, подход нормальной формы Смита, о котором я упоминал в сообщении партнера , вычислит определитель за время O ( n ωm O(nω) если вы используете «медленные» алгоритмы умножения ∗ . ω можно выбрать равным 2,337.O(nωlog2mlog(mn)) ∗ ω
Вы получаете замедление в Муре против Вандермонде, так как вы должны дважды возвести в степень коэффициенты матрицы. Когда вы можете учесть это замедление просто полилогарифмическое на m . Если нет, то представленный алгоритм дает снижение Кука до двойного модульного экспонирования на Z m .m m Zm
Примечание *: более быстрые алгоритмы умножения целых чисел позволяют заменить на M ( log m log log m ) .log2m M(logmloglogm)
Обновление : о возможности достижения .O(nlogan)
У меня нет однозначного ответа на этот вопрос, но я нашел некоторую информацию, которая может усилить ваш поиск.
Алгоритмы для структурированных матриц, которые вычисляют такие величины, как определители во времени , в литературе называются «сверхбыстрыми». Все известные «сверхбыстрые» алгоритмы для структурированных матриц (Vandermonde, Toeplitz, Hankel), похоже, полагаются на общее свойство этих матриц, известное как низкий «ранг смещения». Примите участие в обсуждении в первой главе этой книги (страницы открытого доступа) или в этой статье [ACM] , [PDF] .O(nlogan)
Из того, что я прочитал, учитывая матрицу Мура M , если вы смогли найти матрицы A , B такие, что новая матрица L ( M ) = A M - M B (или, альтернативно, L ( M ) = M - A М б ) имеет следующую структуруm×n M A B L(M)=AM−MB L(M)=M−AMB
и ранг мал (либо постоянен, либо ограничен o ( minr>0 ), тогда вы можете применить существующие методы (см. главу 5 книги, страницы открытого доступа), чтобы треугольнизировать M и, следовательно, вычислить det M , используя O ( n log 2 n ) . Выше g k , h k обозначают векторы. Если вы не можете найти книгу выше, чтобы прочитать все это, вэтой статьетакже много информации об этих методах.o(min{m,n}) M detM O(nlog2n) gk hk
К сожалению, я не смог найти структуру с низким рангом смещения для матрицы Мура (Вандермонд имеет). Основное осложнение здесь, по-видимому, связано с «нелинейной» природой двойной экспоненты. Если это поможет, в книге разрабатываются дела для Вандермонде, Коши, Теплица, Ханкеля.
источник