On the efficient evaluation of the azimuthal Fourier components of the Green's function for Helmholtz's equation in cylindrical coordinates.

In this paper, we develop an efficient algorithm to evaluate the azimuthal Fourier components of the Green's function for the Helmholtz equation in cylindrical coordinates. A computationally efficient algorithm for this modal Green's function is essential for solvers for electromagnetic scattering from bodies of revolution (e.g., radar cross sections, antennas). Current algorithms to evaluate this modal Green's function become computationally intractable when the source and target are close or when the wavenumber is large or complex. Furthermore, most state-of-the-art methods cannot be easily parallelized. In this paper, we present an algorithm for evaluating the modal Green's function that has performance independent of both source-to-target proximity and wavenumber, and whose cost grows as O(m), where m is the Fourier mode. Our algorithm's performance is independent of whether the wavenumber is real or complex. Furthermore, our algorithm is embarrassingly parallelizable.

A FAST SIMPLE ALGORITHM FOR COMPUTING THE POTENTIAL OF CHARGES ON A LINE.

We present a fast method for evaluating expressions of the form u j = ∑ i = 1 , i ≠ j n α i x i - x j , for j = 1 , … , n , where αi are real numbers, and xi are points in a compact interval of R . This expression can be viewed as representing the electrostatic potential generated by charges on a line in R 3 . While fast algorithms for computing the electrostatic potential of general distributions of charges in R 3 exist, in a number of situations in computational physics it is useful to have a simple and extremely fast method for evaluating the potential of charges on a line; we present such a method in this paper, and report numerical results for several examples.

A Fast Summation Method for Oscillatory Lattice Sums.

We present a fast summation method for lattice sums of the type which arise when solving wave scattering problems with periodic boundary conditions. While there are a variety of effective algorithms in the literature for such calculations, the approach presented here is new and leads to a rigorous analysis of Wood's anomalies. These arise when illuminating a grating at specific combinations of the angle of incidence and the frequency of the wave, for which the lattice sums diverge. They were discovered by Wood in 1902 as singularities in the spectral response. The primary tools in our approach are the Euler-Maclaurin formula and a steepest descent argument. The resulting algorithm has super-algebraic convergence and requires only milliseconds of CPU time.

On the solution of the Helmholtz equation on regions with corners.

In this paper we solve several boundary value problems for the Helmholtz equation on polygonal domains. We observe that when the problems are formulated as the boundary integral equations of potential theory, the solutions are representable by series of appropriately chosen Bessel functions. In addition to being analytically perspicuous, the resulting expressions lend themselves to the construction of accurate and efficient numerical algorithms. The results are illustrated by a number of numerical examples.

Randomized approximate nearest neighbors algorithm.

We present a randomized algorithm for the approximate nearest neighbor problem in d-dimensional Euclidean space. Given N points {x(j)} in R(d), the algorithm attempts to find k nearest neighbors for each of x(j), where k is a user-specified integer parameter. The algorithm is iterative, and its running time requirements are proportional to T·N·(d·(log d) + k·(d + log k)·(log N)) + N·k(2)·(d + log k), with T the number of iterations performed. The memory requirements of the procedure are of the order N·(d + k). A by-product of the scheme is a data structure, permitting a rapid search for the k nearest neighbors among {x(j)} for an arbitrary point x ∈ R(d). The cost of each such query is proportional to T·(d·(log d) + log(N/k)·k·(d + log k)), and the memory requirements for the requisite data structure are of the order N·(d + k) + T·(d + N). The algorithm utilizes random rotations and a basic divide-and-conquer scheme, followed by a local graph search. We analyze the scheme's behavior for certain types of distributions of {x(j)} and illustrate its performance via several numerical examples.

A fast randomized algorithm for overdetermined linear least-squares regression.

We introduce a randomized algorithm for overdetermined linear least-squares regression. Given an arbitrary full-rank m x n matrix A with m >/= n, any m x 1 vector b, and any positive real number epsilon, the procedure computes an n x 1 vector x such that x minimizes the Euclidean norm ||Ax - b || to relative precision epsilon. The algorithm typically requires ((log(n)+log(1/epsilon))mn+n(3)) floating-point operations. This cost is less than the (mn(2)) required by the classical schemes based on QR-decompositions or bidiagonalization. We present several numerical examples illustrating the performance of the algorithm.

Randomized algorithms for the low-rank approximation of matrices.

We describe two recently proposed randomized algorithms for the construction of low-rank approximations to matrices, and demonstrate their application (inter alia) to the evaluation of the singular value decompositions of numerically low-rank matrices. Being probabilistic, the schemes described here have a finite probability of failure; in most cases, this probability is rather negligible (10(-17) is a typical value). In many situations, the new procedures are considerably more efficient and reliable than the classical (deterministic) ones; they also parallelize naturally. We present several numerical examples to illustrate the performance of the schemes.