# Efficient storage of Kronecker sum of circulant matrices+diagonal matrix

I have a square matrix of the form $$M=D+\overset{N}{\underset{n=1}\bigoplus}R_n,$$

where $R_n$ are circulant matrices, $D$ is a diagonal matrix and $\oplus$ is Kronecker sum. Its size is quite big, but as can be seen from its form, it's in fact not very dense in a way. Namely, its elements can be generated by a simple procedure not needing much memory - the only things needing storage are a vector for diagonal of $D$, and a set of smaller vectors for first rows of $R_n$ (i.e. totally two vectors matching dimensions of $M$).

Actually, diagonal matrix is simple to get with SparseArray, but I don't know how to make "sparse" circulant matrices.

So the question: is there a nice way to store this matrix sparsely so that it could be operated on by e.g. Eigensystem[] with Arnoldi method or something similar?

• Is $M$ is a Hamiltonian matrix for a multidimensional system? I'm actually doing something similar, however I'm applying a similarity transform to $M$ and then only taking a small subset of the rows and columns; this destroys the structure of $M$, but it also vastly reduces the size which makes it easier to use dense matrix methods. – DumpsterDoofus Feb 22 '14 at 15:40
• @DumpsterDoofus yes, it's a Hamiltonian matrix. What similarity transform do you apply? – Ruslan Feb 22 '14 at 15:43
• I'm trying the one at arxiv.org/pdf/1201.2299.pdf. I found the paper a bit hard to understand at first, I'm still working on optimization. – DumpsterDoofus Feb 22 '14 at 15:48
• Using SparseArray as the second argument to IdentityMatrix allows a KroneckerSum on sparse matrices to be easily built on top of KroneckerProduct. – b3m2a1 Aug 6 '18 at 9:30