Efficient computation of Kronecker product

Question

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!

Answer 1

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:

• There may be a way to reduce the number of multiplications (FFT?) by using extra additions, but it won't improve the asymptotic complexity;
• This is easy to parallelize;
• You can do this on-the-fly, i.e. store the matrix M as "Kronecker product of A and B" and perform the multiplication only after a request for an element M[p,q].
• 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$.