Mathematical group theory has wide applications to the sciences and to other branches of mathematics. Some important examples of current interest are fast matrix multiplication, search in the presence of symmetry, and symmetries to be found in physics and chemistry. Current algorithms do not always scale or are not always practical in implementation. Some levels beyond which current algorithms tend to become impractical are permutations of a million points, matrix group dimensions beyond a few tens, and coset methods (defining equations on groups) beyond 100 million cosets. We call such groups "very large groups".
This project will develop a new class of algorithms for very large groups. The new algorithms will take advantage of the experience of the P.I. and his lab in previous computations and algorithms using terabytes of parallel disk storage. The feasibility of a many-disk approach had previously been shown in a popular demonstration concerning Rubik's cube: Rubik's cube can be solved in 26 moves or less. Both that and more traditional problems will be used to further develop the disk-based language, Roomy.
Emphasis will be given to well-known problems not known to be in polynomial time (centralizer, group intersection, normalizer, etc.). These problems have seen little progress during the last decade. They are considered hard in part due to their close connection with the conjugate group action of a group on itself. In this conjugate action view, a group is seen as a permutation group acting on almost as many points as there are elements in the group itself. In this view, even moderate size groups quickly turn into very large groups under the conjugate action. Novel methods such as the biased tadpole, coupled with the power of the Roomy language, will enable a resumption of progress in this area.
The broader impact lies in the ability to harness these new algorithms and implementations in pursuit of applications outside of group theory such as those mentioned earlier. Researchers outside of group theory have long had the potential to generate groups beyond the capabilities of standard software, such as the free and open source GAP package. Extending the capabilities of GAP and other familiar tools will enable new discoveries. The further development of the Roomy platform is also an important byproduct, whose value will extend far beyond its group theory origins.
The emphasis of this project was on techniques from computational group theory (the use of mathematical symmetries), and the development of algorithms for scalable data structures. The techniques were applied to computational chemistry, high energy physics, BDDs (binary decision diagrams for formal verification of protocols and software), computation with large mathematical permutations. An additional broader outcome concerns educational infrastructure. Two PhD students have completed a PhD in computer science as a result of this work, and a third PhD student defended and will graduate in early 2013. A fourth, undergraduate student (Tyler Denniston) contributed to research on reversible debuggers, received an honorable mention from the Computer Research Association, and has now joined PhD program at MIT. Each of the three PhD students produced a separate open source scientific software package, which is freely available to others. Daniel Kunkle produced the Roomy package (http://roomy.sourceforge.net), which enables software requiring large memory to expand after exhausting available RAM on a local computer. Roomy uses the parallel disks of a computer cluster to emulate large RAM (many terabytes) of a single computer, while extending standard RAM-based data structures and lower-level algorithms to operate in this new regime. Xin Dong extended Geant4 (http://http://geant4.cern.ch; a million-line C++ program from CERN, home of the large hadron collider). Geant4 is a toolkit for the simulation of the passage of particles through matter. It is used by thousands of scientists and engineers for nuclear and accelerator physics, for medical science, and for space sicnece. Geant4 was originally designed to use only a single thread. It was extended to Geant4-MT (multi-threaded) to efficiently use the many cores of today's computer chips. Geant4-MT transparently and scalably runs on many-core architectures, including Intel's Xeon Phi. The software was successfully shown to scale efficiently on the 61 cores available on one Xeon Phi chip. Based on this work, the Geant4 developers merged Geant4-MT with the standard Geant4 software distribution, so as to make it available to all users. Vlad Slavici extended the MADNESS software for computational chemistry (www.csm.ornl.gov/ccsg/html/projects/madness.html; Multiresolution ADaptive NumErical Scientific Simulation). The MADNESS software was accelerated by using the NVIDIA GPUs on the Titan supercomputer. MADNESS is a simulation framework that implements a set of basic operations that are used in computational chemistry, nuclear physics and other related ?elds employing quantum mechanics.
