Answers.Body: <p>From the NumPy Linear algebra <a href="https://numpy.org/doc/stable/reference/routines.linalg.html" rel="nofollow noreferrer">documentation</a>:</p>
  <blockquote>
  <p>The NumPy linear algebra functions rely on <a href="https://en.wikipedia.org/wiki/Basic_Linear_Algebra_Subprograms" rel="nofollow noreferrer">BLAS</a> and <a href="https://en.wikipedia.org/wiki/LAPACK" rel="nofollow noreferrer">LAPACK</a> to provide
  efficient low level implementations of standard linear algebra
  algorithms. Those libraries may be provided by NumPy itself using C
  versions of a subset of their reference implementations but, when
  possible, highly optimized libraries that take advantage of
  specialized processor functionality are preferred.</p>
  </blockquote>
  <p>In your case, <code>np.dot()</code> is a matrix-vector multiplication which internally calls  such a highly optimized BLAS routine. Those libraries are implemented in low-level languages like Fortan or C, they exist for many years now and are still unbeaten in terms of speed.<br />
  Your <em>naive</em> implementation of the convolution operation in python on the other hand is not optimized for execution speed and will be executed by the python interpreter (which is much slower than the compiled C functions).</p>
  <p>You could try to replace your manual convolution by the SciPy's equivalent <a href="https://docs.scipy.org/doc/scipy/reference/generated/scipy.signal.convolve2d.html" rel="nofollow noreferrer"><code>scipy.signal.convolve2d()</code></a>, to make advantage of optimized libraries as well and get a speed up.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-09-06T20:36:44.023Z
Answers.LastActivityDate: 2020-09-06T20:36:44.023Z
Answers.UserDisplayName: Tinu
Body: <p>Let's take a 32 x 32 x 3 NumPy array and convolve with 10 filters of size 2 x 2 x 3 with stride 2 to produce feature maps of volume 16 x 16 x 10. The total number of operations - 16 * 16 * 10 * 2 * 2 * 2 * 3 = 61440 operations. Now, let's take an input array of length 3072 (flattening the 32 * 32 * 3 array) and dot it with a weight matrix of size 500 x 3072. The total number of operations - 500 * 3072 * 2 = 3072000 operations. The convolution takes 4-5 times longer than <code>np.dot(w, x)</code> even though number of operations is less.</p>
  <p>Here's my code for the convolution operation:</p>
  <pre><code>for i in range(16):
      for j in range(16):
          for k in range(10):
              v[i, j, k] = np.sum(x[2 * i:2 * i + 2, 2 * j:2 * j + 2] * kernels[k]) 
  </code></pre>
  <p>Is <code>np.dot(w, x)</code> optimized or something? Or are my calculations wrong? Sorry if this is a silly question...</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-09-06T20:43:56.533Z
Comments.Text: Programming questions are generally off-topic here. Please, ask this type of question on Stack Overflow. Here we focus on theoretical, philosophical and social aspects of AI. Please, read also our on-topic page https://ai.stackexchange.com/help/on-topic to know more about it.
Comments.UserDisplayName: nbro
Tags: <convolutional-neural-networks><time-complexity>
Title: Why does CNN forward pass take longer compared to MLP forward pass?
UserDisplayName: Karthik
ThreadText: # Why does CNN forward pass take longer compared to MLP forward pass?
  
  (Asked by: username_0 on 2020-09-06)
  
  Let's take a 32 x 32 x 3 NumPy array and convolve with 10 filters of size 2 x 2 x 3 with stride 2 to produce feature maps of volume 16 x 16 x 10. The total number of operations - 16 \* 16 \* 10 \* 2 \* 2 \* 2 \* 3 = 61440 operations. Now, let's take an input array of length 3072 (flattening the 32 \* 32 \* 3 array) and dot it with a weight matrix of size 500 x 3072. The total number of operations - 500 \* 3072 \* 2 = 3072000 operations. The convolution takes 4-5 times longer than `np.dot(w, x)` even though number of operations is less.
  
  Here's my code for the convolution operation:
  
  ```
  for i in range(16):
      for j in range(16):
          for k in range(10):
              v[i, j, k] = np.sum(x[2 * i:2 * i + 2, 2 * j:2 * j + 2] * kernels[k]) 
  
  ```
  
  Is `np.dot(w, x)` optimized or something? Or are my calculations wrong? Sorry if this is a silly question...
  
  **Tags:** convolutional-neural-networks, time-complexity
  
  > **Comments:**
  > **username_1**: Programming questions are generally off-topic here. Please, ask this type of question on Stack Overflow. Here we focus on theoretical, philosophical and social aspects of AI. Please, read also our on-topic page https://ai.stackexchange.com/help/on-topic to know more about it.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2020-09-06. Score: 0
  
  From the NumPy Linear algebra [documentation](https://numpy.org/doc/stable/reference/routines.linalg.html):
  
  > The NumPy linear algebra functions rely on [BLAS](https://en.wikipedia.org/wiki/Basic_Linear_Algebra_Subprograms) and [LAPACK](https://en.wikipedia.org/wiki/LAPACK) to provide
  > efficient low level implementations of standard linear algebra
  > algorithms. Those libraries may be provided by NumPy itself using C
  > versions of a subset of their reference implementations but, when
  > possible, highly optimized libraries that take advantage of
  > specialized processor functionality are preferred.
  
  In your case, `np.dot()` is a matrix-vector multiplication which internally calls such a highly optimized BLAS routine. Those libraries are implemented in low-level languages like Fortan or C, they exist for many years now and are still unbeaten in terms of speed.  
  Your *naive* implementation of the convolution operation in python on the other hand is not optimized for execution speed and will be executed by the python interpreter (which is much slower than the compiled C functions).
  
  You could try to replace your manual convolution by the SciPy's equivalent [`scipy.signal.convolve2d()`](https://docs.scipy.org/doc/scipy/reference/generated/scipy.signal.convolve2d.html), to make advantage of optimized libraries as well and get a speed up.
  
  
  ---
  
  