0

I have M points in 2-dimensional Euclidean space, and have stored them in an array X of size M x 2.

I have constructed a cost matrix whereby element ij is the distance d(X[i, :], X[j, :]). The distance function I am using is the standard Euclidean distance weighted by an inverse of the matrix D. i.e d(x,y)= < D^{-1}(x-y) , x-y >. I would like to know if there is a more efficient way of doing this, note I have practically avoided for loops.

import numpy as np Dinv = np.linalg.inv(D) def cost(X, Dinv): Msq = len(X) ** 2 mesh = [] for i in range(2): # separate each coordinate axis xmesh = np.meshgrid(X[:, i], X[:, i]) # meshgrid each axis xmesh = xmesh[1] - xmesh[0] # create the difference matrix xmesh = xmesh.reshape(Msq) # reshape into vector mesh.append(xmesh) # save/append into list meshv = np.vstack((mesh[0], mesh[1])).T # recombined coordinate axis # apply D^{-1} Dx = np.einsum("ij,kj->ki", Dinv, meshv) return np.sum(Dx * meshv, axis=1) # dot the elements 
2
  • Arrays of size (N, 2) tends to be inefficient compared to the alternative (2,N) . This is because the former is not SIMD friendly, because Numpy is not optimised for small dimension (this is a pain to optimize so we did not tried to do that yet except in few rare cases) but also because of the inefficient memory layout. Indeed, reading X[:, 0] cause the whole X to be read from the memory while only half the value are needed. X[:, 1] re-read the values again so it could be 2x faster (especially if the array do not fit in cache). Commented Dec 14, 2022 at 18:02
  • Besides this, can you specify which part is a bottleneck or complete the example so it can be reproducible? Commented Dec 14, 2022 at 18:05

1 Answer 1

1

I ll try something like this, mostly optimizing your meshv calculation:

meshv = (X[:,None]-X).reshape(-1,2) ((meshv @ Dinv.T)*meshv).sum(1) 
Sign up to request clarification or add additional context in comments.

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.