L’acceptation et l’utilisation des services Web en industrie se développent de par leursupport au développement d’application distribuées comme compositions d’entitéslogicielles plus simples appelées services. En complément à la vérification, le testpermet de vérifier la correction d’une implémentation binaire (code source nondisponible) par rapport à une spécification. Dans cette thèse, nous proposons uneapproche boîte-noire du test de conformité de compositions de services centralisées(orchestrations). Par rapport à l’état de l’art, nous développons une approchesymbolique de façon à éviter des problèmes d’explosion d’espace d’état dus à la largeutilisation de données XML dans les services Web. Cette approche est basée sur desmodèles symboliques (STS), l’exécution symbolique de ces modèles et l’utilisationd’un solveur SMT. De plus, nous proposons une approche de bout en bout, quiva de la spécification à l’aide d’un langage normalisé d’orchestration (ABPEL) etde la possible description d’objectifs de tests à la concrétisation et l’exécution enligne de cas de tests symboliques. Un point important est notre transformation demodèle entre ABPEL et les STS qui prend en compte les spécifications sémantiquesd’ABPEL. L’automatisation de notre approche est supportée par un ensemble d’outilsque nous avons développés. / Web services are gaining industry-wide acceptance and usage by fostering the developmentof distributed applications out of the composition of simpler entities calledservices. In complement to verification, testing allows one to check for the correctnessof a binary (no source code) service implementation with reference to a specification.In this thesis, we propose black box conformance testing approach for centralizedservice compositions (orchestrations). With reference to the state of the art, wedevelop a symbolic approach in order to avoid state space explosion issues due to theXML data being largely used in Web services. This approach is based on symbolicmodels (STS), symbolic execution, and the use of a satisfiability modulo theory(SMT) solver. Further, we propose a comprehensive end-to-end approach that goesfrom specification using a standard orchestration language (ABPEL), and the possibledescription of test purposes, to the online realization and execution of symbolic testcases against an implementation. A crucial point is a model transformation fromABPEL to STS that we have defined and that takes into account the peculiarities ofABPEL semantics. The automation of our approach is supported by a tool-chainthat we have developed.

L’objectif principal de cette thèse concerne l’étude, la conception et la mise en œuvre numérique de schémas volumes finis associés aux solveurs de type Godunov. On s’intéresse à des systèmes hyperboliques de lois de conservation non linéaires, avec une attention particulière sur les équations d’Euler et les équations MHD idéale. Tout d’abord, nous dérivons un solveur de Riemann simple et véritablement multidimensionnelle, pouvant s’appliquer à tout système de lois de conservation. Ce solveur peut être considéré comme une généralisation 2D de l’approche HLL. Les ingrédients de base de la dérivation sont : la consistance avec la formulation intégrale et une utilisation adéquate des relations de Rankine-Hugoniot. Au final nous obtenons des expressions assez simples et applicables dans les contextes des maillages structurés et non structurés. Dans un second temps, nous nous intéressons à la préservation, au niveau discret, de la contrainte de divergence nulle du champ magnétique pour les équations de la MHD idéale. Deux stratégies sont évaluées et nous montrons comment le solveur de Riemann multidimensionnelle peut être utilisé pour obtenir des simulations robustes à divergence numérique nulle. Deux autres points sont abordés dans cette thèse : la méthode de relaxation pour un système Euler-Poisson pour des écoulements gravitationnels en astrophysique, la formulation volumes finis en coordonnées curvilignes. Tout au long de la thèse, les choix numériques sont validés à travers de nombreux résultats numériques. / The main objective of this thesis concerns the study, design and numerical implementation of finite volume schemes based on the so-Called Godunov-Type solvers for hyperbolic systems of nonlinear conservation laws, with special attention given to the Euler equations and ideal MHD equations. First, we derive a simple and genuinely two-Dimensional Riemann solver for general conservation laws that can be regarded as an actual 2D generalization of the HLL approach, relying heavily on the consistency with the integral formulation and on the proper use of Rankine-Hugoniot relations to yield expressions that are simple enough to be applied in the structured and unstructured contexts. Then, a comparison between two methods aiming to numerically maintain the divergence constraint of the magnetic field for the ideal MHD equations is performed and we show how the 2D Riemann solver can be employed to obtain robust divergence-Free simulations. Next, we derive a relaxation scheme that incorporates gravity source terms derived from a potential into the hydrodynamic equations, an important problem in astrophysics, and finally, we review the design of finite volume approximations in curvilinear coordinates, providing a fresher view on an alternative discretization approach. Throughout this thesis, numerous numerical results are shown.

