Beschreibung der Finite Elemente Software-Familie SPC-PM3-AdH-XX für: (S)cientific (P)arallel (C)omputing - (P)rogramm-(M)odul (3)D (ad)aptiv (H)exaederelemente. Für XX stehen die einzelnen Spezialvarianten, die in Teil 2 detailliert geschildert werden. Stand: Ende 2013:1 Allgemeine Vorbemerkungen 2 Grundstruktur 3 Datenstrukturen 4 Gesamtablauf 5 Parallelisierung 6 Die Grundvariante A3D_Original und ihre Bibliotheken

Beschreibung der Finite Elemente Software-Familie SPC-PM3-AdH-XX für: (S)cientific (P)arallel (C)omputing - (P)rogramm-(M)odul (3)D (ad)aptiv (H)exaederelemente. Für XX stehen die einzelnen Spezialvarianten, die in Teil 2 detailliert geschildert werden. Stand: Ende 2013:1 Vorbemerkungen 2 Probleme mit transversal-isotropem Material 3 Gleichungen vom Sattelpunktstyp 4 Probleme der Thermo-Elastizität 5 Nichtlineare Probleme der großen Deformationen

L'objectif de cette thèse était de proposer, puis de valider expérimentalement, un ensemble de méthodes algorithmiques permettant le remaillage parallèle de maillages distribués, en s'appuyant sur une méthode séquentielle de remaillage préexistante. Cet objectif a été atteint par étapes : définition de structures de données et de schémas de communication adaptés aux maillages distribués, permettant le déplacement à moindre coût des interfaces entre sous-domaines sur les processeurs d'une architecture à mémoire distribuée ; utilisation d'algorithmes de répartition dynamique de la charge adaptés aux techniques parallèles de remaillage ; conception d'algorithmes parallèles permettant de scinder le problème global de remaillage parallèle en plusieurs sous-tâches séquentielles, susceptibles de s'exécuter concurremment sur les processeurs de la machine parallèle. Ces contributions ont été mises en oeuvre au sein de la bibliothèque parallèle PaMPA, en s'appuyant sur les briques logicielles MMG3D (remaillage séquentiel de maillages tétraédriques) et PT-Scotch (repartitionnement parallèle de graphes). La bibliothèque PaMPA offre ainsi les fonctionnalités suivantes : communication transparente entre processeurs voisins des valeurs portées par les noeuds, les éléments, etc. ;remaillage, selon des critères fournis par l'utilisateur, de portions du maillage distribué, en offrant une qualité constante, que les éléments à remailler soient portés par un unique processeur ou bien répartis sur plusieurs d'entre eux ; répartition et redistribution de la charge des maillages pour préserver l'efficacité des simulations après remaillage. / The purpose of this thesis was to propose and to validate experimentally a set of algorithmic methods for the parallel remeshing of distributed meshes, based on a preexisting sequential remeshing method. This goal has been achieved through several steps : definition of data structures and of communication schemes suitable for distributed meshes, allowing for cheap migration of subdomain interfaces across the processors of a distributed-memory architecture ; use of dynamic load balancing algorithms suitable for parallel remeshing techniques ; design of parallel algorithms for splitting the global remeshing problem into several independent sequential tasks, susceptible to be executed concurrently across the processors of the parallel machine. These contributions have been implemented into the PaMPA parallel library, taking advantage of the MMG3D (sequential anisotropic tetrahedral remesher) PT-Scotch (parallel graph repartitioning) software. The PaMPA library consequently provides the following features : transparent communication across neighboring processors of data borne by nodes, elements, etc.; remeshing, according to used-defined criteria, of portions of the distributed mesh, that yields constant quality, irrespective of whether elements to be remeshed are located on a single processor or distributed across several of them ; balancing and redistribution of the workload of the mesh, to preserve the efficiency of simulations after the remeshing phase.

