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)$$