Efficient Way to Permutate a Symmetric Square Matrix in Numpy

Question

What's the best way to do the following in Numpy when dealing with symmetric square matrices (NxN) where N > 20000?

>>> a = np.arange(9).reshape([3,3])
>>> a = np.maximum(a, a.T)
>>> a
array([[0, 3, 6],
       [3, 4, 7],
       [6, 7, 8]])
>>> perm = np.random.permutation(3)
>>> perm
array([1, 0, 2])
>>> shuffled_arr = a[perm, :][:, perm]
>>> shuffled_arr
array([[4, 3, 7],
       [3, 0, 6],
       [7, 6, 8]])

This takes about 6-7 secs when N is about 19K. While the same opertation in Matlab takes less than a second:

perm = randperm(N);
shuffled_arr = arr(perm, perm);

I'd do `arr[np.ix_(perm, perm)]`, though I don't know whether it'd be any faster. — user2357112, Oct 06 '16 at 23:05
@user2357112 good to know that! It only reduces the processing time about 1 sec though (still 5-6 sec). — NULL, Oct 06 '16 at 23:15
You could also try `arr[perm, perm[:, None]]`, but I don't know if will be much faster. — Warren Weckesser, Oct 06 '16 at 23:29
Ignore that suggestion. It takes more than twice as long as `arr[np.ix_(perm, perm)]` for an array with shape (10000, 10000). — Warren Weckesser, Oct 06 '16 at 23:34
See http://stackoverflow.com/questions/11800075/faster-numpy-fancy-indexing-and-reduction/11813040#11813040. In your case, `np.take(np.take(a,perm,0),perm,1)`. — user545424, Oct 07 '16 at 00:21

hpaulj · Accepted Answer · 2016-10-07T04:16:53.373

In [703]: N=10000
In [704]: a=np.arange(N*N).reshape(N,N);a=np.maximum(a, a.T)
In [705]: perm=np.random.permutation(N)

One indexing step is quite a bit faster:

In [706]: timeit a[perm[:,None],perm]   # same as `np.ix_...`
1 loop, best of 3: 1.88 s per loop

In [707]: timeit a[perm,:][:,perm]
1 loop, best of 3: 8.88 s per loop

In [708]: timeit np.take(np.take(a,perm,0),perm,1)
1 loop, best of 3: 1.41 s per loop

a[perm,perm[:,None]] is in the 8s category.

Efficient Way to Permutate a Symmetric Square Matrix in Numpy

1 Answers1