# Efficient computation of Kronecker product

Given matrices $A \in \mathbb{C}^{n_1,m_1}, B \in \mathbb{C}^{n_2,m_2}$ a naive way to computer the Kronecker product would be as such:

$M = \operatorname{zeros}(n_1n_2,m_1m_2)$ (initialize an empty array)
For $p = 1,2,\ldots n_1n_2:$
For $q = 1,2,\ldots m_1m_2:$
$M_{p,q} = A_{{\lfloor {{p}{n_1}} \rfloor},{\lfloor {{q}{m_1}} \rfloor}} B_{p \bmod n_2,\ q\bmod m_2}$

Which will have running time $O(n_1n_2m_1m_2)$.

I was wondering if there is a more efficient way to computer $M$?

Thanks!

You cannot fill a matrix with $n_1 n_2 m_1 m_2$ entries in time faster than $\Theta(n_1 n_2 m_1 m_2)$. Some considerations:
• Conceptually you can forget about the rectangular shape of a matrix and think about the situation where you have two vectors $\left[x_1,...,x_k\right], \left[y_1,...,y_m\right]$ and want to compute $k \cdot m$ products $x_i y_j$ for each $i,j$.