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.

In this study, we consider electrostatics contributed from the molecules in the ionic solution. It plays a significant role in determining the binding affinity of molecules and drugs. We develop the overall framework of computing electrostatic properties for three-dimensional molecular structures, including potential, energy, and forces. These properties are derived from Poisson-Boltzmann equation, a partial differential equation that describes the electrostatic behavior of molecules in ionic solutions. In order to compute these properties, we derived new boundary integral equations and designed a boundary element algorithm based on the linear time fast multipole method for solving the linearized Poisson-Boltzmann equation. Meanwhile, a higher-order parametric formulation called algebraic spline model is used for accurate approximation of the unknown solution of the linearized Poisson-Boltzmann equation. Based on algebraic spline model, we represent the normal derivative of electrostatic potential by surrounding electrostatic potential. This representation guarantees the consistent relation between electrostatic potential and its normal derivative. In addition, accurate numerical solution and fast computation for electrostatic energy and forces are also discussed. In addition, we described our hierarchical modeling and parameter optimization of molecular structures. Based on this technique, we can control the scalability of molecular models for electrostatic computation. The numerical test and experimental results show that the proposed techniques offer an efficient and accurate solution for solving the electrostatic problem of molecules. / text

Here we describe the fitting and testing, via molecular dynamics simulation, of a bond-order potential for water with a unique force field parameterization. Most potentials for water, including some bond-order (reactive) potentials, are based on a traditional, many-body decomposition to describe water's structure with bond stretch, angle bend, electrostatics, and non-bonded terms. Our model uses an expanded version of the Bond Valence Model, the Valence Multipole Model, to describe all aspects of molecular structure using multibody, bond-order terms. Prior work successfully related these multibody, bond order terms to energy, provided the structures were close to equilibrium. The success of this equilibrium energy model demonstrated the plausibility of adapting its parameterization to a molecular dynamics force field. Further, we present extensive testing of ab initio methods to show that the ab initio data we obtained, using the CCSD(t)/cc-pwCVTZ level of theory, to augment the fitting set of our parameters is of the highest quality currently available for the OH system. While the force field is not yet finished, the model has demonstrated remarkable improvement since its initial testing. The test results and the insights gleaned from them have brought us significantly closer to adapting our unique parametrization to a fully functional molecular dynamics force field. Once the water potential is finished, it is our intent to develop and expand the Valence Multipole Model into a fully reactive alternative to CLAYFF, a non-reactive potential typically used to simulate fluid interfaces with clays and other minerals.

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

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

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.

In this thesis we study the relativistic multipole moments for stationary asymptotically flat spacetimes as introduced by Geroch and Hansen. These multipole moments give an asymptotic description of the gravitational field in a coordinate independent way. Due to this good description of the spacetimes, it is natural to try to construct a spacetime from only the set of multipole moments. Here we present a simple method to do this for the static axisymmetric case. We also give explicit solutions for the cases where the number of non-zero multipole moments are finite. In addition, for the general stationary axisymmetric case, we present methods to generate solutions. It has been a long standing conjecture that the multipole moments give a complete characterization of the stationary spacetimes. Much progress toward a proof has been made over the years. However, there is one remaining difficult task: to prove that a spacetime exists with an a-priori given arbitrary set of multipole moments subject to some given condition. Here we present such a condition for the axisymmetric case, and prove that it is both necessary and sufficient. We also extend this condition to the general case without axisymmetry, but in this case we only prove the necessity of our condition.

This thesis deals with quantum chemistry methods for large systems. In particular, the thesis focuses on the efficient construction of the Coulomb and exchange matrices which are important parts of the Fock matrix in Hartree-Fock calculations. Density matrix purification, which is a method used to construct the density matrix for a given Fock matrix, is also discussed. The methods described are not only applicable in the Hartree-Fock case, but also in Kohn-Sham Density Functional Theory calculations, where the Coulomb and exchange matrices are parts of the Kohn-Sham matrix. Screening techniques for reducing the computational complexity of both Coulomb and exchange computations are discussed, including the fast multipole method, used for efficient computation of the Coulomb matrix. The thesis also discusses how sparsity in the matrices occurring in Hartree-Fock and Kohn-Sham Density Functional Theory calculations can be used to achieve more efficient storage of matrices as well as more efficient operations on them. / QC 20100817

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.

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.