Is there a way to compute $(A\otimes B)x$ quickly without forming the Kronecker product?

Question

Is there a way to compute $(A\otimes B)x$ quickly without forming the Kronecker product? Often, I'd like to compute the matrix-vector product of a Kronecker product, but I'm not sure of a good way to efficiently produce the product directly. In case it's any easier, I'm also interested in the computing $(A\otimes A)x$.

Thanks for the help!

Answer 1

A basic property of Kronecker products is $$(A\otimes B)\,{\rm vec}(X) = {\rm vec}(BXA^T)$$ where the RHS does not contain any Kronecker products, although it does require a vectorization (and de-vectorization) operation.

Similarly $$(A\otimes A)\,{\rm vec}(X) = {\rm vec}(AXA^T)$$

Answer 2

This is a specific case of vector-Kronecker product multiplication with two matrices in the Kronecker product. It is possible to compute $$ (A_1 \otimes \ldots \otimes A_d) x $$ without explicitly computing Kronecker product and vectorization. Details of algorithms to compute vector-Kronecker product multiplication can be found in Vector Multiplication with Multiple Kronecker Products