No description available.

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.

On présente ici un ensemble de méthodes numériques performantes pour lasimulation micromagnétique 3D reposant sur l’équation de Landau-Lifchitz-Gilbert, constituantun code nommé feeLLGood. On a choisi l’approche éléments finis pour sa flexibilitégéométrique. La formulation adoptée respecte la contrainte d’orthogonalité entre l’aimantationet sa dérivée temporelle, contrairement à la formulation classique sur-dissipative.On met au point un schéma de point milieu pour l’équation Landau-Lifchitz-Gilbert quiest stable et d’ordre deux en temps. Cela permet de prendre, à précision égale, des pas detemps beaucoup plus grands (typiquement un ordre de grandeur) que les schémas classiques.Un véritable enjeu numérique est le calcul du champ démagnétisant, non local. Oncompare plusieurs techniques de calcul rapide pour retenir celles, inédites dans le domaine,des multipôles rapides (FMM) et des transformées de Fourier hors-réseau (NFFT). Aprèsavoir validé le code sur des cas-tests et établi son efficacité, on présente les applications àla simulation des nanostructures : sélection de chiralité et résonance ferromagnétique d’unplot monovortex de cobalt, hystérésis des chapeaux de Néel dans un plot allongé de fer.Enfin, l’étude d’un oscillateur spintronique prouve l’évolutivité du code. / Here is presented a set of efficient numerical methods for 3D micromagneticsimulation based on the Landau-Lifchitz-Gilbert equation, making up a code named feeLLGood.The finite element approach was chosen for its geometrical flexibility. The adoptedformulation meets the orthogonality constraint between the magnetization and its time derivative,unlike the over-dissipative classical formulation. A midoint rule was developed forthe Landau-Lifchitz-Gilbert equation which is stable and second order in time. This allowsfor much bigger time steps (typically an order of magnitude) than classical schemes at thesame precision. Computing the nonlocal demagnetizing interaction is a real numerical challenge.Several fast computation techniques are compared. Those selected are novel to thefield : the Fast Multipole Method (FMM) and Non-uniform Fast Fourier Transforms (NFFT).After the code is validated on test cases and its efficiency established, applications to the simulationof nanostructures are presented : chirality selection and ferromagnetic resonanceof a cobalt monovortex dot, Neel caps hysteresis in an iron dot. Finally, the study of a spintronicoscillator proves the code’s upgradability.

[pt] 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. / [en] 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.

<p>The development of the new programming language Scream, within the project Software Renaissance, led to the need of a good multiple dispatch algorithm. A multiple dispatch algorithm, called Compressed n-dimensional table with row sharing; CNT-RS, was developed from the algorithm Compressed n-dimensional table, CNT. The purpose of CNT-RS was to create a more efficient algorithm. This report is the result of the work to analyse the CNT-RS algorithm. </p><p>In this report the domain of multiple dispatch, the multiple dispatch algorithm CNT and the new extended algorithm CNT-RS are presented. The correctness of CNT- RS algorithm is shown and it’s proven that the CNT-RS algorithm is at least as good as the CNT algorithm, in regards to space complexity of the dispatch structure.</p>

Computer simulation of wave propagation is an active research area as wave phenomena are prevalent in many applications. Examples include wireless communication, radar cross section, underwater acoustics, and seismology. For high frequency waves, this is a challenging multiscale problem, where the small scale is given by the wavelength while the large scale corresponds to the overall size of the computational domain. Research into wave equation modeling can be divided into two regimes: time domain and frequency domain. In each regime, there are two further popular research directions for the numerical simulation of the scattered wave. One relies on direct discretization of the wave equation as a hyperbolic partial differential equation in the full physical domain. The other direction aims at solving an equivalent integral equation on the surface of the scatterer. In this dissertation, we present three new techniques for the frequency domain, boundary integral equations. / text

[pt] 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. / [en] 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.

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.

The development of the new programming language Scream, within the project Software Renaissance, led to the need of a good multiple dispatch algorithm. A multiple dispatch algorithm, called Compressed n-dimensional table with row sharing; CNT-RS, was developed from the algorithm Compressed n-dimensional table, CNT. The purpose of CNT-RS was to create a more efficient algorithm. This report is the result of the work to analyse the CNT-RS algorithm. In this report the domain of multiple dispatch, the multiple dispatch algorithm CNT and the new extended algorithm CNT-RS are presented. The correctness of CNT- RS algorithm is shown and it’s proven that the CNT-RS algorithm is at least as good as the CNT algorithm, in regards to space complexity of the dispatch structure.

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étrique. / Advanced 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.