Integrated Multiscale Modeling of Molecular Computing Devices Page: 3 of 8
This report is part of the collection entitled: Office of Scientific & Technical Information Technical Reports and was provided to Digital Library by the UNT Libraries Government Documents Department.
The following text was automatically extracted from the image on this page using optical character recognition software:
We now detail the results stated in the summary.
1. We have constructed an approximation of the free space Green's function for the Helmholtz equation in
such a way that the application of the resulting operator is split between the spatial and the Fourier do-
mains, similar to Ewald method for evaluating lattice sums. Furthermore, we developed new quadratures
appropriate for integration in the disk in the Fourier domain to account for the singularity of the Green's
function. The contribution in the spatial domain requires a convolution with a small number of Gaussians
with negative exponents and positive weights which fits well into our existing fast algorithm. The combina-
tion of approximation and new quadratures yields a fast algorithm for computing volumetric convolutions
with this oscillatory Green's function in dimensions two and three. The algorithmic complexity effectively
scales as O(kd log k + C(log E-)d), where E is selected accuracy, k is the number of wavelengths in the
problem, d is the dimension, and C is a constant. Importantly, the algorithm maintains its efficiency when
applied to functions with singularities. We note that our approximation differs from that used in the Fast
Multipole Method and, as k -> 0, makes a smooth transition to the free space Green's function for the
Poisson equation. The results have been published in .
2. We have developed a fast and accurate algorithm for computing convolutions with the quasi-periodic
Helmholtz Green's function in two and three dimensions. This Green's function is defined by a conditionally
convergent (lattice) sum. Although the main idea of our approach is similar to that of Ewald summation,
in contrast to Ewald's method we use different means to interpret the sum. This provides an additional
insight and a fast algorithm for its application. As in Ewald's method, we split the sum into two, one in the
spatial domain and the other in the Fourier domain and both with exponential decay in their corresponding
domains. In each domain we describe a method for fast convolution with combined algorithmic complexity
O(kd log k), where k is the number of wavelengths in the problem and d is the dimension.
Due to the exponential decay of the terms in both in the spatial and Fourier domains, we truncate them
for a finite by arbitrary accuracy. As a result, our algorithm maintains its performance when applied to
functions with singularities. We approximate the terms in the spatial domain as a sum of Gaussians having
negative exponents and positive weights. Thus, to compute a convolution, we may use the multiresolution
algorithm developed previously (and, in part, supported by this grant). In the Fourier domain, we use the
Unequally Spaced Fast Fourier Transform (USFFT) to compute convolutions with the terms of Fourier
sum. Our algorithm is applicable to volumetric problems and has computational complexity 0(4d log n).
We note that in the Fourier domain we use quadratures for bandlimited functions. The results have been
published in .
3. We have developed a multiresolution representation of a class of integral operators satisfying boundary
conditions on simple domains and constructed fast algorithms for their application. We have also elucidated
some delicate theoretical issues related to the construction of periodic Green's functions for Poisson's
By applying the method of images to the non-standard form of the free space operator, we obtain lattice
sums that converge absolutely on all scales, except possibly on the coarsest scale. On the coarsest scale the
lattice sums may be only conditionally convergent and, thus, allow for some freedom in their definition.
We use the limit of square partial sums as a definition of the limit and obtain a systematic, simple
approach to the construction (in any dimension) of periodized operators with sparse non-standard forms.
We illustrate the results on several examples in dimensions one and three: the Hilbert transform, the
projector on divergence free functions, the non-oscillatory Helmholtz Green's function and the Poisson
operator. Remarkably, the limit of square partial sums yields a periodic Poisson Green's function which is
not a convolution. Using a short sum of decaying Gaussians to approximate periodic Green's functions, we
arrive at fast algorithms for their application. We further show that the results obtained for operators with
periodic boundary conditions extend to operators with Dirichlet, Neumann, or mixed boundary conditions.
The results are available electronically .
4. We have implemented improvements to the algorithm based on separated multiresolution representations
of Green's functions for the Poisson kernel and other non-oscillatory kernels and/or potentials. The speed
up is about 3-5 times depending on the order of the multiwavelet basis (the more significant acceleration is
for higher orders). This code is being used in the construction of solutions to the multiparticle Schrbdinger
equation, see [2, 6, 7].
Here’s what’s next.
This report can be searched. Note: Results may vary based on the legibility of text within the document.
Tools / Downloads
Get a copy of this page or view the extracted text.
Citing and Sharing
Basic information for referencing this web page. We also provide extended guidance on usage rights, references, copying or embedding.
Reference the current page of this Report.
Beylkin, Gregory. Integrated Multiscale Modeling of Molecular Computing Devices, report, March 23, 2012; United States. (digital.library.unt.edu/ark:/67531/metadc840610/m1/3/: accessed March 24, 2018), University of North Texas Libraries, Digital Library, digital.library.unt.edu; crediting UNT Libraries Government Documents Department.