Checking triangle inequality in a massive numpy matrix

user_4492932 0
Viewed 850

I have a symmetric NumPy matrix D of non-negative floating point numbers. A number in the ith row and jth column represents the distance between objects i and j, whatever they are. The matrix is large (~10,000 rows/columns). I would like to check if all the distances in the matrix obey the triangle inequality, that is: D[i,j]<=D[i,k]+D[k,j] for all i, j, k.

The problem can be solved, quite inefficiently, by using a triple-nested loop. But is there a faster, vectorized solution?

distance numpy algorithm python
1 Answers

You can certainly vectorise the innermost loop easily enough with (untested):

for i in range(N):
    for j in range(i):
        assert all(D[i,j] <= D[i,:] + D[:,j])

For double vectorisation you can loop through k (also untested):

for k in range(N):
    row = D[k,:].reshape(1, N)
    col = D[:,k].reshape(N, 1)
    assert (D <= row + col).all()

(row + col generates a square matrix the same size as D)

user_94509910
Related