Tech Reports in Computer Science and Engineering
Permanent URI for this communityhttp://hdl.handle.net/1903/5
The technical reports collections in this community are deposited by the Library of the Computer Science department. If you have questions about these collections, please contact library staff at library@cs.umd.edu
Browse
10 results
Search Results
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 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 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 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 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 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 Kernelized Renyi distance for subset selection and similarity scoring(2011-10-12) Srinivasan, Balaji Vasan; Duraiswami, RamaniRenyi entropy refers to a generalized class of entropies that have been used in several applications. In this work, we derive a non-parametric distance between distributions based on the quadratic Renyi entropy. The distributions are estimated via Parzen density estimates. The quadratic complexity of the distance evaluation is mitigated with GPU-based parallelization. This results in an efficiently evaluated non-parametric entropic distance - the kernelized Renyi distance or the KRD. We adapt the KRD into a similarity measure and show its application to speaker recognition. We further extend KRD to measure dissimilarities between distributions and illustrate its applications to statistical subset selection and dictionary learning for object recognition and pose estimation.Item 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 Random sampling for estimating the performance of fast summations(2010-10-18) Srinivasan, Balaji Vasan; Duraiswami, RamaniSummation of functions of N source points evaluated at M target points occurs commonly in many applications. To scale these approaches for large datasets, many fast algorithms have been proposed. In this technical report, we propose a Chernoff bound based efficient approach to test the performance of a fast summation algorithms providing a probabilistic accuracy. We further validate and use our approach in separate comparisons.Item Partial least squares on graphical processor for efficient pattern recognition(2010-10-18) Srinivasan, Balaji Vasan; Schwartz, William Robson; Duraiswami, Ramani; Davis, LarryPartial least squares (PLS) methods have recently been used for many pattern recognition problems in computer vision. Here, PLS is primarily used as a supervised dimensionality reduction tool to obtain effective feature combinations for better learning. However, application of PLS to large datasets is hindered by its higher computational cost. We propose an approach to accelerate the classical PLS algorithm on graphical processors to obtain the same performance at a reduced cost. Although, PLS modeling is practically an offline training process, accelerating it helps large scale modeling. The proposed acceleration is shown to perform well and it yields upto ~30X speedup, It is applied on standard datasets in human detection and face recognition.