We develop and evaluate algorithms for generating random variates for simulation input. One group called automatic, or black-box algorithms can be used to sample from distributions with known density. They are based on the rejection principle. The hat function is generated automatically in a setup step using the idea of transformed density rejection. There the density is transformed into a concave function and the minimum of several tangents is used to construct the hat function. The resulting algorithms are not too complicated and are quite fast. The principle is also applicable to random vectors. A second group of algorithms is presented that generate random variates directly from a given sample by implicitly estimating the unknown distribution. The best of these algorithms are based on the idea of naive resampling plus added noise. These algorithms can be interpreted as sampling from the kernel density estimates. This method can be also applied to random vectors. There it can be interpreted as a mixture of naive resampling and sampling from the multi-normal distribution that has the same covariance matrix as the data. The algorithms described in this paper have been implemented in ANSI C in a library called UNURAN which is available via anonymous ftp. (author's abstract) / Series: Preprint Series / Department of Applied Statistics and Data Processing

Smoothed Particle Hydrodynamics (SPH) is analysed as the weighted residual method. In particular the analysis focuses on the collocation aspect of the method. Using Monte Carlo experiments we demonstrate that SPH is highly sensitive to node disorder, especially in its symmetrised energy and momentum conserving form. This aspect of the method is related to low [Beta] MHD instabilities observed by other authors. A remedy in the form of the Weighted Differences Method is suggested, which addresses this problem to some extent, but at a cost of losing automatic conservation of energy and momentum. ¶ The Weighted Differences Method is used to simulate propagation of Alfven and magnetosonic wave fronts in [Beta] = 0 plasma, and the results are compared with data obtained with the NCSA Zeus3D code with the Method of Characteristics (MOC) module. ¶ SPH is then applied to two interesting astrophysical situations: accretion on to a white dwarf in a compact binary system, which results in a formation of an accretion disk, and gravitational collapse of a magnetised vortex. Both models are 3 dimensional. ¶ The accretion disk which forms in the binary star model is characterised by turbulent flow: the Karman vortex street is observed behind the stream-disk interaction region. The shock that forms at the point of stream-disk interaction is controlled by the means of particle merges, whereas Monaghan-Lattanzio artificial viscosity is used to simulate Smagorinsky closure. ¶ The evolution of the collapsing magnetised vortex ends up in the formation of an expanding ring in the symmetry plane of the system. We observe the presence of spiralling inward motion towards the centre of attraction. That final state compares favourably with the observed qualitative and quantitative characteristics of the circumnuclear disk in the Galactic Centre. That simulation has also been verified with the NCSA Zeus3D run. ¶ In conclusions we contrast the result of our Monte Carlo experiments with the results delivered by our production runs. We also compare SPH and Weighted Differences against the new generation of conservative finite differences methods, such as the Godunov method and the Piecewise Parabolic Method. We conclude that although SPH cannot match the accuracy and performance of those methods, it appears to have some advantage in simulation of rotating flows, which are of special interest to astrophysics.

Cette thèse porte sur le développement, la validation et l'application d'un code de calcul numérique à surface libre. Smoothed Particle Hydrodynamics (SPH) est une méthode particulaire,Lagrangienne, imaginée à l'origine pour la simulation de corps gravitaires en Astrophysique. Depuis les années 90, elle a été étendue à la modélisation d'écoulements à surface libre. En effet, lors de grandes déformations des interfaces (déferlement par exemple), l'absence de maillage est particulièrement intéressante. Cette propriété est également intéressante pour la simulation de plusieurs phases liquides aux propriétés différentes (eau/fond sédimentaire par exemple). Les applications visées sont la propagation de la houle et son interaction avec des obstacles immergés. Le modèle SPH a donc été établi en se basant sur la bibliographie et validé sur le cas de l'étirement d'une goutte en l'absence de gravité.Ensuite, la prise en compte de conditions aux limites sur des parois solides est étudiée puis appliquée à l'effondrement d'une colonne d'eau suivi d'un impact sur un mur vertical. Enfin, le modèle est étendu aux écoulements visqueux. Une nouvelle méthode de prise en compte des conditions limites de type adhérence, inspirée des frontières immergées en différences finies, a ainsi été développée. Elle autorise la simulation d'écoulements autour d'objets de formes complexes immergés dans le fluide. Le modèle est finalement appliqué à la propagation de la houle en canal et à son amortissement par une plaque horizontale immergée.

A parallel GPU compatible Lagrangian mesh free particle solver for multiphase fluid flow based on SPH scheme is developed and used to capture the interface evolution during droplet impact. Surface tension is modeled employing the multiphase scheme of Hu et al. (2006). In order to precisely simulate the wetting phenomena, a method based on the work of Šikalo et al. (2005) is jointly used with the model proposed by Afkhami et al. (2009) to ensure accurate dynamic contact angle calculations. Accurate predictions were obtained for droplet contact angle during spreading. A two-dimensional analytical model is developed as an expansion to the work of Chandra et al. (1991). Results obtain from the solver agrees well to this analytical results. Effects of memory management techniques along with a variety of task assigning algorithms on GPU are studied. GPU speedups of up to 120 times faster than a single processor CPU were obtained.

A parallel GPU compatible Lagrangian mesh free particle solver for multiphase fluid flow based on SPH scheme is developed and used to capture the interface evolution during droplet impact. Surface tension is modeled employing the multiphase scheme of Hu et al. (2006). In order to precisely simulate the wetting phenomena, a method based on the work of Šikalo et al. (2005) is jointly used with the model proposed by Afkhami et al. (2009) to ensure accurate dynamic contact angle calculations. Accurate predictions were obtained for droplet contact angle during spreading. A two-dimensional analytical model is developed as an expansion to the work of Chandra et al. (1991). Results obtain from the solver agrees well to this analytical results. Effects of memory management techniques along with a variety of task assigning algorithms on GPU are studied. GPU speedups of up to 120 times faster than a single processor CPU were obtained.

No description available.

Fluid-structure interaction (FSI), occurrent in many areas of engineering and in the natural world, has been the subject of much research using a wide range of modelling strategies. However, problems with high levels of structural deformation are difficult to resolve and this is particularly the case for biomedical flows. A Lagrangian flow model coupled with a robust model for nonlinear structural mechanics seems a natural candidate since large distortion of the computational geometry is expected. Smoothed particle Hydrodynamics (SPH) has been widely applied for nonlinear interface modelling and this approach is investigated here. Biomedical applications often involve thin flexible structures and a consistent approach for modelling the interaction of fluids with such structures is also required. The Lagrangian weakly compressible SPH method is investigated in its recent delta-SPH form utilising inter-particle density fluxes to improve stability. Particle shifting is also used to maintain particle distributions sufficiently close to uniform to enable stable computation. The use of artificial viscosity is avoided since it introduces unphysical dissipation. First, solid boundary conditions are studied using a channel flow test. Results show that when the particle distribution is allowed to evolve naturally instabilities are observed and deviations are noted from the expected order of accuracy. A parallel development in the SPH group at Manchester has considered SPH in Eulerian form (for different applications). The Eulerian form is applied to the channel flow test resulting in improved accuracy and stability due to the maintenance of a uniform particle distribution. A higher-order accurate boundary model is developed and applied for the Eulerian SPH tests and third-order convergence is achieved. The well documented case of flow past a thin plate is then considered. The immersed boundary method (IBM) is now a natural candidate for the solid boundary. Again, it quickly becomes apparent that the Lagrangian SPH form has limitations in terms of numerical noise arising from anisotropic particle distributions. This corrupts the predicted flow structures for moderate Reynolds numbers (O(102)). Eulerian weakly compressible SPH is applied to the problem with the IBM and is found to give accurate and convergent results without any numerical stability problems (given the time step limitation defined by the Courant condition). Modelling highly flexible structures using the discrete element model is investigated where granular structures are represented as bonded particles. A novel vector-based form (the V-Model) is identified as an attractive approach and developed further for application to solid structures. This is shown to give accurate results for quasi-static and dynamic structural deformation tests. The V-model is applied to the decay of structural vibration in a still fluid modelled using Eulerian SPH with no artificial stabilising techniques. Again, results are in good agreement with predictions of other numerical models. A more demanding case representative of pulsatile flow through a deep leg vein valve is also modelled using the same form of Eulerian SPH. The results are free of numerical noise and complex FSI features are captured such as vortex shedding and non-linear structural deflection. Reasonable agreement is achieved with direct in-vivo observations despite the simplified two-dimensional numerical geometry. A robust, accurate and convergent method has thus been developed, at present for laminar two-dimensional low Reynolds number flows but this may be generalised. In summary a novel robust and convergent FSI model has been established based on Eulerian SPH coupled to the V-Model for large structural deformation. While these developments are in two dimensions the method is readily extendible to three-dimensional, laminar and turbulent flows for a wide range of applications in engineering and the natural world.

In this thesis, I study numerical and semi-analytical models of self-gravitating protostellar discs, with the aim of furthering our understanding of the role of disc-self gravity in planet formation. At the time of writing, the ALMA era of observational astronomy is upon us. Therefore, I place my research into this context with synthetic images of both numerical and semi-analytical models. I begin with an examination into the apparent lack of convergence, with increasing resolution, of the fragmentation boundary in Smoothed Particle Hydrodynamics (SPH) simulations of a protostellar disc. I run a suite of SPH with different numerical implementations, and find that even very similar implementations can fundamentally change the final answer. I analyse a suite of SPH simulations that fragment to form gravitationally bound objects, with the motivation of informing future population synthesis model development. I find that fragment-fragment and fragment-disc interaction dominates the orbital evolution of the system even at very early times, and any attempt to produce a population of objects from the gravitational instability process must include these interactions. Before a disc fragments, it will go through a self-gravitating phase. If the disc cools globally on a timescale such that it is balanced by heating due to gravitational stresses, the disc will be in a state of quasi-equilibrium. So long as the disc mass is sufficiently low, and spirals are sufficiently tightly wound, then angular momentum transport can be described by the local approximation, for which there is an analytical description. Using this analytical description, I develop an existing 1D model into 3D, and examine a wide range of parameter space for which disc self-gravity produces significant non-axisymmetry. Using radiative transfer calculations coupled with synthetic observations, I determine that there is a very narrow range of parameter space in which a disc will have sufficiently large gravitational stresses so as to produce detectable spirals, but the stresses not be so large as to cause the disc to fragment. By developing a simple analytical prescription for dust, I show that this region of parameter space can be broadened considerably. However, it requires grains that are large enough to become trapped by pressure maxima in the disc, so I conclude that if self-gravitating spiral arms are detected in the continuum, it is likely that at least some grain growth has taken place.

There are situations in the framework of quasi-Monte Carlo integration where nonuniform low-discrepancy sequences are required. Using the inversion method for this task usually results in the best performance in terms of the integration errors. However, this method requires a fast algorithm for evaluating the inverse of the cumulative distribution function which is often not available. Then a smoothed version of transformed density rejection is a good alternative as it is a fast method and its speed hardly depends on the distribution. It can easily be adjusted such that it is almost as good as the inversion method. For importance sampling it is even better to use the hat distribution as importance distribution directly. Then the resulting algorithm is as good as using the inversion method for the original importance distribution but its generation time is much shorter. / Series: Preprint Series / Department of Applied Statistics and Data Processing

São analisados nesta dissertação problemas em teoria dos jogos, com enfoque no efeito que perturbações acarretam em jogos. A análise suavizada (smoothed analysis) é utilizada para tal análise, e dois tipos de jogos são o foco principal desta dissertação, jogos bimatrizes e o problema de atribuição de tráfego (Traffic Assignment Problem.) O algoritmo de Lemke-Howson é um método utilizado amplamente para computar um equilíbrio Nash de jogos bimatrizes. Esse problema é PPAD-completo (Polynomial Parity Arguments on Directed graphs), e existem instâncias em que um tempo exponencial é necessário para terminar o algoritmo. Mesmo utilizando análise suavizada, esse problema permanece exponencial. Entretanto, nenhum estudo experimental foi realizado para demonstrar na prática como o algoritmo se comporta em casos com perturbação. Esta dissertação demonstra como as instâncias de pior caso conhecidas atualmente podem ser geradas e mostra que a performance do algoritmo nestas instâncias, quando perturbações são aplicadas, difere do comportamento esperado provado pela teoria. O Problema de Atribuição de Tráfego modela situações em uma rede viária onde usuários necessitam viajar de um nodo origem a um nodo destino. Esse problema pode ser modelado como um jogo, usando teoria dos jogos, onde um equilíbrio Nash acontece quando os usuários se comportam de forma egoísta. O custo total ótimo corresponde ao melhor fluxo de um ponto de vista global. Nesta dissertação, uma nova medida de perturbação é apresentada, o Preço da Anarquia Suavizado (Smoothed Price of Anarchy), baseada na análise suavizada de algoritmos, com o fim de analisar os efeitos da perturbação no Preço da Anarquia. Usando esta medida, são estudados os efeitos que perturbações têm no Preço da Anarquia para instâncias reais e teóricas para o Problema de Atribuição de Tráfego. É demonstrado que o Preço da Anarquia Suavizado se mantém na mesma ordem do Preço da Anarquia sem perturbações para funções de latência polinomiais. Finalmente, são estudadas instâncias de benchmark em relação à perturbação. / This thesis analyzes problems in game theory with respect to perturbation. It uses smoothed analysis to accomplish such task and focuses on two kind of games, bimatrix games and the traffic assignment problem. The Lemke-Howson algorithm is a widely used algorithm to compute a Nash equilibrium of a bimatrix game. This problem is PPAD-complete (Polynomial Parity Arguments on Directed graphs), and there exists an instance which takes exponential time (with any starting pivot.) It has been proven that even with a smoothed analysis it is still exponential. However, no experimental study has been done to verify and evaluate in practice how the algorithm behaves in such cases. This thesis shows in detail how the current known worst-case instances are generated and shows that the performance of the algorithm on these instances, when perturbed, differs from the expected behavior proven in theory. The Traffic Assignment Problem models a situation in a road network where users want to travel from an origin to a destination. It can be modeled as a game using game theory, with a Nash equilibrium happening when users behave selfishly and an optimal social welfare being the best possible flow from a global perspective. We provide a new measure, which we call the Smoothed Price of Anarchy, based on the smoothed analysis of algorithms in order to analyze the effects of perturbation on the Price of Anarchy. Using this measure, we analyze the effects that perturbation has on the Price of Anarchy for real and theoretical instances for the Traffic Assignment Problem. We demonstrate that the Smoothed Price of Anarchy remains in the same order as the original Price of Anarchy for polynomial latency functions. Finally, we study benchmark instances in relation to perturbation.