(Python) How to get diagonal(A*B) without having to perform A*B?

Question

Let's say we have two matrices A and B and let matrix C be A*B (matrix multiplication not element-wise). We wish to get only the diagonal entries of C, which can be done via np.diagonal(C). However, this causes unnecessary time overhead, because we are multiplying A with B even though we only need the the multiplications of each row in A with the column of B that has the same 'id', that is row 1 of A with column 1 of B, row 2 of A with column 2 of B and so on: the multiplications that form the diagonal of C. Is there a way to efficiently achieve that using Numpy? I want to avoid using loops to control which row is multiplied with which column, instead, I wish for a built-in numpy method that does this kind of operation to optimize performance.

Thanks in advance..

Answer 1

I might use einsum here:

>>> a = np.random.randint(0, 10, (3,3))
>>> b = np.random.randint(0, 10, (3,3))
>>> a
array([[9, 2, 8],
       [5, 4, 0],
       [8, 0, 6]])
>>> b
array([[5, 5, 0],
       [3, 5, 5],
       [9, 4, 3]])
>>> a.dot(b)
array([[123,  87,  34],
       [ 37,  45,  20],
       [ 94,  64,  18]])
>>> np.diagonal(a.dot(b))
array([123,  45,  18])
>>> np.einsum('ij,ji->i', a,b)
array([123,  45,  18])

For larger arrays, it'll be much faster than doing the multiplication directly:

>>> a = np.random.randint(0, 10, (1000,1000))
>>> b = np.random.randint(0, 10, (1000,1000))
>>> %timeit np.diagonal(a.dot(b))
1 loops, best of 3: 7.04 s per loop
>>> %timeit np.einsum('ij,ji->i', a, b)
100 loops, best of 3: 7.49 ms per loop

[Note: originally I'd done the elementwise version, ii,ii->i, instead of matrix multiplication. The same einsum tricks work.]