A class of preconditioning techniques suitable for partial differential equations of structured and unstructured Mesh
Institution:
Paris 11Disciplines:
Directors:
Abstract EN:
In this thesis, several preconditioning techniques for large sparse linear systems are proposed and compared. In the first part of the thesis, we study preconditioners for partial differential equations defined on structured mesh. In particular, we study nested factorization preconditioner and low frequency tangential filtering preconditioner. A variant of nested factorization is believed to be part of ECLIPSE, a oil reservoir simulator of schlumberger. In this thesis, several preconditioning techniques for large sparse linear systems are proposed and compared. In the first part of the thesis, we study preconditioners for partial differential equations defined on structured mesh. In particular, we study nested factorization preconditioner and low frequency tangential filtering preconditioner. A variant of nested factorization is believed to be part of ECLIPSE, a oil reservoir simulator of schlumberger. In this work, a relaxed version of nested factorization preconditioner is proposed, namely, RNF(a,b) and an effective combination preconditioner is proposed using tangential filtering preconditioner. The multiplicative preconditioning of RNF(0,0) with LFTFD is as robust as the combination of ILU(0) with LFTFD proposed in literature. Moreover, no cost of construction is involved with RNF(0,0). Thus the new combination proposed has less overall cost of construction and less storage requirements. Hence, the method RNF(0,0) can be used as a replacement for ILU(0). It is proved that RNF(0,0) exists and it is convergent for a given SPD matrix. It is also proved that the condition number of RNF(0,0) is O(h^{-2}) which is same as that of ILU(0), where h stands for the mesh size. We prove that the condition number of a modified form of NF is O(h^{-1}) which is no better than MILU. This result indicates that the popular method of NF may not be a good choice for a large 3D problem where the size of the problem becomes significantly larger. Moreover, we prove that the condition number for Modified LFTFD is O(h^{-2/3}), this in turn proves that the method of LFTFD is better than ILU(0) and NF alone. In the second part of the thesis, we present hybrid multilevel parallel preconditioners, which are efficient for a range of problems. The preconditioners presented are NSSOR (Nested SSOR), NMILUR (Nested MILU with rowsum constraint) NMILUC (Nested MILU with colsum constraint). All the methods above can be seen as a multilevel extension of the classical preconditioners like SSOR and MILU (modified ILU). A first attempt is made to implement the NSSOR method on shared memory architecture using cilk++. In this context, another method has been developed which is currently under patent consideration.
Abstract FR:
Dans cette thèse, plusieurs techniques de préconditionnement utiles pour la résolution des systémes linéaires grandes et creux sont proposées et comparées. Dans la première partie de la thèse, nous étudions les préconditionneurs pour des EDPs définies sur le maillage structuré. Particulièrement, nous étudions le préconditionneur appelé ``Nested Factorization'' (NF) et ``Low Frequency tangential Filtering Decomposition'' (LFTFD). On estime qu'une forme modifiée de NF est utilisée dans ECLIPSE, un simulateur de réservoir de pétrole de Schlumberger. Nous proposons ``Relaxed Nested Factorization'' à savoir RNF(a,b). Nous proposons un préconditionneur RNFTF qui est une combinaison de RNF(a,b) et LFTFD. Le méthode RNFTF est aussi robuste que la réconditionneur obtenu en combinant LFTFD avec ILU(0) (LFILU). Contrairement à ILU, la méthode RNF(0,0) n'a pas de coût de construction et n'a pas les exigences de la mémoire supplémentaire. Pour une matrice qui est symétrique définie positive, nous prouvons que RNF(0,0) existe et il est convergente. En utilisant l'analyse de Fourier, nous établissons que le conditionnement de RNF(0,0) varie en O(h^{-2}) et le conditionnement de RNF(1,1) (ou NF) varie en O(h^{-1}), où h étant la taille de la maille. Pendant ses études de LFTFD, nous avons également découvert une forme améliorée de LFTFD, connu sous le nom de MLFTFD. En utilisant l'analyse de Fourier à nouveau, nous prouvons que le conditionnement de MLFTFD est O(h^{-2/3}). Dans la deuxième partie de cette thèse, nous présentons les préconditionneurs qui sont hybrides à plusieurs niveaux. Les préconditionneurs présentés sont NSSOR (Nested SSOR), NMILUR (Nested MILUR with row sum property), et NMILUC (Nested MILUC with column sum property). Toutes ces méthodes peuvent être considérées comme une extension des méthodes multi niveaux de SSOR et MILU. Nous essayons de mettre en oeuvre la méthode NSSOR pour la mémoire partagée en utilisant Cilk++. Dans ce contexte, une autre méthode a été développée et fait l'objet actuel de l'examen d'un brevet.