Dissertations / Theses on the topic 'Fast multipolar method'
To see the other types of publications on this topic, follow the link: Fast multipolar method.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Fast multipolar method.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Poirier, Yohan. "Contribution à l'accélération d'un code de calcul des interactions vagues/structures basé sur la théorie potentielle instationnaire des écoulements à surface libre." Electronic Thesis or Diss., Ecole centrale de Nantes, 2023. http://www.theses.fr/2023ECDN0042.
Abstract:
De nombreuses méthodes numériques ont été développées pour modéliser et étudier les interactions entre les vagues et les structures. Les plus couramment utilisées sont celles basées sur la théorie potentielle des écoulements à surface libre.Dans l'approche Weak-Scatterer, conditions aux limites de surface libre sont linéarisées par rapport à la position de la houle incidente, ainsi les perturbations sur la houle doivent être de faibles amplitudes en comparaison de la houle incidente, mais aucune hypothèse n'est faite sur le mouvement des corps et sur l'amplitude de la houle incidente ; augmentant ainsi le champ d'application. Lorsque cette approche est couplée à une méthode des éléments de frontière, il est nécessaire à chaque itération temporelle, de construire et résoudre un système linéaire dense. La complexité spatiale importante de ces étapes limite l'utilisation de cette méthode à des systèmes de relativement faibles dimensions. Ce travail de thèse vise à réduire cette contrainte via la mise en oeuvre de méthodes d’accélération des calculs. On montre que l'utilisation de la méthode multipolaire permet de réduire la complexité spatiale en temps et en espace mémoire associées à la résolution du système linéaire rendant possible l'étude de système de plus grandes dimensions. Plusieurs méthodes de préconditionnement ont été étudiées de façon à réduire le nombre d'itérations nécessaires à la recherche de la solution du système par un solveur itératif.Au contraire de la méthode multiplaire rapide, la méthode de parallélisation en temps Parareal permet, en principe, d’accélérer l’ensemble de la simulation. On montre qu’elle permet d’accélérer les temps de calcul dans le cas de flotteurs fixes et libres dans la houle, mais que le facteur d’accélération décroit rapidement avec la cambrure de la houleNumerous numerical methods have been developed to model and study the interactions between waves and structures. The most commonly used are those based on potential free-surface flow theory. In the Weak-Scatterer approach, the free-surface boundary conditions are linearized with respect to the position of the incident wave, so the disturbances on the wave must be of low amplitude compared to the incident wave, but no assumptions are made about the motion of the bodies and the amplitude of the incident wave, thus increasing the scope of application. When this approach is coupled with a boundary element method, it is necessary to construct and solve a dense linear system at each time iteration. The high spatial complexity of these steps limits the use of this method to relatively small systems. This thesis aims to reduce this constraint by implementing methods for accelerating calculations. It is shown that the use of the multipole method reduces the spatial complexity in time and memory space associated with solving the linear system, making it possible to study larger systems. Several preconditioning methods have been studied in order to reduce the number of iterations required to find the solution to the system using an iterative solver. In contrast to the fast multiparallelization method, the Parareal time parallelization method can, in principle, accelerate the entire simulation. We show that it speeds up calculation times in the case of fixed floats free in the swell, but that the acceleration factor decreases rapidly with the camber of the swell
2
Chandramowlishwaran, Aparna. "The fast multipole method at exascale." Diss., Georgia Institute of Technology, 2013. http://hdl.handle.net/1853/50388.
Abstract:
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.
3
Ridderstolpe, Ludwig. "Multithreading in adaptive fast multipole methods." Thesis, Uppsala universitet, Institutionen för informationsteknologi, 2021. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-452393.
Abstract:
It has been shown that fast multipole methods can achieve good scalability on multi-core architectures. We have for an adaptive single-threaded fast multipole method implemented multithreading support via the OpenMP API. The downward- and upward pass in the fast multipole method are parallelized, and the multithreaded implementation achieves on a quad-core architecture for uniform distributions a 6.6x speedup and a non-uniform distribution a 4.2x speedup. The lower speedup for the non-uniform distributions results from poor load balancing caused by higher variance in connectivity. We conclude that future research in how connectivity affects parallel performance is needed.
4
Yoshida, Kenichi. "Applications of Fast Multipole Method to Boundary Integral Equation Method." Kyoto University, 2001. http://hdl.handle.net/2433/150672.
5
Gutting, Martin. "Fast multipole methods for oblique derivative problems." Aachen Shaker, 2007. http://d-nb.info/988919346/04.
6
PEIXOTO, HELVIO DE FARIAS COSTA. "A FAST MULTIPOLE METHOD FOR HIGH ORDER BOUNDARY ELEMENTS." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2018. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=34740@1.
Abstract:
PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIROCONSELHO NACIONAL DE DESENVOLVIMENTO CIENTÍFICO E TECNOLÓGICO
FUNDAÇÃO DE APOIO À PESQUISA DO ESTADO DO RIO DE JANEIRO
BOLSA NOTA 10
Desde a década de 1990, o Método Fast Multipole (FMM) tem sido usado em conjunto com o Métodos dos Elementos de Contorno (BEM) para a simulação de problemas de grande escala. Este método utiliza expansões em série de Taylor para aglomerar pontos da discretização do contorno, de forma a reduzir o tempo computacional necessário para completar a simulação. Ele se tornou uma ferramenta bastante importante para os BEMs, pois eles apresentam matrizes cheias e assimétricas, o que impossibilita a utilização de técnicas de otimização de solução de sistemas de equação. A aplicação do FMM ao BEM é bastante complexa e requer muita manipulação matemática. Este trabalho apresenta uma formulação do FMM que é independente da solução fundamental utilizada pelo BEM, o Método Fast Multipole Generalizado (GFMM), que se aplica a elementos de contorno curvos e de qualquer ordem. Esta característica é importante, já que os desenvolvimentos de fast multipole encontrados na literatura se restringem apenas a elementos constantes. Todos os aspectos são abordados neste trabalho, partindo da sua base matemática, passando por validação numérica, até a solução de problemas de potencial com muitos milhões de graus de liberdade. A aplicação do GFMM a problemas de potencial e elasticidade é discutida e validada, assim como os desenvolvimentos necessários para a utilização do GFMM com o Método Híbrido Simplificado de Elementos de Contorno (SHBEM). Vários resultados numéricos comprovam a eficiência e precisão do método apresentado. A literatura propõe que o FMM pode reduzir o tempo de execução do algoritmo do BEM de O(N2) para O(N), em que N é o número de graus de liberdade do problema. É demonstrado que esta redução é de fato possível no contexto do GFMM, sem a necessidade da utilização de qualquer técnica de otimização computacional.
The Fast Multipole Method (FMM) has been used since the 1990s with the Boundary Elements Method (BEM) for the simulation of large-scale problems. This method relies on Taylor series expansions of the underlying fundamental solutions to cluster the nodes on the discretised boundary of a domain, aiming to reduce the computational time required to carry out the simulation. It has become an important tool for the BEMs, as they present matrices that are full and nonsymmetric, so that the improvement of storage allocation and execution time is not a simple task. The application of the FMM to the BEM ends up with a very intricate code, and usually changing from one problem s fundamental solution to another is not a simple matter. This work presents a kernel-independent formulation of the FMM, here called the General Fast Multipole Method (GFMM), which is also able to deal with high order, curved boundary elements in a straightforward manner. This is an important feature, as the fast multipole implementations reported in the literature only apply to constant elements. All necessary aspects of this method are presented, starting with the mathematical basics of both FMM and BEM, carrying out some numerical assessments, and ending up with the solution of large potential problems. The application of the GFMM to both potential and elasticity problems is discussed and validated in the context of BEM. Furthermore, the formulation of the GFMM with the Simplified Hybrid Boundary Elements Method (SHBEM) is presented. Several numerical assessments show that the GFMM is highly efficient and may be as accurate as arbitrarily required, for problems with up to many millions of degrees of freedom. The literature proposes that the FMM is capable of reducing the time complexity of the BEM algorithms from O(N2) to O(N), where N is the number of degrees of freedom. In fact, it is shown that the GFMM is able to arrive at such time reduction without resorting to techniques of computational optimisation.
7
Tang, Zhihui. "Fast transforms based on structured matrices with applications to the fast multipole method." College Park, Md. : University of Maryland, 2003. http://hdl.handle.net/1903/142.
Abstract:
Thesis (Ph. D.) -- University of Maryland, College Park, 2003.Thesis research directed by: Applied Mathematics and Scientific Computation Program. Title from t.p. of PDF. Includes bibliographical references. Published by UMI Dissertation Services, Ann Arbor, Mich. Also available in paper.
8
BAPAT, MILIND SHRIKANT. "FAST MULTIPOLE BOUNDARY ELEMENT METHOD FOR SOLVING TWO-DIMENSIONAL ACOUSTIC WAVE PROBLEMS." University of Cincinnati / OhioLINK, 2006. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1163773308.
9
Li, Yuxiang. "A Fast Multipole Boundary Element Method for Solving Two-dimensional Thermoelasticity Problems." University of Cincinnati / OhioLINK, 2014. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1397477834.
10
MITRA, KAUSIK PRADIP. "APPLICATION OF MULTIPOLE EXPANSIONS TO BOUNDARY ELEMENT METHOD." University of Cincinnati / OhioLINK, 2002. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1026411773.
11
Gutting, Martin [Verfasser]. "Fast Multipole Methods for Oblique Derivative Problems / Martin Gutting." Aachen : Shaker, 2008. http://d-nb.info/116279187X/34.
12
Huang, Shuo. "A Fast Multipole Boundary Element Method for the Thin Plate Bending Problem." University of Cincinnati / OhioLINK, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1368026582.
13
Grasso, Eva. "Modelling visco-elastic seismic wave propagation : a fast-multipole boundary element method and its coupling with finite elements." Phd thesis, Université Paris-Est, 2012. http://tel.archives-ouvertes.fr/tel-00730752.
Abstract:
The numerical simulation of elastic wave propagation in unbounded media is a topical issue. This need arises in a variety of real life engineering problems, from the modelling of railway- or machinery-induced vibrations to the analysis of seismic wave propagation and soil-structure interaction problems. Due to the complexity of the involved geometries and materials behavior, modelling such situations requires sophisticated numerical methods. The Boundary Element method (BEM) is a very effective approach for dynamical problems in spatially-extended regions (idealized as unbounded), especially since the advent of fast BEMs such as the Fast Multipole Method (FMM) used in this work. The BEM is based on a boundary integral formulation which requires the discretization of the only domain boundary (i.e. a surface in 3-D) and accounts implicitly for the radiation conditions at infinity. As a main disadvantage, the BEM leads a priori to a fully-populated and (using the collocation approach) non-symmetrical coefficient matrix, which make the traditional implementation of this method prohibitive for large problems (say O(106) boundary DoFs). Applied to the BEM, the Multi-Level Fast Multipole Method (ML-FMM) strongly lowers the complexity in computational work and memory that hinder the classical formulation, making the ML-FMBEM very competitive in modelling elastic wave propagation. The elastodynamic version of the Fast Multipole BEM (FMBEM), in a form enabling piecewise-homogeneous media, has for instance been successfully used to solve seismic wave propagation problems in a previous work (thesis dissertation of S. Chaillat, ENPC, 2008). This thesis aims at extending the capabilities of the existing frequency-domain elastodynamic FMBEM in two directions. Firstly, the time-harmonic elastodynamic ML-FMBEM formulation has been extended to the case of weakly dissipative viscoelastic media. Secondly, the FMBEM and the Finite Element Method (FEM) have been coupled to take advantage of the versatility of the FEM to model complex geometries and non-linearities while the FM-BEM accounts for wave propagation in the surrounding unbounded medium. In this thesis, we consider two strategies for coupling the FMBEM and the FEM to solve three-dimensional time-harmonic wave propagation problems in unbounded domains. The main idea is to separate one or more bounded subdomains (modelled by the FEM) from the complementary semi-infinite viscoelastic propagation medium (modelled by the FMBEM) through a non-overlapping domain decomposition. Two coupling strategies have been implemented and their performances assessed and compared on several examples
14
Bapat, Milind S. "New Developments in Fast Boundary Element Method." University of Cincinnati / OhioLINK, 2012. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1331296947.
15
Otani, Yoshihiro. "Fast multipole methods for periodic problems in elasticity and electromagnetics." 京都大学 (Kyoto University), 2007. http://hdl.handle.net/2433/135988.
16
Keuchel, Sören [Verfasser]. "Aufwandsreduzierungen in der Fast-Multipole-Boundary-Elemente-Methode / Sören Keuchel." Aachen : Shaker, 2017. http://d-nb.info/1138177822/34.
17
NOVELINO, LARISSA SIMOES. "APPLICATION OF FAST MULTIPOLE TECHNIQUES IN THE BOUNDARY ELEMENT METHODS." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2015. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=37003@1.
Abstract:
PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIROCOORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR
PROGRAMA DE EXCELENCIA ACADEMICA
Este trabalho visa à implementação de um programa de elementos de contorno para problemas com milhões de graus de liberdade. Isto é obtido com a implementação do Método Fast Multipole (FMM), que pode reduzir o número de operações, para a solução de um problema com N graus de liberdade, de O(N(2)) para O(NlogN) ou O(N). O uso de memória também é reduzido, por não haver o armazenamento de matrizes de grandes dimensões como no caso de outros métodos numéricos. A implementação proposta é baseada em um desenvolvimento consistente do convencional, Método de colocação dos elementos de contorno (BEM) – com conceitos provenientes do Hibrido BEM – para problemas de potencial e elasticidade de larga escala em 2D e 3D. A formulação é especialmente vantajosa para problemas de topologia complicada ou que requerem soluções fundamentais complicadas. A implementação apresentada, usa um esquema para expansões de soluções fundamentais genéricas em torno de níveis hierárquicos de polos campo e fonte, tornando o FMM diretamente aplicável para diferentes soluções fundamentais. A árvore hierárquica dos polos é construída a partir de um conceito topológico de superelementos dentro de superelementos. A formulação é inicialmente acessada e validada em termos de um problema de potencial 2D. Como resolvedores iterativos não são necessários neste estágio inicial de simulação numérica, podese acessar a eficiência relativa à implementação do FMM.
This work aims to present an implementation of a boundary element solver for problems with millions of degrees of freedom. This is achieved through a Fast Multipole Method (FMM) implementation, which can lower the number of operations for solving a problem, with N degrees of freedom, from O(N(2)) to O(NlogN) or O(N). The memory usage is also very small, as there is no need to store large matrixes such as required by other numerical methods. The proposed implementations are based on a consistent development of the conventional, collocation boundary element method (BEM) - with concepts taken from the variationally-based hybrid BEM - for large-scale 2D and 3D problems of potential and elasticity. The formulation is especially advantageous for problems of complicated topology or requiring complicated fundamental solutions. The FMM implementation presented in this work uses a scheme for expansions of a generic fundamental solution about hierarchical levels of source and field poles. This makes the FMM directly applicable to different kinds of fundamental solutions. The hierarchical tree of poles is built upon a topological concept of superelements inside superelements. The formulation is initially assessed and validated in terms of a simple 2D potential problem. Since iterative solvers are not required in this first step of numerical simulations, an isolated efficiency assessment of the implemented fast multipole technique is possible.
18
Koteeswaran, Prabhavathi. "Fast dynamic force computation for electrostatic and electromagnetic conductors." Texas A&M University, 2004. http://hdl.handle.net/1969.1/1443.
Abstract:
This thesis presents an improved method for dynamic force computation applicable
to both electrostatic and electromagnetic conductors with complex 3D geometries.
During the transient simulation of electrostatic actuated MEMS, the positions of the
conductors as well as the potential applied to the conductors may change, necessitating
recalculation of electrostatic forces at each time step of computation. Similarly,
during the simulation of electromagnetic actuated MEMS, the current re-distribution
in the conductors requires recalculation of electromagnetic forces at each time step.
In this thesis, a simple method based on the principles of fast multipole algorithm
is explored to effectively recalculate the potential coefficients to compute the surface
charges and thereby forces during transient simulation of electrostatic conductors.
The proposed method improves the speed of electrostatic force computation by 15
- 60% at each time step, depending on the displacement, with an error less than
3%. Electromagnetic forces are also computed by the same method. In addition,
an efficient method is also presented for electrostatic analysis of dummy metal filled
interconnects.
19
Junior, Wagner Gomes Rodrigues. "Coloides carregados ou porosos: estudos das propriedades hidrodinâmicas e eletrocinéticas com o método Lattice Boltzmann." Universidade de São Paulo, 2016. http://www.teses.usp.br/teses/disponiveis/43/43134/tde-27092016-163121/.
Abstract:
Este trabalho teve como motivação experimental problemas surgidos nos laboratórios de biofísica do IF-USP em medidas com vesículas carregadas, que podem ser usadas para estudar membranas biológicas. As propriedades destes sistemas, e, em particular, como função da temperatura, só podem ser investigadas indiretamente. A interpretação dos resultados depende de uma modelagem coerente. Entre as exigências de coerência, estariam a justificativa para a discrepância entre resultados para as medidas de raio dos macroíons lipídicos, no intervalo de temperaturas próximas à transição gelfluido, obtidas por técnicas experimentais diferentes (Static Light Scattering (SLS) e Dynamic Light Scattering (DLS)) e as anomalias no calor específico, na condutividade e na mobilidade eletroforética da solução coloidal iônica, no mesmo intervalo de temperatura. Estudos anteriores a este trabalho sugeriam a formação de poros em tais vesículas, como tentativa de explicar diferenças nos resultados das técnicas de espalhamento, bem como o papel da análise do equilíbrio termodinâmico da dissociação sobre as propriedades térmicas e termoelétricas. Para interpretar e dar coerência aos diversos resultados experimentais existentes, é necessário desenvolver modelos teóricos. É objetivo deste trabalho desenvolver técnicas de tratamento de modelos teóricos quanto às propriedades de transporte. Assim, neste estudo utilizamos o método computacional conhecido como ``Lattice Boltzmann\'\' (LBM) procurando focar no estudo de propriedades de meios porosos e de coloides carregados. Para melhor compreensão dos limites e justificativas do modelo, realizamos um breve estudo sobre a equação de Boltzmann e suas propriedades. Assim, depois de desenvolver um código em linguagem C para o LBM, e testá-lo com resultados conhecidos, utilizamos o ``Lattice Boltzmann\'\' para determinar o coeficiente de arrasto de esferas e cascas esféricas porosas, comparando com resultados analíticos e experimentais conhecidos. Para o estudo de sistemas coloidais carregados, acoplamos o ``Lattice Boltzmann`` a outra técnica computacional, ``Fast Multipole Method\'\' (FMM), para poder estudar efeitos elétricos e hidrodinâmicos associados aos coloides com carga. Foram feitas simulações de fluxo eletrosmótico e eletrólitos entre placas carregadas que apresentaram resultados animadores ao comparar com resultados analíticos, constatando que FMM pode ser uma alternativa à resolução da equação de Laplace para determinar o potencial eletrostático em simulações com LBM. Além disso foram feitas simulações de mobilidade eletroforética em meios sem sal, que mostram que o código pode ser utilizado como ferramenta na busca da solução para as dúvidas surgidas no estudo de vesículas carregadas.This study was inspired by the problem of interpreting experimental results arising in the Biophysics Laboratory of the Institute of Physics - USP. Different techniques are used to investigate charged vesicles that are used as an experimental model for biological membranes. Careful measurements of vesicle radius, in the range of gel-fluid transition temperature, through different experimental techniques, namely Static and Dynamic Light Scattering (SLS and DLS) led to very different results. Previous studies of the same system suggested the formation of pores in such vesicles. In addition, specific heat and conductivity measurements on charged vesicles displayed an anomalous region, in the range of gel-fluid transition temperature, as compared to neutral vesicles. In an attempt to make progress in the understanding of the above problems, we use the computational method known as Lattice Boltzmann Method (LBM) seeking to focus on the study of transport properties of porous and charged colloids. To better understand the limits of the model and justifications, we make a brief study of the Boltzmann equation and its properties. Thus, after developing a code in $C$ language for LBM, and testing it with known results, we use the Lattice Boltzmann method to obtain the drag coefficient of spheres and porous spherical shells. We compare our results with analytical and experimental results from the literature and obtain good fitting. For the study of charged colloidal systems, we associate the Lattice Boltzmann method with a computational technique for the calculation of the eletrostatic potential: the Fast Multipole Method (FMM), which enables us to study electrical and hydrodynamic effects on charged colloids. We simulate electroosmotic flow and electrolytes between charged plates, with encouraging results in the comparison with known analytical result. This suggests that FMM may be a good alternative to resolution of the Laplace equation to determine the electrostatic potential simulations with LBM. Moreover we have obtained the electrophoretic mobility for charged colloids in saltless solutions, which makes our code a possible instrument for the interpretation of experimental results on charged vesicles.
20
Kabadshow, Ivo [Verfasser]. "Periodic Boundary Conditions and the Error-Controlled Fast Multipole Method / Ivo Kabadshow." Wuppertal : Universitätsbibliothek Wuppertal, 2012. http://d-nb.info/1020476176/34.
21
Banjai, Lehel. "Computation of conformal maps by fast multipole method accelerated Schwarz-Christoffel transformation." Thesis, University of Oxford, 2003. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.400550.
22
PEIXOTO, HELVIO DE FARIAS COSTA. "A STUDY OF THE FAST MULTIPOLE METHOD APPLIED TO BOUNDARY ELEMENT PROBLEMS." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2014. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=24364@1.
Abstract:
PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIROCONSELHO NACIONAL DE DESENVOLVIMENTO CIENTÍFICO E TECNOLÓGICO
FUNDAÇÃO DE APOIO À PESQUISA DO ESTADO DO RIO DE JANEIRO
BOLSA NOTA 10
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.
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.
23
Wang, Yang. "The fast multipole method for 2D coulombic problems analysis, implementation and visualization /." College Park, Md. : University of Maryland, 2005. http://hdl.handle.net/1903/3074.
Abstract:
Thesis (M.S.) -- University of Maryland, College Park, 2005.Thesis research directed by: Applied Mathematics and Scientific Computation Program. Title from t.p. of PDF. Includes bibliographical references. Published by UMI Dissertation Services, Ann Arbor, Mich. Also available in paper.
24
Profit, Anthony Thomas James. "On fast multipole methods for the solution of the Helmholtz equation." Thesis, University of Salford, 1999. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.299122.
25
SHEN, LIANG. "ADAPTIVE FAST MULTIPOLE BOUNDARY ELEMENT METHODS FOR THREE-DIMENSIONAL POTENTIAL AND ACOUSTIC WAVE PROBLEMS." University of Cincinnati / OhioLINK, 2007. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1193706024.
26
Fischer, Matthias. "The fast multipole boundary element method and its application to structure acoustic field interaction." [S.l. : s.n.], 2004. http://www.bsz-bw.de/cgi-bin/xvms.cgi?SWB11380456.
27
Jacobs, Ralf Theo. "A contribution towards the solution of scattering problems with the fast multipole method." Dresden TUDpress, 2009. http://d-nb.info/996092536/04.
28
Kachanovska, Maryna. "Fast, Parallel Techniques for Time-Domain Boundary Integral Equations." Doctoral thesis, Universitätsbibliothek Leipzig, 2014. http://nbn-resolving.de/urn:nbn:de:bsz:15-qucosa-132183.
Abstract:
This work addresses the question of the efficient numerical solution of time-domain boundary integral equations with retarded potentials arising in the problems of acoustic and electromagnetic scattering. The convolutional form of the time-domain boundary operators allows to discretize them with the help of Runge-Kutta convolution quadrature. This method combines Laplace-transform and time-stepping approaches and requires the explicit form of the fundamental solution only in the Laplace domain to be known. Recent numerical and analytical studies revealed excellent properties of Runge-Kutta convolution quadrature, e.g. high convergence order, stability, low dissipation and dispersion.
As a model problem, we consider the wave scattering in three dimensions. The convolution quadrature discretization of the indirect formulation for the three-dimensional wave equation leads to the lower triangular Toeplitz system of equations. Each entry of this system is a boundary integral operator with a kernel defined by convolution quadrature. In this work we develop an efficient method of almost linear complexity for the solution of this system based on the existing recursive algorithm. The latter requires the construction of many discretizations of the Helmholtz boundary single layer operator for a wide range of complex wavenumbers. This leads to two main problems:
the need to construct many dense matrices and to evaluate many singular and near-singular integrals.
The first problem is overcome by the use of data-sparse techniques, namely, the high-frequency fast multipole method (HF FMM) and H-matrices. The applicability of both techniques for the discretization of the Helmholtz boundary single-layer operators with complex wavenumbers is analyzed. It is shown that the presence of decay can favorably affect the length of the fast multipole expansions and thus reduce the matrix-vector multiplication times. The performance of H-matrices and the HF FMM is compared for a range of complex wavenumbers, and the strategy to choose between two techniques is suggested.
The second problem, namely, the assembly of many singular and nearly-singular integrals, is solved by the use of the Huygens principle. In this work we prove that kernels of the boundary integral operators $w_n^h(d)$ ($h$ is the time step and $t_n=nh$ is the time) exhibit exponential decay outside of the neighborhood of $d=nh$ (this is the consequence of the Huygens principle). The size of the support of these kernels for fixed $h$ increases with $n$ as $n^a,a<1$, where $a$ depends on the order of the Runge-Kutta method and is (typically) smaller for Runge-Kutta methods of higher order. Numerical experiments demonstrate that theoretically predicted values of $a$ are quite close to optimal.
In the work it is shown how this property can be used in the recursive algorithm to construct only a few matrices with the near-field, while for the rest of the matrices the far-field only is assembled. The resulting method allows to solve the three-dimensional wave scattering problem with asymptotically almost linear complexity. The efficiency of the approach is confirmed by extensive numerical experiments.
29
Karban, Ugur. "Three-dimensional Flow Solutions For Non-lifting Flows Using Fast Multipole Boundary Element Method." Master's thesis, METU, 2012. http://etd.lib.metu.edu.tr/upload/12615042/index.pdf.
Abstract:
Driving aim of this study was to develop a solver which is accurate enough to be used in analysis and fast enough to be used in optimization purposes. As a first step, a three-dimensional potential flow solver is developed using Fast Multipole Boundary Element (FMBEM) for calculating the pressure distributions in non-lifting flows.
It is a steady state solver which uses planar triangular unstructured mesh. After the geometry is introduced, the program creates a prescribed wake surface attached to the trailing edge(s), obtains a solution using panel elements on which the doublet and source strengths vary linearly. The reason for using FMBEM instead of classical BEM is the availability of solutions of systems having DOFs up to several millions within a few hours using a standard computer which is impossible to accomplish with classical BEM. Solutions obtained for different test cases are compared with the analytical solution (if applicable), the experimental data or the results obtained by JavaFoil.
30
Hjerpe, Daniel. "A study on SSE optimisation regarding initialisation and evaluation of the Fast Multipole Method." Thesis, Uppsala universitet, Avdelningen för beräkningsvetenskap, 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-298122.
Abstract:
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.
31
Kachanovska, Maryna. "Fast, Parallel Techniques for Time-Domain Boundary Integral Equations." Doctoral thesis, Max-Planck-Institut für Mathematik in den Naturwissenschaften, 2013. https://ul.qucosa.de/id/qucosa%3A12278.
Abstract:
This work addresses the question of the efficient numerical solution of time-domain boundary integral equations with retarded potentials arising in the problems of acoustic and electromagnetic scattering. The convolutional form of the time-domain boundary operators allows to discretize them with the help of Runge-Kutta convolution quadrature. This method combines Laplace-transform and time-stepping approaches and requires the explicit form of the fundamental solution only in the Laplace domain to be known. Recent numerical and analytical studies revealed excellent properties of Runge-Kutta convolution quadrature, e.g. high convergence order, stability, low dissipation and dispersion.
As a model problem, we consider the wave scattering in three dimensions. The convolution quadrature discretization of the indirect formulation for the three-dimensional wave equation leads to the lower triangular Toeplitz system of equations. Each entry of this system is a boundary integral operator with a kernel defined by convolution quadrature. In this work we develop an efficient method of almost linear complexity for the solution of this system based on the existing recursive algorithm. The latter requires the construction of many discretizations of the Helmholtz boundary single layer operator for a wide range of complex wavenumbers. This leads to two main problems:
the need to construct many dense matrices and to evaluate many singular and near-singular integrals.
The first problem is overcome by the use of data-sparse techniques, namely, the high-frequency fast multipole method (HF FMM) and H-matrices. The applicability of both techniques for the discretization of the Helmholtz boundary single-layer operators with complex wavenumbers is analyzed. It is shown that the presence of decay can favorably affect the length of the fast multipole expansions and thus reduce the matrix-vector multiplication times. The performance of H-matrices and the HF FMM is compared for a range of complex wavenumbers, and the strategy to choose between two techniques is suggested.
The second problem, namely, the assembly of many singular and nearly-singular integrals, is solved by the use of the Huygens principle. In this work we prove that kernels of the boundary integral operators $w_n^h(d)$ ($h$ is the time step and $t_n=nh$ is the time) exhibit exponential decay outside of the neighborhood of $d=nh$ (this is the consequence of the Huygens principle). The size of the support of these kernels for fixed $h$ increases with $n$ as $n^a,a<1$, where $a$ depends on the order of the Runge-Kutta method and is (typically) smaller for Runge-Kutta methods of higher order. Numerical experiments demonstrate that theoretically predicted values of $a$ are quite close to optimal.
In the work it is shown how this property can be used in the recursive algorithm to construct only a few matrices with the near-field, while for the rest of the matrices the far-field only is assembled. The resulting method allows to solve the three-dimensional wave scattering problem with asymptotically almost linear complexity. The efficiency of the approach is confirmed by extensive numerical experiments.
32
Nawas, Zain. "Performance of Adaptive Fast Multipole Methods In Three Dimensions For Time-Dependent Problem." Thesis, Uppsala universitet, Institutionen för informationsteknologi, 2021. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-434772.
Abstract:
In the last two decades, physical constraints in chip design have spawned a paradigm shift in computer architecture. The availability of multi-core threaded systems has increased the parallel execution which has provided an opportunity for analysing computationallydemanding problems. The N-Body problem is a fundamental problem in the field of computational science and in this project, we havereviewed one of the N-body algorithms named the Fast Multipole Methods(FMM). The implementation of FMM is pretty complex and is dependent on multiple subroutines and in each subroutine, communication, and computation patterns are different. In the previous implementation, the FMM algorithm has been tested with multiple MPI process and highlighted that P2P (point to point) subroutine lacks in execution time. The P2P is the last subroutine in FMM algorithm and its a core function in FMM algorithm that deals with point to point potentials. This project analysed the working of the FMM implementation where computational time is lacking andbenchmark using OpenMP threads on P2P subroutine. The P2P subroutine is implemented with two level OpenMP approach inside MPI process.First, the behaviour of P2P subroutine by tuning parameter settings of the FMM algorithm is analysed. Finally, in the end the speedups of P2P subroutine having multiple threads with different number of MPI processes are analyzed. It achieved a reasonable absolute efficiency by increasing the number of threads with MPI processes.Tryckt av:
33
Nilsson, Martin. "Fast Numerical Techniques for Electromagnetic Problems in Frequency Domain." Doctoral thesis, Uppsala : Acta Universitatis Upsaliensis : Univ.-bibl. [distributör], 2003. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-3884.
34
Barrett, John Patrick Ph D. Massachusetts Institute of Technology. "A spatially resolved study of the KATRIN main spectrometer using a novel fast multipole method." Thesis, Massachusetts Institute of Technology, 2017. http://hdl.handle.net/1721.1/114314.
Abstract:
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Physics, 2017.Cataloged from PDF version of thesis.
Includes bibliographical references (pages 333-350).
The Karlsruhe Tritium Neutrino (KATRIN) experiment is intended to make a sensitive (~ 200 meV) model-independent measurement of the neutrino mass through high precision electrostatic spectroscopy of the tritium /-decay spectrum. One of the principle components in this experiment is the main spectrometer which serves as an integrating MAC-E filter with 0(1) eV resolution. Thorough understanding of the transmission properties of the main spectrometer system is an inextricable challenge associated with this effort, and requires a very accurate and fast method for calculating the electrostatic fields created within its volume. To this end, the work described in this thesis documents the development of a novel variation on the Fast Multipole Method (FNM), which is a hybrid of the canonical algorithm and the Fast Fourier Transform on Multipoles (FFTM) method. This hybrid technique has been implemented to take advantage of scalable parallel computing resources and has been used to solve the Laplace boundary value problem using the Boundary Element Method with millions of degrees of freedom. Detailed measurements taken during the KATRIN main spectrometer commissioning phase are used to validate the fully three-dimensional electrostatic field calculation and the hybrid fast multipole method. Then, the hybrid method is used to greatly accelerate charged particle tracking in a high-statistics Monte Carlo simulation. The data from this simulation is then used to develop a spatially resolved model of the main spectrometer transmission function. This full transmission function model is then used to evaluate the performance of several of approximate transmission function models, the results of which show that a purely axially symmetric treatment of the main spectrometer is not sufficient. We conclude by addressing the appropriate level of measurement detail needed in order to reconstruct a realistic, non-axially symmetric transmission function model.
by John Patrick Barrett.
Ph. D.
35
Wilkes, Daniel. "The development of a fast multipole boundary element method for coupled acoustic and elastic problems." Thesis, Curtin University, 2014. http://hdl.handle.net/20.500.11937/122.
Abstract:
This thesis presents a dual fast multipole boundary element method (FMBEM) for modelling 3D acoustic coupled fluid-structure interaction problems in the frequency domain. Boundary integral representations are used to represent both the exterior fluid and interior elastic solid domains and the fast multipole method is employed to accelerate the calculations in both domains. The dual FMBEM yields a similar solution accuracy to the conventional models, while its solution times and memory requirements are substantially reduced.
36
Vuylsteke, Xavier. "Development of a reference method based on the fast multipole boundary element method for sound propagation problems in urban environments : formalism, improvements & applications." Thesis, Paris Est, 2014. http://www.theses.fr/2014PEST1174/document.
Abstract:
Décrit comme l'un des algorithmes les plus prometteurs du 20ème siècle, le formalisme multipolaire appliqué à la méthode des éléments de frontière, permet de nos jours de traiter de larges problèmes encore inconcevables il y a quelques années. La motivation de ce travail de thèse est d'évaluer la capacité, ainsi que les avantages concernant les ressources numériques, de ce formalisme pour apporter une solution de référence aux problèmes de propagation sonore tri-dimensionnels en environnement urbain, dans l'objectif d'améliorer les algorithmes plus rapides déjà existants. Nous présentons la théorie nécessaire à l'obtention de l'équation intégrale de frontière pour la résolution de problèmes non bornés. Nous discutons également de l'équation intégrale de frontière conventionnelle et hyper-singulière pour traiter les artefacts numériques liés aux fréquences fictives, lorsque l'on résout des problèmes extérieurs. Nous présentons par la suite un bref aperçu historique et technique du formalisme multipolaire rapide et des outils mathématiques requis pour représenter la solution élémentaire de l'équation de Helmholtz. Nous décrivons les principales étapes, d'un point de vue numérique, du calcul multipolaire. Un problème de propagation sonore dans un quartier, composé de 5 bâtiments, nous a permis de mettre en évidence des problèmes d'instabilités dans le calcul par récursion des matrices de translations, se traduisant par des discontinuités sur le champs de pression de surface et une non convergence du solveur. Ceci nous a conduits à considérer le travail très récent de Gumerov et Duraiswamy en lien avec un processus récursif stable pour le calcul des coefficients des matrices de rotation. Cette version améliorée a ensuite été testée avec succès sur un cas de multi diffraction jusqu'à une taille dimensionnelle de problème de 207 longueur d'ondes. Nous effectuons finalement une comparaison entre un algorithme d'élément de frontière, Micado3D, un algorithme multipolaire et un algorithme basé sur le tir de rayons, Icare, pour le calcul de niveaux de pression moyennés dans une cour ouverte et fermée. L'algorithme multipolaire permet de valider les résultats obtenus par tir de rayons dans la cour ouverte jusqu'à 300 Hz (i.e. 100 longueur d'ondes), tandis que concernant la cour fermée, zone très sensible par l'absence de contribution directes ou réfléchies, des études complémentaires sur le préconditionnement de la matrice semblent requises afin de s'assurer de la pertinence des résultats obtenus à l'aide de solveurs itératifsDescribed as one of the best ten algorithms of the 20th century, the fast multipole formalism applied to the boundary element method allows to handle large problems which were inconceivable only a few years ago. Thus, the motivation of the present work is to assess the ability, as well as the benefits in term of computational resources provided by the application of this formalism to the boundary element method, for solving sound propagation problems and providing reference solutions, in three dimensional dense urban environments, in the aim of assessing or improving fast engineering tools. We first introduce the mathematical background required for the derivation of the boundary integral equation, for solving sound propagation problems in unbounded domains. We discuss the conventional and hyper-singular boundary integral equation to overcome the numerical artifact of fictitious eigen-frequencies, when solving exterior problems. We then make a brief historical and technical overview of the fast multipole principle and introduce the mathematical tools required to expand the elementary solution of the Helmholtz equation and describe the main steps, from a numerical viewpoint, of fast multipole calculations. A sound propagation problem in a city block made of 5 buildings allows us to highlight instabilities in the recursive computation of translation matrices, resulting in discontinuities of the surface pressure and a no convergence of the iterative solver. This observation leads us to consider the very recent work of Gumerov & Duraiswamy, related to a ``stable'' recursive computation of rotation matrices coefficients in the RCR decomposition. This new improved algorithm has been subsequently assessed successfully on a multi scattering problem up to a dimensionless domain size equal to 207 wavelengths. We finally performed comparisons between a BEM algorithm, extit{Micado3D}, the FMBEM algorithm and a ray tracing algorithm, Icare, for the calculation of averaged pressure levels in an opened and closed court yards. The fast multipole algorithm allowed to validate the results computed with Icare in the opened court yard up to 300 Hz corresponding, (i.e. 100 wavelengths), while in the closed court yard, a very sensitive area without direct or reflective fields, further investigations related to the preconditioning seem required to ensure reliable solutions provided by iterative solver based algorithms
37
Juttu, Sreekanth. "A new approach for fast potential evaluation in N-body problems." Thesis, Texas A&M University, 2003. http://hdl.handle.net/1969.1/351.
Abstract:
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.
38
Barakat, Khalil. "The multi-level fast multipole method and prediction of cellular signal strength in an urban environment /." Thesis, McGill University, 2002. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=33955.
Abstract:
There is great interest in solving microwave propagation problems in the urban environment, for planning and simulating cell phone systems. The most accurate approach would be to solve Maxwell's equations for the unknown field strength at every point. Traditional computational methods require dividing space into N subregions (e.g. finite elements) that are no longer than about half a wavelength across, and introducing several unknowns per subregion. This thesis investigates computationally efficient methods of solving such problems on electrically large domains and as a result, the Multi-Level Fast Multi-pole Method (MLFMM) is implemented to resolve two-dimensional problems and predict cellular signal strength. The simulation tool computational cost is of O(N ln N) per iteration, as compared to O(N2) for more straightforward methods. The tool was successfully tested in the case of cylindrical scatterers for whom analytical solutions are available for comparison. It was then used to predict the field strength in a simple urban model.
39
McCorquodale, Peter William 1967. "Fast multipole-type methods in one and two dimensions, with application to parallel Fourier transforms." Thesis, Massachusetts Institute of Technology, 1998. http://hdl.handle.net/1721.1/10044.
40
Lee, Jimin. "Earthquake site effect modeling in sedimentary basins using a 3-D indirect boundary element-fast multipole method." Diss., Online access via UMI:, 2007.
41
Misawa, Ryota. "Boundary integral equation methods for the calculation of complex eigenvalues for open spaces." 京都大学 (Kyoto University), 2017. http://hdl.handle.net/2433/225738.
42
Cocle, Roger. "Combining the vortex-in-cell and parallel fast multipole methods for efficient domain decomposition simulations : DNS and LES approaches." Université catholique de Louvain, 2007. http://edoc.bib.ucl.ac.be:81/ETD-db/collection/available/BelnUcetd-08172007-165806/.
Abstract:
This thesis is concerned with the numerical simulation of high Reynolds number, three-dimensional, incompressible flows in open domains. Many problems treated in Computational Fluid Dynamics (CFD) occur in free space: e.g., external aerodynamics past vehicles, bluff bodies or aircraft; shear flows such as shear layers or jets. In observing all these flows, we can remark that they are often unsteady, appear chaotic with the presence of a large range of eddies, and are mainly dominated by convection. For years, it was shown that Lagrangian Vortex Element Methods (VEM) are particularly well appropriate for simulating such flows. In VEM, two approaches are classically used for solving the Poisson equation. The first one is the Biot-Savart approach where the Poisson equation is solved using the Green's function approach. The unbounded domain is thus implicitly taken into account. In that case, Parallel Fast Multipole (PFM) solvers are usually used. The second approach is the Vortex-In-Cell (VIC) method where the Poisson equation is solved on a grid using fast grid solvers. This requires to impose boundary conditions or to assume periodicity. An important difference is that fast grid solvers are much faster than fast multipole solvers. We here combine these two approaches by taking the advantages of each one and, eventually, we obtain an efficient VIC-PFM method to solve incompressible flows in open domain. The major interest of this combination is its computational efficiency: compared to the PFM solver used alone, the VIC-PFM combination is 15 to 20 times faster. The second major advantage is the possibility to run Large Eddy Simulations (LES) at high Reynolds number. Indeed, as a part of the operations are done in an Eulerian way (i.e. on the VIC grid), all the existing subgrid scale (SGS) models used in classical Eulerian codes, including the recent "multiscale" models, can be easily implemented.
43
Rudberg, Elias. "Quantum Chemistry for Large Systems." Doctoral thesis, Stockholm : Bioteknologi, Kungliga Tekniska högskolan, 2007. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-4561.
44
Shaw, Michelle. "Application of density functional theory to large systems: Implementation of the continuous fast multipole method and investigation of models of pentacoordinate phosphorus." Thesis, University of Ottawa (Canada), 2005. http://hdl.handle.net/10393/29261.
Abstract:
The density functional package DeFT is used for systems with a large number of charge distributions, and the bottleneck of the computation is the evaluation of two-electron integrals. Previously, it scaled quadratically with system size. A particular strategy, called the continuous fast multipole method, has been implemented in DeFT and combined with traditional methods for evaluating the two-electron integrals. The result is a code which scales linearly with system size and is able to treat larger systems.
The Continuous Fast Multipole Method (CFMM) uses the divide-and-conquer strategy to approximate the pairwise potentials between continuous charge distributions. Pairwise potentials are computed using the direct method if they are within a defined distance of one another; and are approximated by a multipolar expansion if they are not. The algorithm involves successive subdivisions of the simulation space until the desired precision is reached, which reduces the number of pairwise potentials evaluated. For large systems, this algorithm scales linearly with the number of charge distributions.
Enzyme-catalyzed phosphoryl transfer reactions have many applications in biological systems. It has been shown in previous investigations that phosphoryl transfer in enzymes proceeds via a pentacoordinate phosphorus intermediate. Few theoretical investigations have been conducted on this class of enzymes due to the large number of atoms treated quantum mechanically.
In this investigation, models of the pentacoordinate phosphorus intermediate are investigated with density functional methods. Comparison of the results of calculations using the VSXC functional with experiment and perturbation theory are employed to validate its use in investigations of phosphoryl transfer reactions.
45
Fischer, Matthias [Verfasser]. "The fast multipole boundary element method and its application to structure-acoustic field interaction / Institut A für Mechanik der Universität Stuttgart. Matthias Fischer." Stuttgart : Inst. A für Mechanik, 2004. http://d-nb.info/972310819/34.
46
Lee, Dong Ryeol. "A distributed kernel summation framework for machine learning and scientific applications." Diss., Georgia Institute of Technology, 2012. http://hdl.handle.net/1853/44727.
Abstract:
The class of computational problems I consider in
this thesis share the common trait of requiring
consideration of pairs (or higher-order tuples)
of data points. I focus on the problem of kernel
summation operations ubiquitous in many data
mining and scientific algorithms.
In machine learning, kernel summations appear in
popular kernel methods which can model nonlinear
structures in data. Kernel methods include many
non-parametric methods such as kernel density
estimation, kernel regression, Gaussian process
regression, kernel PCA, and kernel support vector
machines (SVM). In computational physics,
kernel summations occur inside the classical
N-body problem for simulating positions of a set
of celestial bodies or atoms.
This thesis attempts to marry, for the first
time, the best relevant techniques in parallel
computing, where kernel summations are in low
dimensions, with the best general-dimension
algorithms from the machine learning literature.
We provide a unified, efficient parallel
kernel summation framework that can utilize:
(1) various types of deterministic and
probabilistic approximations that may be
suitable for both low and high-dimensional
problems with a large number of data points;
(2) indexing the data using any multi-dimensional
binary tree with both distributed memory (MPI)
and shared memory (OpenMP/Intel TBB) parallelism;
(3) a dynamic load balancing scheme to adjust
work imbalances during the computation.
I will first summarize my previous research in
serial kernel summation algorithms. This work
started from Greengard/Rokhlin's earlier work on
fast multipole methods for the purpose of
approximating potential sums of many particles.
The contributions of this part of this thesis
include the followings: (1) reinterpretation of
Greengard/Rokhlin's work for the computer science
community; (2) the extension of the algorithms to
use a larger class of approximation strategies,
i.e. probabilistic error bounds via Monte Carlo
techniques; (3) the multibody series expansion:
the generalization of the theory of fast
multipole methods to handle interactions of more
than two entities; (4) the first O(N) proof of
the batch approximate kernel summation using a
notion of intrinsic dimensionality. Then I move
onto the problem of parallelization of the kernel
summations and tackling the scaling of two other
kernel methods, Gaussian process regression
(kernel matrix inversion) and kernel PCA (kernel
matrix eigendecomposition).
The artifact of this thesis has contributed to an
open-source machine learning package called
MLPACK which has been first demonstrated at the
NIPS 2008 and subsequently at the NIPS 2011 Big
Learning Workshop. Completing a portion of this
thesis involved utilization of high performance
computing resource at XSEDE (eXtreme Science and
Engineering Discovery Environment) and NERSC
(National Energy Research Scientific Computing
Center).
47
Wei, Jiangong. "Surface Integral Equation Methods for Multi-Scale and Wideband Problems." The Ohio State University, 2014. http://rave.ohiolink.edu/etdc/view?acc_num=osu1408653442.
48
Blanchard, Pierre. "Fast hierarchical algorithms for the low-rank approximation of matrices, with applications to materials physics, geostatistics and data analysis." Thesis, Bordeaux, 2017. http://www.theses.fr/2017BORD0016/document.
Abstract:
Les techniques avancées pour l’approximation de rang faible des matrices sont des outils de réduction de dimension fondamentaux pour un grand nombre de domaines du calcul scientifique. Les approches hiérarchiques comme les matrices H2, en particulier la méthode multipôle rapide (FMM), bénéficient de la structure de rang faible par bloc de certaines matrices pour réduire le coût de calcul de problèmes d’interactions à n-corps en O(n) opérations au lieu de O(n2). Afin de mieux traiter des noyaux d’interaction complexes de plusieurs natures, des formulations FMM dites ”kernel-independent” ont récemment vu le jour, telles que les FMM basées sur l’interpolation polynomiale. Cependant elles deviennent très coûteuses pour les noyaux tensoriels à fortes dimensions, c’est pourquoi nous avons développé une nouvelle formulation FMM efficace basée sur l’interpolation polynomiale, appelée Uniform FMM. Cette méthode a été implémentée dans la bibliothèque parallèle ScalFMM et repose sur une grille d’interpolation régulière et la transformée de Fourier rapide (FFT). Ses performances et sa précision ont été comparées à celles de la FMM par interpolation de Chebyshev. Des simulations numériques sur des cas tests artificiels ont montré que la perte de précision induite par le schéma d’interpolation était largement compensées par le gain de performance apporté par la FFT. Dans un premier temps, nous avons étendu les FMM basées sur grille de Chebyshev et sur grille régulière au calcul des champs élastiques isotropes mis en jeu dans des simulations de Dynamique des Dislocations (DD). Dans un second temps, nous avons utilisé notre nouvelle FMM pour accélérer une factorisation SVD de rang r par projection aléatoire et ainsi permettre de générer efficacement des champs Gaussiens aléatoires sur de grandes grilles hétérogènes. Pour finir, nous avons développé un algorithme de réduction de dimension basé sur la projection aléatoire dense afin d’étudier de nouvelles façons de caractériser la biodiversité, à savoir d’un point de vue géométriqueAdvanced techniques for the low-rank approximation of matrices are crucial dimension reduction tools in many domains of modern scientific computing. Hierarchical approaches like H2-matrices, in particular the Fast Multipole Method (FMM), benefit from the block low-rank structure of certain matrices to reduce the cost of computing n-body problems to O(n) operations instead of O(n2). In order to better deal with kernels of various kinds, kernel independent FMM formulations have recently arisen such as polynomial interpolation based FMM. However, they are hardly tractable to high dimensional tensorial kernels, therefore we designed a new highly efficient interpolation based FMM, called the Uniform FMM, and implemented it in the parallel library ScalFMM. The method relies on an equispaced interpolation grid and the Fast Fourier Transform (FFT). Performance and accuracy were compared with the Chebyshev interpolation based FMM. Numerical experiments on artificial benchmarks showed that the loss of accuracy induced by the interpolation scheme was largely compensated by the FFT optimization. First of all, we extended both interpolation based FMM to the computation of the isotropic elastic fields involved in Dislocation Dynamics (DD) simulations. Second of all, we used our new FMM algorithm to accelerate a rank-r Randomized SVD and thus efficiently generate multivariate Gaussian random variables on large heterogeneous grids in O(n) operations. Finally, we designed a new efficient dimensionality reduction algorithm based on dense random projection in order to investigate new ways of characterizing the biodiversity, namely from a geometric point of view
49
Lang, Jens. "Energie- und Ausführungszeitmodelle zur effizienten Ausführung wissenschaftlicher Simulationen." Doctoral thesis, Universitätsbibliothek Chemnitz, 2015. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-qucosa-159435.
Abstract:
Das wissenschaftliche Rechnen mit der Computersimulation hat sich heute als dritte Säule der wissenschaftlichen Methodenlehre neben der Theorie und dem Experiment etabliert. Aufgabe der Informatik im wissenschaftlichen Rechnen ist es, sowohl effiziente Simulationsalgorithmen zu entwickeln als auch ihre effiziente Implementierung. Die vorliegende Arbeit richtet ihren Fokus auf die effiziente Implementierung zweier wichtiger Verfahren des wissenschaftlichen Rechnens: die Schnelle Multipolmethode (FMM) für Teilchensimulationen und die Methode der finiten Elemente (FEM), die z. B. zur Berechnung der Deformation von Festkörpern genutzt wird. Die Effizienz der Implementierung bezieht sich hier auf die Ausführungszeit der Simulationen und den zur Ausführung notwendigen Energieverbrauch der eingesetzten Rechnersysteme. Die Steigerung der Effizienz wurde durch modellbasiertes Autotuning erreicht. Beim modellbasierten Autotuning wird für die wesentlichen Teile des Algorithmus ein Modell aufgestellt, das dessen Ausführungszeit bzw. Energieverbrauch beschreibt. Dieses Modell ist abhängig von Eigenschaften des genutzten Rechnersystems, von Eingabedaten und von verschiedenen Parametern des Algorithmus. Die Eigenschaften des Rechnersystems werden durch Ausführung des tatsächlich genutzten Codes für verschiedene Implementierungsvarianten ermittelt. Diese umfassen eine CPU-Implementierung und eine Grafikprozessoren-Implementierung für die FEM und die Implementierung der Nahfeld- und der Fernfeldwechselwirkungsberechnung für die FMM. Anhand der aufgestellten Modelle werden die Kosten der Ausführung für jede Variante vorhergesagt. Die optimalen Algorithmenparameter können somit analytisch bestimmt werden, um die gewünschte Zielgröße, also Ausführungszeit oder Energieverbrauch, zu minimieren. Bei der Ausführung der Simulation werden die effizientesten Implementierungsvarianten entsprechend der Vorhersage genutzt. Während bei der FMM die Performance-Messungen unabhängig von der Ausführung der Simulation durchgeführt werden, wird für die FEM ein Verfahren zur dynamischen Verteilung der Rechenlast zwischen CPU und GPU vorgestellt, das auf Ausführungszeitmessungen zur Laufzeit der Simulation reagiert. Durch Messung der tatsächlichen Ausführungszeiten kann so dynamisch auf sich während der Laufzeit verändernde Verhältnisse reagiert und die Verteilung der Rechenlast entsprechend angepasst werden. Die Ergebnisse dieser Arbeit zeigen, dass modellbasiertes Autotuning es ermöglicht, die Effizienz von Anwendungen des wissenschaftlichen Rechnens in Bezug auf Ausführungszeit und Energieverbrauch zu steigern. Insbesondere die Berücksichtigung des Energieverbrauchs alternativer Ausführungspfade, also die Energieadaptivität, wird in naher Zukunft von großer Bedeutung im wissenschaftlichen Rechnen seinComputer simulation as a part of the scientific computing has established as third pillar in scientific methodology, besides theory and experiment. The task of computer science in the field of scientific computing is the development of efficient simulation algorithms as well as their efficient implementation. The thesis focuses on the efficient implementation of two important methods in scientific computing: the Fast Multipole Method (FMM) for particle simulations, and the Finite Element Method (FEM), which is, e.g., used for deformation problems of solids. The efficiency of the implementation considers the execution time of the simulations and the energy consumption of the computing systems needed for the execution. The method used for increasing the efficiency is model-based autotuning. For model-based autotuning, a model for the substantial parts of the algorithm is set up which estimates the execution time or energy consumption. This model depends on properties of the computer used, of the input data and of parameters of the algorithm. The properties of the computer are determined by executing the real code for different implementation variants. These implementation variantss comprise a CPU and a graphics processor implementation for the FEM, and implementations of near field and far field interaction calculations for the FMM. Using the models, the execution costs for each variant are predicted. Thus, the optimal algorithm parameters can be determined analytically for a minimisation of the desired target value, i.e. execution time or energy consumption. When the simulation is executed, the most efficient implementation variants are used depending on the prediction of the model. While for the FMM the performance measurement takes place independently from the execution of the simulation, for the FEM a method for dynamically distributing the workload to the CPU and the GPU is presented, which takes into account execution times measured at runtime. By measuring the real execution times, it is possible to response to changing conditions and to adapt the distribution of the workload accordingly. The results of the thesis show that model-based autotuning makes it possible to increase the efficiency of applications in scientific computing regarding execution time and energy consumption. Especially, the consideration of the energy consumption of alternative execution paths, i.e. the energy adaptivity, will be of great importance in scientific computing in the near future
50
Deglaire, Paul. "Analytical Aerodynamic Simulation Tools for Vertical Axis Wind Turbines." Doctoral thesis, Uppsala universitet, Elektricitetslära, 2010. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-132073.
Abstract:
Wind power is a renewable energy source that is today the fastest growing solution to reduce CO2 emissions in the electric energy mix. Upwind horizontal axis wind turbine with three blades has been the preferred technical choice for more than two decades. This horizontal axis concept is today widely leading the market. The current PhD thesis will cover an alternative type of wind turbine with straight blades and rotating along the vertical axis. A brief overview of the main differences between the horizontal and vertical axis concept has been made. However the main focus of this thesis is the aerodynamics of the wind turbine blades. Making aerodynamically efficient turbines starts with efficient blades. Making efficient blades requires a good understanding of the physical phenomena and effective simulations tools to model them. The specific aerodynamics for straight bladed vertical axis turbine flow are reviewed together with the standard aerodynamic simulations tools that have been used in the past by blade and rotor designer. A reasonably fast (regarding computer power) and accurate (regarding comparison with experimental results) simulation method was still lacking in the field prior to the current work. This thesis aims at designing such a method. Analytical methods can be used to model complex flow if the geometry is simple. Therefore, a conformal mapping method is derived to transform any set of section into a set of standard circles. Then analytical procedures are generalized to simulate moving multibody sections in the complex vertical flows and forces experienced by the blades. Finally the fast semi analytical aerodynamic algorithm boosted by fast multipole methods to handle high number of vortices is coupled with a simple structural model of the rotor to investigate potential aeroelastic instabilities. Together with these advanced simulation tools, a standard double multiple streamtube model has been developed and used to design several straight bladed rotor ranging from 2 kW to 20 kW.Felaktigt tryckt som Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology 704