Explore the vast range of titles available.

The “gravitational million-body problem,” to model the dynamical evolution of a self-gravitating, collisional N -body system with ∼10 6 particles over many relaxation times, remains a major challenge in computational astrophysics. Unfortunately, current techniques to model such systems suffer from severe limitations. A direct N -body simulation with more than 10 5 particles can require months or even years to complete, while an orbit-sampling Monte Carlo approach cannot adequately model the dynamics in a dense cluster core, particularly in the presence of many black holes. We have developed a new technique combining the precision of a direct N -body integration with the speed of a Monte Carlo approach. Our Rapid And Precisely Integrated Dynamics code, the RAPID code, statistically models interactions between neighboring stars and stellar binaries while integrating directly the orbits of stars or black holes in the cluster core. This allows us to accurately simulate the dynamics of the black holes in a realistic globular cluster environment without the burdensome N 2 scaling of a full N -body integration. We compare RAPID models of idealized globular clusters to identical models from the direct N -body and Monte Carlo methods. Our tests show that RAPID can reproduce the half-mass radii, core radii, black hole ejection rates, and binary properties of the direct N -body models far more accurately than a standard Monte Carlo integration while remaining significantly faster than a full N -body integration. With this technique, it will be possible to create more realistic models of Milky Way globular clusters with sufficient rapidity to explore the full parameter space of dense stellar clusters.

The modeling of collisional N-body stellar systems is a topic of great current interest in several branches of astrophysics and cosmology. These systems are dominated by the physics of relaxation, the collective effect of many weak, random gravitational encounters between stars. They connect directly to our understanding of star clusters, and to the formation of exotic objects such as X-ray binaries, pulsars, and massive black holes. As a prototypical multi-physics, multi-scale problem, the numerical simulation of such systems is computationally intensive, and can only be achieved through high-performance computing. The goal of this thesis is to present parallelization and optimization strategies that can be used to develop efficient computational tools for simulating collisional N-body systems. This leads to major advances: 1) From an astrophysics perspective, these tools enable the study of new physical regimes out of reach by previous simulations. They also lead to much more complete parameter space exploration, allowing direct comparison of numerical results to observational data. 2) On the high-performance computing front, efficient parallelization of a multi-component application requires the meticulous redesign of the various components, as well as innovative parallelization techniques. Many of the challenges faced in this process lie at the very heart of high-performance computing research, including achieving optimal load balancing, maximizing utilization of computational resources, and making effective use of different parallel platforms. For modeling collisional N-body systems, a Monte Carlo approach provides ideal balance between speed and accuracy, as opposed to the more accurate but less scalable direct N-body method. We describe the development of a new version of the Cluster Monte Carlo (CMC) code capable of simulating systems with a realistic number of stars, while accounting for all important physical processes. This efficient and scalable parallel version of CMC runs on both GPUs and distributed-memory architectures. We introduce various parallelization and optimization strategies that include the use of best-suited data structures, adaptive data partitioning schemes, parallel random number generation, parallel I/O, and optimized parallel algorithms, resulting in a very desirable scalability of the run-time with the processor number.

The \"gravitational million-body problem,\" to model the dynamical evolution of a self-gravitating, collisional N-body system with ~10^6 particles over many relaxation times, remains a major challenge in computational astrophysics. Unfortunately, current techniques to model such systems suffer from severe limitations. A direct N-body simulation with more than 10^5 particles can require months or even years to complete, while an orbit-sampling Monte Carlo approach cannot adequately model the dynamics in a dense cluster core, particularly in the presence of many black holes. We have developed a new technique combining the precision of a direct N-body integration with the speed of a Monte Carlo approach. Our Rapid And Precisely Integrated Dynamics code, the RAPID code, statistically models interactions between neighboring stars and stellar binaries while integrating directly the orbits of stars or black holes in the cluster core. This allows us to accurately simulate the dynamics of the black holes in a realistic globular cluster environment without the burdensome N^2 scaling of a full N-body integration. We compare RAPID models of idealized globular clusters to identical models from the direct N-body and Monte Carlo methods. Our tests show that RAPID can reproduce the half-mass radii, core radii, black hole ejection rates, and binary properties of the direct N-body models far more accurately than a standard Monte Carlo integration while remaining significantly faster than a full N-body integration. With this technique, it will be possible to create more realistic models of Milky Way globular clusters with sufficient rapidity to explore the full parameter space of dense stellar clusters.

