In this dissertation, we explore parallel algorithms for general N-Body problems in high dimensions, and their applications in machine learning and image analysis on distributed infrastructures. In the first part of this work, we proposed and developed a set of basic tools built on top of Message Passing Interface and OpenMP for massively parallel nearest neighbors search. In particular, we present a distributed tree structure to index data in arbitrary number of dimensions, and a novel algorithm that eliminate the need for collective coordinate exchanges during tree construction. To the best of our knowledge, our nearest neighbors package is the first attempt that scales to millions of cores in up to a thousand dimensions. Based on our nearest neighbors search algorithms, we present "ASKIT", a parallel fast kernel summation tree code with a new near-far field decomposition and a new compact representation for the far field. Specially our algorithm is kernel independent. The efficiency of new near far decomposition depends only on the intrinsic dimensionality of data, and the new far field representation only relies on the rand of sub-blocks of the kernel matrix. In the second part, we developed a Bayesian inference framework and a variational formulation for a MAP estimation of the label field for medical image segmentation. In particular, we propose new representations for both likelihood probability and prior probability functions, as well as their fast calculation. Then a parallel matrix free optimization algorithm is given to solve the MAP estimation. Our new prior function is suitable for lots of spatial inverse problems. Experimental results show our framework is robust to noise, variations of shapes and artifacts.

We consider the curved N-body problem, N > 2, on a surface of constant Gaussian curvature κ ≠ 0; i.e., on spheres S2κ, for κ > 0, and on hyperbolic manifolds H2κ, for κ < 0. Our goal is to define and study relative equilibria, which are orbits whose mutual distances remain constant during the motion. We find new relative equilibria in the curved N-body problem for N = 4, and see whether bifurcations occur when passing through κ = 0. After obtaining a criterion for the existence of quadrilateral configurations on the equator of the sphere, we study two restricted 4-body problems: One in which two bodies are massless , and the second in which only one body is massless. In the former we prove the evidence for square-like relative equilibria, whereas in the latter we discuss the existence of kite-shaped relative equilibria. We will further study the 5-body problem on surfaces of constant curvature. Four of the masses arranged at the vertices of a square, and the fifth mass at the north pole of S2κ, when the curvature is positive, it is shown that relative equilibria exists when the four masses at the vertices of the square are either equal or two of them are infinitesimal, such that they do not affect the motion of the remaining three masses. In the hyperbolic case H2κ, κ < 0, there exist two values for the angular velocity which produce negative elliptic relative equilibria when the masses at the vertices of the square are equal. We also show that the square pyramidal relative equilibria with non-equal masses do not exist in H2κ. Based on the work of Florin Diacu on the existence of relative equilibria for 3-body problem on the equator of S2κ, we investigate the motion of more than three bodies. Furthermore, we study the motion of the negative curved 2-and 3-centre problems on the Poincaré upper semi-plane model. Using this model, we prove that the 2-centre problem is integrable, and we study the dynamics around the equilibrium point. Further, we analyze the singularities of the 3- centre problem due to the collision; i.e., the configurations for which at least two bodies have identical coordinates. / Graduate

In this thesis we investigate the existence and stability of periodic solutions of Hamiltonian systems with a discrete symmetry. The global existence of periodic motions can be proven using the classical techniques of the calculus of variations; our particular interest is in how the stability type of the solutions thus obtained can be determined analytically using solely the variational problem and the symmetries of the system -- we make no use of numerical or perturbation techniques. Instead, we use a method introduced in [41] in the context of a special case of the three-body problem. Using techniques from symplectic geometry, and specifically the Maslov index for curves of Lagrangian subspaces along the minimizing trajectories, we verify conditions which preclude the existence of eigenvalues of the monodromy matrix on the unit circle. We study the applicability of this method in two specific cases. Firstly, we consider another special case from celestial mechanics: the hip-hop solutions of the 2N-body problem. This is a family of Z_2-symmetric, periodic orbits which arise as collision-free minimizers of the Lagrangian action on a space of symmetric loops [14, 53]. Following a symplectic reduction, it is shown that the hip-hop solutions are brake orbits which are generically hyperbolic on the reduced energy-momentum surface. Secondly we consider a class of natural Hamiltonian systems of two degrees of freedom with a homogeneous potential function. The associated action functional is unbounded above and below on the function space of symmetric curves, but saddle points can be located by minimization subject to a certain natural constraint of a type first considered by Nehari [37, 38]. Using the direct method of the calculus of variations, we prove the existence of symmetric solutions of both prescribed period and prescribed energy. In the latter case, we employ a variational principle of van Groesen [55] based upon a modification of the Jacobi functional, which has not been widely used in the literature. We then demonstrate that the (constrained) minimizers are again hyperbolic brake orbits; this is the first time the method has been applied to solutions which are not globally minimizing. / Thesis (Ph.D, Mathematics & Statistics) -- Queen's University, 2013-09-25 10:47:53.257

