FAST TRANSFORMS BASED ON STRUCTURED MATRICES WITH APPLICATIONS TO THE FAST MULTIPOLE METHOD

Abstract

The solution of many problems in engineering and science is enabled by the availability of a fast algorithm, a significant example being the fast Fourier transform, which computes the matrix-vector product for a $N \times N$ Fourier matrix in $O(N\log(N))$ time. Related fast algorithms have been devised since to evaluate matrix-vector products for other structured matrices such as matrices with Toeplitz, Hankel, Vandermonde, etc. structure.

A recent fast algorithm that was developed is the fast multipole method (FMM). The original FMM evaluates all pair-wise interactions in large ensembles of $N$ particles in $O(p^2N)$ time, where $p$ is the number of terms in the truncated multipole/local expansions it uses. Analytical properties of translation operators that shift the center of a multipole or local expansion to another location and convert a multipole expansion into a local expansion are used. The original translation operators achieve the translation in $O(p^2)$ operations for a $p$ term expansion. Translation operations are among the most important and expensive steps in an FMM algorithm. The main focus of this dissertation is on developing fast accurate algorithms for the translation operators in the FMM for Coulombic potentials in two or three dimensions.

We show that the matrices involved in the translation operators of the FMM for Coulombic potentials can be expressed as products of structured matrices. Some of these matrices have fast transform algorithms available, while for others we show how they can be constructed. A particular algorithm we develop is for fast computation of matrix vector products of the form $Px$, $P'x$, and $PP'x$, where $P$ is a Pascal matrix.

When considering fast translation algorithms for the 3D FMM we decompose translations into an axial translation and a pair of rotations. We show how a fast axial translation can be performed. The bottleneck for achieving fast translation is presented by the lack of a fast rotation transform. A fast rotation algorithm is also important for many other applications, including quantum mechanics, geoscience, computer vision, etc, and fast rotation algorithms are being developed based on the properties of spherical harmonics. We follow an alternate path by showing that the rotation matrix $R$ can be factored in two different ways into the product of structured matrices. Both factorizations allow a fast matrix-vector product. Our algorithm efficiently computes the coefficients of spherical harmonic expansions on rotation.

Numerical experiments confirm that the new $O(p\log p)$ translation operators for both the 2D and 3D FMM have the same accuracy as the original ones, achieve their asymptotic complexity for modest $p$, and significantly speed up the FMM algorithms in 2D and 3D. We hope that this thesis will also lead to promising future research in establishing fast translation for the FMM for other potentials, as well as applying the transforms in other applications such as in harmonic analysis on the sphere.