[SciPy-user] Creating a Matrix from a Sum

Tom K. tpk@kraussfamily....
Fri Jul 3 20:18:40 CDT 2009

David Warde-Farley-2 wrote:
> On 3-Jul-09, at 2:45 PM, David Warde-Farley wrote:
>> On 2-Jul-09, at 9:25 AM, Lorenzo Isella wrote:
> Then you want the max of i and j at each position in the matrix. For  
> this, though there may be a more efficient way, you can use mgrid to  
> get i and j indices at each position in the matrix and then use  
> concatenate and max on them to concatenate along a third axis and then  
> do a max along that same axis to recover a 2D array:
> 	idx = np.concatenate([M[:,:,np.newaxis] for M in mgrid[0:len(x),  
> 0:len(x)]],axis=2).max(axis=2)

David this is interesting however I think the use of mgrid followed by
concatenation into a 3D array here is overkill.  The idx array is the same
as the max_ij array that I suggested - a one liner for it is 
  max_ij = np.maximum(np.arange(len(x))[:,np.newaxis], np.arange(len(x)))

This problem involves O(N) sums and O(N^2) assignments.   The vectorized
versions that David and I posted (my version 2) are doing just that much
work - however with overhead of several intermediate arrays.  A more
straight-forward approach in python is just a double for-loop, which may be
the most readable and perfectly sufficient unless your N is huge and/or this
function becomes the most significant item in a profile of your application. 

sums = np.cumsum(x[::-1])[::-1]
P = np.zeros((len(x), len(x))
for i in range(len(x)):
  for j in  range(len(x)):
    P[i, j] = sums[np.max((i, j))]

#Here it is with list comprehensions:
  P = np.array([[sums[np.max((i, j))] for j in range(len(x))] for i in

By the way I do NOT recommend using the first method I posted in my earlier
post - I think it is doing O(N^3) adds and O(N^3) assigns!
View this message in context: http://www.nabble.com/Creating-a-Matrix-from-a-Sum-tp24306698p24330442.html
Sent from the Scipy-User mailing list archive at Nabble.com.

More information about the SciPy-user mailing list