In the context of future human space exploration missions in the solar system (with an horizon of 2025) and according to the roadmap proposed by ISECG (International Space Exploration Coordination Group) [1], a new step could be to maintain as an outpost, at one of the libration points of the Earth-Moon system, a space station. This would ease access to far destinations as Moon, Mars and asteroids and would allow testing some innovative technologies, before employing them for far distant human missions. One of the main challenges will be to maintain permanently, and ensure on board crew health thanks to an autonomous space medical center docked to the proposed space station, as a Space haven. Then the main problem to solve is to manage the station servitude, during deployment (modules integration) and operational phase. Challenges lie, on a global point of view, in the design of the operational scenarios and, on a local point of view, in trajectories selection, so as to minimize velocity increments (energy consumption) and transportation duration (crew safety). Which recommendations could be found out as far as trajectories optimization is concerned, that would fulfill energy consumption, transportation duration and safety criterion? What would technological hurdles be to rise for the building of such Space haven? What would be performances to aim at for critical sub-systems? Expected results of this study could point out research and development perspectives for human spaceflight missions and above all, in transportation field for long lasting missions. Thus, the thesis project, presented here, aims starting from global system life-cycle decomposition, to identify by phase operational scenario and optimize resupply vehicle mission. The main steps of this project consist of: - Bibliographical survey, that covers all involved disciplines like mission analysis (Astrodynamics, Orbital mechanics, Orbitography, N-Body Problem, Rendezvous…), Applied Mathematics, Optimization, Systems Engineering…. - Entire system life-cycle analysis, so as to establish the entire set of scenarios for deployment and operations (nominal cases, degraded cases, contingencies…) and for all trajectories legs (Low Earth Orbit, Transfer, Rendezvous, re-entry…) - Trade-off analysis for Space Station architecture - Modeling of the mission legs trajectories - Trajectories optimization Three main scenarios have been selected from the results of the preliminary design of the Space Station, named THOR: the Space Station deployment, the resupply cargo missions and the crew transportation. The deep analysis of those three main steps pointed out the criticality of the rendezvous strategies in the vicinity of Lagrangian points. A special effort has been set on those approach maneuvers. The optimization of those rendezvous trajectories led to consolidate performances (in term of energy and duration) of the global transfer from the Earth to the Lagrangian point neighborhood and return. Finally, recommendations have been deduced that support the Lagrangian points importance for next steps of Human Spaceflight exploration of the Solar system.

Fast algorithms for potential evaluation in N-body problems often tend to be extremely abstract and complex. This thesis presents a simple, hierarchical approach to solving the potential evaluation problem in O(n) time. The approach is developed in the field of electrostatics and can be extended to N-body problems in general. Herein, the potential vector is expressed as a product of the potential matrix and the charge vector. The potential matrix itself is a product of component matrices. The potential function satisfies the Laplace equation and is hence expressed as a linear combination of spherical harmonics, which form the general solutions of the Laplace equation. The orthogonality of the spherical harmonics is exploited to reduce execution time. The duality of the various lists in the algorithm is used to reduce storage and computational complexity. A smart tree-construction strategy leads to efficient parallelism at computation intensive stages of the algorithm. The computational complexity of the algorithm is better than that of the Fast Multipole Algorithm, which is one of the fastest contemporary algorithms to solve the potential evaluation problem. Experimental results show that accuracy of the algorithm is comparable to that of the Fast Multipole Algorithm. However, this approach uses some implementation principles from the Fast Multipole Algorithm. Parallel efficiency and scalability of the algorithms are studied by the experiments on IBM p690 multiprocessors.

