c++ - C中1的稀疏矩阵的快速矩阵乘法

标签 c++ c arrays matrix matrix-multiplication

我正在尝试执行包含稀疏数量的 1 的乘法矩阵,并将结果转换为另一个 1 的所有值 > =1。例如:

[ 1 1 0 ]   [ 1 0 0 ]    [ 2 0 0 ]    [ 1 0 0 ]
[ 0 0 0 ] x [ 1 0 0 ] => [ 0 0 0 ] => [ 0 0 0 ] (output)
[ 0 0 0 ]   [ 0 0 0 ]    [ 0 0 0 ]    [ 0 0 0 ]

(这些矩阵代表等权有向图,有助于解决一些理论问题。)到目前为止,我发现的最简单的策略是替换标准

output[i][j] += A[i][k] * B[k][j]

按位运算利用了我的输入矩阵中只有 01 并且只需要 1 这一事实s 在输出中,像这样:

void mult(int n, int A[][n], int B[][n], int output[n][n])
{
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            for (int k = 0; k < n; k++)
                output[i][j] = output[i][j] | A[i][k] & B[k][j];
}

但是,这仍然很慢!对于中等大小的密集矩阵 (n>100),快速基准测试表明 MATLAB 的底层 BLAS 子例程比我上面的方法快大约 3 倍!

我该怎么办?在不进行缓存级优化的情况下,我能想到的唯一主要步骤是将这些矩阵表示为仅包含 1 坐标的数组,以利用任何稀疏性,但即使在密集情况下,似乎我可以做些什么来加快速度。

最佳答案

也许你应该去缓存级别优化。其实并不难。您可以使用 C code from ulmBLAS .

在您的情况下,没有必要在汇编程序中实现微内核。根据您的实现修改第 135-143 行应该就足够了。

编辑:此外,按照 nwellnhof 的建议在 int/long 中存储/压缩 32/64 位应该会给您进一步的性能提升。尽管如此,使用阻塞(缓存友好)算法仍然是高效矩阵矩阵乘积的必要条件。

关于c++ - C中1的稀疏矩阵的快速矩阵乘法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28391014/

相关文章:

c++ - 读取包含矩阵 C++ 的文本文件

c++ - OpenGL Loader Generator 对 gl::BindBuffer 等的 undefined reference (OpenGL 函数)

c - 尝试再次打开时未出现 Gtk 对话框

c - 如何检查 void* 指针是否可以安全地转换为其他内容?

arrays - 面试题 : Replacing two arrays's place in memory

arrays - 给定一个按行排序的 bool 矩阵。返回最大数量为 1 的行

c++ - 为什么我只能使用 auto 类型创建函数别名?

c++ - 带有工厂设计尝试的段错误 unique_ptr

c - 编译器如何存储 C 字符串?

c - 返回函数中声明的数组返回C中局部变量的地址?