二元矩阵向量乘法 [英] Binary matrix vector multiplication

问题描述

我要乘以8×8的二进制的矩阵重新$ P $由一个无符号字符psented一个8位向量重新presented作为一个无符号的64位整数。然而，由于其他一些问题矩阵的必须按列排序，ERGO还有方便乘字节不容易匹配。

I want to multiply a 8x8 binary matrix represented as a unsigned 64 bit integer by a 8 bit vector represented by a unsigned char. However, due to some other issues the matrix must be ordered by columns, ergo there's no easy matching of bytes for easy multiplication.

任何想法如何加快这样的计算？每个操作计数，因为我需要数十亿美元做了这样的计算。

Any idea how to speed up such a calculation? Every operation counts for I need billions of such calculations made.

的乘法超过2元领域取得了（F-2）。

The multiplications are made over a 2 element field (F-2).

推荐答案

通过这个矩阵与向量重新presentation，它有助于做矩阵乘法是这样的：

With this matrix and vector representation, it helps to do matrix multiplication this way:

（COL ₁ ...山坳 ₈ ）*（V ₁ ... v ₈ ） ^T =山坳 ₁ * v ₁ + ... +山坳 ₈ * v ₈

(col₁ ... col₈) * (v₁ ... v₈)^T = col₁ * v₁ + ... + col₈ * v₈

其中矩阵A =（COL ₁ ...山坳 ₈ ）

where matrix A = (col₁ ... col₈)

和列向量V =（V ₁ ... v ₈ ） ^T

and column vector v = (v₁ ... v₈)^T

这进一步思考，你可以一次做乘法，如果你通过8次重复的每一位，然后计算 P = A和夸大的8位向量到64位向量; v_inflated 。然后剩下的唯一一件事，就是产品的增加（即XOR）。

Thinking this further, you can do all multiplications at once if you inflate the 8-bit vector to a 64-bit vector by repeating every bit 8 times and then calculating P = A & v_inflated. The only thing left then, is the addition (i.e. XOR) of the products.

有关异或产品一个简单的方法是。

A simple approach for XORing the products is.

uint64_t P = calculated products from text above;
uint64_t sum = 0;
for( int i = 8; i; --i )
{
   sum ^= P & 0xFF;
   P >> 8;  
}

这篇关于二元矩阵向量乘法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！