Introduction to the Fast Multipole Method Topics in Computational Biophysics, Theory, and Implementation

Introduction to the Fast Multipole Method introduces the reader to the theory and computer implementation of the Fast Multipole Method. It covers the topics of Laplaces equation, spherical harmonics, angular momentum, the Wigner matrix, the addition theorem for solid harmonics, and lattice sums for periodic boundary conditions, along with providing a complete, self-contained explanation of the math of the method, so that anyone having an undergraduate grasp of calculus should be able to follow the material presented. The authors derive the Fast Multipole Method from first principles and systematically construct the theory connecting all the parts.Key FeaturesIntroduces each topic from first principlesDerives every equation presented, and explains each step in its derivationBuilds the necessary theory in order to understand, develop, and use the methodDescribes the conversion from theory to computer implementationGuides through code optimization and parallelization

1. Legendre Polynomials 1.1 Potential of a Point Charge Located on the z-Axis 1.2 Laplaces Equation 1.3 Solution of Laplaces Equation in Cartesian Coordinates 1.4 Laplaces Equation in Spherical-Polar Coordinates 1.5 Orthogonality and Normalization of Legendre Polynomials 1.6 Expansion of an Arbitrary Function in Legendre Series 1.7 Recurrence Relations for Legendre Polynomials 1.8 Analytic Expressions for First Few Legendre Polynomials 1.9 Symmetry Properties of Legendre Polynomials2. Associated Legendre Functions 2.1 Generalized Legendre Equation 2.2 Associated Legendre Functions 2.3 Orthogonality and Normalization of Associated Legendre Functions 2.4 Recurrence Relations for Associated Legendre Functions 2.5 Derivatives of Associated Legendre Functions 2.6 Analytic Expression for First Few Associated Legendre Functions 2.7 Symmetry Properties of Associated Legendre Functions3. Spherical Harmonics 3.1 Spherical Harmonics Functions 3.2 Orthogonality and Normalization of Spherical Harmonics 3.3 Symmetry Properties of Spherical Harmonics 3.4 Recurrence Relations for Spherical Harmonics 3.5 Analytic Expression for the First Few Spherical Harmonics 3.6 Nodal Properties of Spherical Harmonics4. Angular Momentum 4.1 Rotation Matrices 4.2 Unitary Matrices 4.3 Rotation Operator 4.4 Commutative Properties of the Angular Momentum 4.5 Eigenvalues of the Angular Momentum 4.6 Angular Momentum Operator in Spherical Polar Coordinates 4.7 Eigenvectors of the Angular Momentum Operator 4.8 Characteristic Vectors of the Rotation Operator 4.9 Rotation of Eigenfunctions of Angular Momentum5. Wigner Matrix 5.1 The Euler Angles 5.2 Wigner Matrix for j = 1 5.3 Wigner Matrix for j = 1/2 5.4 General Form of the Wigner Matrix Elements 5.5 Addition Theorem for Spherical Harmonics6. ClebschGordan Coefficients 6.1 Addition of Angular Momenta 6.2 Evaluation of ClebschGordan Coefficients 6.3 Addition of Angular Momentum and Spin 6.4 Rotation of the Coupled Eigenstates of Angular Momentum7. Recurrence Relations for Wigner Matrix 7.1 Recurrence Relations with Increment in Index m 7.2 Recurrence Relations with Increment in Index k8. Solid Harmonics 8.1 Regular and Irregular Solid Harmonics 8.2 Regular Multipole Moments 8.3 Irregular Multipole Moments 8.4 Computation of Electrostatic Energy via Multipole Moments 8.5 Recurrence Relations for Regular Solid Harmonics 8.6 Recurrence Relations for Irregular Solid Harmonics 8.7 Generating Functions for Solid Harmonics 8.8 Addition Theorem for Regular Solid Harmonics 8.9 Addition Theorem for Irregular Solid Harmonics 8.10 Transformation of the Origin of Irregular Harmonics 8.11 Vector Diagram Approach to Multipole Translations9. Electrostatic Force 9.1 Gradient of Electrostatic Potential 9.2 Differentiation of Multipole Expansion 9.3 Differentiation of Regular Solid Harmonics in Spherical Polar Coordinates 9.4 Differentiation of Spherical Polar Coordinates 9.5 Differentiation of Regular Solid Harmonics in Cartesian Coordinates 9.6 FMM Force in Cartesian Coordinates10. Scaling of Solid Harmonics 10.1 Optimization of Expansion of Inverse Distance Function 10.2 Scaling of Associated Legendre Functions 10.3 Recurrence Relations for Scaled Regular Solid Harmonics 10.4 Recurrence Relations for Scaled Irregular Solid Harmonics 10.5 First Few Terms of Scaled Solid Harmonics 10.6 Design of Computer Code for Computation of Solid Harmonics 10.7 Program Code for Computation of Multipole Expansions 10.8 Computation of Electrostatic Force Using Scaled Solid Harmonics 10.9 Program Code for Computation of Force11. Scaling of Multipole Translations 11.1 Scaling of Multipole Translation Operations 11.2 Program Code for M2M Translation 11.3 Program Code for M2L Translation 11.4 Program Code for L2L Translation12. Fast Multipole Method 12.1 Near and Far Fields: Prerequisites for the Use of the Fast Multipole Method 12.2 Series Convergence and Truncation of Multipole Expansion 12.3 Hierarchical Division of Boxes in the Fast Multipole Method 12.4 Far Field 12.5 NF and FF Pair Counts 12.6 FMM Algorithm 12.7 Accuracy Assessment of Multipole Operations13. Multipole Translations along the z-Axis 13.1 M2M Translation along the z-Axis 13.2 L2L Translation along the z-Axis 13.3 M2L Translation along the z-Axis14. Rotation of Coordinate System 14.1 Rotation of Coordinate System to Align the z-axis with the Axis of Translation 14.2 Rotation Matrix 14.3 Computation of Scaled Wigner Matrix Elements with Increment in Index m 14.4 Computation of Scaled Wigner Matrix Elements with Increment in Index k 14.5 Program Code for Computation of Scaled Wigner Matrix Elements Based on the k-set 14.6 Program Code for Computation of Scaled Wigner Matrix Elements Based on the m-set15. Rotation-Based Multipole Translations 15.1 Assembly of Rotation Matrix 15.2 Rotation-Based M2M Operation 15.3 Rotation-Based M2L Operation 15.4 Rotation-Based L2L Operation16. Periodic Boundary Condition 16.1 Principles of Periodic Boundary Condition 16.2 Lattice Sum for Energy in Periodic FMM 16.3 Multipole Moments of the Central Super-Cell 16.4 Far-Field Contribution to the Lattice Sum for Energy 16.5 Contribution of the Near-Field Zone into the Central Unit Cell 16.6 Derivative of Electrostatic Energy on Particles in the Central Unit Cell 16.7 Stress Tensor 16.8 Analytic Expression for Stress Tensor 16.9 Lattice Sum for Stress Tensor