Hierarchical triple-star systems are expected to form frequently via close binary-binary encounters in the dense cores of globular clusters. In a sufficiently inclined triple, gravitational interactions between the inner and outer binary can cause large-amplitude oscillations in the eccentricity of the inner orbit (\"Lidov-Kozai cycles\"), which can lead to a collision and merger of the two inner components. In this paper we use Monte Carlo models of dense star clusters to identify all triple systems formed dynamically and we compute their evolution using a highly accurate three-body integrator which incorporates relativistic and tidal effects. We find that a large fraction of these triples evolve through a non-secular dynamical phase which can drive the inner binary to higher eccentricities than predicted by the standard secular perturbation theory (even including octupole-order terms). We place constraints on the importance of Lidov-Kozai-induced mergers for producing: (i) gravitational wave sources detectable by Advanced LIGO (aLIGO), for triples with an inner pair of stellar black holes; and (ii) blue straggler stars, for triples with main-sequence-star components. We find a realistic aLIGO detection rate of black hole mergers due to the Lidov-Kozai mechanism of 1yr^-1, with about 20% of these having a finite eccentricity when they first chirp into the aLIGO frequency band. While rare, these events are likely to dominate among eccentric compact object inspirals that are potentially detectable by aLIGO. For blue stragglers, we find that the Lidov-Kozai mechanism can contribute only up to ~10% of their total numbers in globular clusters.

The predicted rate of binary black hole mergers from galactic fields can vary over several orders of magnitude and is extremely sensitive to the assumptions of stellar evolution. But in dense stellar environments such as globular clusters, binary black holes form by well-understood gravitational interactions. In this letter, we study the formation of black hole binaries in an extensive collection of realistic globular cluster models. By comparing these models to observed Milky Way and extragalactic globular clusters, we find that the mergers of dynamically-formed binaries could be detected at a rate of ~100 per year, potentially dominating the binary black hole merger rate. We also find that a majority of cluster-formed binaries are more massive than their field-formed counterparts, suggesting that Advanced LIGO could identify certain binaries as originating from dense stellar environments.

Our current understanding of the stellar initial mass function and massive star evolution suggests that young globular clusters may have formed hundreds to thousands of stellar-mass black holes, the remnants of stars with initial masses from \\(\\sim 20 - 100\\, M_\\odot\\). Birth kicks from supernova explosions may eject some black holes from their birth clusters, but most should be retained. Using a Monte Carlo method we investigate the long-term dynamical evolution of globular clusters containing large numbers of stellar black holes. We describe numerical results for 42 models, covering a range of realistic initial conditions, including up to \\(1.6\\times10^6\\) stars. In almost all models we find that significant numbers of black holes (up to \\(\\sim10^3\\)) are retained all the way to the present. This is in contrast to previous theoretical expectations that most black holes should be ejected dynamically within a few Gyr. The main reason for this difference is that core collapse driven by black holes (through the Spitzer \"mass segregation instability\") is easily reverted through three-body processes, and involves only a small number of the most massive black holes, while lower-mass black holes remain well-mixed with ordinary stars far from the central cusp. Thus the rapid segregation of stellar black holes does not lead to a long-term physical separation of most black holes into a dynamically decoupled inner core, as often assumed previously. Combined with the recent detections of several black hole X-ray binary candidates in Galactic globular clusters, our results suggest that stellar black holes could still be present in large numbers in many globular clusters today, and that they may play a significant role in shaping the long-term dynamical evolution and the present-day dynamical structure of many clusters.

The maximum clique problem is a well known NP-Hard problem with applications in data mining, network analysis, information retrieval and many other areas related to the World Wide Web. There exist several algorithms for the problem with acceptable runtimes for certain classes of graphs, but many of them are infeasible for massive graphs. We present a new exact algorithm that employs novel pruning techniques and is able to find maximum cliques in very large, sparse graphs quickly. Extensive experiments on different kinds of synthetic and real-world graphs show that our new algorithm can be orders of magnitude faster than existing algorithms. We also present a heuristic that runs orders of magnitude faster than the exact algorithm while providing optimal or near-optimal solutions. We illustrate a simple application of the algorithms in developing methods for detection of overlapping communities in networks.

We present a new parallel code for computing the dynamical evolution of collisional N-body systems with up to N~10^7 particles. Our code is based on the the Henon Monte Carlo method for solving the Fokker-Planck equation, and makes assumptions of spherical symmetry and dynamical equilibrium. The principal algorithmic developments involve optimizing data structures, and the introduction of a parallel random number generation scheme, as well as a parallel sorting algorithm, required to find nearest neighbors for interactions and to compute the gravitational potential. The new algorithms we introduce along with our choice of decomposition scheme minimize communication costs and ensure optimal distribution of data and workload among the processing units. The implementation uses the Message Passing Interface (MPI) library for communication, which makes it portable to many different supercomputing architectures. We validate the code by calculating the evolution of clusters with initial Plummer distribution functions up to core collapse with the number of stars, N, spanning three orders of magnitude, from 10^5 to 10^7. We find that our results are in good agreement with self-similar core-collapse solutions, and the core collapse times generally agree with expectations from the literature. Also, we observe good total energy conservation, within less than 0.04% throughout all simulations. We analyze the performance of the code, and demonstrate near-linear scaling of the runtime with the number of processors up to 64 processors for N=10^5, 128 for N=10^6 and 256 for N=10^7. The runtime reaches a saturation with the addition of more processors beyond these limits which is a characteristic of the parallel sorting algorithm. The resulting maximum speedups we achieve are approximately 60x, 100x, and 220x, respectively.

The maximum clique problem is a well known NP-Hard problem with applications in data mining, network analysis, informatics, and many other areas. Although there exist several algorithms with acceptable runtimes for certain classes of graphs, many of them are infeasible for massive graphs. We present a new exact algorithm that employs novel pruning techniques to very quickly find maximum cliques in large sparse graphs. Extensive experiments on several types of synthetic and real-world graphs show that our new algorithm is up to several orders of magnitude faster than existing algorithms for most instances. We also present a heuristic variant that runs orders of magnitude faster than the exact algorithm, while providing optimal or near-optimal solutions.

Despite substantial exposure to infectious pulmonary tuberculosis (TB) cases, some household contacts (HHC) never acquire latent TB infection (LTBI). Characterizing these \"resisters\" can inform who to study immunologically for the development of TB vaccines. We enrolled HHCs of culture-confirmed adult pulmonary TB in India who underwent LTBI testing using tuberculin skin test (TST) and QuantiFERON TB Gold Test-in-tube (QFT-GIT) at baseline and, if negative by both (<5mm TST and <0.35IU/mL QFT-GIT), underwent follow-up testing at 4-6 and/or 12 months. We defined persons with persistently negative LTBI tests at both baseline and followup as pLTBI- and resisters as those who had a high exposure to TB using a published score and remained pLTBI-. We calculated the proportion of resisters overall and resisters with complete absence of response to LTBI tests (0mm TST and/or QFT-GIT <0.01 IU/ml). Using random effects Poisson regression, we assessed factors associated with pLTBI-. Of 799 HHCs in 355 households, 67 (8%) were pLTBI- at 12 months; 52 (6.5%) pLTBI- in 39 households were resisters. Complete absence of response to LTBI tests was found in 27 (53%) resisters. No epidemiological characteristics were associated with the pLTBI- phenotype. LTBI free resisters among HHC exist but are uncommon and are without distinguishing epidemiologic characteristics. Assessing the genetic and immunologic features of such resister individuals is likely to elucidate mechanisms of protective immunity to TB.