Adam Florence
Research
Block Kronecker Product Systems

 Let A be an m n2-by-m n2 matrix. Divide it into m-by-m blocks, where each block is n2-by-n2. We will consider the case when each block is a Kronecker product
Aij = Bij kron Cij
for i, j = 1 to m. We wish to solve a linear system on A.

When m = 1, linear systems can be solved quickly, in O(n3) flops. When m > 1, fast direct algorithms are impossible. However, due to the Kronecker structure, matrix-vector products on A can be computed quickly, in only 4 m2 n3 flops. Thus, it seems reasonable to try an iterative method. The success of iterative methods depends on the quality of the preconditioners used.

We considered the case when A is SPD. We have developed a preconditioners which cluster the eigenvalues of the preconditioned matrix into the interval (0, 1]. Conjugate Gradients using our preconditioners can solve systems on A in O(m2 n3) flops, which is of the same order as matrix-vector products on A.

Our algorithm is explained in [1]. The Matlab code is given below. It is also available as a zip file.

There is no warranty of any kind on this code or its documentation. All code is copyrighted (c) 2000, 2001 by Adam Florence.

If you have any questions about the code, please e-mail me.

Bibliography
  1. FLORENCE, ADAM G. Computational Multilinear Algebra, Ph.D. thesis, Cornell University, 2001.
Back to my home page.

Last updated 13 August 2001.