Dissertationen zum Thema „Solveurs linéaires directs“
Geben Sie eine Quelle nach APA, MLA, Chicago, Harvard und anderen Zitierweisen an
Machen Sie sich mit Top-19 Dissertationen für die Forschung zum Thema "Solveurs linéaires directs" bekannt.
Neben jedem Werk im Literaturverzeichnis ist die Option "Zur Bibliographie hinzufügen" verfügbar. Nutzen Sie sie, wird Ihre bibliographische Angabe des gewählten Werkes nach der nötigen Zitierweise (APA, MLA, Harvard, Chicago, Vancouver usw.) automatisch gestaltet.
Sie können auch den vollen Text der wissenschaftlichen Publikation im PDF-Format herunterladen und eine Online-Annotation der Arbeit lesen, wenn die relevanten Parameter in den Metadaten verfügbar sind.
Sehen Sie die Dissertationen für verschiedene Spezialgebieten durch und erstellen Sie Ihre Bibliographie auf korrekte Weise.
Ramet, Pierre. „Optimisation de la communication et de la distribution des données pour des solveurs parallèles directs en algèbre linéaire dense et creuse“. Bordeaux 1, 2000. http://www.theses.fr/2000BOR10506.
Der volle Inhalt der QuelleL'Excellent, Jean-Yves. „Multifrontal Methods: Parallelism, Memory Usage and Numerical Aspects“. Habilitation à diriger des recherches, Ecole normale supérieure de lyon - ENS LYON, 2012. http://tel.archives-ouvertes.fr/tel-00737751.
Der volle Inhalt der QuelleGerest, Matthieu. „Using Block Low-Rank compression in mixed precision for sparse direct linear solvers“. Electronic Thesis or Diss., Sorbonne université, 2023. http://www.theses.fr/2023SORUS447.
Der volle Inhalt der QuelleIn order to solve large sparse linear systems, one may want to use a direct method, numerically robust but rather costly, both in terms of memory consumption and computation time. The multifrontal method belong to this class algorithms, and one of its high-performance parallel implementation is the solver MUMPS. One of the functionalities of MUMPS is the use of Block Low-Rank (BLR) matrix compression, that improves its performance. In this thesis, we present several new techniques aiming at further improving the performance of dense and sparse direct solvers, on top of using a BLR compression. In particular, we propose a new variant of BLR compression in which several floating-point formats are used simultaneously (mixed precision). Our approach is based on an error analysis, and it first allows to reduce the estimated cost of a LU factorization of a dense matrix, without having a significant impact on the error. Second, we adapt these algorithms to the multifrontal method. A first implementation uses our mixed-precision BLR compression as a storage format only, thus allowing to reduce the memory footprint of MUMPS. A second implementation allows to combine these memory gains with time reductions in the triangular solution phase, by switching computations to low precision. However, we notice performance issues related to BLR for this phase, in case the system has many right-hand sides. Therefore, we propose new BLR variants of triangular solution that improve the data locality and reduce data movements, as highlighted by a communication volume analysis. We implement our algorithms within a simplified prototype and within solver MUMPS. In both cases, we obtain time gains
Moreau, Gilles. „On the Solution Phase of Direct Methods for Sparse Linear Systems with Multiple Sparse Right-hand Sides“. Thesis, Lyon, 2018. http://www.theses.fr/2018LYSEN084/document.
Der volle Inhalt der QuelleWe consider direct methods to solve sparse linear systems AX = B, where A is a sparse matrix of size n x n with a symmetric structure and X and B are respectively the solution and right-hand side matrices of size n x nrhs. A is usually factorized and decomposed in the form LU, where L and U are respectively a lower and an upper triangular matrix. Then, the solve phase is applied through two triangular resolutions, named respectively the forward and backward substitutions.For some applications, the very large number of right-hand sides (RHS) in B, nrhs >> 1, makes the solve phase the computational bottleneck. However, B is often sparse and its structure exhibits specific characteristics that may be efficiently exploited to reduce this cost. We propose in this thesis to study the impact of the exploitation of this structural sparsity during the solve phase going through its theoretical aspects down to its actual implications on real-life applications.First, we investigate the asymptotic complexity, in the big-O sense, of the forward substitution when exploiting the RHS sparsity in order to assess its efficiency when increasing the problem size. In particular, we study on 2D and 3D regular problems the asymptotic complexity both for traditional full-rank unstructured solvers and for the case when low-rank approximation is exploited. Next, we extend state-of-the-art algorithms on the exploitation of RHS sparsity, and also propose an original approach converging toward the optimal number of operations while preserving performance. Finally, we show the impact of the exploitation of sparsity in a real-life electromagnetism application in geophysics that requires the solution of sparse systems of linear equations with a large number of sparse right-hand sides. We also adapt the parallel algorithms that were designed for the factorization to solve-oriented algorithms.We validate and combine the previous improvements using the parallel solver MUMPS, conclude on the contributions of this thesis and give some perspectives
Pichon, Grégoire. „On the use of low-rank arithmetic to reduce the complexity of parallel sparse linear solvers based on direct factorization techniques“. Thesis, Bordeaux, 2018. http://www.theses.fr/2018BORD0249/document.
Der volle Inhalt der QuelleSolving sparse linear systems is a problem that arises in many scientific applications, and sparse direct solvers are a time consuming and key kernel for those applications and for more advanced solvers such as hybrid direct-iterative solvers. For those reasons, optimizing their performance on modern architectures is critical. However, memory requirements and time-to-solution limit the use of direct methods for very large matrices. For other approaches, such as iterative methods, general black-box preconditioners that can ensure fast convergence for a wide range of problems are still missing. In the first part of this thesis, we present two approaches using a Block Low-Rank (BLR) compression technique to reduce the memory footprint and/or the time-to-solution of a supernodal sparse direct solver. This flat, non-hierarchical, compression method allows to take advantage of the low-rank property of the blocks appearing during the factorization of sparse linear systems. The proposed solver can be used either as a direct solver at a lower precision or as a very robust preconditioner. The first approach, called Minimal Memory, illustrates the maximum memory gain that can be obtained with the BLR compression method, while the second approach, called Just-In-Time, mainly focuses on reducing the computational complexity and thus the time-to-solution. In the second part, we present a reordering strategy that increases the block granularity to better take advantage of the locality for multicores and provide larger tasks to GPUs. This strategy relies on the block-symbolic factorization to refine the ordering produced by tools such as Metis or Scotch, but it does not impact the number of operations required to solve the problem. From this approach, we propose in the third part of this manuscript a new low-rank clustering technique that is designed to cluster unknowns within a separator to obtain the BLR partition, and demonstrate its assets with respect to widely used clustering strategies. Both reordering and clustering where designed for the flat BLR representation but are also a first step to move to hierarchical formats. We investigate in the last part of this thesis a modified nested dissection strategy that aligns separators with respect to their father to obtain more regular data structure
Chanaud, Mathieu. „Conception d’un solveur haute performance de systèmes linéaires creux couplant des méthodes multigrilles et directes pour la résolution des équations de Maxwell 3D en régime harmonique discrétisées par éléments finis“. Thesis, Bordeaux 1, 2011. http://www.theses.fr/2011BOR14324/document.
Der volle Inhalt der QuelleMultigrid algorithm. The system is solved thanks to a direct method on the coarse mesh anditerative splitting method on refined meshes; inter-grid operators are defined to interpolate theapproximate solutions on the different refinement levels. Applied to 3D electromagnetic simulations(Nédélec first order finite element approximation of time harmonic Maxwell equations) thissolver is used either as a stationary method or as a preconditioner for a Krylov subspace method(GMRES)
Gaidamour, Jérémie. „Conception d'un solveur linéaire creux parallèle hybride direct-itératif“. Phd thesis, Université Sciences et Technologies - Bordeaux I, 2009. http://tel.archives-ouvertes.fr/tel-00456605.
Der volle Inhalt der QuelleGaidamour, Jérémie. „Conception d’un solveur linéaire creux parallèle hybride direct-itératif“. Thesis, Bordeaux 1, 2009. http://www.theses.fr/2009BOR13904/document.
Der volle Inhalt der QuelleThis thesis presents a parallel resolution method for sparse linear systems which combines effectively techniques of direct and iterative solvers using a Schur complement approach. A domain decomposition is built ; the interiors of the subdomains are eliminated by a direct method in order to use an iterative method only on the interface unknowns. The system on the interface (Schur complement) is solved thanks to an iterative method preconditioned by a global incomplete factorization. A special ordering on the Schur complement allows to build a scalable preconditioner. Algorithms minimizing the memory peak that appears during the construction of the preconditioner are presented. The memory is balanced thanks to a multiple domains per processors parallelization scheme. The methods are implemented in the HIPS solver and parallel experimental results are presented on large industrial test cases
Haidar, Azzam. „Sur l'extensibilité parallèle de solveurs linéaires hybrides pour des problèmes tridimensionnels de grandes tailles“. Toulouse, INPT, 2008. http://ethesis.inp-toulouse.fr/archive/00000650/.
Der volle Inhalt der QuelleLarge-scale scientific applications and industrial simulations are nowadays fully integrated in many engineering areas. They involve the solution of large sparse linear systems. The use of large high performance computers is mandatory to solve these problems. The main topic of this research work was the study of a numerical technique that had attractive features for an efficient solution of large scale linear systems on large massively parallel platforms. The goal is to develop a high performance hybrid direct/iterative approach for solving large 3D problems. We focus specifically on the associated domain decomposition techniques for the parallel solution of large linear systems. We have investigated several algebraic preconditioning techniques, discussed their numerical behaviors, their parallel implementations and scalabilities. We have compared their performances on a set of 3D grand challenge problems
Faverge, Mathieu. „Ordonnancement hybride statique-dynamique en algèbre linéaire creuse pour de grands clusters de machines NUMA et multi-coeurs“. Thesis, Bordeaux 1, 2009. http://www.theses.fr/2009BOR13922/document.
Der volle Inhalt der QuelleNew supercomputers incorporate many microprocessors which include themselves one or many computational cores. These new architectures induce strongly hierarchical topologies. These are called NUMA architectures. Sparse direct solvers are a basic building block of many numerical simulation algorithms. They need to be adapted to these new architectures with Non Uniform Memory Accesses. We propose to introduce a dynamic scheduling designed for NUMA architectures in the PaStiX solver. The data structures of the solver, as well as the patterns of communication have been modified to meet the needs of these architectures and dynamic scheduling. We are also interested in the dynamic adaptation of the computation grain to use efficiently multi-core architectures and shared memory. Experiments on several numerical test cases will be presented to prove the efficiency of the approach on different architectures
Haidar, Azzam. „Sur l'extensibilité parallèle de solveurs linéaires hybrides pour des problèmes tridimensionels de grandes tailles“. Phd thesis, Institut National Polytechnique de Toulouse - INPT, 2008. http://tel.archives-ouvertes.fr/tel-00347948.
Der volle Inhalt der QuelleCasadei, Astrid. „Optimisations des solveurs linéaires creux hybrides basés sur une approche par complément de Schur et décomposition de domaine“. Thesis, Bordeaux, 2015. http://www.theses.fr/2015BORD0186/document.
Der volle Inhalt der QuelleIn this thesis, we focus on the parallel solving of large sparse linear systems. Our main interestis on direct-iterative hybrid solvers such as HIPS, MaPHyS, PDSLIN or ShyLU, whichrely on domain decomposition and Schur complement approaches. Althrough these solvers arenot as time and space consuming as direct methods, they still suffer from serious overheads. Ina first part, we thus present the existing techniques for reducing the memory consumption, andwe present a new method which does not impact the numerical robustness of the preconditioner.This technique reduces the memory peak by doing a special scheduling of computation, allocation,and freeing tasks in particular in the Schur coupling blocks of the matrix. In a second part,we focus on the load balancing of the domain decomposition in a parallel context. This problemconsists in partitioning the adjacency graph of the matrix in as many domains as desired. Wepoint out that a good load balancing for the most expensive steps of an hybrid solver such asMaPHyS relies on the balancing of both interior nodes and interface nodes of the domains.Through, until now, graph partitioners such as MeTiS or Scotch used to optimize only thefirst criteria (i.e., the balancing of interior nodes) in the context of sparse matrix ordering. Wepropose different variations of the existing algorithms to improve the balancing of interface nodesand interior nodes simultaneously. All our changes are implemented in the Scotch partitioner.We present our results on large collection of matrices coming from real industrial cases
Gueye, Ibrahima. „Résolution de grands systèmes linéaires issus de la méthode des éléments finis sur des calculateurs massivement parallèles“. Phd thesis, École Nationale Supérieure des Mines de Paris, 2009. http://tel.archives-ouvertes.fr/tel-00477653.
Der volle Inhalt der QuelleMary, Théo. „Solveurs multifrontaux exploitant des blocs de rang faible : complexité, performance et parallélisme“. Thesis, Toulouse 3, 2017. http://www.theses.fr/2017TOU30305/document.
Der volle Inhalt der QuelleWe investigate the use of low-rank approximations to reduce the cost of sparse direct multifrontal solvers. Among the different matrix representations that have been proposed to exploit the low-rank property within multifrontal solvers, we focus on the Block Low-Rank (BLR) format whose simplicity and flexibility make it easy to use in a general purpose, algebraic multifrontal solver. We present different variants of the BLR factorization, depending on how the low-rank updates are performed and on the constraints to handle numerical pivoting. We first investigate the theoretical complexity of the BLR format which, unlike other formats such as hierarchical ones, was previously unknown. We prove that the theoretical complexity of the BLR multifrontal factorization is asymptotically lower than that of the full-rank solver. We then show how the BLR variants can further reduce that complexity. We provide an experimental study with numerical results to support our complexity bounds. After proving that BLR multifrontal solvers can achieve a low complexity, we turn to the problem of translating that low complexity in actual performance gains on modern architectures. We first present a multithreaded BLR factorization, and analyze its performance in shared-memory multicore environments on a large set of real-life problems. We put forward several algorithmic properties of the BLR variants necessary to efficiently exploit multicore systems by improving the arithmetic intensity and the scalability of the BLR factorization. We then move on to the distributed-memory BLR factorization, for which additional challenges are identified and addressed. The algorithms presented throughout this thesis have been implemented within the MUMPS solver. We illustrate the use of our approach in three industrial applications coming from geosciences and structural mechanics. We also compare our solver with the STRUMPACK package, based on Hierarchically Semi-Separable approximations. We conclude this thesis by reporting results on a very large problem (130 millions of unknowns) which illustrates future challenges posed by BLR multifrontal solvers at scale
Lacoste, Xavier. „Scheduling and memory optimizations for sparse direct solver on multi-core/multi-gpu duster systems“. Thesis, Bordeaux, 2015. http://www.theses.fr/2015BORD0016/document.
Der volle Inhalt der QuelleThe ongoing hardware evolution exhibits an escalation in the number, as well as in the heterogeneity, of computing resources. The pressure to maintain reasonable levels of performance and portability forces application developers to leave the traditional programming paradigms and explore alternative solutions. PaStiX is a parallel sparse direct solver, based on a dynamic scheduler for modern hierarchical manycore architectures. In this thesis, we study the benefits and the limits of replacing the highly specialized internal scheduler of the PaStiX solver by two generic runtime systems: PaRSEC and StarPU. Thus, we have to describe the factorization algorithm as a tasks graph that we provide to the runtime system. Then it can decide how to process and optimize the graph traversal in order to maximize the algorithm efficiency for thetargeted hardware platform. A comparative study of the performance of the PaStiX solver on top of its original internal scheduler, PaRSEC, and StarPU frameworks is performed. The analysis highlights that these generic task-based runtimes achieve comparable results to the application-optimized embedded scheduler on homogeneous platforms. Furthermore, they are able to significantly speed up the solver on heterogeneous environments by taking advantage of the accelerators while hiding the complexity of their efficient manipulation from the programmer. In this thesis, we also study the possibilities to build a distributed sparse linear solver on top of task-based runtime systems to target heterogeneous clusters. To permit an efficient and easy usage of these developments in parallel simulations, we also present an optimized distributed interfaceaiming at hiding the complexity of the construction of a distributed matrix to the user
Nuentsa, Wakam Désiré. „Parallélisme et robustesse dans les solveurs hybrides pour grands systèmes linéaires : application à l'optimisation en dynamique des fluides“. Phd thesis, Université Rennes 1, 2011. http://tel.archives-ouvertes.fr/tel-00690965.
Der volle Inhalt der QuelleWeisbecker, Clément. „Improving multifrontal solvers by means of algebraic Block Low-Rank representations“. Phd thesis, Toulouse, INPT, 2013. http://oatao.univ-toulouse.fr/10506/1/weisbecker.pdf.
Der volle Inhalt der QuelleWeisbecker, Clement. „Amélioration des solveurs multifrontaux à l'aide de représentations algébriques rang-faible par blocs“. Phd thesis, Institut National Polytechnique de Toulouse - INPT, 2013. http://tel.archives-ouvertes.fr/tel-00934939.
Der volle Inhalt der QuelleLopez, Florent. „Task-based multifrontal QR solver for heterogeneous architectures“. Thesis, Toulouse 3, 2015. http://www.theses.fr/2015TOU30303/document.
Der volle Inhalt der QuelleTo face the advent of multicore processors and the ever increasing complexity of hardware architectures, programming models based on DAG parallelism regained popularity in the high performance, scientific computing community. Modern runtime systems offer a programming interface that complies with this paradigm and powerful engines for scheduling the tasks into which the application is decomposed. These tools have already proved their effectiveness on a number of dense linear algebra applications. In this study we investigate the design of task-based sparse direct solvers which constitute extremely irregular workloads, with tasks of different granularities and characteristics with variable memory consumption on top of runtime systems. In the context of the qr mumps solver, we prove the usability and effectiveness of our approach with the implementation of a sparse matrix multifrontal factorization based on a Sequential Task Flow parallel programming model. Using this programming model, we developed features such as the integration of dense 2D Communication Avoiding algorithms in the multifrontal method allowing for better scalability compared to the original approach used in qr mumps. In addition we introduced a memory-aware algorithm to control the memory behaviour of our solver and show, in the context of multicore architectures, an important reduction of the memory footprint for the multifrontal QR factorization with a small impact on performance. Following this approach, we move to heterogeneous architectures where task granularity and scheduling strategies are critical to achieve performance. We present, for the multifrontal method, a hierarchical strategy for data partitioning and a scheduling algorithm capable of handling the heterogeneity of resources. Finally we present a study on the reproducibility of executions and the use of alternative programming models for the implementation of the multifrontal method. All the experimental results presented in this study are evaluated with a detailed performance analysis measuring the impact of several identified effects on the performance and scalability. Thanks to this original analysis, presented in the first part of this study, we are capable of fully understanding the results obtained with our solver