10

I have as small c# project that involves matrices. I am processing large amounts of data by splitting it into n-length chunks, treating the chucks as vectors, and multiplying by a Vandermonde** matrix. The problem is, depending on the conditions, the size of the chucks and corresponding Vandermonde** matrix can vary. I have a general solution which is easy to read, but way too slow:

    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

This can process about 1/4 megabytes per second on my i5 U470 @ 1.33GHz. I can make this faster by manually inlining the matrix multiplication:

        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

This can process about 1 meg a second.

(Please note the "mod" is performing operations over GF(2^8) modulo my favorite irreducible polynomial.)

I know this can get a lot faster: After all, the Vandermonde** matrix is mostly zeros. I should be able to make a routine, or find a routine, that can take my matrix and return a optimized method which will effectively multiply vectors by the given matrix, but faster. Then, when I give this routine a 5x5 Vandermonde matrix (the identity matrix), there is simply no arithmetic to perform, and the original data is just copied.

** Please note: What I use the term "Vandermonde", I actually mean an Identity matrix with some number of rows from the Vandermonde matrix appended (see comments). This matrix is wonderful because of all the zeros, and because if you remove enough rows (of your choosing) to make it square, it is an invertible matrix. And, of course, I would like to use this same routine to convert any one of those inverted matrices into an optimized series of instructions.

How can I make this matrix multiplication faster?

Thanks!

(edited to correct my mistake with Vandermonde matrix)

2

4 Answers 4

3

Maybe you can define a matrix interface and build implementations at runtime using Reflection.Emit.

IMatrix m = MatrixGenerator.CreateMatrix(data);

m.multiplyBy(...)

Here, MatrixGenerator.CreateMatrix will create a tailored IMatrix implementation, with full loop unrolling, and further code pruning (0 cell, identity, etc). MatrixGenerator.CreateMatrix may cache matrices to avoid recreating it later for the same set of data.

3

I've seen solutions using Reflection.Emit, and I've seen solutions which involve TPL. The real answer here is, for most situations, that you want to use an existing unmanaged library such as Intel MKL via P/Invoke. Alternatively, if you are using the GPU, you can go with the GPGPU approach which would go a lot faster.

And yes, SSE together with multi-core processing is the fastest way to do it on a CPU. But I wouldn't recommend writing your own algorithm - instead, go look for something that's already out there. Most likely, it will end up being a C++ library, possibly with a C# wrapper.

2
  • 1
    +1. .NET does not make use of SSE, but managed C++ can wrap a native C++ library and then use unmanaged methods / code to execute SSE operations. This is as fast as it gets short of using the GPU, which will not be more efficient for individual transformations (you use some time uploading the data / downloading the results - this is for HEAVILY parallel things).
    – TomTom
    Dec 29, 2010 at 16:40
  • My concern with SSE, or with GPU, is the GF(2^8) field I am using to perform these operations. I doubt they support this type of math. Dec 29, 2010 at 19:10
2

While it won't speed up the math, you could at least use all your cores with the Parallel.For in .Net 4.0. Microsoft link

0

From the math perspective

You could look at Eigen Spaces, Eigen Vectors, Eigen Values. I'm not sure what your application does and if it will help.

You could look at LU Decomposition.

All of the above topics can be found at wikipedia

From a programming perspective

You could try SIMD, but they are designed for 4x4 matrices to do homogeneous transformations of 3D space, mostly for computer graphics.

You could write special algorithms for your most common dimensions.

Using SSE in c# is it possible?

1
  • Unfortunately, the 4x4 matrices used in 3D graphics are too small, and do not operate on the GF(2^8) field that I need. Dec 29, 2010 at 19:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.