Search

We develop fast discrete Fourier transforms (and their adjoints) from a square in space to a disk in the Fourier domain. Since our new transforms are not unitary, we develop a fast inversion algorithm and derive corresponding estimates that allow us to avoid iterative methods typically used for inversion. We consider the eigenfunctions of the corresponding band-limiting and space-limiting operator to describe spaces on which these new transforms can be inverted and made useful. In the process, we construct polar grids which provide quadratures and interpolation with controlled accuracy for functions band-limited within a disk. For rapid computation of the involved trigonometric sums we use the unequally spaced fast Fourier transform, thus yielding fast algorithms for all new transforms. We also introduce polar grids motivated by linearized scattering problems which are obtained by discretizing a family of circles. These circles are generated by using a single circle passing through the origin and rotating this circle with the origin as a pivot. For such grids, we provide a fast algorithm for interpolation to a near optimal grid in the disk, yielding an accurate adjoint transform and inversion algorithm.

Multiresolution techniques in multiwavelet bases, made practical in three and higher dimensions by separated representations, have enabled significant advances in the accuracy and manner of computation of molecular electronic structure. The mathematical and numerical techniques are described in the article by Fann. This paper summarizes the major accomplishments in computational chemistry which represent the first substantial application of most of these new ideas in three and higher dimensions. These include basis set limit computation with linear scaling for Hartree-Fock and Density Functional Theory with a wide variety of functionals including hybrid and asymptotically corrected forms. Current capabilities include energies, analytic derivatives, and excitation energies from linear response theory. Direct solution in 6-D of the two-particle wave equation has also been demonstrated. These methods are written using MADNESS which provides a high level of composition using functions and operators with guarantees of speed and precision.

We describe some recent mathematical results in constructing computational methods that lead to the development of fast and accurate multiresolution numerical methods for solving problems in computational chemistry (the so-called multiresolution quantum chemistry). Using low separation rank representations of functions and operators and representations in multiwavelet bases, we developed a multiscale solution method for integral and differential equations and integral transforms. The Poisson equation and the Schrodinger equation, the projector on the divergence free functions, provide important examples with a wide range of applications in computational chemistry, computational electromagnetic and fluid dynamics. We have implemented these ideas that include adaptive representations of operators and functions in the multiwavelet basis and low separation rank approximation of operators and functions. These methods have been implemented into a software package called Multiresolution Adaptive Numerical Evaluation for Scientific Simulation (MADNESS).

We use optimal rational approximations of projection data collected in x-ray tomography to improve image resolution. Under the assumption that the object of interest is described by functions with jump discontinuities, for each projection we construct its rational approximation with a small (near optimal) number of terms for a given accuracy threshold. This allows us to augment the measured data, i.e., double the number of available samples in each projection or, equivalently, extend (double) the domain of their Fourier transform. We also develop a new, fast, polar coordinate Fourier domain algorithm which uses our nonlinear approximation of projection data in a natural way. Using augmented projections of the Shepp–Logan phantom, we provide a comparison between the new algorithm and the standard filtered back-projection algorithm. We demonstrate that the reconstructed image has improved resolution without additional artifacts near sharp transitions in the image.

We describe some recent mathematical results in constructing computational methods that lead to the development of fast and accurate multiresolution numerical methods for solving quantum chemistry and nuclear physics problems based on Density Functional Theory (DFT). Using low separation rank representations of functions and operators in conjunction with representations in multiwavelet bases, we developed a multiscale solution method for integral and differential equations and integral transforms. The Poisson equation, the Schrodinger equation, and the projector on the divergence free functions provide important examples with a wide range of applications in computational chemistry, nuclear physics, computational electromagnetic and fluid dynamics. We have implemented this approach along with adaptive representations of operators and functions in the multiwavelet basis and low separation rank (LSR) approximation of operators and functions. These methods have been realized and implemented in a software package called Multiresolution Adaptive Numerical Evaluation for Scientific Simulation (MADNESS).

Formulae involving double integrals over spheres arise naturally in inverse scattering problems since the scattered data are measured in the space R*S2*S2. The authors derive a relation between differential forms on the space Sn-1*Sn-1, and those on the space I*Sn-2*Sn-1, where I is a real interval. Specifically, d xi d eta =sinn-2 theta d theta d psi d nu ( xi , eta ) in Sn-1*Sn-1 and ( theta , psi , nu ) in I*Sn-2*Sn-1. This allows them to derive the results of John relating the iterated spherical mean of a function to its spherical mean in a simple way; to obtain new inversion formulae for the Fourier and Radon transforms; to extend formulae for linearised inverse quantum scattering and diffraction tomography to the multifrequency case; and also to establish a relation between multifrequency diffraction tomography and seismic migration algorithms.

The authors consider the inverse scattering problem for the wave equation with variable speed where the region of interest is probed with waves emanating from point sources. They obtain a three-dimensional trace-type formula which gives the unknown speed in terms of data and the interior wavefield.

A certain integral operator T, which arises in some linearised inverse scattering problems, is shown to be a pseudodifferential operator and its points of ellipticity are explicitly described. Consequently for the equation Tf=g, one can find the relationship between the wavefront sets of f and g. From this viewpoint a class of algorithms called the migration schemes and used extensively in geophysics for imaging the Earth's interior can be understood clearly.