c# - C# 中更快的矩阵乘法

Question

我有一个涉及矩阵的小型 C# 项目。我正在处理大量数据，方法是将其拆分为长度为 n 的 block ，将卡盘视为向量，然后乘以 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 矩阵的错误)

Answer 1

也许您可以使用 Reflection.Emit 在运行时定义一个矩阵接口(interface)并构建实现.

IMatrix m = MatrixGenerator.CreateMatrix(data);

m.multiplyBy(...)

在这里，MatrixGenerator.CreateMatrix 将创建一个定制的 IMatrix 实现，具有完整的循环展开和进一步的代码修剪(0 单元、身份等)。 MatrixGenerator.CreateMatrix 可以缓存矩阵以避免稍后为同一组数据重新创建它。