High dimensional finite difference problems often lead to linear systems of the form $$ A x = b, \qquad A = B_1 \oplus B_2 \oplus \cdots \oplus B_d, $$ where $\oplus$ denotes the Kronecker sum. $B_i \in \mathbb{R}^{n \times n}$ are 1D finite difference matrices, often tridiagonal or pentadiagonal. When $d=2$, for example, this is $$ A = B_1 \otimes I + I \otimes B_2. $$

My question is about how to solve these systems most efficiently in MATLAB. The simplest approach is to construct the matrices using kron and solve with mldivide, but these systems can have a large bandwidth. In How to efficiently invert $K \otimes M+I_T\otimes \Sigma$? and in the literature on Sylvester equations, I've come across more efficient approaches based on diagonalizations or Schur decompositions of $B_i$. As $B_i$ are often Toeplitz or circulant, there are efficient FFT-based techniques for this, but I can't always make these structural assumptions. If my understanding is correct, the cost of this is $O(d n^3 + n^d)$.

Is there a more efficient way to solve these Kronecker sum systems when $B_i$ are banded? I speculate it is possible to do in $O(d n + n^d)$ time. Can this problem be decomposed into a sequence of 1D linear solves which are easily handled with mldivide?


1 Answer 1


They only deal with the 2D case, but I can point you to the work of some of my colleagues on https://doi.org/10.1137/17M1157155 . Using the off-diagonal low-rank structure in a recursive fashion, they can reach quasi-linear cost for the 2D case.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.