python - モジュロを使用したでこぼこ行列の累乗/指数?

Question

numpy の linalg.matrix_power をモジュロで使用して、要素が特定の値よりも大きくならないようにすることは可能ですか?

Answer 1

Answer 2

Numpy の実装を使用する:

https://github.com/numpy/numpy/blob/master/numpy/matrixlib/defmatrix.py#L98

モジュロ項を追加して適応させました。ただし、オーバーフローOverflowErrorが発生した場合、例外が発生しないか、その他の種類の例外が発生するというバグがあります。その時点から、解決策は間違っています。ここにバグレポートがあります。

これがコードです。注意して使用してください：

from numpy.core.numeric import concatenate, isscalar, binary_repr, identity, asanyarray, dot
from numpy.core.numerictypes import issubdtype    
def matrix_power(M, n, mod_val):
    # Implementation shadows numpy's matrix_power, but with modulo included
    M = asanyarray(M)
    if len(M.shape) != 2 or M.shape[0] != M.shape[1]:
        raise ValueError("input  must be a square array")
    if not issubdtype(type(n), int):
        raise TypeError("exponent must be an integer")

    from numpy.linalg import inv

    if n==0:
        M = M.copy()
        M[:] = identity(M.shape[0])
        return M
    elif n<0:
        M = inv(M)
        n *= -1

    result = M % mod_val
    if n <= 3:
        for _ in range(n-1):
            result = dot(result, M) % mod_val
        return result

    # binary decompositon to reduce the number of matrix
    # multiplications for n > 3
    beta = binary_repr(n)
    Z, q, t = M, 0, len(beta)
    while beta[t-q-1] == '0':
        Z = dot(Z, Z) % mod_val
        q += 1
    result = Z
    for k in range(q+1, t):
        Z = dot(Z, Z) % mod_val
        if beta[t-k-1] == '1':
            result = dot(result, Z) % mod_val
    return result % mod_val

Answer 3

明白なアプローチの何が問題になっていますか？

例えば

import numpy as np

x = np.arange(100).reshape(10,10)
y = np.linalg.matrix_power(x, 2) % 50