Dans cette thèse, nous présentons notre travail de recherche dans le domaine du calcul haute performance en mécanique des fluides. Avec la demande croissante de simulations à haute résolution, il est devenu important de développer des solveurs numériques pouvant tirer parti des architectures récentes comprenant des processeurs multi-cœurs et des accélérateurs. Nous nous proposons dans cette thèse de développer un solveur efficace pour la résolution sur architectures hétérogènes CPU/GPU des équations de Navier-Stokes (NS) relatives aux écoulements 3D de fluides incompressibles.Tout d'abord nous présentons un aperçu de la mécanique des fluides avec les équations de NS pour fluides incompressibles et nous présentons les méthodes numériques existantes. Nous décrivons ensuite le modèle mathématique, et la méthode numérique choisie qui repose sur une technique de prédiction-projection incrémentale.Nous obtenons une distribution équilibrée de la charge de calcul en utilisant une méthode de décomposition de domaines. Une parallélisation à deux niveaux combinée avec de la vectorisation SIMD est utilisée dans notre implémentation pour exploiter au mieux les capacités des machines multi-cœurs. Des expérimentations numériques sur différentes architectures parallèles montrent que notre solveur NS obtient des performances satisfaisantes et un bon passage à l'échelle.Pour améliorer encore la performance de notre solveur NS, nous intégrons le calcul sur GPU pour accélérer les tâches les plus coûteuses en temps de calcul. Le solveur qui en résulte peut être configuré et exécuté sur diverses architectures hétérogènes en spécifiant le nombre de processus MPI, de threads, et de GPUs.Nous incluons également dans ce manuscrit des résultats de simulations numériques pour des benchmarks conçus à partir de cas tests physiques réels. Les résultats obtenus par notre solveur sont comparés avec des résultats de référence. Notre solveur a vocation à être intégré dans une future bibliothèque de mécanique des fluides pour le calcul sur architectures parallèles CPU/GPU. / In this PhD thesis, we present our research in the domain of high performance software for computational fluid dynamics (CFD). With the increasing demand of high-resolution simulations, there is a need of numerical solvers that can fully take advantage of current manycore accelerated parallel architectures. In this thesis we focus more specifically on developing an efficient parallel solver for 3D incompressible Navier-Stokes (NS) equations on heterogeneous CPU/GPU architectures. We first present an overview of the CFD domain along with the NS equations for incompressible fluid flows and existing numerical methods. We describe the mathematical model and the numerical method that we chose, based on an incremental prediction-projection method.A balanced distribution of the computational workload is obtained by using a domain decomposition method. A two-level parallelization combined with SIMD vectorization is used in our implementation to take advantage of the current distributed multicore machines. Numerical experiments on various parallel architectures show that this solver provides satisfying performance and good scalability.In order to further improve the performance of the NS solver, we integrate GPU computing to accelerate the most time-consuming tasks. The resulting solver can be configured for running on various heterogeneous architectures by specifying explicitly the numbers of MPI processes, threads and GPUs. This thesis manuscript also includes simulation results for two benchmarks designed from real physical cases. The computed solutions are compared with existing reference results. The code developed in this work will be the base for a future CFD library for parallel CPU/GPU computations.

