title: How to get better performance with Strassen Algorithm than the naive approach without a cut off point?
body: <p>I'm trying to test the naive and Strassen method for matrix multiplication.</p>
  <p>However, the Strassen algorithm works way slower than the naive approach. For a 1024 sized matrix, the naive approach completes in 3542ms while Strassen in 83602ms. (with Strassen not using cut off/naive approach)
  Here is the Strassen code that I'm using. LEAF SIZE is the number where it switches to the naive approach:</p>
  <pre class="lang-java prettyprint-override"><code>int n = A.length;
  
  if (n &lt;= LEAF_SIZE) {
      return ikjAlgorithm(A, B);
  } else {
      // initializing the new sub-matrices
      int newSize = n / 2;
      int[][] a11 = new int[newSize][newSize];
      int[][] a12 = new int[newSize][newSize];
      int[][] a21 = new int[newSize][newSize];
      int[][] a22 = new int[newSize][newSize];
  
      int[][] b11 = new int[newSize][newSize];
      int[][] b12 = new int[newSize][newSize];
      int[][] b21 = new int[newSize][newSize];
      int[][] b22 = new int[newSize][newSize];
  
      int[][] aResult = new int[newSize][newSize];
      int[][] bResult = new int[newSize][newSize];
  
      // dividing the matrices in 4 sub-matrices:
      for (int i = 0; i &lt; newSize; i++) {
          for (int j = 0; j &lt; newSize; j++) {
              a11[i][j] = A[i][j]; // top left
              a12[i][j] = A[i][j + newSize]; // top right
              a21[i][j] = A[i + newSize][j]; // bottom left
              a22[i][j] = A[i + newSize][j + newSize]; // bottom right
  
              b11[i][j] = B[i][j]; // top left
              b12[i][j] = B[i][j + newSize]; // top right
              b21[i][j] = B[i + newSize][j]; // bottom left
              b22[i][j] = B[i + newSize][j + newSize]; // bottom right
          }
      }
  
      // Calculating p1 to p7:
      aResult = add(a11, a22);
      bResult = add(b11, b22);
      int[][] p1 = strassenR(aResult, bResult);
      // p1 = (a11+a22) * (b11+b22)
  
      aResult = add(a21, a22); // a21 + a22
      int[][] p2 = strassenR(aResult, b11); // p2 = (a21+a22) * (b11)
  
      bResult = subtract(b12, b22); // b12 - b22
      int[][] p3 = strassenR(a11, bResult);
      // p3 = (a11) * (b12 - b22)
  
      bResult = subtract(b21, b11); // b21 - b11
      int[][] p4 = strassenR(a22, bResult);
      // p4 = (a22) * (b21 - b11)
  
      aResult = add(a11, a12); // a11 + a12
      int[][] p5 = strassenR(aResult, b22);
      // p5 = (a11+a12) * (b22)
  
      aResult = subtract(a21, a11); // a21 - a11
      bResult = add(b11, b12); // b11 + b12
      int[][] p6 = strassenR(aResult, bResult);
      // p6 = (a21-a11) * (b11+b12)
  
      aResult = subtract(a12, a22); // a12 - a22
      bResult = add(b21, b22); // b21 + b22
      int[][] p7 = strassenR(aResult, bResult);
      // p7 = (a12-a22) * (b21+b22)
  
      // calculating c21, c21, c11 e c22:
      int[][] c12 = add(p3, p5); // c12 = p3 + p5
      int[][] c21 = add(p2, p4); // c21 = p2 + p4
  
      aResult = add(p1, p4); // p1 + p4
      bResult = add(aResult, p7); // p1 + p4 + p7
      int[][] c11 = subtract(bResult, p5);
      // c11 = p1 + p4 - p5 + p7
  
      aResult = add(p1, p3); // p1 + p3
      bResult = add(aResult, p6); // p1 + p3 + p6
      int[][] c22 = subtract(bResult, p2);
      // c22 = p1 + p3 - p2 + p6
  
      // Grouping the results obtained in a single matrix:
      int[][] C = new int[n][n];
      for (int i = 0; i &lt; newSize; i++) {
          for (int j = 0; j &lt; newSize; j++) {
              C[i][j] = c11[i][j];
              C[i][j + newSize] = c12[i][j];
              C[i + newSize][j] = c21[i][j];
              C[i + newSize][j + newSize] = c22[i][j];
          }
      }
      return C;
  }
  </code></pre>
  <pre class="lang-java prettyprint-override"><code>private static int[][] add(int[][] A, int[][] B) {
      int n = A.length;
      int[][] C = new int[n][n];
      for (int i = 0; i &lt; n; i++) {
          for (int j = 0; j &lt; n; j++) {
              C[i][j] = A[i][j] + B[i][j];
          }
      }
      return C;
  }
  
  private static int[][] subtract(int[][] A, int[][] B) {
      int n = A.length;
      int[][] C = new int[n][n];
      for (int i = 0; i &lt; n; i++) {
          for (int j = 0; j &lt; n; j++) {
              C[i][j] = A[i][j] - B[i][j];
          }
      }
      return C;
  }
  </code></pre>
  <p>With the leaf size at around 32, it does indeed perform faster(that is the cut-off point where the naive algorithm kicks in)</p>
  <p>This is in Java language. The code is from the internet, however more or less all of the implementations are similar.</p>
  <p>Is it not possible to beat naive with just Strassen without a cut off point?
  Any ideas would be appreciated. Thank you.</p>
  <p><em><strong>EDIT</strong></em> Added add and subtract methods.</p>
  <p><em><strong>EDIT2</strong></em> From the code is the biggest overhead from the creating of new submatrices? If so, what method could be applied to remove as much overhead as possible? If nothing can be done in java I'm not against using c++.</p>
  <p><strong>EDIT3</strong> Could anyone suggest a method on how to reduce the memory allocation that used here? Would be grateful for the suggestions.</p>