La thèse porte sur la résolution des problèmes de satisfaisabilité booléenne (SAT) dans un cadre massivement parallèle. Le problème SAT est largement utilisé pour résoudre des problèmes combinatoires de première importance comme la vérification formelle de matériels et de logiciels, la bio-informatique, la cryptographie, la planification et l’ordonnancement de tâches. Plusieurs contributions sont apportées dans cette thèse. Elles vont de la conception d’algorithmes basés sur les approches « portfolio » et « diviser pour mieux régner », à l’adaptation de modèles de programmation parallèle, notamment hybride (destinés à des architectures à mémoire partagée et distribuée), à SAT, en passant par l’amélioration des stratégies de résolution. Ce travail de thèse a donné lieu à plusieurs contributions dans des conférences internationales du domaine ainsi qu’à plusieurs outils (open sources) de résolution des problèmes SAT, compétitifs au niveau international. / This thesis deals with propositional satisfiability (SAT) in a massively parallel setting. The SAT problem is widely used for solving several combinatorial problems (e.g. formal verification of hardware and software, bioinformatics, cryptography, planning, scheduling, etc.). The first contribution of this thesis concerns the design of efficient algorithms based on the approaches « portfolio » and « divide and conquer ». Secondly, an adaptation of several parallel programming models including hybrid (parallel and distributed computing) to SAT is proposed. This work has led to several contributions to international conferences and highly competitive distributed SAT solvers.

La maîtrise du bruit et des vibrations est un objectif fréquemment rencontré dans le domaine industriel. Qu’il s’agisse de questions de confort ou de sécurité, les domaines d’applications sont nombreux et variés : transport, BTP, ingénierie civile et militaire… Dans cette thèse, un problème de vibroacoustique interne avec couplage fluide-structure est étudié. Il s’agit d’une cavité remplie de fluide dont les parois sont constituées d’une structure sandwich viscoélastique. Les difficultés numériques associées à ce modèle portent sur la non linéarité du matériau et sur les propriétés des opérateurs matriciels manipulés (conditionnement, non symétrie). Le calcul des vibrations du système dissipatif couplé nécessite une valeur initiale, choisie comme la solution du problème conservatif. Cette solution n’étant pas aisée à déterminer, deux solveurs aux valeurs propres basés sur la Méthode Asymptotique Numérique (MAN) sont proposés pour résoudre le problème des vibrations libres du système conservatif. Associant des techniques de perturbation d'ordre élevé et de continuation, la MAN permet de transformer le problème non linéaire de départ en une suite de problèmes linéaires, plus simples à résoudre. Les solutions obtenues sont ensuite utilisées comme point initial pour déterminer la réponse libre du système dissipatif. Un solveur de Newton d’ordre élevé, basé sur les techniques d’homotopie et de perturbation est développé pour résoudre ce problème. Enfin, le régime forcé est étudié. Pour toutes les configurations envisagées, les résultats obtenus mettent en évidence des performances numériques améliorées par rapport aux méthodes classiquement utilisées (Arpack, Newton…). / Noises and vibrations control is a common objective in the industrial field. Whether it is a question of comfort or safety, the fields of application are numerous and varied: transport, building, civil and military engineering… In this thesis, a vibroacoustics interior problem with fluid-structure coupling is studied. A cavity filled of fluid whose walls are made of a sandwich viscoelastic structure is considered. The numerical difficulties associated with this model relate to the non-linearity of the viscoelastic material and the properties of the matrix operators used (conditioning, non-symmetry). The calculation of the vibrations of the coupled dissipative system requires an initial value, chosen as the solution to the conservative problem. Since this solution is difficult to determine, two eigenvalue algorithms based on the Asymptotic Numerical Method (ANM) are proposed to solve the problem of free vibrations of the conservative system. Combining high order perturbation and continuation techniques, ANM transforms the initial non-linear problem into a set of linear problems that are easier to solve. The solutions obtained are then used as the initial point to determine the free vibrations of the dissipative problem. A high order Newton solver, based on homotopy and perturbation techniques, is developed to solve this problem. Finally, the forced harmonic response of the damped system is computed. For all the configurations tested, the results obtained show improved numerical performance compared to the methods conventionally used (Arpack solver, Newton algorithm…).

