1
$\begingroup$

Suppose I have this matrix in Matlab R2013a

M = kron(A,B);

where A and B are $N \times N$ matrices, with $N$ a "big" number. Now, I just want to extract a submatrix of M, composed by taking just few rows from it

Msub = M(rows,:);

where rows is a vector of length $m \ll N$.


Q: Is there an efficient way, in Matlab R2013a, to build Msub without building M before?

$\endgroup$
  • $\begingroup$ To build Msub without first building M suggests that you plan to rewrite code that does the latter to evaluate only certain rows of the matrix. Whether this can be done elegantly (not to say efficiently) depends on the way that the code to construct M works. For example, the construction of M might be recursive on columns, or in some other order not felicitous for extracting only certain rows. $\endgroup$ – hardmath Aug 11 '15 at 13:25
  • $\begingroup$ My matrix is essentially a sum of Kronecker products, so I can assume M = kron(A,B) for simplicity $\endgroup$ – Paglia Aug 11 '15 at 15:37
  • $\begingroup$ Extracting rows from a matrix is going to be very inefficient, since Matlab stores arrays in column-major format. If you were able to instead construct $M^T$ and extract columns, that would be much faster. $\endgroup$ – Tyler Olsen Aug 12 '15 at 23:17
4
$\begingroup$

Here is an idea that might help. It seems that, roughly speaking, the row of a Kronecker product is a Kronecker product of rows. (I hoped to find a nice reference for this online somewhere but I could not; so here is a little sketch.)

In general, for ${A_{R \times S}} \otimes {B_{M \times L}} = {C_{RM \times SL}}$, the formula for an element of $C$ is $$ {c_{m + rM,l + sL}} = {a_{r,s}}{b_{m,l}} $$ (Reference for this definition is Tolimieri et al., Algorithms for Discrete Fourier Transform and Convolution, 2ed, chapter 2.)

Consider ${P_{1 \times S}} \otimes {Q_{1 \times L}} = {Z_{1 \times SL}}$. Since $Z$ only has one row, it follows that $m=0$ and $r=0$. $$ {z_{0,l + sL}} = {a_{0,s}}{b_{0,l}} $$

Let $i=m+rM$. If $P$ is the $r$th row of $A$, i.e. ${p_{0,s}} = {a_{r,s}}$, and similarly $Q$ is the $m$th row of $B$, i.e. ${q_{0,l}} = {b_{m,l}}$, then $$ {z_{0,l + sL}} = {a_{r,s}}{b_{m,l}} $$ which is the $i$th row of $C$.

The corresponding algorithm would be something like this. To compute the $i$th row of $C$,

r = floor(i/M);
m = i - r*M;
kron(A(r,:), B(m,:))

Actually this will not quite work in Matlab, because the math above uses arrays that index from 0, whereas Matlab uses 1-based arrays; unfortunately I don't have Matlab handy to test those implementation details.

Even so, stacking up a few rows computed along these lines might be more efficient for your application than selecting a subset from the full Kronecker product.

$\endgroup$

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.