Fast algorithms for potential evaluation in N-body problems often tend to be extremely abstract and complex. This thesis presents a simple, hierarchical approach to solving the potential evaluation problem in O(n) time. The approach is developed in the field of electrostatics and can be extended to N-body problems in general. Herein, the potential vector is expressed as a product of the potential matrix and the charge vector. The potential matrix itself is a product of component matrices. The potential function satisfies the Laplace equation and is hence expressed as a linear combination of spherical harmonics, which form the general solutions of the Laplace equation. The orthogonality of the spherical harmonics is exploited to reduce execution time. The duality of the various lists in the algorithm is used to reduce storage and computational complexity. A smart tree-construction strategy leads to efficient parallelism at computation intensive stages of the algorithm. The computational complexity of the algorithm is better than that of the Fast Multipole Algorithm, which is one of the fastest contemporary algorithms to solve the potential evaluation problem. Experimental results show that accuracy of the algorithm is comparable to that of the Fast Multipole Algorithm. However, this approach uses some implementation principles from the Fast Multipole Algorithm. Parallel efficiency and scalability of the algorithms are studied by the experiments on IBM p690 multiprocessors.

We consider the N-body problem given by quasihomogeneous force functions of the form (C_1)/r^a + (C_2)/r^b (C_1, C_2, a, b constants and a, b positive with a less than or equal to b) and address the fundamentals of homographic solutions. Generalizing techniques of the classical N-body problem, we prove necessary and sufficient conditions for a homographic solution to be either homothetic, or relative equilibrium. We further prove an analogue of the Lagrange-Pizzetti theorem based on our techniques. We also study the central configurations for quasihomogeneous force functions and settle the classification and properties of simultaneous and extraneous central configurations. In the last part of the thesis, we combine these findings with the Lagrange-Pizzetti theorem to show the link between homographic solutions and central configurations, to prove the existence of homographic solutions and to give algorithms for their construction. / Graduate

The following study examines whether the initialisation (multipole expansions at the finest level) and evaluation of the numerical method Fast Multipole Method (FMM) can benefit from implementing SSE instructions. The implementation of SSE-instructions have been studied and compared to the serial case. Moreover, studied parts of the algorithm include arithmetics on complex numbers, and the usage of applying SSE instructions to complex numbers of double precision. In conclusion, the initialisation has not experienced any improvement in terms of throughput by appliying SSE instructions. However, the evaluation reached almost the double speed-up when SSE instructions were applied. The difference in results are most likely due to the structure of the both algorithms. The initialisation is simple, but the evaluation which involves more operations can benefit from SSE instructions. Furthermore, a scheme is proposed for how SSE instructions can be applied to data sets which are not divisable by the unroll factor and to data sets of varying size.

We extend the concept of central configurations to the N-body problem in spaces of nonzero constant curvature. Based on the work of Florin Diacu on relative equilib- ria of the curved N-body problem and the work of Smale on general relative equilibria, we find a natural way to define the concept of central configurations with the effective potentials. We characterize the ordinary central configurations as constrained critical points of the cotangent potential, which helps us to establish the existence of ordi- nary central configurations for any given masses. After these fundamental results, we study central configurations on H2, ordinary central configurations in S3, and special central configurations in S3 in three separate chapters. For central configurations on H2, we generalize the theorem of Moulton on geodesic central configurations, the theorem of Shub on the compactness of central configurations, the theorem of Conley on the index of geodesic central configurations, and the theorem of Palmore on the lower bound for the number of central configurations. We show that all three-body central configurations that form equilateral triangles must have three equal masses. For ordinary central configurations in S3, we construct a class of S3 ordinary central configurations. We study the geodesic central configurations of two and three bodies. Three-body non-geodesic ordinary central configurations that form equilateral trian- gles must have three equal masses. We also put into the evidence some other classes of central configurations. For special central configurations, we show that for any N ≥ 3, there are masses that admit at least one special central configuration. We then consider the Dziobek special central configurations and obtain the central con- figuration equation in terms of mutual distances and volumes formed by the position vectors. We end the thesis with results concerning the stability of relative equilibria associated with 3-body special central configurations. We find that these relative equilibria are Lyapunov stable when confined to S1, and that they are linearly stable on S2 if and only if the angular momentum is bigger than a certain value determined by the configuration. / Graduate

We exhibit multiple periodic, collision-based orbits of the Newtonian n-body problem. Many of these orbits feature regularizable collisions between the masses. We demonstrate existence of the periodic orbits after performing the appropriate regularization. Stability, including linear stability, for the orbits is then computed using a technique due to Roberts. We point out other interesting features of the orbits as appropriate. When applicable, the results are extended to a broader family of orbits with similar behavior.