C#中更快的矩阵乘法

Question

我有一个小的C#项目涉及到矩阵。我通过将大量数据分成n长度块，将这些块当作向量处理，并乘以一个Vandermonde**矩阵来处理数据。问题是，根据条件，块的大小和相应的Vandermonde**矩阵的大小会发生变化。我有一个通用的解决方案，易于阅读，但速度太慢：

    public byte[] addBlockRedundancy(byte[] data) {
        if (data.Length!=numGood) D.error("Expecting data to be just "+numGood+" bytes long");

        aMatrix d=aMatrix.newColumnMatrix(this.mod, data);
        var r=vandermonde.multiplyBy(d);
        return r.ToByteArray();
    }//method

在我的i5 U470 @ 1.33GHz上，此代码可以处理大约每秒1/4兆字节。我可以通过手动将矩阵乘法内联来加快速度：

        int o=0;
        int d=0;
        for (d=0; d<data.Length-numGood; d+=numGood) {
            for (int r=0; r<numGood+numRedundant; r++) {
                Byte value=0;
                for (int c=0; c<numGood; c++) {
                    value=mod.Add(value, mod.Multiply(vandermonde.get(r, c), data[d+c]));
                }//for
                output[r][o]=value;
            }//for
            o++;
        }//for

这个程序每秒可以处理大约1兆字节。

请注意，“mod”是在GF（2^8）模下执行操作。

我知道这个程序可以更快：毕竟，Vandermonde矩阵大多数都是零。我应该能够编写或找到一种程序，可以将我的矩阵转换为一个优化的方法，以更快地有效地通过给定的矩阵乘以向量。然后，当我将一个5x5 Vandermonde矩阵（即单位矩阵）提供给此程序时，不需要执行任何算术运算，原始数据只需复制即可。

请注意：当我使用术语“Vandermonde”时，实际上是指附加了一些来自Vandermonde矩阵的行的单位矩阵（请参见注释）。由于该矩阵有许多零，并且如果您删除足够的行（自己选择）使其成为正方形，则它是可逆矩阵。当然，我希望使用相同的程序将这些反演矩阵之一转换为优化的指令系列。

如何使这个矩阵乘法更快？

谢谢！

（编辑以纠正我对Vandermonde矩阵的错误）

- Kyle Lahnakoski

---

恒等矩阵或任何具有零的矩阵都不是范德蒙矩阵，根据http://en.wikipedia.org/wiki/Vandermonde_matrix或http://mathworld.wolfram.com/VandermondeMatrix.html（或GVL）的定义。但是你说你的矩阵有零。你能澄清一下你的定义吗？ - Pete Kirkham

我的错误。我要找的矩阵不是范德蒙矩阵，而是一个恒等矩阵，其中附加了范德蒙行作为额外行。请参见http://www.cs.tau.ac.il/~ohadrode/slides/ReedSolomon.pdf第11页。 - Kyle Lahnakoski

Answer 1

也许你可以定义一个矩阵接口，并使用 Reflection.Emit 在运行时构建实现。

IMatrix m = MatrixGenerator.CreateMatrix(data);

m.multiplyBy(...)

在这里，MatrixGenerator.CreateMatrix将创建一个定制的IMatrix实现，具有完全展开的循环和进一步的代码修剪（0单元格，身份等）。MatrixGenerator.CreateMatrix可能会缓存矩阵，以避免为相同的数据集重新创建它。

- Nicolas Repiquet

Answer 2

我见过使用Reflection.Emit的解决方案，也见过涉及TPL的解决方案。对于大多数情况来说，真正的答案是你希望使用现有的未托管库，如通过P/Invoke使用英特尔MKL。或者，如果你正在使用GPU，可以采用GPGPU方法，这样速度会更快。

是的，SSE和多核处理一起在CPU上执行是最快的方法。但我不建议编写自己的算法——相反，去寻找已经存在的东西。很可能，它最终会成为一个C++库，可能带有C#包装器。

- Dmitri Nesteruk

---

+.NET不使用SSE，但是托管C++可以包装本地C++库，然后使用非托管方法/代码执行SSE操作。这是除了使用GPU之外最快的方法，对于单个转换来说，GPU不会更有效率（您需要一些时间上传数据/下载结果-这适用于高度并行的事情）。 - TomTom

我对SSE或GPU的担忧是，我正在使用GF（2 ^ 8）域来执行这些操作。我怀疑它们是否支持这种类型的数学运算。 - Kyle Lahnakoski

Answer 3

虽然它不能加速数学计算，但至少你可以使用 .Net 4.0 中的 Parallel.For 来利用所有核心。 Microsoft 链接

- Joel Lucsy

Answer 4

从数学角度来看

您可以研究特征空间、特征向量和特征值。我不确定您的应用程序是什么，以及它是否有所帮助。

您可以研究LU分解。

所有上述主题都可以在维基百科上找到。

从编程角度来看

您可以尝试使用SIMD，但它们是为4x4矩阵设计的，用于进行三维空间的同构变换，主要用于计算机图形。

您可以为最常见的维度编写特殊算法。

在C#中使用SSE是否可行？

- EnabrenTane

---

不幸的是，用于3D图形的4x4矩阵太小了，无法在我需要的GF(2^8)域上操作。 - Kyle Lahnakoski