The central theme of this thesis is the design of optimal balanced black-box stopping criteria in iterative solvers of symmetric positive-definite, symmetric indefinite, and nonsymmetric linear systems arising from finite element approximation of stochastic (parametric) partial differential equations. For a given stochastic and spatial approximation, it is known that iteratively solving the corresponding linear(ized) system(s) of equations to too tight algebraic error tolerance results in a wastage of computational resources without decreasing the usually unknown approximation error. In order to stop optimally-by avoiding unnecessary computations and premature stopping-algebraic error and a posteriori approximation error estimate must be balanced at the optimal stopping iteration. Efficient and reliable a posteriori error estimators do exist for close estimation of the approximation error in a finite element setting. But the algebraic error is generally unknown since the exact algebraic solution is not usually available. Obtaining tractable upper and lower bounds on the algebraic error in terms of a readily computable and monotonically decreasing quantity (if any) of the chosen iterative solver is the distinctive feature of the designed optimal balanced stopping strategy. Moreover, this work states the exact constants, that is, there are no user-defined parameters in the optimal balanced stopping tests. Hence, an iterative solver incorporating the optimal balanced stopping methodology that is presented here will be a black-box iterative solver. Typically, employing such a stopping methodology would lead to huge computational savings and in any case would definitely rule out premature stopping. The constants in the devised optimal balanced black-box stopping tests in MINRES solver for solving symmetric positive-definite and symmetric indefinite linear systems can be estimated cheaply on-the- fly. The contribution of this thesis goes one step further for the nonsymmetric case in the sense that it not only provides an optimal balanced black-box stopping test in a memory-expensive Krylov solver like GMRES but it also presents an optimal balanced black-box stopping test in memory-inexpensive Krylov solvers such as BICGSTAB(L), TFQMR etc. Currently, little convergence theory exists for the memory-inexpensive Krylov solvers and hence devising stopping criteria for them is an active field of research. Also, an optimal balanced black-box stopping criterion is proposed for nonlinear (Picard or Newton) iterative method that is used for solving the finite dimensional Navier-Stokes equations. The optimal balanced black-box stopping methodology presented in this thesis can be generalized for any iterative solver of a linear(ized) system arising from numerical approximation of a partial differential equation. The only prerequisites for this purpose are the existence of a cheap and tight a posteriori error estimator for the approximation error along with cheap and tractable bounds on the algebraic error.

Diffusion is a phenomenon in which particles move from regions of higher density to regions of lower density. Many physical systems, in fields as diverse as plant biology and finance, are known to involve diffusion phenomena. Typically, diffusion systems are modeled by partial differential equations (PDEs), which include certain parameters. These parameters characterize a given diffusion system. Therefore, for both modeling and simulation of a diffusion system, one has to either know or determine these parameters. Moreover, as PDEs are infinite order dynamic systems, for computational purposes one has to approximate them by a finite order model. In this thesis, we investigate these two issues of model reduction and parameter estimation by considering certain specific cases of heat diffusion systems. We first address model reduction by considering two specific cases of heat diffusion systems. The first case is a one-dimensional heat diffusion across a homogeneous wall, and the second case is a two-dimensional heat diffusion across a homogeneous rectangular plate. In the one-dimensional case we construct finite order approximations by using some well known PDE solvers and evaluate their effectiveness in approximating the true system. We also construct certain other alternative approximations for the one-dimensional diffusion system by exploiting the different modal structures inherently present in it. For the two-dimensional heat diffusion system, we construct finite order approximations first using the standard finite difference approximation (FD) scheme, and then refine the FD approximation by using its asymptotic limit. As for parameter estimation, we consider the same one-dimensional heat diffusion system, as in model reduction. We estimate the parameters involved, first using the standard batch estimation technique. The convergence of the estimates are investigated both numerically and theoretically. We also estimate the parameters of the one-dimensional heat diffusion system recursively, initially by adopting the standard recursive prediction error method (RPEM), and later by using two different recursive algorithms devised in the frequency domain. The convergence of the frequency domain recursive estimates is also investigated.

