Я заинтересован в вычислении «ю мощность матрицы . Предположим, у нас есть алгоритм умножения матриц, который выполняется за время . Тогда можно легко вычислить за время. Можно ли решить эту проблему за меньшее время?
Матричные записи, как правило, могут быть из полукольца, но вы можете принять дополнительную структуру, если это поможет.
Примечание: я понимаю, что в общем случае вычисление за даст алгоритм для возведения в степень. Но ряд интересных проблем сводится к частному случаю возведения в степень матрицы, где m = , и я не смог доказать то же самое об этой более простой задаче.
Ответы:
Если матрица диагонализируемы затем принимает - й мощности может быть сделано в время O ( D ( п ) + п входе п ) , где D ( п ) время , чтобы диагонализовать A .n
Просто, чтобы завершить детали, если с диагональю D , то A n = ( P - 1 D P ) n = P - 1 D n PA=P−1DP D
и можно вычислить, просто взяв каждый элемент диагонали (каждое собственное значение A ) в n- ую степень.Dn A n
источник
Обновление после комментария Дело в том, что как только SVD найден, любой мощности требуется только для вычисления по вашему собственному алгоритму CW. Но это не ваш вопрос. Если бы на самом деле существовал алгоритм o ( M ( n ) log ( m ) ) , он немедленно конвертировался бы в алгоритм o ( log n ) для целых чисел. Я подозреваю, что одного такого не существует.O(n2.3727+nlogm) o(M(n)log(m)) o(logn)
источник