ckronx: Efficient Computation with Kronecker Products

Performs a sequence of Kronecker products times a vector

This function performs a similar operation to two previously submitted functions, kronm and kronmult. The algorithm used is described in Algorithm 993: Efficient Computation with Kronecker Products, ACM Transactions on Mathematical Software 45(2):1-9, May 2019. DOI: 10.1145/3291041.

The problem addressed is to compute C=(A1 x A2 x ... x Ad)*B where x represents a Kronecker product. Additionally some or all of the matrices can be transposed. The computations can be done without actually forming the chain of Kronecker products. In addition, unlike the algorithms previously submitted, it can be done with no copying and reshuffling of array in memory.

When the Ai matrices are not square and are of different sizes the order of operations matters. ckronx can perform the computations in a forward or backward sequence and also can check to determine an optimal ordering (in terms of fewest arithmetic operations). The use of an optimal ordering and the avoidance of memory shuffling can result in significant reductions in computational time (see paper for timing comparisons).