A Kronecker product variant of the FACR method for solving the generalized Poisson equation

We present a fast direct method for the solution of a linear system Mx→=y→, where M is a block tridiagonal Toeplitzmatrix with A on the diagonal and T on the two subdiagonals (A and T commute). Such matrices are obtained from a finite difference approximation to Poissonʹs equation with nonconstant coefficients in one direction (among others). w method is called KPCR(l)-method and begins with l steps of cyclic reduction after which the remaining system is solved by a Kronecker product method. For an appropriate choice of l the asymptotic operation count for an n×n grid is O(n2 log2 log2 n), which is faster than either cyclic reduction or the Kronecker product method itself. The algorithm is similar to and has the same complexity as the FACR(l)-algorithm, which is a combination of cyclic reduction and Fourier analysis (or matrix decomposition). However, the FACR(l)-algorithm only reaches this complexity if A (and T) can be diagonalized by a fast transformation, where the new method is fast for every banded A and T. Moreover, the KPCR(l)-method can be easily generalized to the case where A and T do not commute.