PythonでMin-plus行列の乗算を高速化する方法は？

Question

私はAとBの2つの行列を持っており、ここで与えられたmin-plus積を計算したい：Min-plus matrix multiplication。そのために私は以下を実装しました：

def min_plus_product(A,B): 
    B = np.transpose(B) 
    Y = np.zeros((len(B),len(A))) 
    for i in range(len(B)): 
     Y[i] = (A + B[i]).min(1) 
    return np.transpose(Y) 

これはうまくいきますが、大きなマトリックスでは遅いですが、それを速くする方法はありますか？私は、Cでの実装やGPUの使用が良い選択肢かもしれないと聞いてきました。

Answer 1

中間ディメンションが十分に大きく、エントリが均一に分散されている場合、ビットを節約するアルゴです。これは、最小の合計が典型的に2つの小さな用語からなるという事実を利用する。

import numpy as np 

def min_plus_product(A,B): 
    B = np.transpose(B) 
    Y = np.zeros((len(B),len(A))) 
    for i in range(len(B)): 
     Y[i] = (A + B[i]).min(1) 
    return np.transpose(Y) 


def min_plus_product_opt(A,B, chop=None): 
    if chop is None: 
     # not sure this is optimal 
     chop = int(np.ceil(np.sqrt(A.shape[1]))) 
    B = np.transpose(B) 
    Amin = A.min(1) 
    Y = np.zeros((len(B),len(A))) 
    for i in range(len(B)): 
     o = np.argsort(B[i]) 
     Y[i] = (A[:, o[:chop]] + B[i, o[:chop]]).min(1) 
     if chop < len(o): 
      idx = np.where(Amin + B[i, o[chop]] < Y[i])[0] 
      for j in range(chop, len(o), chop): 
       if len(idx) == 0: 
        break 
       x, y = np.ix_(idx, o[j : j + chop]) 
       slmin = (A[x, y] + B[i, o[j : j + chop]]).min(1) 
       slmin = np.minimum(Y[i, idx], slmin) 
       Y[i, idx] = slmin 
       nidx = np.where(Amin[idx] + B[i, o[j + chop]] < Y[i, idx])[0] 
       idx = idx[nidx] 
    return np.transpose(Y) 

A = np.random.random(size=(1000,1000)) 
B = np.random.random(size=(1000,2000)) 

print(np.allclose(min_plus_product(A,B), min_plus_product_opt(A,B))) 

import time 
t = time.time();min_plus_product(A,B);print('naive {}sec'.format(time.time()-t)) 
t = time.time();min_plus_product_opt(A,B);print('opt {}sec'.format(time.time()-t)) 

サンプル出力：

True 
naive 7.794037580490112sec 
opt 1.65810227394104sec 

Answer 2

可能簡単な経路がnumbaを使用することです。 1000x1000 Aに

from numba import autojit 
import numpy as np 
@autojit(nopython=True) 
def min_plus_product(A,B): 
    n = A.shape[0] 
    C = np.zeros((n,n)) 
    for i in range(n): 
     for j in range(n): 
      minimum = A[i,0]+B[0,j] 
      for k in range(1,n): 
       minimum = min(A[i,k]+B[k,j],minimum) 
      C[i,j] = minimum 
    return C 

タイミング、B行列は、次のとおり

1ループ、3の最良のオリジナルコードのループ当たり4.28秒

1ループ、3の最もよい：ループ当たり2.32秒numbaコード