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).The new 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(n2log2log2n), 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.