3
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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$.
$\endgroup$
  • $\begingroup$ Yes, I'm unsure why I thought you could! The extra considerations were helpful though, thankyou $\endgroup$ – HBeel Mar 1 '15 at 20:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.