Fast Computational Techniques


In the solution of the time-dependent incompressible Navier-Stokes equations one is led to the problem of solving a Poisson equation (or a Poisson like equation) at each time-step. It is this task that is responsible for most of the CPU time expended in the solution of incompressible fluid flow problems. In an effort to improve the efficiency of procedures for solving the Navier-Stokes equations, I've worked on techniques for the rapid solution of Poisson's equation. Most of these techniques were developed in order to accelerate calculations using vortex methods and hence there is a focus on methods for finding the solution of Poisson's equation when the forcing function is a collection of discrete sources (e.g. particles).

The central idea behind fast techniques is that one can trade accuracy for computational efficiency. A paper that discusses how this general idea is used for solving Poisson's equations is "Computational Aspects of "Fast" Particle Simulations". Details of the procedures described in that paper are presented in "An Implementation of the Fast Multipole Method Without Multipoles" and
"A Method of Local Corrections for Computing the Velocity Field Due to a Distribution of Vortex Blobs".

Additionally, I've worked a little on developing a computational technique for computing the discrete Fourier transform of a set of points that are not a power of 2, or are un-equally spaced. This is described in the paper "Rapid Computation of the Discrete Fourier Transform".



"Rapid Computation of the Discrete Fourier Transform", Chris. Anderson and Marie Dillon Dahleh, SIAM J. Sci. Stat. Comput., Vol. 17, No. 4, pp 913-919, July 1996.

Abstract: Algorithms for the rapid computation of the forward and inverse discrete Fourier transform for points which are nonequispaced or whose number is unrestricted are presented. The computational procedure is based on approximation using a local Taylor series expansion and the fast Fourier transform (FFT). The forward transform for nonequispaced points is computed as the solution of a linear system involving the inverse Fourier transform. This latter system is solved using the iterative method GMRES with preconditioning. Numerical results are given to confirm the efficiency of the algorithm.

"Computational Aspects of "Fast" Particle Simulations", Christopher R. Anderson, Proceedings of the Ninth International Conference on Computational Methods in Applied Science and Engineering, Paris, France 1990. ed. R. Glowinski, A. Lichnewsky, SIAM publications, 1990., pg. 123-135.

Abstract: In many particle simulations the calculations of the potential (velocity field, force, etc..) requires O(N2) operations where N is the number of particles. In this paper we described the basic ideas behind three methods which are employed to reduce this operation count to approximately O(N) . We discuss the issue of parameter selection for these methods and present some computational evidence which demonstrate the importance of making good choices for the method parameters. We conclude with some opinions about the relative merits of the methods.


"An Implementation of the Fast Multipole Method Without Multipoles", Christopher R. Anderson, SIAM J. Sci. Stat. Comput., Vol. 13, No. 4, pp 923-947, July 1992.

Abstract: An implementation is presented of the fast multiple method, that uses approximations based on Poisson's formula. Details for the implementation in both two and three dimensions are given. Also discussed is how the multigrid aspect of a fast multiple method can be exploited to yield efficient programming procedures. The issue of the selection of an appropriate refinement level for the method is addressed. Computational results are given that show the importance of good level selection. An efficient technique that can be used to determine an optimal level to choose for the method is presented.


"A Method of Local Corrections for Computing the Velocity Field Due to a Distribution of Vortex Blobs", Christopher R. Anderson, J. of Comp. Phys., Vol. 62, No. 1, January 1986. 111-123.

Abstract: A computationally efficient method for computing the velocity field due to a distribution a vortex blobs is presented. The method requires fewer calculations the straight forward vortex method velocity procedure and does sacrifice the high order accuracy which can be achieved using higher-order vortex core functions.