Сложность вычислительных матриц

14

Я заинтересован в вычислении N «ю мощность матрицы . Предположим, у нас есть алгоритм умножения матриц, который выполняется за время . Тогда можно легко вычислить за время. Можно ли решить эту проблему за меньшее время?N×NAО(M(N))ANO(M(n)log(n))

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

Примечание: я понимаю, что в общем случае вычисление за даст алгоритм для возведения в степень. Но ряд интересных проблем сводится к частному случаю возведения в степень матрицы, где m = , и я не смог доказать то же самое об этой более простой задаче.Amo(M(n)log(m))o(logm)O(n)

Shitikanth
источник
Какие записи матрицы? Целые?
Каве
1
Как правило, записи могут быть из полукольца, но вы можете принять дополнительную структуру, если это поможет.
Шитикант,
Я не мог получить сокращение от умножения до возведения в квадрат от предложенного выше метода (то есть, используя ). Однако использование ( 0 A B 0 ) 2 работает. Однако это дает только Ω ( M ( n ) ) при вычислении A n . (A±B)2(0AB0)2Ω(M(n))An
Шитикант

Ответы:

11

Если матрица диагонализируемы затем принимает - й мощности может быть сделано в время O ( D ( п ) + п входе п ) , где D ( п ) время , чтобы диагонализовать A .n

O(D(n)+nlogn)
D(n)A

Просто, чтобы завершить детали, если с диагональю D , то A n = ( P - 1 D P ) n = P - 1 D n PA=P1DPD

An=(P1DP)n=P1DnP

и можно вычислить, просто взяв каждый элемент диагонали (каждое собственное значение A ) в n- ую степень.DnAn

Ран Г.
источник
6
Даже если матрица диагонализуема, лучшие известные алгоритмы собственного разложения занимают времени. Используя алгоритм Копперсмита-Винограда, у нас уже есть алгоритм O ( n 2,3727 log ( m ) ) для вычисления A m . O(n3)O(n2.3727log(m))Am
Шитикант
1
(1) Время, которое вы цитируете, не принадлежит Копперсмит-Винограду (как вы, вероятно, знаете). (2) Все алгоритмы этой формы работают только для колец; они не работают для общих полуколец (как вы позволяете в своем вопросе).
Райан Уильямс
5

n×nAA=UΣUTΣO(n3)Am=UΣmUTO(nlogm)U×Σm×UTO(n2.3727)O(n3+nlogm)

Обновление после комментария Дело в том, что как только SVD найден, любой мощности требуется только для вычисления по вашему собственному алгоритму CW. Но это не ваш вопрос. Если бы на самом деле существовал алгоритм o ( M ( n ) log ( m ) ) , он немедленно конвертировался бы в алгоритм o ( log n ) для целых чисел. Я подозреваю, что одного такого не существует.O(n2.3727+nlogm)o(M(n)log(m))o(logn)

PKG
источник
Поскольку алгоритм Копперсмита – Винограда находит произведение двух матриц за время , у нас уже есть алгоритм O ( n 2,3727 log ( m ) ) для вычисления A m . Мне интересно знать, можно ли это улучшить, не требуя лучшего алгоритма умножения матриц, особенно для m = O ( n ) . O(n2.3727)O(n2.3727log(m))Amm=O(n)
Шитикант,
1
A=UΣUVU
1
nmn=1O(M(1)logmAm
2
logm
1
Это было неясно из вашего вопроса, как указано.
PKG