Approved for public release, distribution is unlimited / A Markov Model was used to determine the number of nurses the Navy must gain each year in order to maintain desired end strength. Significant characteristics affecting career progression of individuals in the Navy Nurse Corps were identified. The characteristic of primary concern, accession source, was determined to be significant. Markov models were created to identify personnel flow from ENS through LCDR. The models end-strength projections for 2006-2009 were then compared to Nurse Corps targeted end-strengths for this same period. Several scenarios were run to minimize overages and underages in rank distribution. Optimization was achieved by changing both the distribution of accession sources and the distribution of recruited ranks. Optimal distribution of accession source and rank are dependant upon the degree of accepTable deviation from these targets. As stated above we were not able to acquire this information limiting our ability to accurately forecast optimized distribution of accession source or rank. The Markov Model demonstrated that the Nurse Corps current business practices optimize accessions for two year projections. Increasing variation between the current force structure plan and our models projections suggest that greater efficiency could be obtained in the out-years. This Markov Model provides a tool for improving extended forecasts. / Lieutenant Commander, United States Navy

A mesh-less method for solving incompressible, multi-phase flow problems has been developed and is discussed along with the presentation of benchmark results showing good agreement with theoretical and experimental results. Results of a systematic, parametric study of the single phase flow around a 2D circular cylinder at Reynolds numbers up to 1000 are presented and discussed. Simulation results show good agreement with experimental results. Extension of the method to deal with multiphase flow including liquid-to-vapor phase transition along with applications to cavitating flow are discussed. Insight gleaned from numerical experiments of the cavity closure problem are discussed along with recommendations for additional research. Several conclusions regarding the use of the method are made.

La résolution de systèmes linéaires creux est un problème qui apparaît dans de nombreuses applications scientifiques, et les solveurs creux sont une étape coûteuse pour ces applications ainsi que pour des solveurs plus avancés comme les solveurs hybrides direct-itératif. Pour ces raisons, optimiser la performance de ces solveurs pour les architectures modernes est un problème critique. Cependant, les contraintes mémoire et le temps de résolution limitent l’utilisation de ce type de solveur pour des problèmes de très grande taille. Pour les approches concurrentes, par exemple les méthodes itératives, des préconditionneurs garantissant une bonne convergence pour un large ensemble de problèmes sont toujours inexistants. Dans la première partie de cette thèse, nous présentons deux approches exploitant la compression Block Low-Rank (BLR) pour réduire la consommation mémoire et/ou le temps de résolution d’un solveur creux. Ce format de compression à plat, sans hiérarchie, permet de tirer profit du caractère low-rank des blocs apparaissant dans la factorisation de systèmes linéaires creux. La solution proposée peut être utilisée soit en tant que solveur direct avec une précision réduite, soit comme un préconditionneur très robuste. La première approche, appelée Minimal Memory, illustre le meilleur gain mémoire atteignable avec la compression BLR, alors que la seconde approche, appelée Just-In-Time, est dédiée à la réduction du nombre d’opérations, et donc du temps de résolution. Dans la seconde partie, nous présentons une stratégie de reordering qui augmente la granularité des blocs pour tirer davantage profit de la localité dans l’utilisation d’architectures multi-coeurs et pour fournir de tâches plus volumineuses aux GPUs. Cette stratégie s’appuie sur la factorisation symbolique par blocs pour raffiner la numérotation produite par des outils de partitionnement comme Metis ou Scotch, et ne modifie pas le nombre d’opérations nécessaires à la résolution du problème. A partir de cette approche, nous proposons dans la troisième partie de ce manuscrit une technique de clustering low-rank qui a pour objectif de former des clusters d’inconnues au sein d’un séparateur. Nous démontrons notamment les intérêts d’une telle approche par rapport aux techniques de clustering classiquement utilisées. Ces deux stratégies ont été développées pour le format à plat BLR, mais sont également une première étape pour le passage à un format hiérarchique. Dans la dernière partie de cette thèse, nous nous intéressons à une modification de la technique de dissection emboîtée afin d’aligner les séparateurs par rapport à leur père pour obtenir des structures de données plus régulières. / Solving sparse linear systems is a problem that arises in many scientific applications, and sparse direct solvers are a time consuming and key kernel for those applications and for more advanced solvers such as hybrid direct-iterative solvers. For those reasons, optimizing their performance on modern architectures is critical. However, memory requirements and time-to-solution limit the use of direct methods for very large matrices. For other approaches, such as iterative methods, general black-box preconditioners that can ensure fast convergence for a wide range of problems are still missing. In the first part of this thesis, we present two approaches using a Block Low-Rank (BLR) compression technique to reduce the memory footprint and/or the time-to-solution of a supernodal sparse direct solver. This flat, non-hierarchical, compression method allows to take advantage of the low-rank property of the blocks appearing during the factorization of sparse linear systems. The proposed solver can be used either as a direct solver at a lower precision or as a very robust preconditioner. The first approach, called Minimal Memory, illustrates the maximum memory gain that can be obtained with the BLR compression method, while the second approach, called Just-In-Time, mainly focuses on reducing the computational complexity and thus the time-to-solution. In the second part, we present a reordering strategy that increases the block granularity to better take advantage of the locality for multicores and provide larger tasks to GPUs. This strategy relies on the block-symbolic factorization to refine the ordering produced by tools such as Metis or Scotch, but it does not impact the number of operations required to solve the problem. From this approach, we propose in the third part of this manuscript a new low-rank clustering technique that is designed to cluster unknowns within a separator to obtain the BLR partition, and demonstrate its assets with respect to widely used clustering strategies. Both reordering and clustering where designed for the flat BLR representation but are also a first step to move to hierarchical formats. We investigate in the last part of this thesis a modified nested dissection strategy that aligns separators with respect to their father to obtain more regular data structure.

