Fast adaptive algorithms in the non-standard form for multidimensional problems

We present a fast, adaptive multiresolution algorithm for applying integral operators with a wide class of radially symmetric kernels in dimensions one, two and three. This algorithm is made efficient by the use of separated representations of the kernel. We discuss operators of the class (−Δ+μ²I)^−α, where μ0 and 0<α<3/2, and illustrate the algorithm for the Poisson and Schrödinger equations in dimension three. The same algorithm may be used for all operators with radially symmetric kernels approximated as a weighted sum of Gaussians, making it applicable across multiple fields by reusing a single implementation. This fast algorithm provides controllable accuracy at a reasonable cost, comparable to that of the Fast Multipole Method (FMM). It differs from the FMM by the type of approximation used to represent kernels and has the advantage of being easily extendable to higher dimensions.     

On computing distributions of products of non-negative independent random variables

We introduce a new functional representation of probability density functions (PDFs) of non-negative random variables via a product of a monomial factor and linear combinations of decaying exponentials with complex exponents. This approximate representation of PDFs is obtained for any finite, user-selected accuracy. Using a fast algorithm involving Hankel matrices, we develop a general numerical method for computing the PDF of the sums, products, or quotients of any number of non-negative independent random variables yielding the result in the same type of functional representation. We present several examples to demonstrate the accuracy of the approach.     

Fast wavelet transforms and numerical algorithms I

A class of algorithms is introduced for the rapid numerical application of a class of linear operators to arbitrary vectors. Previously published schemes of this type utilize detailed analytical information about the operators being applied and are specific to extremely narrow classes of matrices. In contrast, the methods presented here are based on the recently developed theory of wavelets and are applicable to all Calderon-Zygmund and pseudo-differential operators. The algorithms of this paper require order O(N) or O(N log N) operations to apply an N × N matrix to a vector (depending on the particular operator and the version of the algorithm being used), and our numerical experiments indicate that many previously intractable problems become manageable with the techniques presented here.     

Multiresolution quantum chemistry: basic theory and initial applications

We describe a multiresolution solver for the all-electron local density approximation Kohn-Sham equations for general polyatomic molecules. The resulting solutions are obtained to a user-specified precision and the computational cost of applying all operators scales linearly with the number of parameters. The construction and use of separated forms for operators (here, the Green's functions for the Poisson and bound-state Helmholtz equations) enable practical computation in three and higher dimensions. Initial applications include the alkali-earth atoms down to strontium and the water and benzene molecules.     

Efficient solution of Poisson's equation with free boundary conditions

Interpolating scaling functions give a faithful representation of a localized charge distribution by its values on a grid. For such charge distributions, using a fast Fourier method, we obtain highly accurate electrostatic potentials for free boundary conditions at the cost of O(N log N) operations, where N is the number of grid points. Thus, with our approach, free boundary conditions are treated as efficiently as the periodic conditions via plane wave methods.     

Multiresolution Analysis of Elastic Degradation in Heterogeneous Materials

In this study we examine the stiffness properties of heterogeneous elastic materials and their degradation at different levels of observations. To this end we explore the opportunities and limitations of multiresolution wavelet analysis, where successive Haar transformations lead to a recursive separation of the stiffness properties and the response into coarse- and fine-scale features. In the limit, this recursive process results in a homogenization parameter which is an average measure of stiffness and strain energy capacity at the coarse scale. The basic concept of multiresolution analysis is illustrated with one- and two-dimensional model problems of a two-phase particulate composite representative of the morphology of concrete materials. The computational studies include the microstructural features of concrete in the form of a bi-material system of aggregate particles which are immersed in a hardened cement paste taking due account of the mismatch of the two elastic constituents. Sommario. In questo studio si esaminano le proprietà di rigidezza di materiali elastici eterogenei ed il loro degrado a diverse scale di osservazione. A questo scopo si esplorano le opportunità e le limitazioni di analisi con wavelets a risoluzione multipla, dove successive trasformazioni di Haar conducono ad una separazione ricorsiva della proprietà della rigidezza e della risposta nelle loro caratteristiche di scala fine e grossolana. Al limite, questo processo ricorsivo dà luogo ad un parametro di omogeneizzazione che rappresenta una misura media della rigidezza e della capacità di immagazzinare energia di deformazione alla grande scala. Il concetto di base dell'analisi a risoluzione multipla è illustrato per mezzo di problemi modello mono- e bi-dimensionali che si riferiscono ad un composito particolato a due fasi rappresentativo della morfologia del calcestruzzo. Le caratteristiche microstrutturali del calcestruzzo sono modellate nello studio computazionale sotto forma di un sistema a due materiali di particelle aggregate, immerse in una pasta di cemento indurita e tenendo conto della mencata congruenza tra i due constituenti elastici.     

Nonlinear inversion of a band-limited Fourier transform

We consider the problem of reconstructing a compactly supported function with singularities either from values of its Fourier transform available only in a bounded interval or from a limited number of its Fourier coefficients. Our results are based on several observations and algorithms in [G. Beylkin, L. Monzón, On approximation of functions by exponential sums, Appl. Comput. Harmon. Anal. 19 (1) (2005) 17–48]. We avoid both the Gibbs phenomenon and the use of windows or filtering by constructing approximations to the available Fourier data via a short sum of decaying exponentials. Using these exponentials, we extrapolate the Fourier data to the whole real line and, on taking the inverse Fourier transform, obtain an efficient rational representation in the spatial domain. An important feature of this rational representation is that the positions of its poles indicate location of singularities of the function. We consider these representations in the absence of noise and discuss the impact of adding white noise to the Fourier data. We also compare our results with those obtained by other techniques. As an example of application, we consider our approach in the context of the kernel polynomial method for estimating density of states (eigenvalues) of Hermitian operators. We briefly consider the related problem of approximation by rational functions and provide numerical examples using our approach.