This thesis presents a top to bottom analysis on designing and implementing fast algorithms for current and future systems. We present new analysis, algorithmic techniques, and implementations of the Fast Multipole Method (FMM) for solving N- body problems. We target the FMM because it is broadly applicable to a variety of scientific particle simulations used to study electromagnetic, fluid, and gravitational phenomena, among others. Importantly, the FMM has asymptotically optimal time complexity with guaranteed approximation accuracy. As such, it is among the most attractive solutions for scalable particle simulation on future extreme scale systems. We specifically address two key challenges. The first challenge is how to engineer fast code for today’s platforms. We present the first in-depth study of multicore op- timizations and tuning for FMM, along with a systematic approach for transforming a conventionally-parallelized FMM into a highly-tuned one. We introduce novel opti- mizations that significantly improve the within-node scalability of the FMM, thereby enabling high-performance in the face of multicore and manycore systems. The second challenge is how to understand scalability on future systems. We present a new algorithmic complexity analysis of the FMM that considers both intra- and inter- node communication costs. Using these models, we present results for choosing the optimal algorithmic tuning parameter. This analysis also yields the surprising prediction that although the FMM is largely compute-bound today, and therefore highly scalable on current systems, the trajectory of processor architecture designs, if there are no significant changes could cause it to become communication-bound as early as the year 2015. This prediction suggests the utility of our analysis approach, which directly relates algorithmic and architectural characteristics, for enabling a new kind of highlevel algorithm-architecture co-design. To demonstrate the scientific significance of FMM, we present two applications namely, direct simulation of blood which is a multi-scale multi-physics problem and large-scale biomolecular electrostatics. MoBo (Moving Boundaries) is the infrastruc- ture for the direct numerical simulation of blood. It comprises of two key algorithmic components of which FMM is one. We were able to simulate blood flow using Stoke- sian dynamics on 200,000 cores of Jaguar, a peta-flop system and achieve a sustained performance of 0.7 Petaflop/s. The second application we propose as future work in this thesis is biomolecular electrostatics where we solve for the electrical potential using the boundary-integral formulation discretized with boundary element methods (BEM). The computational kernel in solving the large linear system is dense matrix vector multiply which we propose can be calculated using our scalable FMM. We propose to begin with the two dielectric problem where the electrostatic field is cal- culated using two continuum dielectric medium, the solvent and the molecule. This is only a first step to solving biologically challenging problems which have more than two dielectric medium, ion-exclusion layers, and solvent filled cavities. Finally, given the difficulty in producing high-performance scalable code, productivity is a key concern. Recently, numerical algorithms are being redesigned to take advantage of the architectural features of emerging multicore processors. These new classes of algorithms express fine-grained asynchronous parallelism and hence reduce the cost of synchronization. We performed the first extensive performance study of a recently proposed parallel programming model, called Concurrent Collections (CnC). In CnC, the programmer expresses her computation in terms of application-specific operations, partially-ordered by semantic scheduling constraints. The CnC model is well-suited to expressing asynchronous-parallel algorithms, so we evaluate CnC using two dense linear algebra algorithms in this style for execution on state-of-the-art mul- ticore systems. Our implementations in CnC was able to match and in some cases even exceed competing vendor-tuned and domain specific library codes. We combine these two distinct research efforts by expressing FMM in CnC, our approach tries to marry performance with productivity that will be critical on future systems. Looking forward, we would like to extend this to distributed memory machines, specifically implement FMM in the new distributed CnC, distCnC to express fine-grained paral- lelism which would require significant effort in alternative models.

We describe the theory and implementation of a multipole method for calculating the modes of microstructured optical fibers (MOFs). We develop tools for exploiting results obtained through the multipole method, including a discrete Bloch transform. Using the multipole method, we study in detail the physical nature of solid core MOF modes, and establish a distinction between localized defect modes and extended modes. Defect modes, including the fundamental mode, can undergo a localization transition we identify with the mode�s cutoff. We study numerically and theoretically the cutoff of the fundamental and the second mode extensively, and establish a cutoff diagram enabling us to predict with accuracy MOF properties, even for exotic MOF geometries. We study MOF dispersion and loss properties and develop unconventional MOF designs with low losses and ultra-flattened near-zero dispersion on a wide wavelength range. Using the cutoff-diagram we explain properties of these MOF designs.

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.

