Slavova, Tzvetomila. Parallel triangular solution in the outofcore multifrontal approach for solving large sparse linear systems. PhD, Institut National Polytechnique de Toulouse, 2009

(Document in English)
PDF  Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader 1MB 
Official URL: http://ethesis.inptoulouse.fr/archive/00000774/
Abstract
We consider the solution of very large systems of linear equations with direct multifrontal methods. In this context the size of the factors is an important limitation for the use of sparse direct solvers. We will thus assume that the factors have been written on the local disks of our target multiprocessor machine during parallel factorization. Our main focus is the study and the design of efficient approaches for the forward and backward substitution phases after a sparse multifrontal factorization. These phases involve sparse triangular solution and have often been neglected in previous works on sparse direct factorization. In many applications, however, the time for the solution can be the main bottleneck for the performance. This thesis consists of two parts. The focus of the first part is on optimizing the outofcore performance of the solution phase. The focus of the second part is to further improve the performance by exploiting the sparsity of the righthand side vectors. In the first part, we describe and compare two approaches to access data from the hard disk. We then show that in a parallel environment the task scheduling can strongly influence the performance. We prove that a constraint ordering of the tasks is possible; it does not introduce any deadlock and it improves the performance. Experiments on large real test problems (more than 8 million unknowns) using an outofcore version of a sparse multifrontal code called MUMPS (MUltifrontal Massively Parallel Solver) are used to analyse the behaviour of our algorithms. In the second part, we are interested in applications with sparse multiple righthand sides, particularly those with single nonzero entries. The motivating applications arise in electromagnetism and data assimilation. In such applications, we need either to compute the null space of a highly rank deficient matrix or to compute entries in the inverse of a matrix associated with the normal equations of linear leastsquares problems. We cast both of these problems as linear systems with multiple righthand side vectors, each containing a single nonzero entry. We describe, implement and comment on efficient algorithms to reduce the inputoutput cost during an outof core execution. We show how the sparsity of the righthand side can be exploited to limit both the number of operations and the amount of data accessed. The work presented in this thesis has been partially supported by SOLSTICE ANR project (ANR06CIS6010).
Item Type:  PhD Thesis 

Uncontrolled Keywords:  
Institution:  Université de Toulouse > Institut National Polytechnique de Toulouse  Toulouse INP (FRANCE) 
Laboratory name:  
Research Director:  Amestoy, Patrick R. 
Statistics:  download 
Deposited On:  21 Nov 2012 13:51 
Repository Staff Only: item control page