Как вычислить степени квадратных матриц?

16

Предположим, нам дана матрица , и пусть . Как быстро мы можем вычислить мощность этой матрицы?ARN×NmN0Am

Следующая лучшая вещь по сравнению с вычислением продуктов - это использование быстрой экспоненты, для которой требуются матричные продукты .mO(logm)

Для диагонализуемых матриц можно использовать разложение по собственным значениям. Это естественное обобщение, разложение Джордана, неустойчиво при пертурбации и поэтому не учитывается (afaik).

Можно ли ускорить возведение матрицы в общем случае?

Быстрое возведение в степень предполагает, что вариант этого вопроса тоже полезен:

Можно ли вычислить квадрат общей матрицы быстрее, чем с помощью известных алгоритмов умножения матриц?A

shuhalo
источник
Если вы заботитесь о стабильности при возмущениях, быстрое возведение в степень также не кажется безопасным.
MCH
Ну, я полагаю, это не менее безопасно, чем повторное умножение, которое так же безопасно, как скалярное возведение в степень, не так ли?
shuhalo

Ответы:

20

Как вы заметили, вычисление может быть выполнено за O ( log m ), умноженное на количество операций для умножения матриц на N × N матриц. Ответ на ваш второй вопрос - нет, по крайней мере, для асимптотической сложности - матричный квадрат и умножение матриц имеют эквивалентную временную / арифметическую сложность (с точностью до постоянных множителей). Сокращение возведения в квадрат до умножения матриц очевидно. Чтобы уменьшить умножение на возведение в квадрат, предположим , что мы хотим вычислить произведение A и B . Форма 2 n × 2 n матрицы C с блочной структурой:AmO(logm)N×NAB2n×2nС

[0  A]

[B  0]

То есть имеет матрицу из всех нулей n × n в своем верхнем левом квадранте и нижнем правом квадранте. Обратите внимание, что C 2 содержит A B в своем верхнем левом квадранте.Cn×nC2AB

Райан Уильямс
источник
Недавно я задал вопрос на cs.SE о сложности вычисления в особом случае, когда m = O ( n ) . Легко дать верхнюю оценку O ( M ( n ) log ( n ) ) , но лучшая нижняя граница, которую я могу дать, это Ω ( M ( n ) ) . Есть ли у вас какие-либо комментарии по этой проблеме? Я думаю, что много интересных проблем сводятся к этому частному случаю. AmO(n)O(M(n)log(n))Ω(M(n))
Шитикант,