| Home > Publications > Reports > Numerical Analysis and Applied Mathematics (TW) |
TW 313
J. Hendrickx, M. Van Barel
A combination of cyclic reduction and Kronecker product methods for the direct solution of Poisson's equation
Abstract
We present a fast direct method for the solution of a linear system M x = 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 (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 nxn grid is O(n2 log log 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.
report.pdf / mailto: J. Hendrickx