El Método de los Momentos (MoM) ha sido ampliamente utilizado en las últimas décadas para la discretización y la solución de las formulaciones de ecuación integral que aparecen en muchos problemas electromagnéticos de antenas y dispersión. Las más utilizadas de dichas formulaciones son la Ecuación Integral de Campo Eléctrico (EFIE), la Ecuación Integral de Campo Magnético (MFIE) y la Ecuación Integral de Campo Combinada (CFIE), que no es más que una combinación lineal de las dos anteriores.Las formulaciones MFIE y CFIE son válidas únicamente para objetos cerrados y necesitan tratar la integración de núcleos con singularidades de orden superior al de la EFIE. La falta de técnicas eficientes y precisas para el cálculo de dichas integrales singulares a llevado a imprecisiones en los resultados. Consecuentemente, su uso se ha visto restringido a propósitos puramente académicos, incluso cuando tienen una velocidad de convergencia muy superior cuando son resuelto iterativamente, debido a su excelente número de condicionamiento.En general, la principal desventaja del MoM es el alto coste de su construcción, almacenamiento y solución teniendo en cuenta que es inevitablemente un sistema denso, que crece con el tamaño eléctrico del objeto a analizar. Por tanto, un gran número de métodos han sido desarrollados para su compresión y solución. Sin embargo, muchos de ellos son absolutamente dependientes del núcleo de la ecuación integral, necesitando de una reformulación completa para cada núcleo, en caso de que sea posible.Esta tesis presenta nuevos enfoques o métodos para acelerar y incrementar la precisión de ecuaciones integrales discretizadas con el Método de los Momentos (MoM) en electromagnetismo computacional.En primer lugar, un nuevo método iterativo rápido, el Multilevel Adaptive Cross Approximation (MLACA), ha sido desarrollado para acelerar la solución del sistema lineal del MoM. En la búsqueda por un esquema de propósito general, el MLACA es un método independiente del núcleo de la ecuación integral y es puramente algebraico. Mejora simultáneamente la eficiencia y la compresión con respecto a su versión mono-nivel, el ACA, ya existente. Por tanto, representa una excelente alternativa para la solución del sistema del MoM de problemas electromagnéticos de gran escala.En segundo lugar, el Direct Evaluation Method, que ha provado ser la referencia principal en términos de eficiencia y precisión, es extendido para superar el cálculo del desafío que suponen las integrales hiper-singulares 4-D que aparecen en la formulación de Ecuación Integral de Campo Magnético (MFIE) así como en la de Ecuación Integral de Campo Combinada (CFIE). La máxima precisión asequible -precisión de máquina se obtiene en un tiempo más que razonable, sobrepasando a cualquier otra técnica existente en la bibliografía.En tercer lugar, las integrales hiper-singulares mencionadas anteriormente se convierten en casi-singulares cuando los elementos discretizados están muy próximo pero sin llegar a tocarse. Se muestra como las reglas de integración tradicionales tampoco convergen adecuadamente en este caso y se propone una posible solución, basada en reglas de integración más sofisticadas, como la Double Exponential y la Gauss-Laguerre.Finalmente, un esfuerzo en facilitar el uso de cualquier programa de simulación de antenas basado en el MoM ha llevado al desarrollo de un modelo matemático general de un puerto de excitación en el espacio discretizado. Con este nuevo modelo, ya no es necesaria la adaptación de los lados del mallado al puerto en cuestión. / The Method of Moments (MoM) has been widely used during the last decades for the discretization and the solution of integral equation formulations appearing in several electromagnetic antenna and scattering problems. The most utilized of these formulations are the Electric Field Integral Equation (EFIE), the Magnetic Field Integral Equation (MFIE) and the Combined Field Integral Equation (CFIE), which is a linear combination of the other two. The MFIE and CFIE formulations are only valid for closed objects and need to deal with the integration of singular kernels with singularities of higher order than the EFIE. The lack of efficient and accurate techniques for the computation of these singular integrals has led to inaccuracies in the results. Consequently, their use has been mainly restricted to academic purposes, even having a much better convergence rate when solved iteratively, due to their excellent conditioning number. In general, the main drawback of the MoM is the costly construction, storage and solution considering the unavoidable dense linear system, which grows with the electrical size of the object to analyze. Consequently, a wide range of fast methods have been developed for its compression and solution. Most of them, though, are absolutely dependent on the kernel of the integral equation, claiming for a complete re-formulation, if possible, for each new kernel. This thesis dissertation presents new approaches to accelerate or increase the accuracy of integral equations discretized by the Method of Moments (MoM) in computational electromagnetics. Firstly, a novel fast iterative solver, the Multilevel Adaptive Cross Approximation (MLACA), has been developed for accelerating the solution of the MoM linear system. In the quest for a general-purpose scheme, the MLACA is a method independent of the kernel of the integral equation and is purely algebraic. It improves both efficiency and compression rate with respect to the previously existing single-level version, the ACA. Therefore, it represents an excellent alternative for the solution of the MoM system of large-scale electromagnetic problems. Secondly, the direct evaluation method, which has proved to be the main reference in terms of efficiency and accuracy, is extended to overcome the computation of the challenging 4-D hyper-singular integrals arising in the Magnetic Field Integral Equation (MFIE) and Combined Field Integral Equation (CFIE) formulations. The maximum affordable accuracy --machine precision-- is obtained in a more than reasonable computation time, surpassing any other existing technique in the literature. Thirdly, the aforementioned hyper-singular integrals become near-singular when the discretized elements are very closely placed but not touching. It is shown how traditional integration rules fail to converge also in this case, and a possible solution based on more sophisticated integration rules, like the Double Exponential and the Gauss-Laguerre, is proposed. Finally, an effort to facilitate the usability of any antenna simulation software based on the MoM has led to the development of a general mathematical model of an excitation port in the discretized space. With this new model, it is no longer necessary to adapt the mesh edges to the port.

