title: How can I vectorize and speed up this large array calculation?
body: <p>I'm currently trying to <em>calculate the sum of all sum of subsquares in a 10.000 x 10.000 array of values</em>. As an example, if my array was :</p>
  
  <pre><code>1 1 1 
  2 2 2
  3 3 3 
  </code></pre>
  
  <p>I want the result to be :</p>
  
  <pre><code>1+1+1+2+2+2+3+3+3                        [sum of squares of size 1]
  +(1+1+2+2)+(1+1+2+2)+(2+2+3+3)+(2+2+3+3) [sum of squares of size 2]
  +(1+1+1+2+2+2+3+3+3)                     [sum of squares of size 3]
  ________________________________________
  68
  </code></pre>
  
  <p>So, as a first try i wrote a very simple python code to do that. As it was in O(k^2.n^2) (n being the size of the big array and k the size of the subsquares we are getting), the processing was awfully long. I wrote another algorithm in O(n^2) to speed it up :</p>
  
  <pre><code>def getSum(tab,size):
      n = len(tab)
      tmp = numpy.zeros((n,n))
  
      for i in xrange(0,n):
          sum = 0
          for j in xrange(0,size):
              sum += tab[j][i]
          tmp[0][i] = sum
  
          for j in xrange(1,n-size+1):
              sum += (tab[j+size-1][i] - tab[j-1][i])
              tmp[j][i] = sum
  
      finalsum = 0
      for i in xrange(0,n-size+1):
          sum = 0 
          for j in xrange(0,size):
              sum += tmp[i][j]
          finalsum += sum
  
          for j in xrange(1,n-size+1):
              finalsum += (tmp[i][j+size-1] - tmp[i][j-1])
  
  return finalsum
  </code></pre>
  
  <p>So this code works fine. Given an array and a size of subsquares, it will return the sum of the values in all this subsquares. I basically iterate over the size of subsquares to get all the possible values.</p>
  
  <p>The problem is this is again waaay to long for big arrays (over 20 days for a 10.000 x 10.000 array). I googled it and learned I could vectorize the iterations over arrays with numpy. However, i couldn't figure out how to make it so in my case...</p>
  
  <p><strong>If someone can help me to speed my algorithm up, or give me good documentation on the subject, i'll be glad !</strong></p>
  
  <p>Thank you !</p>