计算矩阵的 n 次方

Question

我正在尝试优化我的代码以计算矩阵的 n 次方。

之前我只会调用 multiplySquare n 次，但那太慢了。问题是，它构建得很好，但是当我运行它时，我遇到了退出值 1 的失败。我相信我的算法是正确的，那么是什么原因造成的呢？

[编辑] 添加了递归终止条件，但我仍然得到同样的错误。

[再次编辑] 我再次重写了递归部分，现在它似乎可以工作，但仅适用于 n 的某些输入。我将不得不更多地使用它。任何帮助，将不胜感激。

void multiplySquare(long long A[2][2], long long B[2][2]){

    long long result[2][2];
    for (int i = 0; i < 2; i++){
        for (int j = 0; j < 2; j++){
            result[i][j] = 0;
            for (int k = 0; k < 2; k++){
                result[i][j] += A[i][k] * B[k][j];
            }
        }
    }

    for (int i=0; i<2; i++){
        for (int j=0; j<2; j++){
            A[i][j] = result[i][j]; 
        }
    }
}

void power(long long A[2][2], long long B[2][2], long long n){
    if(n/2 != 0){   
        power(A, B, n/2);
    }
    if(n%2 != 0){
        multiplySquare(A, B);
    }
}

Answer 1

有效计算数字 x 的 N 次方的算法是：

如果 N 为零，return 1。
如果 N 为 1，则 return x.
计算 (N/2) 次方。 y = x^(N/2)
如果 N 是偶数，则 return y*y
如果 N 是奇数，则 return x*y*y

如果您将该逻辑转化为您的案例，您将需要以下内容：

// Assuming that the result is returned in B.
void power(long long A[2][2], long long B[2][2], long long n)
{
   if ( n == 0 )
   {
      makeIdentity(B);
      return;
   }

   if ( n == 1 )
   {
      assign(A, B);  // Make B same as A.
      return;
   }

   power(A, B, n/2);

   multiplySquare(B, B);
   if(n % 2 != 0)
   {
      multiplySquare(B, A);
   }
}

Answer 2

I'm trying to optimize my code to calculate the nth power of a matrix.

由于您的目标是优化，因此考虑对角矩阵具有微不足道的 n-th 幂可能是一件好事，即主对角线元素的 n-th 幂。

所以，首先你应该对角化你的矩阵。一种方法是找到初始矩阵 A 的特征向量和特征值，并利用以下关系：

A = P D P^-1

其中 P 是包含 A 的（列）特征向量的矩阵，P^-1 是它的逆矩阵，D 是包含特征值的对角矩阵。

则：Aⁿ = P Dⁿ P^-1

上式：

将 A 带到一个提升 n-th 次方微不足道的地方。
计算 n-th 幂。
Returns一回原处

Answer 3

看来你的代码片段不是你想要的。我猜想你的意思是这样的：

void power(long long A[2][2], long long B[2][2], long long n){
    if (n == 1) {
        multiplySquare(A, B);
    }
    else if(n % 2 == 0) {
        power(A, B, n / 2);
        multiplySquare(A, A);
    }
    else {
        power(A, B, (n - 1) / 2);
        multiplySquare(A, A);
        multiplySquare(A, B);
    }

计算矩阵的 n 次方

Calculate nth power of a matrix

c++

math

matrix

linear-algebra

exponential