用整数计算矩阵的幂

Question

假设我有一个常数矩阵A，我想计算pow(A, n)。 如此问题所述，我可以计算其特征值分解（或更一般地，其不变子空间和广义模态矩阵）以加速该过程。

如果A是大小为k的方阵，则通过平方幂运算，该算法的复杂度为O(k log n)，预处理成本（计算模态矩阵）为O(k ^ 3)。

我正在考虑的问题是精度丧失。 计算特征值等将我们从整数域带入浮点数。 即使最终，我们知道pow（A，n）必须具有所有整数条目，上述算法仅计算浮点数。

另一种方法是仅利用平方幂，但这只给我们一个O(k^3log n)算法。

是否有一种准确 - 不转换为浮点数 - 可以快速计算pow（A，n）的方法？

- WorldSEnder

---

最好的情况是这会导致一个人可以在纸上完成的算法，但这是高度可选的。 - WorldSEnder

即使您使用（固定大小的）整数，由于溢出而导致信息丢失仍然是一个问题。因此，通常需要使用任意精度整数。您也可以使用任意精度有理数来计算特征值，从而避免了固定精度浮点数的精度损失。 - Chris Dodd

@ChrisDodd 考虑矩阵 [1 1] 在 [1 0] 上的运算。它的特征值为 (1+sqrt(5))/2 和 (1 - sqrt(5))/2。任意精度有理数也无法拯救你。 - btilly

Answer 1

特征值分解对于有限域上的矩阵也是可能的，但前提是该域合适。因此，进行特征值分解不仅需要预处理，还需要找到（一些）可行的有限域。

寻找多个解可以避免在巨大的有限域中工作，然后在一些小域中计算pow(A, n)，并使用CRT来计算ℤ中的解。但这需要有足够数量和足够大小的域来使用，并且您事先无法知道什么大小足够（总有某个n超过它的工作停止），因此，实际上可能无法使用这种方法。

以一个小例子为例：

A = [[1, 1],
     [1, 0]]

特征方程为 x² - x - 1，假设对于模数1009有效（实际有效），那么它有根383和627，因此：

A = QDP mod 1009
Q = [[  1,   1],
     [382, 626]]
D = [[383,   0],
     [  0, 627]]
P = [[ 77, 153],
     [933, 856]]

所以举个例子。

pow(A, 15) = Q [[928,   0], P = [[987, 610],
                [  0, 436]]      [610, 377]]

斐波那契数列如预期的那样，一切都顺利。但是，当取模为1009时，指数超过15会导致结果与ℤ中不匹配，这需要更多/更大的域。

- harold

---

我是否正确理解了这个想法，即如果您找到两个（或更多）这样的字段，您可以通过中国剩余定理计算出Z中的结果？ - WorldSEnder

只有当字段大小的乘积足够大时，@WorldSEnder 才能使用，这是令人烦恼的部分。 - harold

Answer 2

使用Cayley-Hamilton定理可以加快计算速度。该定理指出，每个维度为k的矩阵幂都可以写成A的前k个幂的和。

如果我们知道这一点，就可以使用平方幂来代替矩阵运算，在整数系数下计算A上的多项式。在每一步骤后，我们可以通过特征多项式将多项式化简。

以下是一个小例子：

A = [[1, 1],
     [1, 0]]
A^2 = A + 1 = writing poly. coefficients = {1, 1}

pow(A, 15) = {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
           = {1, 0} * ({1, 0} * ({1, 0} * {1, 0}^2)^2)^2
           = {1, 0} * ({1, 0} * ({1, 0} * {1, 0, 0})^2)^2
           = {1, 0} * ({1, 0} * ({1, 0} * {1, 1})^2)^2
           = {1, 0} * ({1, 0} * ({1, 1, 0})^2)^2
           = {1, 0} * ({1, 0} * {2, 1}^2)^2
           = {1, 0} * ({1, 0} * {4, 4, 1})^2
           = {1, 0} * ({1, 0} * {8, 5})^2
           = {1, 0} * ({8, 5, 0})^2
           = {1, 0} * {13, 8}^2
           = {1, 0} * {169, 208, 64}
           = {1, 0} * {377, 233}
           = {377, 233, 0}
           = {610, 377}
           = [[987, 610],
              [610, 377]]

那么，运行时成本是什么？简单来说，O(k^2 * log n)，因为在每个平方步骤中，我们需要计算两个多项式的平方并通过字符多项式进行约减。使用与其他答案中的@harold类似的技巧，通过使用离散傅里叶多项式乘法，我们可以找到原根，从而得到O(k log k log n)。

- WorldSEnder