A quasi-direct fast Poisson solver for general regions

摘要

A fast Poisson solver for general regions with Dirichlet boundary conditions is proposed and analyzed numerically. This solver uses an unsymmetrical preconditioner for the conjugate gradient method. The preconditioner is generated by the recursive construction of factorable finite-difference approximations of the Laplacian which, formally, are fully consistent both in the interior of the region and near its boundary. The construction of the difference operators is mildly unstable but their entries (and thus the error constants) are proven to remain finite for any finite number of recursion steps.The solver is studied numerically for a number of test problems and is found to have novel, interesting convergence properties. The iteration is started from a first guess provided by the preconditioner itself with correct boundary conditions. Asymptotically, as the number n of discretization steps in each direction gets large, the accuracy of the first guess apparently tends to a constant. Furthermore, the important early phase of the iteration, during which the errors are reduced down to any specified level (say the truncation error of the five-point star approximation of the Laplacian), is characterized by convergence rates which are virtually independent of the grid parameter. Hence this solver appears to be quasi-direct, in the sense that it generates numerical solutions of specified accuracy in a number of passes which seems to be independent of the number of discretization steps n as that number becomes large.