如何使python中的最小加矩阵乘法更快? [英] How to make Min-plus matrix multiplication in python faster?

问题描述

因此，我有两个矩阵A和B，我想按以下公式计算最小加乘积:最小加矩阵乘法.为此，我实现了以下内容:

So I have two matrices, A and B, and I want to compute the min-plus product as given here: Min-plus matrix multiplication. For that I've implemented the following:

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可能是不错的选择.

This works fine, but is slow for big matrices, is there a way to make it faster? I've heard that implemeting in C or using the GPU might be good options.

推荐答案

这里是一种算法，如果中间维度足够大并且条目均匀分布，则可以节省一些时间.它利用了一个事实，即最小的总和通常来自两个小项.

Here is an algo that saves a bit if the middle dimension is large enough and entries are uniformly distributed. It exploits the fact that the smallest sum typically will be from two small terms.

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

这篇关于如何使python中的最小加矩阵乘法更快?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！