<div>The design of advanced engineering systems generally results in large-scale numerical problems, which require efficient computational electromagnetic (CEM) solutions. Among existing CEM methods, iterative methods have been a popular choice since conventional direct solutions are computationally expensive. The optimal complexity of an iterative solver is <i>O(NN_itN_rhs)</i> with <i>N</i> being matrix size, <i>N_it</i>the number of iterations and <i>N_rhs</i> the number of right hand sides. How to invert or factorize a dense matrix or a sparse matrix of size <i>N</i> in <i>O(N)</i> (optimal) complexity with explicitly controlled accuracy has been a challenging research problem. For solving a dense matrix of size <i>N</i>, the computational complexity of a conventional direct solution is <i>O(N³)</i>; for solving a general sparse matrix arising from a 3-D EM analysis, the best computational complexity of a conventional direct solution is <i>O(N²)</i>. Recently, an <i>H²</i>-matrix based mathematical framework has been developed to obtain fast dense matrix algebra. However, existing linear-complexity <i>H²</i>-based matrix-matrix multiplication and matrix inversion lack an explicit accuracy control. If the accuracy is to be controlled, the inverse as well as the matrix-matrix multiplication algorithm must be completely changed, as the original formatted framework does not offer a mechanism to control the accuracy without increasing complexity.</div><div> </div><div>In this work, we develop a series of new accuracy controlled fast <i>H²</i> arithmetic, including matrix-matrix multiplication (MMP) without formatted multiplications, minimal-rank MMP, new accuracy controlled <i>H²</i> factorization and inversion, new accuracy controlled <i>H²</i> factorization and inversion with concurrent change of cluster bases, <i>H²</i>-based direct sparse solver and new <i>HSS</i> recursive inverse with directly controlled accuracy. For constant-rank <i>H²</i>-matrices, the proposed accuracy directly controlled <i>H²</i> arithmetic has a strict <i>O(N)</i> complexity in both time and memory. For rank that linearly grows with the electrical size, the complexity of the proposed <i>H²</i> arithmetic is <i>O(NlogN)</i> in factorization and inversion time, and <i>O(N)</i> in solution time and memory for solving volume IEs. Applications to large-scale interconnect extraction as well as large-scale scattering analysis, and comparisons with state-of-the-art solvers have demonstrated the clear advantages of the proposed new <i>H²</i> arithmetic and resulting fast direct solutions with explicitly controlled accuracy. In addition to electromagnetic analysis, the new <i>H²</i> arithmetic developed in this work can also be applied to other disciplines, where fast and large-scale numerical solutions are being pursued. </div>

