0

I need to perform a Matrix multiplication of two matrices with dimension 10,000 x 10,000. I am using simple array multiplication, and it takes more than 2 hours to complete the calculation. I need to reduce the times to complete the multiplication.

 Double[,] array1 = new double [10000, 10000];
 Double[,] array2 = new double [10000, 10000];
 Random randNum = new Random();

 for (int i = 0; i < array1.GetLength(0); i++)
 {
     for (int j = 0; j < array1.GetLength(1); j++)
     {
         array1[i, j] = randNum.Next(1, 10);
     }
 }

 for (int i = 0; i < array2.GetLength(0); i++)
 {
     for (int j = 0; j < array2.GetLength(1); j++)
     {
         array2[i, j] = randNum.Next(1, 10);
     }
 }

Double [,] mt = mMat(array1,array2);

public static double[,] mMat(double[,] A, double[,] B)
{

    int aRows = A.GetLength(0);
    int aColumns = A.GetLength(1);
    int bRows = B.GetLength(0);
    int bColumns = B.GetLength(1);

    if (aColumns != bRows)
    {

        throw new ArgumentException("A:Rows: " + aColumns + " did not match B:Columns " + bRows + ".");
    }

    double[,] C = new double[aRows, bColumns];

    for (int i = 0; i < aRows; i++)
    { // aRow
        for (int j = 0; j < bColumns; j++)
        { // bColumn
            for (int k = 0; k < aColumns; k++)
            { // aColumn
                C[i, j] += A[i, k] * B[k, j];
            }
        }
    }

    return C;
}

I am newbie in programming world and need to do task to perform large matrix multiplication

Harith
  • 35
  • 5
  • 2
    Out of the top of my head you'll probably be best served to rewrite it for Multithreading. – Vulpex Mar 04 '21 at 04:57
  • 1
    There are several vector algebra libraries out there, see e.g. https://stackoverflow.com/questions/392857/c-sharp-linear-algebra-library – Klaus Gütter Mar 04 '21 at 04:59
  • 2
    you can check this https://www.geeksforgeeks.org/strassens-matrix-multiplication/ – Vivek Nuna Mar 04 '21 at 05:01
  • 2
    @Vulpex multithreading won't help. Even if you can run in 8 threads then the time will still be ~15 minutes. This is the worst matrix multiplication algorithm which takes O(n³) time. Besides it's extremely cache-unfriendly due to the vertical memory access. The current best algorithm is O(n^2.3728596) will run ~323 times faster than this. And then use something more cache friendly, run in parallel and use SIMD or GPU to accelerate and it'll run thousands of times faster (or more). See [Why is MATLAB so fast in matrix multiplication?](https://stackoverflow.com/q/6058139/995714) – phuclv Mar 04 '21 at 10:37
  • 2
    [how to optimize and speed up the multiplication of matrix](https://stackoverflow.com/q/55245000/995714) – phuclv Mar 04 '21 at 10:39
  • As a very quick try, you can get CudaFy or similar C#-based GPGPU libraries with exact same code, and get 10x-20x speedup on a simple GPU. Some other libraries work even faster but require you to stringify the kernel code for it but its nothing too complex about it. Even with naive multiplication algorithm, having 1000 pipelines still gives a speedup. – huseyin tugrul buyukisik Dec 24 '22 at 09:00

1 Answers1

1

I recently did the same thing for a C# benchmark, and here are a few tips to make it run faster. The C# version runs in about 1 minute and 15 seconds on an 8 core laptop.

  1. Calculate the transpose of B before beginning the matrix multiplication because accessing the matrix in row order is MUCH faster than column order. Scott Meyers did a talk about CPU caches that explains why row order traversal is faster.

  2. Make the outer loop a Parallel.For loop. The link also has some examples that use matrix multiplication.

  3. Use the Vector class to take advantage of SIMD.

  4. Consider using float instead of double unless you really need the extra precision.

Psycho Inferno
  • 31
  • 4