Browsing by Author "Gumerov, Nail A."
Now showing 1 - 18 of 18
Results Per Page
Sort Options
Item Accurate computation of Galerkin double surface integrals in the 3-D boundary element method(2015-05-29) Adelman, Ross; Gumerov, Nail A.; Duraiswami, RamaniMany boundary element integral equation kernels are based on the Green’s functions of the Laplace and Helmholtz equations in three dimensions. These include, for example, the Laplace, Helmholtz, elasticity, Stokes, and Maxwell equations. Integral equation formulations lead to more compact, but dense linear systems. These dense systems are often solved iteratively via Krylov subspace methods, which may be accelerated via the fast multipole method. There are advantages to Galerkin formulations for such integral equations, as they treat problems associated with kernel singularity, and lead to symmetric and better conditioned matrices. However, the Galerkin method requires each entry in the system matrix to be created via the computation of a double surface integral over one or more pairs of triangles. There are a number of semi-analytical methods to treat these integrals, which all have some issues, and are discussed in this paper. We present novel methods to compute all the integrals that arise in Galerkin formulations involving kernels based on the Laplace and Helmholtz Green’s functions to any specified accuracy. Integrals involving completely geometrically separated triangles are non-singular and are computed using a technique based on spherical harmonics and multipole expansions and translations, which results in the integration of polynomial functions over the triangles. Integrals involving cases where the triangles have common vertices, edges, or are coincident are treated via scaling and symmetry arguments, combined with automatic recursive geometric decomposition of the integrals. Example results are presented, and the developed software is available as open source.Item Boundary Element Solution of Electromagnetic Fields for Non-Perfect Conductors at Low Frequencies and Thin Skin Depths(2020-05-13) Gumerov, Nail A.; Adelman, Ross N.; Duraiswami, RamaniA novel boundary element formulation for solving problems involving eddy currents in the thin skin depth approximation is developed. It is assumed that the time-harmonic magnetic field outside the scatterers can be described using the quasistatic approximation. A two-term asymptotic expansion with respect to a small parameter characterizing the skin depth is derived for the magnetic and electric fields outside and inside the scatterer, which can be extended to higher order terms if needed. The introduction of a special surface operator (the inverse surface gradient) allows the reduction of the problem complexity. A method to compute this operator is developed. The obtained formulation operates only with scalar quantities and requires computation of surface operators that are usual for boundary element (method of moments) solutions to the Laplace equation. The formulation can be accelerated using the fast multipole method. The method is much faster than solving the vector Maxwell equations. The obtained solutions are compared with the Mie solution for scattering from a sphere and the error of the solution is studied. Computations for much more complex shapes of different topologies, including for magnetic and electric field cages used in testing are also performed and discussed.Item Comparison of the Efficiency of Translation Operators Used in the Fast Multipole Method for the 3D Laplace Equation(2005-11-30T16:21:31Z) Gumerov, Nail A.; Duraiswami, RamaniWe examine the practical implementation of a fast multipole method algorithm for the rapid summation of Laplace multipoles. Several translation operators with different asymptotic computational and memory complexities have been proposed for this problem. These algorithms include: Method 0 — the originally proposed matrix based translations due to Greengard and Rokhlin (1987), Method 1 — the rotation, axial translation and rotation algorithm due to White and Martin Head-Gordon (1993), and Method 3 — the plane-wave version of the multipole-to local translation operator due to Greengard and Rokhlin (1997). We compare the algorithms on data sets of varying size and with varying imposed accuracy requirements. While from the literature it would have been expected that method 2 would always be the method of choice, at least as far as computational speed is concerned, we find that this is not always the case. We find that as far as speed is concerned the choice between methods 1 and 2 depends on problem size and error requirements. Method 2 is the algorithm of choice for large problems where high accuracy is required, though the advantage is not clear cut, especially if memory requirements are an issue. If memory is an issue, Method 1 is the method of choice for most problems. A new analysis of the computational complexities of the algorithms is provided, which explains the observed results. We provide guidelines for choosing parameters for FMM algorithms.Item Computation of the head-related transfer function via the boundary element method and representation via the spherical harmonic spectrum(2009-05-15) Gumerov, Nail A.; O'Donovan, Adam; Duraiswami, Ramani; Zotkin, Dmitry N.The head-related transfer function (HRTF) is computed using the fast multipole accelerated boundary element method. For efficiency, the HRTF is computed using the reciprocity principle, by placing a source at the ear and computing its field. Analysis is presented to modify the boundary value problem accordingly. To compute the HRTF corresponding to different ranges via a single computation, a compact and accurate representation of the HRTF, termed the spherical spectrum, is developed. Computations are reduced to a two stage process, the computation of the spherical spectrum and a subsequent evaluation of the HRTF. This representation allows easy interpolation and range extrapolation of HRTFs. HRTF computations are performed for the range of audible frequencies up to 20 kHz for several models including a sphere, human head models (for the “Fritz” and “Kemar”), and head and torso model (the Kemar manikin). Comparisons between the different cases and analysis of limiting cases is provided. Comparisons with the computational data of other authors and available experimental data are conducted and show satisfactory agreement for the frequencies for which reliable experimental data is available. Our results show that, given a good mesh it is feasible to compute the HRTF over the full audible range on a regular personal computer.Item Data Structures, Optimal Choice of Parameters, and Complexity Results for Generalized Multilevel Fast Multipole Methods in $d$ Dimensions(2003-04-04) Gumerov, Nail A.; Duraiswami, Ramani; Borovikov, Eugene A.We present an overview of the Fast Multipole Method, explain the use of optimal data structures and present complexity results for the algorithm. We explain how octree structures and bit interleaving can be simply used to create efficient versions of the multipole algorithm in $d$ dimensions. We then present simulations that demonstrate various aspects of the algorithm, including optimal selection of the clustering parameter, the influence of the error bound on the complexity, and others. The use of these optimal parameters results in a many-fold speed-up of the FMM, and prove very useful in practice. UMIACS-TR-2003-28Item Efficient FMM accelerated vortex methods in three dimensions via the Lamb-Helmholtz decomposition(2012-01-24) Gumerov, Nail A.; Duraiswami, RamaniVortex-element methods are often used to efficiently simulate incompressible flows using Lagrangian techniques. Use of the FMM (Fast Multipole Method) allows considerable speed up of both velocity evaluation and vorticity evolution terms in these methods. Both equations require field evaluation of constrained (divergence free) vector valued quantities (velocity, vorticity) and cross terms from these. These are usually evaluated by performing several FMM accelerated sums of scalar harmonic functions. We present a formulation of the vortex methods based on the Lamb-Helmholtz decomposition of the velocity in terms of two scalar potentials. In its original form, this decomposition is not invariant with respect to translation, violating a key requirement for the FMM. One of the key contributions of this paper is a theory for translation for this representation. The translation theory is developed by introducing "conversion" operators, which enable the representation to be restored in an arbitrary reference frame. Using this form, extremely efficient vortex element computations can be made, which need evaluation of just two scalar harmonic FMM sums for evaluating the velocity and vorticity evolution terms. Details of the decomposition, translation and conversion formulae, as well as sample numerical results are presented.Item FAST ALGORITHMS TO COMPUTE MATRIX-VECTOR PRODUCTS FOR PASCAL MATRICES(2004-03-25) Tang, Zhihui; Duraiswami, Ramani; Gumerov, Nail A.The Pascal matrix arises in a number of applications. We present a few ways to decompose the Pascal matrices of size $n \times n$ into products of matrices with structure. Based on these decompositions, we propose fast algorithms to compute the product of a Pascal matrix and a vector with omplexity $O(n\log n)$. We also present a strategy to stabilize the proposed algorithms. Finally, we also present some interesting properties of the Pascal matrices that help us to compute fast the product of the inverse of a Pascal matrix and a vector, and fast algorithms for generalized Pascal Matrices. UMIACS-TR-2004-08Item Fast Multipole Accelerated Boundary Element Methods for the 3D Helmholtz Equation(2008-01-02) Gumerov, Nail A.; Duraiswami, RamaniThe development of a fast multipole method accelerated iterative solution of the boundary element equations for large problems involving hundreds of thousands elements for the Helmholtz equations in 3D is described. The BEM requires several approximate computations (numerical quadrature, approximations of the boundary shapes using elements) and the convergence criterion for iterative computation. When accelerated using the FMM, these different errors must all be chosen in a way that on the one hand excess work is not done and on the other that the error achieved by the overall computation is acceptable. Details of translation operators used, choices of representations, and boundary element integration consistent with these approximations are described. A novel preconditioner for accelerating convergence, using a low accuracy FMM accelerated solver as a right preconditioner is also described. Results of the developed and tested solvers for boundary value problems for the Helmholtz equations using the solver are presented for the number of unknowns N <= 106 and product of wavenumber k times domain size D, kD <= 200 and show good performance close to theoretical expectations.Item Fast Multipole Method for the Biharmonic Equation(2005-09-29T20:48:30Z) Gumerov, Nail A.; Duraiswami, RamaniThe evaluation of sums (matrix-vector products) of the solutions of the three-dimensional biharmonic equation can be accelerated using the fast multipole method, while memory requirements can also be significantly reduced. We develop a complete translation theory for these equations. It is shown that translations of elementary solutions of the biharmonic equation can be achieved by considering the translation of a pair of elementary solutions of the Laplace equations. Compared to previous methods that required the translation of five Laplace elementary solutions for the biharmonic Green's function, and much larger numbers for higher order multipoles, our method is significantly more efficient. The theory is implemented and numerical tests presented that demonstrate the performance of the method for varying problem sizes and accuracy requirements. In our implementation the FMM\ is faster than direct solution for a matrix size of $550$ for an accuracy of $10^{-3},$ 950 for an accuracy of $10^{-6} and $N=3550$ for an accuracy of $10^{-9}$.Item Fast Multipole Methods on Graphics Processors(2007-11) Gumerov, Nail A.; Duraiswami, RamaniThe Fast Multipole Method allows the rapid evaluation of sums of radial basis functions centered at points distributed inside a computational domain at a large number of evaluation points to a specified accuracy $\epsilon$. The method scales as $O (N)$ in both time and memory compared to the direct method with complexity $O(N^2)$, which allows the solution of larger problems with given resources. Graphical processing units (GPU) are now increasingly viewed as data parallel compute coprocessors that can provide significant computational performance at low price. We describe acceleration of the FMM using the data parallel GPU architecture. The FMM has a complex hierarchical (adaptive) structure, which is not easily implemented on data parallel processors. We described strategies for parallelization of all components of the FMM, develop a model to explain the performance of the algorithm on the GPU architecture; and determined optimal settings for the FMM on the GPU, which are different from those on usual CPUs. Some innovations in the FMM algorithm, including the use of modified stencils, real polynomial basis functions for the Laplace kernel, and decompositions of the translation operators, are also described. We obtained accelerations of the Laplace kernel FMMon a single NVIDIA GeForce 8800 GTX GPU in the range of 30-60 compared to a serial CPU FMM implementation. For a problem with a million sources, the summations involved are performed in approximately one second. This performance is equivalent to solving of the same problem at a 43 Teraflop rate if we use straightforward summation.Item Fast, Exact, and Stable Computation of Multipole Translation and Rotation Coefficients for the 3-D Helmholtz Equation(2001-09-05) Gumerov, Nail A.; Duraiswami, RamaniWe develop exact expressions for translations and rotations of local and multipole fundamental solutions of the Helmholtz equation in spherical coordinates. These expressions are based on recurrence relations that we develop, and to our knowledge are presented here for the first time. The symmetry and other properties of the coefficients are also examined, and based on these efficient procedures for calculating them are presented. Our expressions are direct, and do not use the Clebsch-Gordan coefficients or the Wigner 3-j symbols, though we compare our results with methods that use these, to prove their accuracy. We test our expressions on a number of simple calculations, and show their accuracy. For evaluating a $N_t$ term truncation of the translation (involving $O(N_t^2)$ multipoles), compared to previous exact expressions that rely on the Clebsch-Gordan coefficients or the Wigner $3-j$ symbol that require $O(N_t^5)$ operations, our expressions require $O(N_t^4)$) evaluations, with a small constant multiplying the order term. The recent trend in evaluating such translations has been to use approximate "diagonalizations," that require $O(N_t^3)$ evaluations with a large coefficient for the order term. For the Helmholtz equation, these translations in addition have stabilty problems unless the accuracy of the truncation and approximate translation are balanced. We derive explicit exact expressions for achieving "diagonal" translations in $O(N_t^3)$ operations. Our expressions are based on recursive evaluations of multipole coefficients for rotations, and are accurate and stable, and have a much smaller coeffiicient for the order term, resulting practically in much fewer operations. Future use of the developed methods in computational acoustic scattering, electromagnetic scattering (radar and microwave), optics and computational biology are expected. Cross-referenced as UMIACS-TR-2001-44Item A Hierarchical Algorithm for Fast Debye Summation with Applications to Small Angle Scattering(2011-09-01) Gumerov, Nail A.; Berlin, Konstantin; Fushman, David; Duraiswami, RamaniDebye summation, which involves the summation of sinc functions of distances between all pair of atoms in three dimensional space, arises in computations performed in crystallography, small/wide angle X-ray scattering (SAXS/WAXS) and small angle neutron scattering (SANS). Direct evaluation of Debye summation has quadratic complexity, which results in computational bottleneck when determining crystal properties, or running structure refinement protocols that involve SAXS or SANS, even for moderately sized molecules. We present a fast approximation algorithm that efficiently computes the summation to any prescribed accuracy epsilon in linear time. The algorithm is similar to the fast multipole method (FMM), and is based on a hierarchical spatial decomposition of the molecule coupled with local harmonic expansions and translation of these expansions. An even more efficient implementation is possible when the scattering profile is all that is required, as in small angle scattering reconstruction (SAS) of macromolecules. We examine the relationship of the proposed algorithm to existing approximate methods for profile computations, and provide detailed description of the algorithm, including error bounds and algorithms for stable computation of the translation operators. Our theoretical and computational results show orders of magnitude improvement in computation complexity over existing methods, while maintaining prescribed accuracy.Item Hierarchical O(N) Computation of Small-Angle Scattering Profiles and their Associated Derivatives(2013-05-25) Berlin, Konstantin; Gumerov, Nail A.; Fushman, David; Duraiswami, RamaniFast algorithms for Debye summation, which arises in computations performed in crystallography, small/wide-angle X-ray scattering (SAXS/WAXS) and small-angle neutron scattering (SANS), were recently presented in Gumerov et al. (J. Comput. Chem., 2012, 33:1981). The use of these algorithms can speed up computation of scattering profiles in macromolecular structure refinement protocols. However, these protocols often employ an iterative gradient-based optimization procedure, which then requires derivatives of the profile with respect to atomic coordinates. An extension to one of the algorithms is presented which allows accurate, O(N) cost computation of the derivatives along with the scattering profile. Computational results show orders of magnitude improvement in computational efficiency, while maintaining prescribed accuracy. This opens the possibility to efficiently integrate small-angle scattering data into structure determination and refinement of macromolecular systems.Item Improved Fast Gauss Transform(2003-08-01) Yang, Changjiang; Duraiswami, Ramani; Gumerov, Nail A.The fast Gauss transform proposed by Greengard and Strain reduces the computational complexity of the evaluation of the sum of $N$ Gaussians at $M$ points in $d$ dimensions from $O(MN)$ to $O(M+N)$. However, the constant factor in $O(M+N)$ grows exponentially with increasing dimensionality $d$, which makes the algorithm impractical in higher dimensions. In this paper we present an improved fast Gauss transform where the constant factor is reduced to asymptotically polynomial order. The reduction is based on a new multivariate Taylor expansion scheme combined with the space subdivision using the $k$-center algorithm. The complexity analysis and error bound are presented which helps to determine parameters automatically given a desired precision to which the sum must be evaluated. We present numerical results on the performance of our algorithm and provide numerical verification of the corresponding error estimate. (UMIACS-TR-2003-64)Item A Method to Compute Periodic Sums(2013-10-09) Gumerov, Nail A.; Duraiswami, RamaniIn a number of problems in computational physics, a finite sum of kernel functions centered at N particle locations located in a box in three dimensions must be extended by imposing periodic boundary conditions on box boundaries. Even though the finite sum can be efficiently computed via fast summation algorithms, such as the fast multipole method (FMM), the periodized extension, posed as an infinite sum of kernel functions, centered at the particle locations in the box, and their images, is usually treated via a different algorithm, Ewald summation. This is then accelerated via the fast Fourier transform (FFT). A method for computing this periodized sum just using a blackbox finite fast summation algorithm is presented in this paper. The method splits the periodized sum in to two parts. The first, comprising the contribution of all points outside a large sphere enclosing the box, and some of its neighbors, is approximated inside the box by a collection of kernel functions (“sources”) placed on the surface of the sphere. These are approximated within the box using an expansion in terms of spectrally convergent local basis functions. The second part, comprising the part inside the sphere, and including the box and its immediate neighborhood, is treated via the summation algorithm. The coefficients of the sources are determined by least squares collocation of the periodicity condition of the total potential, imposed on a circumspherical surface for the box. While the method is presented in general, details are worked out for the case of evaluating potentials and forces due to electrostatically charged particles in a box. Results show that when used with the FMM, the periodized sum can be computed to any specified accuracy, at a cost of about twice the cost of the free-space FMM with the same accuracy. Several technical details and efficient algorithms for auxiliary computations are also provided, as are numerical comparisons.Item Multiple Scattering from $N$ Spheres Using Multipole Reexpansion(2001-10-10) Gumerov, Nail A.; Duraiswami, RamaniA semi-analytical technique for the solution of problems of wave scattering from multiple spheres is developed. This technique extensively uses the theory for the translation and rotation of Helmholtz multipoles that was developed in our earlier work (Gumerov & Duraiswami, 2001). Results are verified by comparison with commercial boundary element software. The method developed is likely to be very useful in developing fast algorithms for many important problems, including those arising in simulations of composite media and multiphase flow. (Also cross-referenced UMIACS-TR-2001-72)Item Recursive computation of spherical harmonic rotation coefficients of large degree(2014-03-28) Gumerov, Nail A.; Duraiswami, RamaniComputation of the spherical harmonic rotation coefficients or elements of Wigner's d-matrix is important in a number of quantum mechanics and mathematical physics applications. Particularly, this is important for the Fast Multipole Methods in three dimensions for the Helmholtz, Laplace and related equations, if rotation-based decomposition of translation operators are used. In these and related problems related to representation of functions on a sphere via spherical harmonic expansions computation of the rotation coefficients of large degree n (of the order of thousands and more) may be necessary. Existing algorithms for their computation, based on recursions, are usually unstable, and do not extend to n. We develop a new recursion and study its behavior for large degrees, via computational and asymptotic analyses. Stability of this recursion was studied based on a novel application of the Courant-Friedrichs-Lewy condition and the von Neumann method for stability of finite-difference schemes for solution of PDEs. A recursive algorithm of minimal complexity O(n^2) for degree n and FFT-based algorithms of complexity O(n^2 log n) suitable for computation of rotation coefficients of large degrees are proposed, studied numerically, and cross-validated. It is shown that the latter algorithm can be used for n <~ 10^3 in double precision, while the former algorithm was tested for large n (up to 10^4 in our experiments) and demonstrated better performance and accuracy compared to the FFT-based algorithm.Item A scalar potential formulation and translation theory for the time-harmonic Maxwell equations(2006-02-17T14:53:27Z) Gumerov, Nail A.; Duraiswami, RamaniWe develop a computational method based on a scalar potential representation, which efficiently reduces the solution of Maxwell’s equations to the solution of two scalar Helmholtz equations. One of the key contributions of this paper is a theory for the translation of Maxwell solutions using such a representation, since the scalar potential form is not invariant with respect to translations. The translation theory is developed by introducing “conversion” operators, which enable the representation of the electric and magnetic vector fields via scalar potentials in an arbitrary reference frame. Advantages of this representation include the fact that only two Helmholtz equations need be solved, and moreover, the divergence free constraints are satisfied automatically, by construction. The availability of a translation theory for this representation can find application in methods such as the Fast Multipole Method. For illustration of the use of the representation and translation theory we implemented an algorithm for the simulation of Mie scattering off a system of spherical objects of different sizes and dielectric properties using a variant of the T-matrix method. The resulting system was solved using an iterative method based on GMRES. The results of the computations agree well with previous computational and experimental results.