Research Experience for Undergraduates, Summer 2015

In the Summer of 2015, with support provided by the NSF, CREST hosted two undergraduates for an REU to work on the DASHMM project. Below you will find details about the program participants, their activities, and the initial announcement for the program.

Program Participants

Victor Tilstra-Smith

Victor Tilstra-Smith is a undergraduate student majoring in Math and Physics at Central College in Pella, Iowa. During the Summer of 2015 he worked under a REU grant at the CREST research center. At CREST he studied the Fast Multipole Method, and helped verify the mathematics for FMM used with Laplace, Yukawa, and Helmholtz equations. He plans to pursue a doctorate in physics.

Annelise Tsueda

Annelise Tsueda is currently an undergraduate student studying Biology and Bioinformatics at Loyola University, Chicago. She has previously participated in research labs focusing on Genetics and Biophysics. During the summer of 2015, she worked under the SI2 grant, on the DASHMM project as an REU student, where she worked on developing abstractions for multipole methods. She is currently pursuing her Master’s degree in Computer Science and hopes to obtain her doctorate soon after that.

Research Performed

There were two main thrusts to the work of Victor and Annelise: verification and development of translation operators for the various Kernels that DASHMM will provide, and the exploration of abstractions to facilitate the development of the general multipole method library. Without careful analysis of the former, DASHMM would be unable to produce accurate results. And with the latter, DASHMM will benefit from some techniques of generic programming that allows the library to function and provide efficient and scalable multipole methods for arbitrary user-defined kernels and applications.

At the end of the program, Annelise and Victor presented their work during a CREST colloquium. The slides of their presentation are here (1.5 MiB, 0 downloads)

Work With Kernels

In Multipole methods, a kernel is a function describing the interaction between two points. DASHMM provides a set of builtin kernels that are widely used in end-science applications, including Laplace, Yukawa, and Helmholtz. There are many ways to compress a kernel function. For instance, one can use Taylor series, SVD, or special functions. For the Laplace, Yukawa, and Helmholtz kernels, DASHMM chooses to use special functions based on the mathematical machinery developed by the research group led by V. Rokhlin and L. Greengard. Compared to other techniques, the use of special functions provides better compression, particularly for high accuracy requirements.

Among the three kernels, there exist open-source implementations for the Laplace and Yukawa kernels. Unfortunately, these implementations were done using Fortran and might not be thread safe. Therefore, some research is done to match the existing implementation with the formulas in the published paper to provide an accurate, efficient, and thread-safe implementation in C.

Unlike the Laplace and Yukawa kernels, there are no available open-source packages for the Helmholtz kernel in three dimensions that work for a wide range of frequencies. Therefore, there are more research activities devoted to this kernel, including writing octave scripts verifying various translation operators in the low- and high-frequency regimes, correcting typos of the formulas in the published papers, understanding the switch from low to high frequency regime, and identifying possible numerical stability, underflow/overflow issues.

Defining Abstractions

The two target methods (FMM and BH) that will be provided by DASHMM have some similarities, but are not identical. By carefully considering the two methods, and another related method, the general features of these methods can be lifted out of the specific implementations. The goal of this is to allow a general interface that will be able to support not only BH and FMM, but any method that can be placed into the framework of the abstraction.

Initially three multipole method applications were created that performed the potential calculation for the gravitational field of a set of point masses in one dimension. This simplified treatment allowed the work to proceed in a way that skipped many of the mathematical niceties that are required in the full 3d case, without qualitatively changing the execution of the methods. These three mini applications formed the base from which the general features of the methods were lifted. The result of this lifting was a C++ application, miniDASHMM, that acts in many ways like the full library. The main abstractions defined were the Node, Expansion and Method objects. In the implementation, Method and Expansion were abstract base classes from which specific use cases were derived.

Node

The Node object is responsible for the construction of the hierarchical subdivision of the physical domain. These Nodes can partition both the source and target points, and take responsibility for calling the methods of the Method class to enact whatever multipole method the user has selected. Before the lifting process, the Nodes in the specific cases were taking care of all of the required work; after lifting, the Nodes do not have to know any details of the Method being employed.

Expansion

The Expansion object is the first major abstraction to come out of the lifting process. This concept encapsulates all the operators that form multipole and local expansions of the potential fields of clusters of sources. In principle a different underlying Kernel would only have to implement a single Expansion class, but different choices of expansion center can increase this number. miniDASHMM has two defined Expansion subclasses that both implement the Laplace Kernel. The first expands around the center of Nodes, and the second expands around the center of mass of the represented source particles. The latter was used to make as close an emulation of the classical Barnes-Hut method as presented by Barnes and Hut.

The Expansion object is independent of both the Node and the Method object. The Expansion knows only about converting between various expansion types.

Method

The Method object is the second major abstraction to come out of the work this summer. This object provides a fixed interface that the Node object can use to enact the Method it represents. The differences in BH and FMM were found to be reducible to a set of five operations that the Method needs to define. These include things like a criterion that will evaluate the usability of a given expansion at a given point, a method to collect new expansions that might be relevant for a given node, and a way to process information from the parent of a node so that it will apply for the node itself.

The Method object does use methods from Node, but these are all things that any tree would provide, such as finding links to children, or parents. Also, the Method object, in the current implementation provides a factory for the Expansion being used. This latter weakness could easily have been addressed with some more time.

Results

The result, miniDASHMM, is a flexible, extensible application for performing multipole methods in 1d. The work done in defining the abstractions for the mini-app will apply directly to the DASHMM library. The resulting mini-app preforms at the expected scaling with the number of particles for each method, and meets all expected error bounds guaranteed by the methods.


Program Annoucement

The Center for Research in Extreme Scale Technologies (CREST) invites applications for a 10 week summer REU program. Students will participate in computational science research at a world-class institution, while learning about emerging high-performance computing trends and while gaining hands-on research experience. Students will work directly with faculty and researchers at CREST to develop DASHMM, a computational toolkit being developed at CREST to leverage the power of dynamic adaptive runtime techniques to improve the scalability and efficiency of multipole methods.

Program Details

The program, sponsored by the National Science Foundation, funds two students for 10 weeks, during which they will work intensively with CREST members on projects related to DASHMM. The interests of the students will direct the specific project that each student participates in. Topics include, but are not limited to: developing novel visualizations for existing multipole method codes, implementing new physical models for inclusion with DASHMM, or using DASHMM in end-science applications.

The program will begin on the 25th of May and end on the 31st of July. Students will be given a stipend of $5000.

Successful applicants will:

  • Be a US citizen enrolled full-time in an accredited US institution in good academic standing
  • Have full time availability during the program period (May 25, 2015 through July 31, 2015)
  • Be interested in one or more of the following: multipole methods, computer science, computational science, N-body like problems, computational electromagnetics, scientific visualization
  • Have the ability to work in a team of like-minded individuals
  • Be self-motivated and goal-oriented.

How to Apply

Interested applicants should send the following to jdebuhr [at] indiana.edu, with the subject line “REU”

  • A letter of interest which includes the applicant's background and interest in the REU program, prior research or REU experience, experience with computational methods, a list of programming proficiencies (for example, C, C++, OpenGL, etc.)
  • An unofficial transcript
  • A letter of recommendation from a Professor or Research Supervisor. Applicants should arrange to have the letter sent directly from their letter writer.

Applications will be reviewed as they are received.