title: CPU Time for matrix matrix multiplication
body: <p>I am trying to decide wether several similar but independent problems should be dealt with simultaneously or sequentially (possibly in parallel on different computers). In order to decide, I need to compare the cpu times of the following operations : </p>
  
  <ul>
  <li><p>time_1 is the time for computing X(with shape (n,p)) @ b (with shape (p,1)).</p></li>
  <li><p>time_k is the time for computing X(with shape (n,p)) @ B (with shape (p,k)).</p></li>
  </ul>
  
  <p>where X, b and B are random matrices. The difference between the two operations is the width of the second matrix. </p>
  
  <p>Naively, we expect that time_k = k x time_1. With faster matrix multiplication algorithms (Strassen algorithm, Coppersmith–Winograd algorithm), time_k could be smaller than k x time_1 but the complexity of these algorithms remains much larger than what I observed in practice. Therefore my question is :
  How to explain the large difference in terms of cpu times for these two computations ? </p>
  
  <p><a href="https://i.stack.imgur.com/gFqtp.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/gFqtp.png" alt="Comparison of the CPU times in terms of the width k"></a></p>
  
  <p>The code I used is the following : </p>
  
  <pre><code>import time
  import numpy as np
  import matplotlib.pyplot as plt
  
  p     = 100
  width = np.concatenate([np.arange(1, 20), np.arange(20, 100, 10), np.arange(100, 4000, 100)]).astype(int)
  
  mean_time = []
  for nk, kk in enumerate(width):
      timings = []
      nb_tests = 10000 if kk &lt;= 300 else 100
      for ni, ii in enumerate(range(nb_tests)):
          print('\r[', nk, '/', len(width), ', ',  ni, '/', nb_tests, ']', end = '')
          x     = np.random.randn(p).reshape((1, -1))
          coef  = np.random.randn(p, kk)
          d     = np.zeros((1, kk))
          start = time.time()
          d[:]  = x @ coef
          end   = time.time()
          timings.append(end - start)
  
      mean_time.append(np.mean(timings))
  
  mean_time = np.array(mean_time)
  
  
  fig, ax = plt.subplots(figsize =(14,8))
  plt.plot(width, mean_time, label =  'mean(time\_k)')
  plt.plot(width, width*mean_time[0], label = 'k*mean(time\_1)')
  plt.legend()
  plt.xlabel('k')
  plt.ylabel('time (sec)')
  plt.show()
  </code></pre>