Определитель обобщенной матрицы Вандермонда

10

Матрица Мура похожа на матрицу Вандермонда, но имеет слегка измененное определение. http://en.wikipedia.org/wiki/Moore_matrix

Какова сложность вычисления определителя заданной n×n матрицы Мура полного ранга по модулю некоторого целого числа?

Можно ли уменьшить определитель Мура с O(n3) с использованием методов БПФ до O(nlogan) для некоторого aR+{0} ?

Является ли сложность Moore det по модулю целым числом, а Vandermonde - то же самое? Сложность определителя Вандермонда равна O(nlog2n) (Страница 644 в Справочнике по теоретической информатике: алгоритмы и сложность Яна Леувена)

Пост похож на текущий: определитель по модулю м

Т ....
источник
Может ли определитель Мура даже быть вычислен за O (n ^ 3) времени (в целочисленной ОЗУ)?
Джефф
1
@ Jɛ и далее Е Именно поэтому я говорил по модулю случайных NN .
T ....
Кстати, и мне просто любопытно, есть ли известные приложения, которые выиграли бы от такого «сверхбыстрого» алгоритма?
Хуан Бермехо Вега
@J ФКП, вы случайно не знаете , если вычисления двойной модульного возведения в степень над N в БПП для тривиального N ?. Потому что это проблема для вычисления коэффициентов матрицы. εNN
Хуан Бермехо Вега

Ответы:

4

В общем, существует теоретический алгоритм времени для нахождения LU-разложения произвольной матрицы с использованием алгоритма Копперсмита-Винограда , который затем, очевидно, дает определитель (добавляя время O ( n ) ). Однако существует проблема, заключающаяся в том, что алгоритм Копперсмита – Винограда на практике не считается пригодным для использования. На самом деле, люди в основном используют алгоритм Штрассена времени O ( n 2,807 ) . Разве Boost UBLAS не использует lu_factorize ?O(n2.376)O(n)O(n2.807)

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

Джефф Берджес
источник
Привет, Джефф: Какую ссылку ты ссылаешься на формулу O (n ^ 2)? Я думаю, что Vandermonde det можно рассчитать в O (nlogn), но я не могу найти ссылку. Так должен ли Мур быть также в O (nlogn)?
T ....
Да, я должен был сказать O (n), очевидно, действительно O (n log n) для больших n.
Джефф Берджес
Привет, Джефф: У тебя есть ссылка?
T ....
7
@JeffBurdges: Если время выполнения O (n log n) «для больших n», то по определению время выполнения O (n log n), а не O (n).
Джеффс
Я не вижу формулу ссылается Википедия. В лучшем случае это выглядит Θ ( n 2 ) . O(n)Θ(n2)
Питер Тейлор
3

Важно, чтобы в приведенном вами определении матрица находилась в конечном поле, скажем, где m простое число. Это позволяет использовать теорему Эйлера для вычисления двойных экспонент a q eZmm которые появляются в матрице за время O ( log ( m n )aqemodm . a q ia q iO(log(mn)M(logm)) В противном случае кажется сложным даже вычислить матричные коэффициенты без факторизации m .

aqiaqi(modφ(m))(modm)
m

Если простое или может быть эффективно разложено, в наихудшей сложности преобладает количество шагов, необходимых для умножения матрицы O ( n ω ) . Например, подход нормальной формы Смита, о котором я упоминал в сообщении партнера , вычислит определитель за время O ( n ωmO(nω) если вы используете «медленные» алгоритмы умножения . ω можно выбрать равным 2,337.O(nωlog2mlog(mn))ω

Вы получаете замедление в Муре против Вандермонде, так как вы должны дважды возвести в степень коэффициенты матрицы. Когда вы можете учесть это замедление просто полилогарифмическое на m . Если нет, то представленный алгоритм дает снижение Кука до двойного модульного экспонирования на Z m .mmZm

Примечание *: более быстрые алгоритмы умножения целых чисел позволяют заменить на M ( log m log log m ) .log2mM(logmloglogm)


Обновление : о возможности достижения .O(nlogan)

У меня нет однозначного ответа на этот вопрос, но я нашел некоторую информацию, которая может усилить ваш поиск.

Алгоритмы для структурированных матриц, которые вычисляют такие величины, как определители во времени , в литературе называются «сверхбыстрыми». Все известные «сверхбыстрые» алгоритмы для структурированных матриц (Vandermonde, Toeplitz, Hankel), похоже, полагаются на общее свойство этих матриц, известное как низкий «ранг смещения». Примите участие в обсуждении в первой главе этой книги (страницы открытого доступа) или в этой статье [ACM] , [PDF] .O(nlogan)

Из того, что я прочитал, учитывая матрицу Мура M , если вы смогли найти матрицы A , B такие, что новая матрица L ( M ) = A M - M B (или, альтернативно, L ( M ) = M - A М б ) имеет следующую структуруm×nMABL(M)=AMMBL(M)=MAMB

L(M)=k=1rgkhkT

и ранг мал (либо постоянен, либо ограничен o ( minr>0 ), тогда вы можете применить существующие методы (см. главу 5 книги, страницы открытого доступа), чтобы треугольнизировать M и, следовательно, вычислить det M , используя O ( n log 2 n ) . Выше g k , h k обозначают векторы. Если вы не можете найти книгу выше, чтобы прочитать все это, вэтой статьетакже много информации об этих методах.o(min{m,n})MdetMO(nlog2n)gkhk

К сожалению, я не смог найти структуру с низким рангом смещения для матрицы Мура (Вандермонд имеет). Основное осложнение здесь, по-видимому, связано с «нелинейной» природой двойной экспоненты. Если это поможет, в книге разрабатываются дела для Вандермонде, Коши, Теплица, Ханкеля.

Хуан Бермехо Вега
источник
3m3kk
3k
Хорошо, что это не упрощает сложность, я бы сказал, так как поле очень очень большое.
T ....
φ(3k)=3k3k1aqimodmb=qimodφ(3k)abmod3kO(log(n3k)M(klog3))M(n)=n2O(nωk2log23(logn+klog3))
ω1+ϵω2