TITLE: On Vector-Kronecker Multiplication with Rectangular Factors 

AUTHORS: Tugrul Dayar and M. Can Orhan

ABSTRACT: The infinitesimal generator matrix underlying a multi-dimensional 
Markov chain can be represented compactly by using sums of Kronecker 
products of small rectangular matrices. For such compact representations, 
analysis methods based on vector-Kronecker product multiplication need to 
be employed. When the factors in the Kronecker product terms are relatively 
dense, vector-Kronecker product multiplication can be performed efficiently 
by the shuffle algorithm. When the factors are relatively sparse, it may be 
more efficient to obtain nonzero elements of the generator matrix in 
Kronecker form on the fly and multiply them with corresponding elements of 
the vector. This work proposes a modification to the shuffle algorithm that 
multiplies relevant elements of the vector with submatrices of factors in 
which zero rows and columns are omitted. This approach avoids unnecessary 
floating-point operations that evaluate to zero during the course of the 
multiplication and possibly reduces the amount of memory used. Numerical 
experiments on a large number of models indicate that in many cases the 
modified shuffle algorithm performs a smaller number of floating-point 
operations than the shuffle algorithm and the algorithm that generates 
nonzeros on the fly, sometimes with a minimum number of floating-point 
operations and as little of memory possible.

KEY WORDS: Markov chains, Kronecker representation, vector-Kronecker 
product multiplication, shuffle algorithm