Существует ли более быстрый метод экспоненциальности матрицы для вычисления M ^ n (где M - матрица, а n - целое), чем простой алгоритм деления и покорения.
Быстрая трансформация матрицы
Ответ 1
Вы можете разложить матрицу на собственные значения и собственные векторы. Затем вы получите
M = V^-1 * D * V
Где V - матрица собственного вектора, а D - диагональная матрица. Чтобы поднять это до N-й степени, вы получите что-то вроде:
M^n = (V^-1 * D * V) * (V^-1 * D * V) * ... * (V^-1 * D * V)
= V^-1 * D^n * V
Поскольку все члены V и V ^ -1 отменяются.
Так как D диагонально, вам просто нужно собрать кучу (реальных) чисел в n-ю степень, а не полные матрицы. Вы можете сделать это в логарифмическом времени в n.
Вычисление собственных значений и собственных векторов равно r ^ 3 (где r - количество строк/столбцов M). В зависимости от относительных размеров r и n это может быть быстрее или нет.
Ответ 2
Это довольно простое использование алгоритма быстрой мощности Euler. Используйте следующий алгоритм.
#define SIZE 10
//It simple E matrix
// 1 0 ... 0
// 0 1 ... 0
// ....
// 0 0 ... 1
void one(long a[SIZE][SIZE])
{
for (int i = 0; i < SIZE; i++)
for (int j = 0; j < SIZE; j++)
a[i][j] = (i == j);
}
//Multiply matrix a to matrix b and print result into a
void mul(long a[SIZE][SIZE], long b[SIZE][SIZE])
{
long res[SIZE][SIZE] = {{0}};
for (int i = 0; i < SIZE; i++)
for (int j = 0; j < SIZE; j++)
for (int k = 0; k < SIZE; k++)
{
res[i][j] += a[i][k] * b[k][j];
}
for (int i = 0; i < SIZE; i++)
for (int j = 0; j < SIZE; j++)
a[i][j] = res[i][j];
}
//Caluclate a^n and print result into matrix res
void pow(long a[SIZE][SIZE], long n, long res[SIZE][SIZE])
{
one(res);
while (n > 0) {
if (n % 2 == 0)
{
mul(a, a);
n /= 2;
}
else {
mul(res, a);
n--;
}
}
}
Ниже приведены эквиваленты номеров:
long power(long num, long pow)
{
if (pow == 0) return 1;
if (pow % 2 == 0)
return power(num*num, pow / 2);
else
return power(num, pow - 1) * num;
}
Ответ 3
Экспоненциальное возведение в квадрат часто используется для получения высоких степеней матриц.
Ответ 4
Я бы рекомендовал подход, используемый для вычисления последовательности Фибоначчи в матричной форме. AFAIK, его эффективность равна O (log (n)).