[pt] Este trabalho faz parte de um projeto para a implementação de um programa que possa simular problemas com milhões de graus de liberdade em um computador pessoal. Para isto, combina-se o Método Fast Multipole (FMM) com o Método Expedito dos Elementos de Contorno (EBEM), além de serem utilizados resolvedores iterativos de sistemas de equações. O EBEM é especialmente vantajoso em problemas de complicada topologia, ou que usem funções fundamentais muito complexas. Neste trabalho apresenta-se uma formulação para o Método Fast Multipole (FMM) que pode ser usada para, virtualmente, qualquer função e também para contornos curvos, o que parece ser uma contribuição original. Esta formulação apresenta um formato mais compacto do que as já existentes na literatura, e também pode ser diretamente aplicada a diversos tipos de problemas praticamente sem modificação de sua estrutura básica. É apresentada a validação numérica da formulação proposta. Sua utilização em um contexto do EBEM permite que um programa prescinda de integrações sobre segmentos – mesmo curvos – do contorno quando estes estão distantes do ponto fonte. / [en] This is part of a larger project that aims to develop a program able to simulate problems with millions of degrees of freedom on a personal computer. The Fast Multipole Method (FMM) is combined with the Expedite Boundary Element Method (EBEM) for integration, in the project s final version, with iterative equations solvers. The EBEM is especially advantageous when applied to problems with complicated topology as well as in the case of highly complex fundamental solutions. In this work, a FMM formulation is proposed for the use with virtually any type of fundamental solution and considering curved boundaries, which seems to be an original contribution. This formulation presents a more compact format than the ones shown in the technical literature, and can be directly applied to different kinds of problems without the need of manipulation of its basic structure, being numerically validated for a few applications. Its application in the context of the EBEM leads to the straightforward implementation of higher-order elements for generally curved boundaries that dispenses integration when the boundary segment is relatively far from the source point.

Force field methods are used to investigate the properties of a wide variety of chemical systems on a routine basis. The expression for the electrostatic energy typically does not take into account the anisotropic nature of the atomic electron distribution or the dependence of that distribution on the system geometry. This has been suggested as a cause of the failure of force field methods to reliably predict the behaviour of chemical systems. A method for incorporation of anisotropy and polarisation is described in this work. Anisotropy is modelled by the inclusion of multipole moments centred at atoms whose values are determined by application of the methods of Quantum Chemical Topology. Polarisation, the dependence of the electron distribution on system geometry, is modelled by training machine learning models to predict atomic multipole moments from knowledge of the nuclear positions of a system. The resulting electrostatic method can be implemented for any chemical system. An application to progressively more complex systems is reported, including small organic molecules and larger molecules of biological importance. The accuracy of the method is rigorously assessed by comparison of its predictions to exact interaction energy values. A procedure for generating transferable atomic multipole moment models is defined and tested. The electrostatic method can be combined with the empirical expressions used in force field calculations to describe total system energies by fitting parameters against ab initio conformational energies. Derivatives of the energy are given and the resulting multipolar polarisable force field can be used to perform geometry optimisation calculations. Future applications to conformational searching and problems requiring dynamic descriptions of a system are feasible.

京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第20513号 / 情博第641号 / 新制||情||111(附属図書館) / 京都大学大学院情報学研究科複雑系科学専攻 / (主査)教授 西村 直志, 教授 磯 祐介, 准教授 吉川 仁 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

No description available.

No description available.

The quadrupolar interaction in sodium orthovanadate dodecahydrate, calcium orthovanadate, vanadinite, descloizite, zirconium divanadate, cadmium divanadate, potassium metavanadate and vanadium pentoxide, was studied by nuclear magnetic resonance. The v51 quadrupole coupling constants in these compounds show a strong correlation with the distortion of the tetrahedral symmetry around the vanadium ion. Vanadium pentoxide is an exception and shows a surprisingly small coupling constant. The point multipole model was found to be inadequate for the calculations of the electric field gradients in these compounds. A covalent model provides an explanation of the small magnitude of the coupling constant of vanadium pentoxide. However, because of the numbers of approximations in this model, only a qualitative correlation with the experimental results was achieved. In addition, the chemical shift tensor of the v51 resonance line in a single crystal of vanadium pentoxide was measured to be very large. This result was correlated with a large Van Vleck term in the magnetic susceptibility of vanadium pentoxide. / Thesis / Doctor of Philosophy (PhD)

In this thesis we study multipole moments of axisymmetric spacetimes. Using the recursive definition of the multipole moments of Geroch and Hansen we develop a method for computing all multipole moments of a stationary axisymmetric spacetime without the use of a recursion. This is a generalisation of a method developed by Herberthson for the static case. Using Herberthson’s method we also develop a method for finding a static axisymmetric spacetime with arbitrary prescribed multipole moments, subject to a specified convergence criteria. This method has, in general, a step where one has to find an explicit expression for an implicitly defined function. However, if the number of multipole moments are finite we give an explicit expression in terms of power series. / <p>Note: The two articles are also available in the pdf-file. Report code: LiU-TEK-LIC-2006:4.</p>