Kronecker Efficient Regular Matrix Identity Matrix - NumPy / Python

Question

I am working on a python project and am using numpy. I often have to compute the Kronecker products of matrices using the identity matrix. This is a pretty big bottleneck in my code, so I would like to optimize them. There are two types of products that I should take. The first one is:

np.kron(np.eye(N), A)

This is fairly easy to optimize simply by using scipy.linalg.block_diag . The product is equivalent to:

la.block_diag(*[A]*N)

This is about 10 times faster. However, I'm not sure how to optimize the second product:

np.kron(A, np.eye(N))

Is it possible to use a similar trick?

Answer 1

- 4D, A. , NumPy.

, :

# Get shape of A
m,n = A.shape

# Initialize output array as 4D
out = np.zeros((m,N,n,N))

# Get range array for indexing into the second and fourth axes 
r = np.arange(N)

# Index into the second and fourth axes and selecting all elements along
# the rest to assign values from A. The values are broadcasted.
out[:,r,:,r] = A

# Finally reshape back to 2D
out.shape = (m*N,n*N)

-

def kron_A_N(A, N):  # Simulates np.kron(A, np.eye(N))
    m,n = A.shape
    out = np.zeros((m,N,n,N),dtype=A.dtype)
    r = np.arange(N)
    out[:,r,:,r] = A
    out.shape = (m*N,n*N)
    return out

np.kron(np.eye(N), A), -

def kron_N_A(A, N):  # Simulates np.kron(np.eye(N), A)
    m,n = A.shape
    out = np.zeros((N,m,N,n),dtype=A.dtype)
    r = np.arange(N)
    out[r,:,r,:] = A
    out.shape = (m*N,n*N)
    return out

-

In [174]: N = 100
     ...: A = np.random.rand(100,100)
     ...: 

In [175]: np.allclose(np.kron(A, np.eye(N)), kron_A_N(A,N))
Out[175]: True

In [176]: %timeit np.kron(A, np.eye(N))
1 loops, best of 3: 458 ms per loop

In [177]: %timeit kron_A_N(A, N)
10 loops, best of 3: 58.4 ms per loop

In [178]: 458/58.4
Out[178]: 7.842465753424658