Victor Anisimovis an Application Performance Engineer at the Argonne Leadership Computing Facility. He holds a Ph.D. degree in Physical Chemistry from the Institute of Chemical Physics of the Russian Academy of Sciences (1997), which was followed by 5 years of computational chemistry software development with Fujitsu, where his team developed the linear scaling semi-empirical quantum chemistry code LocalSCF that expanded the limits of the approximate electronic structure theory to millions of atoms. He performed postdoctoral work at the University of Maryland at Baltimore (2003-2008), and at the University of Texas at Houston (2008-2011), improving molecular dynamics methods and contributing to the CHARMM code. In the National Center for Supercomputing Applications at the University of Illinois at Urbana-Champaign (2011-2019), Dr. Anisimov held the position of Senior Research Scientist, conducted application support for petascale resource allocation teams on the Blue Waters supercomputer, optimized various application codes, and improved the performance and scaling profiles of coupled cluster singles and doubles electronic structure method in NWChem code. Dr. Anisimov works on the faithful representation of long-range electrostatic interactions in large-scale molecular simulations, near-neighbor communication algorithms, and linear-scaling methods. He specializes in performance optimization and fidelity improvements of electronic structure and soft matter simulation application codes on exascale platforms.James J. P. Stewart pioneered the use of semiempirical quantum chemistry methods in research and teaching. After teaching at the University of Strathclyde in Glasgow, Scotland, he became a researcher at the United States Air Force Academy, then taught as an adjoint professor at the University of Colorado. For the past 30 years, his company, Stewart Computational Chemistry, has been marketing his program, MOPAC, which now has over 30,000 licensed users and groups worldwide. Dr. Stewart has authored over 150 research papers and his works have been cited over 38,000 times.