在 Julia 中将矩阵提升为幂

Question

我正在用 Julia 编写代码，涉及对一个大的整数矩阵进行高次幂运算，我想让这段代码更有效率。我一直在 JuliaLang 上搜索，但我不确定当我在 Julia 中对矩阵进行幂运算时，Julia 是否会自动使用可用的最快方法（二进制求幂或类似方法）或者它是否会按顺序乘以矩阵，例如A^p = A* A * ... * A. 我可以通过手动实现二进制求幂来加速我的代码，还是 Julia 已经为我做了这件事？

Answer 1

Julia 提供了解决此问题所需的所有内省方法。由于基础库是开源的，并且几乎完全是用 Julia 编写的，因此很容易看到。随便看看：

julia> A = rand(1:10, 4, 4); p = 3;

julia> @less A^p
function (^)(A::AbstractMatrix{T}, p::Integer) where T<:Integer
    # make sure that e.g. [1 1;1 0]^big(3)
    # gets promotes in a similar way as 2^big(3)
    TT = promote_op(^, T, typeof(p))
    return power_by_squaring(convert(AbstractMatrix{TT}, A), p)
end

所以它使用内部 power_by_squaring 函数来完成它的工作：

julia> @less Base.power_by_squaring(A, p)
          "(e.g., [2.0 1.0;1.0 0.0]^$p instead ",
          "of [2 1;1 0]^$p), or write float(x)^$p or Rational.(x)^$p")))
function power_by_squaring(x_, p::Integer)
    x = to_power_type(x_)
    # … skipping the obvious branches to find …
    t = trailing_zeros(p) + 1
    p >>= t
    while (t -= 1) > 0
        x *= x
    end
    y = x
    while p > 0
        t = trailing_zeros(p) + 1
        p >>= t
        while (t -= 1) >= 0
            x *= x
        end
        y *= x
    end
    return y
end

二进制求幂！现在这不会重复使用任何临时对象，因此您可以通过明智地使用就地 mul!.

来做得更好

Answer 2

值得指出的一件事是，如果您的矩阵是方阵，则幂非常大 (>50)，您可能会通过转换为 Jordan Normal Form、提高并转换回来来节省时间。 link 给出了数学方面的基础知识 https://math.stackexchange.com/questions/354277/square-matrix-multiplication-when-raised-to-a-power

在 Julia 中将矩阵提升为幂

Raising a matrix to a power in Julia

matrix

linear-algebra

matrix-multiplication

julia