Existence and computation of low Kronecker-rank approximations for large linear systems of tensor product structure (Q1885280)

The author proposes a method to solve a linear system \(Ax=b\) with \(A\in{\mathbb R}^{N\times N}\) with Kronecker product structure, i.e., with \(N=n^d\), \(A=\sum_{i=1}^d \hat{A}_i\) where \(\hat{A}_i=I\otimes\cdots\otimes I\otimes A_i\otimes\cdots\otimes I\) (the \(A_i\in{\mathbb R}^{n\times n}\) is the \(i\)th factor in this Kronecker product), and \(b=\bigotimes_{i=1}^d b_i\), \(b_i\in{\mathbb R}^n\). This type of problems appears in finite element discretisation of partial differential equations on a Kronecker product grid. It is first observed that if the spectra of the \(A_i\) are in the left half plane, then \(A^{-1}=-\int_0^\infty \bigotimes_{i=1}^d \exp(tA_i)dt\). The numerical method consists in obtaining an approximation by replacing the integral by an appropriate quadrature formula. An error bound for the quadrature formula leads to an error bound for the solution of the linear system that is obtained in this way. Two methods for computing the required values of the matrix exponentials \(\exp(t_k A_i)\) are discusses in more detail.