L'acceptation et l'utilisation des services Web en industrie se développent de par leursupport au développement d'application distribuées comme compositions d'entitéslogicielles plus simples appelées services. En complément à la vérification, le testpermet de vérifier la correction d'une implémentation binaire (code source nondisponible) par rapport à une spécification. Dans cette thèse, nous proposons uneapproche boîte-noire du test de conformité de compositions de services centralisées(orchestrations). Par rapport à l'état de l'art, nous développons une approchesymbolique de façon à éviter des problèmes d'explosion d'espace d'état dus à la largeutilisation de données XML dans les services Web. Cette approche est basée sur desmodèles symboliques (STS), l'exécution symbolique de ces modèles et l'utilisationd'un solveur SMT. De plus, nous proposons une approche de bout en bout, quiva de la spécification à l'aide d'un langage normalisé d'orchestration (ABPEL) etde la possible description d'objectifs de tests à la concrétisation et l'exécution enligne de cas de tests symboliques. Un point important est notre transformation demodèle entre ABPEL et les STS qui prend en compte les spécifications sémantiquesd'ABPEL. L'automatisation de notre approche est supportée par un ensemble d'outilsque nous avons développés.

We report a Hessian-implicit optimization method to quickly solve the charge optimization problem over protein molecules: given a ligand and its complex with a receptor, determine the ligand charge distribution that minimizes the electrostatic free energy of binding. The new optimization couples boundary element method (BEM) and primal-dual interior point method (PDIPM); initial results suggest that the method scales much better than the previous methods. The quadratic objective function is the electrostatic free energy of binding where the Hessian matrix serves as an operator that maps the charge to the potential. The unknowns are the charge values at the charge points, and they are limited by equality and inequality constraints that model physical considerations, i.e. conservation of charge. In the previous approaches, finite-difference method is used to model the Hessian matrix, which requires significant computational effort to remove grid-based inaccuracies. In the novel approach, BEM is used instead, with precorrected FFT (pFFT) acceleration to compute the potential induced by the charges. This part will be explained in detail by Shihhsien Kuo in another talk. Even though the Hessian matrix can be calculated an order faster than the previous approaches, still it is quite expensive to find it explicitly. Instead, the KKT condition is solved by a PDIPM, and a Krylov based iterative solver is used to find the Newton direction at each step. Hence, only Hessian times a vector is necessary, which can be evaluated quickly using pFFT. The new method with proper preconditioning solves a 500 variable problem nearly 10 times faster than the techniques that must find a Hessian matrix explicitly. Furthermore, the algorithm scales nicely due to the robustness in number of IPM iterations to the size of the problem. The significant reduction in cost allows the analysis of much larger molecular system than those could be solved in a reasonable time using the previous methods. / Singapore-MIT Alliance (SMA)

The game of Hex is of interest to the mathematics, algorithms, and artificial intelligence communities. It is a classical PSPACE-complete problem, and its invention is intrinsically tied to the Four Colour Theorem and the well-known strategy-stealing argument. Nash, Shannon, Tarjan, and Berge are among the mathematicians who have researched and published about this game. In this thesis we expand on previous research, further developing the mathematical theory and algorithmic techniques relating to Hex. In particular, we identify new classes of moves that can be pruned from consideration, and devise new algorithms to identify connection strategies efficiently. As a result of these theoretical improvements, we produce an automated solver capable of solving all 8 x 8 Hex openings and most 9 x 9 Hex openings; this marks the first time that computers have solved all Hex openings solved by humans. We also produce the two strongest automated Hex players in the world --- Wolve and MoHex --- and obtain both the gold and silver medals in the 2008 and 2009 International Computer Olympiads.