Over the last 25 years, interior-point methods (IPMs) have emerged as a viable class of algorithms for solving various forms of conic optimization problems. Most IPMs use a modified Newton method to determine the search direction at each iteration. The system of equations corresponding to the modified Newton system can often be reduced to the so-called normal equation, a system of equations whose matrix ADA' is positive definite, yet often ill-conditioned. In this thesis, we first investigate the theoretical properties of the maximum weight basis (MWB) preconditioner, and show that when applied to a matrix of the form ADA', where D is positive definite and diagonal, the MWB preconditioner yields a preconditioned matrix whose condition number is uniformly bounded by a constant depending only on A. Next, we incorporate the results regarding the MWB preconditioner into infeasible, long-step, primal-dual, path-following algorithms for linear programming (LP) and convex quadratic programming (CQP). In both LP and CQP, we show that the number of iterative solver iterations of the algorithms can be uniformly bounded by n and a condition number of A, while the algorithmic iterations of the IPMs can be polynomially bounded by n and the logarithm of the desired accuracy. We also expand the scope of the LP and CQP algorithms to incorporate a family of preconditioners, of which MWB is a member, to determine an approximate solution to the normal equation. For the remainder of the thesis, we develop a new preconditioning strategy for solving systems of equations whose associated matrix is positive definite but ill-conditioned. Our so-called adaptive preconditioning strategy allows one to change the preconditioner during the course of the conjugate gradient (CG) algorithm by post-multiplying the current preconditioner by a simple matrix, consisting of the identity matrix plus a rank-one update. Our resulting algorithm, the Adaptive Preconditioned CG (APCG) algorithm, is shown to have polynomial convergence properties. Numerical tests are conducted to compare a variant of the APCG algorithm with the CG algorithm on various matrices.

A direct solution procedure is proposed and developed which exploits the parallelism that exists in current symmetric multiprocessing (SMP) multi-core processors. Several algorithms are proposed and developed to improve the performance of the direct solution of FE problems. A high-performance sparse direct solver is developed which allows experimentation with the newly developed and existing algorithms. The performance of the algorithms is investigated using a large set of FE problems. Furthermore, operation count estimations are developed to further assess various algorithms. An out-of-core version of the solver is developed to reduce the memory requirements for the solution. I/O is performed asynchronously without blocking the thread that makes the I/O request. Asynchronous I/O allows overlapping factorization and triangular solution computations with I/O. The performance of the developed solver is demonstrated on a large number of test problems. A problem with nearly 10 million degree of freedoms is solved on a low price desktop computer using the out-of-core version of the direct solver. Furthermore, the developed solver usually outperforms a commonly used shared memory solver.