Browsing by Author "Fushman, David"
Now showing 1 - 2 of 2
Results Per Page
Sort Options
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 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.