Dissertations / Theses: 'Multiplication de matrices creuses'

1

Gonon, Antoine. "Harnessing symmetries for modern deep learning challenges : a path-lifting perspective." Electronic Thesis or Diss., Lyon, École normale supérieure, 2024. http://www.theses.fr/2024ENSL0043.

Full text

Abstract:

Les réseaux de neurones connaissent un grand succès pratique, mais les outils théoriques pour les analyser sont encore souvent limités à des situations simples qui ne reflètent pas toute la complexité des cas pratiques d'intérêts. Cette thèse vise à réduire cet écart en rendant les outils théoriques plus concrets. Le premier axe de recherche concerne la généralisation : un réseau donné pourra-t-il bien se comporter sur des données jamais vues auparavant ? Ce travail améliore les garanties de généralisation basées sur la norme de chemins, les rendant applicables à des réseaux ReLU incluant du pooling ou des connexions résiduelles. En réduisant l'écart entre les réseaux analytiquement étudiables et ceux utilisés en pratique, cette thèse permet la première évaluation empirique de ces garanties sur des réseaux ReLU pratiques tels que les ResNets.Le second axe porte sur l'optimisation des ressources (temps, énergie, mémoire). Une nouvelle méthode d'élagage des paramètres, fondée sur la norme de chemins, est proposée. Cette approche conserve non seulement la précision de l'élagage par amplitude, tout en étant robuste aux symétries des paramètres. Cette thèse fournit aussi un nouvel algorithme de multiplication de matrices sur GPU qui améliore l'état de l'art pour les matrices creuses à support de Kronecker, offrant des gains en temps et en énergie. Enfin, ce travail rend les garanties d'approximation pour les réseaux de neurones plus concrètes en établissant des conditions suffisantes de précision en bits pour que les réseaux quantifiés conservent la même vitesse d'approximation que les réseaux avec des poids réels non contraints
Neural networks have demonstrated impressive practical success, but theoretical tools for analyzing them are often limited to simple cases that do not capture the complexity of real-world applications. This thesis seeks to narrow this gap by making theoretical tools more applicable to practical scenarios.The first focus of this work is on generalization: can a given network perform well on previously unseen data? This thesis improves generalization guarantees based on the path-norm and extends their applicability to ReLU networks incorporating pooling or skip connections. By reducing the gap between theoretically analyzable networks and those used in practice, this work provides the first empirical evaluation of these guarantees on practical ReLU networks, such as ResNets.The second focus is on resource optimization (time, energy, memory). This thesis introduces a novel pruning method based on the path-norm, which not only retains the accuracy of traditional magnitude pruning but also exhibits robustness to parameter symmetries. Additionally, this work presents a new GPU matrix multiplication algorithm that enhances the state-of-the-art for sparse matrices with Kronecker-structured support, achieving gains in both time and energy. Finally, this thesis makes approximation guarantees for neural networks more concrete by establishing sufficient bit-precision conditions to ensure that quantized networks maintain the same approximation speed as their unconstrained real-weight counterparts

APA, Harvard, Vancouver, ISO, and other styles

2

Lawson, Jean-Christophe. "Smart : un neurocalculateur parallèle exploitant des matrices creuses." Grenoble INPG, 1993. http://www.theses.fr/1993INPG0030.

Full text

Abstract:

Les annees 80 montrerent l'eclosion du paradigme neuromimetique qui sommeillait depuis un demi-siecle. La simulation interactive intensive est un element cle pour des progres de cette approche qui fait generalement appel a des systemes non lineaires de grande taille. Ainsi, la faible efficacite des calculateurs est un element qui ralentit le developpement de nouveaux modeles. Bien que les modeles existant fassent apparaitre des comportements prometteurs, le fosse separant ces modeles des architectures nerveuses reste abyssal. L'analyse des principales caracteristiques nerveuses et leur traduction en termes informatique est le point de depart a l'amelioration de l'efficacite et des performances. Ainsi, le comportement dynamique est un element a developper a de multiples niveaux. Dans ce memoire, nous rappelons quelques aspects biologiques des structures nerveuses et nous les mettons en relief selon le point de vue du traitement de l'information. Ensuite, nous resumons certains principes fondamentaux du traitement parallele. Nous les exploitons alors dans la partie principale de ce travail pour proposer un calculateur a jeu d'instructions reduit (risc) faisant un tres large appel au traitement en temps masque (pipeline), pour un traitement vectoriel distribue. Un tel modele de calcul assure une bonne efficacite pour les taches tres repetitives qui sont impliquees dans les modeles neuromimetiques: le traitement distribue est bien adapte au faible taux de reutilisation de nombreuses donnees et une structure lineaire permet des echanges et une supervision aises. Une procedure de repartition des donnees, associee a des ressources materielles specifiques, autorise un traitement distribue efficace sur des matrices creuses de topologie dynamique. Une double mise en uvre logicielle et materielle est proposee a partir d'un modele risc standard (sparc). Une evaluation de performance est egalement fournie. La conclusion de ce travail est qu'un formalisme vectoriel est bien adapte a la description des reseaux neuromimetiques et a leur mise en uvre parallele, l'exploitation efficace de matrices de connexion creuses permet alors la simulation efficace des modeles les plus generaux. Cela implique a la fois un materiel specifique et un environnement logiciel adapte

APA, Harvard, Vancouver, ISO, and other styles

3

Geronimi, Sylvain. "Determination d'ensembles essentiels minimaux dans les matrices creuses : application a l'analyse des circuits." Toulouse 3, 1987. http://www.theses.fr/1987TOU30104.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Vömel, Christof. "Contributions à la recherche en calcul scientifique haute performance pour les matrices creuses." Toulouse, INPT, 2003. http://www.theses.fr/2003INPT003H.

Full text

Abstract:

Nous nous intéressons au développement d'un nouvel algorithme pour estimer la norme d'une matrice de manière incrémentale, à l'implantation d'un modèle de référence des Basic Linear Algebra Subprograms for sparse matrices (Sparse BLAS), et à la réalisation d'un nouveau gestionnaire de tâches pour MUMPS, un solveur multifrontal pour des architectures à mémoire distribuée. Notre méthode pour estimer la norme d'une matrice s'applique aux matrices denses et creuses. Elle peut s'avérer utile dans le cadre des factorisations QR, Cholesky, ou LU. Le standard Sparse BLAS définit des interfaces génériques. Nous avons été amenés à répondre aux questions concernant la représentation et la gestion des données. Le séquencement de tâches devient un enjeu important dès que nous travaillons sur un grand nombre de processeurs. Grâce à notre nouvelle approche, nous pouvons améliorer le passage a l'échelle du solveur MUMPS.

APA, Harvard, Vancouver, ISO, and other styles

5

Grigori, Laura. "Prédiction de structure et algorithmique parallèle pour la factorisation LU des matrices creuses." Nancy 1, 2001. http://www.theses.fr/2001NAN10264.

Full text

Abstract:

Cette thèse traite du calcul numérique parallèle et les résultats de recherche portent sur la factorisation LU, telle qu'elle est utilisée pour résoudre des systèmes linéaires creux non-symétriques. En général, les calculs sur des matrices creuses ont une phase initiale de prédiction structurelle de la sortie, qui permet l'allocation de la mémoire, l'initialisation des structures de données et l'ordonnancement des tâches en parallèle. Dans ce but, nous étudions la prédiction structurelle pour la factorisation LU avec pivotage partiel. Nous nous intéressons principalement à identifier des limites supérieures aussi proches que possible de ces structures. Cette prédiction de structure est ensuite utilisée dans une étape appelée étape de factorisation symbolique qui précède l'étape de calcul numérique effectif des facteurs appelée étape de factorisation numérique. Pour des matrices de très grande taille, une partie significative de l'espace mémoire globale est nécessaire pour des structures utilisées lors de l'étape de factorisation symbolique, et ceci pourrait empêcher l'exécution de la factorisation LU. Nous proposons et étudions un algorithme parallèle pour améliorer les besoins en mémoire de la factorisation symbolique. Pour une exécution parallèle efficace de la factorisation numérique, nous considérons l'analyse et la manipulation des graphes de dépendances de données issus du traitement des matrices creuses. Cette analyse nous permet de développer des algorithmes scalables, qui utilisent d'une manière efficace la mémoire et les ressources de calcul disponibles
This dissertation treats of parallel numerical computing considering the Gaussian elimination, as it is used to solve large sparse nonsymmetric linear systems. Usually, computations on sparse matrices have an initial phase that predicts the nonzero structure of the output, which helps with memory allocations, set up data structures and schedule parallel tasks prior to the numerical computation itself. To this end, we study the structure prediction for the sparse LU factorization with partial pivoting. We are mainly interested to identify upper bounds as tight as possible to these structures. This structure prediction is then used in a phase called symbolic factorization, followed by a phase that performs the numerical computation of the factors, called numerical factorization. For very large matrices, a significant part of the overall memory space is needed by structures used during the symbolic factorization, and this can prevent a swap-free execution of the LU factorization. We propose and study a parallel algorithm to decrease the memory requirements of the nonsymmetric symbolic factorization. For an efficient parallel execution of the numerical factorization, we consider the analysis and the handling of the data dependencies graphs resulting from the processing of sparse matrices. This analysis enables us to develop scalable algorithms, which manage memory and computing resources in an effective way

APA, Harvard, Vancouver, ISO, and other styles

6

Geronimi, Sylvain. "Détermination d'ensembles essentiels minimaux dans les matrices creuses application à l'analyse des circuits /." Grenoble 2 : ANRT, 1987. http://catalogue.bnf.fr/ark:/12148/cb376053608.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Puglisi, Chiara. "Factorisation QR de grandes matrices creuses basée sur une méthode multifrontale dans un environnement multiprocesseur." Toulouse, INPT, 1993. http://www.theses.fr/1993INPT091H.

Full text

Abstract:

Nous nous interessons a la factorisation qr de grandes matrices creuses carrees et sur-determinees dans un environnement mimd a memoire partagee. Nous supposons que le rang des vecteurs colonnes de ces matrices est maximal. Notre demarche est basee sur la methode multifrontale (duff et reid (1983)) et utilise les transformations de householder. Nous donnons une description detaillee de l'approche multifrontale pour la factorisation qr et de son implementation dans un environnement multiprocesseur. Nous montrons qu'en choisissant de facon adequate la strategie de factorisation de nuds, des gains considerables peuvent etre obtenus, aussi bien du point de vue de la memoire que du parallelisme et du temps de calcul. Un niveau de parallelisme supplementaire est utilise pour equilibrer le manque de parallelisme pres de la racine de l'arbre d'elimination. Par ailleurs, nous decrivons aussi comment modifier l'arbre d'elimination pour ameliorer les performances du code. Nous examinons ensuite les problemes de stabilite et de precision numerique de la factorisation qr en tant que methode de resolution des systemes lineaires et des problemes de moindres carres. Nous etudions l'influence du raffinement iteratif et du pivotage des lignes et montrons qu'il existe des matrices pour lesquelles une solution precise ne peut etre obtenue que si la factorisation qr est effectuee avec un pivotage par lignes et suivie de quelques etapes de raffinement iteratif. Finalement, nous etudions la factorisation qr en tant que methode de resolution des problemes de moindres carres et nous la comparons a trois autres approches classiques: la methode des equations normales, la methode des equations semi-normales, et l'approche par systeme augmente. La methode qr s'avere etre particulierement appropriee pour les problemes tres mal conditionnes. En outre, notre code parallele optimise est efficace sur toutes les classes de problemes que nous avons testees

APA, Harvard, Vancouver, ISO, and other styles

8

EDJLALI, GUY. "Contribution a la parallelisation de methodes iteratives hybrides pour matrices creuses sur architectures heterogenes." Paris 6, 1994. http://www.theses.fr/1994PA066360.

Full text

Abstract:

Cette these traite de programmation parallele heterogene, des structures de donnees irregulieres et de methode iterative hybride. La methode iterative choisie est la methode d'arnoldi de calcul de valeurs propres et de vecteurs propres de matrices creuses. Dans une premiere partie, une implementation data-parallele de cette methode a ete realisee. Cela a permis de mettre en evidence le comportement du programme et les lacunes existantes au niveau des outils de manipulation de matrices creuses. Dans une deuxieme partie, nous avons developpe des outils de manipulation de matrices creuses et propose un format de stockage data parallele de matrices creuses generales. Ce format est utilise pour implementer le noyau d'une bibliotheque data parallele de manipulation de matrices creuses. Dans une troisieme partie, nous avons etudie les structures de donnees irregulieres pour les machines mimd a memoire distribuee. Cette etude a mis en evidence l'interet de la compilation a l'execution. Nous avons etendu la compilation a l'execution aux environnements adaptatifs, c'est-a-dire aux environnements dont le nombre de processeurs varie a l'execution. Enfin, a travers le calcul de valeurs propres et de vecteurs propres, nous avons aborde les environnements d'execution heterogenes. Nous avons propose une methode d'arnoldi hybride s'executant sur un ensemble de machines paralleles distribuees. Nous avons mis en evidence la necessite de nouveaux algorithmes pour exploiter ces ensembles de machines

APA, Harvard, Vancouver, ISO, and other styles

9

Brown, Christopher Ian. "A VLSI device for multiplication of high order sparse matrices." Thesis, University of Sheffield, 1997. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.265915.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Guermouche, Abdou. "Étude et optimisation du comportement mémoire dans les méthodes parallèles de factorisation de matrices creuses." Lyon, École normale supérieure (sciences), 2004. http://www.theses.fr/2004ENSL0284.

Full text

Abstract:

Les méthodes directes de résolution de systèmes linéaires creux sont connues pour leurs besoins mémoire importants qui peuvent constituer une barrière au traitement de problèmes de grandes taille. De ce fait, les travaux effectués durant cette thèse ont porté d'une part sur l'étude du comportement mémoire d'un algorithme de factorisation de matrices creuses, en l'occurrence la méthode multifrontale, et d'autre part sur l'optimisation et la minimisation de la mémoire nécessaire au bon déroulement de la factorisation aussi bien dans un cadre séquentiel que parallèle. Ainsi, des algorithmes optimaux pour la minimisation de la mémoire ont été proposés pour le cas séquentiel. Pour le cas parallèle, nous avons introduit dans un premier temps des stratégies d'ordonnancement visant une amélioration du comportement mémoire de la méthode. Puis, nous les avons étendues pour avoir un objectif de performance tout en gardant un bon comportement mémoire. Enfin, dans le cas où l'ensemble des données à traiter a encore une taille plus importante que celle de la mémoire, il est nécessaire de concevoir des approches de factorisation out-of-core. Pour être efficaces, ces méthodes nécessitent d'une part de recouvrir les opérations d'entrées/sorties par des calculs, et d'autre part de réutiliser des données déjà présentes en mémoire pour réduire le volume d'entrées/sorties. Ainsi, une partie des travaux présentés dans cette thèse ont porté sur la conception de techniques out-of-core implicites adaptées au schéma des accès de la méthode multifrontale et reposant sur une modification de la politique de pagination du système d'exploitation à l'aide d'un outil bas-niveau (MMUM&MMUSSEL)
Direct methods for solving sparse linear systems are known for their large memory requirements that can represent the limiting factor to solve large systems. The work done during this thesis concerns the study and the optimization of the memory behaviour of a sparse direct method, the multifrontal method, for both the sequential and the parallel cases. Thus, optimal memory minimization algorithms have been proposed for the sequential case. Concerning the parallel case, we have introduced new scheduling strategies aiming at improving the memory behaviour of the method. After that, we extended these approaches to have a good performance while keeping a good memory behaviour. In addition, in the case where the data to be treated cannot fit into memory, out-of-core factorization schemes have to be designed. To be efficient, such approaches require to overlap I/O operations with computations and to reuse the data sets already in memory to reduce the amount of I/O operations. Therefore, another part of the work presented in this thesis concerns the design and the study of implicit out-of-core techniques well-adapted to the memory access pattern of the multifrontal method. These techniques are based on a modification of the standard paging policies of the operating system using a low-level tool (MMUM&MMUSSEL)

APA, Harvard, Vancouver, ISO, and other styles

11

Callant, Julien. "Méthodes numériques pour le calcul des valeurs propres les plus à droite des matrices creuses de très grande taille." Doctoral thesis, Universite Libre de Bruxelles, 2012. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/209578.

Full text

Abstract:

Méthodes numériques pour le calcul des valeurs propres les plus à droite des matrices creuses et non-hermitiennes de très grande taille
Doctorat en Sciences de l'ingénieur
info:eu-repo/semantics/nonPublished

APA, Harvard, Vancouver, ISO, and other styles

12

Kunchum, Rakshith. "On Improving Sparse Matrix-Matrix Multiplication on GPUs." The Ohio State University, 2017. http://rave.ohiolink.edu/etdc/view?acc_num=osu1492694387445938.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Nguyen, Duc Kien. "Parallélisation des algorithmes de multiplication rapide de matrices sur machines à mémoire distribuée." Paris 8, 2007. http://www.theses.fr/2007PA083778.

Full text

Abstract:

Les algorithmes de la multiplication rapide de matrices (FMM) pour multiplier deux matrices n x n réduisent le nombre asymptotique d'opérations de O (n³) de la méthode traditionnelle à O (n²,xx), donc la parallélisation des algorithmes de FMM donne des résultats remarquables par rapport aux algorithmes parallèles de multiplication matricielle basés sur la méthode traditionnelle. Dans cette parallélisation, l'application des algorithmes de FMM au niveau inter-processeur nécessite une conception plus fine de celle-ci mais conduit à des algorithmes plus efficaces. Pour utiliser des algorithmes de FMM au niveau inter-processeur, le point le plus important est de déterminer les sous-matrices après avoir appliqué r fois les formules de FMM et puis de trouver la matrice résultat à partir des produits de ces sous-matrices. Avec une valeur définie de r, nous pouvons manuellement résoudre ce problème comme dans les travaux précédents avec r=1,2, mais la solution pour le cas général n'est pas encore trouvée. Dans cette thèse, en combinant notre solution générale pour ce problème avec un bon modèle de stockage des sous-matrices, et avec les algorithmes parallèles de multiplication matricielle basés sur la méthode traditionnelle (1D-systolic, 2D-systolic, Fox (BMR), Cannon, PUMMA, BiMMeR, SUMMA, DIMMA. . . ) nous avons une voie générale de parallélisation adaptative des algorithmes de FMM sur machines à mémoire distribuée. L'analyse de complexité prouve que nos algorithmes sont plus rapides que les algorithmes parallèles basés sur la méthode traditionnelle quand la taille de matrice est grande et notre travail est pertinent pour exploiter de meilleurs algorithmes quand le niveau de récursivité est assez grand. Les résultats expérimentaux sur Fujitsu Siemens Computers/hpcLine confirment le résultat théorique en montrant que nos algorithmes sont plus rapides que l'algorithme de Cannon de 1,2 à 2,4 fois pour les matrices de taille 8196 x 8196
Fast matrix multiplication (FMM) algorithms to multiply two n x n matrices reduce the asymptotic operation count from O (n³) of the traditional method to O (n². Xx), thus the parallelization of FMM algorithms always gives remarkable results in comparison to the parallel matrix multiplication algorithms based on traditional method. Within this parallelization, the application of FMM algorithms at the inter-processor level requires us to solve more difficult problems in designing but it forms the most effective algorithms. To use FMM algorithms at the inter-processor level, the most significant point is to determine the submatrices after having recursively executed r times the FMM formulas and then to find the result matrix from the products of these sub matrices. With a definite value of r, we can manually solve this problem like in the previous works with r=1,2, but the solution for the general case has not been found. In this PhD work, by combining our general solution for this problem with a good storage map of submatrices to processor, and with the parallel matrix multiplication algorithms based on traditional method (1D-systolic, 2D-systolic, Fox (BMR), Cannon, PUMMA, BiMMeR, SUMMA, DIMMA. . . ) we have a general scalable parallelization of FMM algorithms on distributed memory computers. Complexity analyses show that our algorithms should be faster than the parallel algorithms based on traditional method when the matrix size is large and our work is relevant to exploit better algorithms when the recursion level is large enough. Experimental results on Fujitsu Siemens Computers/hpcLine confirm the theoretical result by showing that our algorithms perform better than Cannon's Algorithm from 1. 2 to 2. 4 times for matrices of size 8196 x 8196

APA, Harvard, Vancouver, ISO, and other styles

14

Amestoy, Patrick. "Factorisation de grandes matrices creuses non symétriques basée sur une méthode multifrontale dans un environnement multiprocesseur." Toulouse, INPT, 1990. http://www.theses.fr/1990INPT050H.

Full text

Abstract:

Nous nous interessons aux methodes directes de resolution des grands systemes lineaires creux. Nous considerons la factorisation lu dans un environnement mimd a memoire partagee. Notre demarche est basee sur la methode multifrontale (duff et reid 1983), ou les taches sont distribuees parmi les processeurs selon un arbre d'elimination qui peut etre engendre automatiquement a partir de n'importe quelle strategie de pivotage. L'algorithme original de duff (1969) a ete modifie afin d'ameliorer ses performances du point de vue de la vectorisation et de la parallelisation. Nous montrons que, meme si une implementation optimale du code depend des caracteristiques de la machine utilisee, un ensemble limite de parametres peut etre mis en place pour controler l'efficacite du code dans un environnement multiprocesseur. La croissance des valeurs numeriques durant la factorisation est controlee a l'aide d'un pivotage partiel avec critere de seuil. Le pivotage partiel degrade les performances de la factorisation. Nous decrivons comment modifier la strategie de pivotage pour reduire le remplissage durant la factorisation. Nous etudions enfin l'influence de l'equilibrage de la matrice sur la precision numerique et sur l'efficacite du solveur. La comparaison avec d'autres methodes montre que nous avons combine la portabilite, l'efficacite, et la precision sur un grand nombre de calculateurs a memoire partagee. Nous montrons finalement que la methode multifrontale est un outil efficace pour la resolution de nombreux problemes numeriques poses par la mecanique des fluides

APA, Harvard, Vancouver, ISO, and other styles

15

Etoa, Etoa Jean-Bosco. "Methodes simpliciales numeriquement stables pour la resolution de programmes lineaires a matrices des contraintes tres creuses." Paris 6, 1987. http://www.theses.fr/1987PA066784.

Full text

Abstract:

Proposition de codes permettant de reduire de maniere considerable le montre d'operations elementaires necessaires a la resolution des differents systemes lineaires inherents a chaque iteration de la methode du simplexe

APA, Harvard, Vancouver, ISO, and other styles

16

Hamdi-Larbi, Olfa. "Étude de la Distribution, sur Système à Grande Échelle, de Calcul Numérique Traitant des Matrices Creuses Compressées." Phd thesis, Université de Versailles-Saint Quentin en Yvelines, 2010. http://tel.archives-ouvertes.fr/tel-00693322.

Full text

Abstract:

Plusieurs applications scientifiques effectuent des calculs sur des matrices creuses de grandes tailles. Pour des raisons d'efficacité en temps et en espace lors du traitement de ces matrices, elles sont stockées selon des formats compressés adéquats. D'un autre coté, la plupart des calculs scientifiques creux se ramènent aux deux problèmes fondamentaux d'algèbre linéaire i.e. la résolution de systèmes linéaires et le calcul d'éléments (valeurs/vecteurs) propres de matrices. Nous étudions dans ce mémoire la distribution, au sein d'un Système Distribué à Grande Echelle (SDGE), des calculs dans des méthodes itératives de résolution de systèmes linéaires et de calcul d'éléments propres et ce, dans le cas creux. Le produit matricevecteur creux (PMVC) constitue le noyau de base pour la plupart de ces méthodes. Notre problématique se ramène en fait à l'étude de la distribution du PMVC sur un SDGE. Généralement, trois étapes sont nécessaires pour accomplir cette tâche, à savoir, (i) le prétraitement, (ii) le traitement et (iii) le post-traitement. Dans la première étape, nous procédons d'abord à l'optimisation de quatre versions de l'algorithme du PMVC correspondant à quatre formats de compression spécifiques de la matrice, puis étudions leurs performances sur des machines cibles séquentielles. Nous nous focalisons de plus sur l'étude de l'équilibrage des charges pour la distribution des données traitées (se ramenant en fait aux lignes de la matrice creuse) sur un SDGE. Concernant l'étape de traitement, elle a consisté à valider l'étude précédente par une série d'expérimentations réalisées sur une plate-forme gérée par l'intergiciel XtremWeb-CH. L'étape de post-traitement, quant à elle, a consisté à analyser et interpréter les résultats expérimentaux obtenus au niveau de l'étape précédente et ce, afin d'en tirer des conclusions adéquates.

APA, Harvard, Vancouver, ISO, and other styles

17

Hamdi-Larbi, Olfa. "Etude de la distribution, sur système à grande échelle, de calcul numérique traitant des matrices creuses compressées." Versailles-St Quentin en Yvelines, 2010. http://www.theses.fr/2010VERS0018.

Full text

Abstract:

Plusieurs applications scientifiques effectuent des calculs sur des matrices creuses de grandes tailles. Pour des raisons d'efficacité en temps et en espace lors du traitement de ces matrices, elles sont stockées selon des formats compressés adéquats. D'un autre côté, la plupart des calculs scientifiques creux se ramènent aux deux problèmes fondamentaux d'algèbre linéaire i. E. La résolution des systèmes linéaires (RSL) et le calcul d'éléments propres (CEP) de matrices. Nous étudions dans ce mémoire la distribution, au sein d'un Système Distribué à Grande Echelle (SDGE), des calculs dans des méthodes itératives de RSL et de CEP et ce, dans le cas creux. Le produit matrice-vecteur creux (PMVC) constitue le noyau de base pour la plupart de ces méthodes. Notre problématique se ramène en fait à l'étude de la distribution du PMVC sur un SDGE. Généralement, trois étapes sont nécessaires pour accomplir cette tâche, à savoir, le prétraitement, le traitement et le post-traitement. Dans la première étape, nous procédons d'abord à l'optimisation de quatre versions de l'algorithme du PMVC correspondant à quatre formats de compression spécifiques de la matrice, puis étudions leurs performances sur des machines cibles séquentielles. Nous nous focalisons de plus sur l'étude de l'équilibrage des charges pour la distribution des données traitées sur un SDGE. Concernant l'étape de traitement, elle a consisté à valider l'étude précédente par une série d'expérimentations réalisées sur une plate-forme gérée par l'intergiciel XtremWeb-CH. L'étape de post-traitement, quant à elle, a consisté à analyser et interpréter les résultats expérimentaux obtenus au niveau de l'étape précédente
Several scientific applications often use kernels performing computations on large sparse matrices. For reasons of efficiency in time and space, specific compression formats are used for storing such matrices. Most of sparse scientific computations address sparse linear algebra problems. Here two fundamental problems are often considered i. E. Linear systems resolution (LSR) and matrix eigen-values/vector computation (EVC). In this thesis, we address the problem of distributing, onto a Large Scale Distributed System (LSDS), computations performed in iterative methods for both LSR and EVC. The sparse matrix-vector product (SMVP) constitutes a basic kernel in such iterative mathods. Thus, our problem reduces to the SMVP distribution study on an LSDS. In principle, three phases are required for achieving this kind of applications, namely, pre -processing, processing and post-processing. In phase 1, we first proceed to the optimization of four versions of the SMVP algorithm corresponding to four specific matrix compressing formats, then study their performances on sequential target machines. In addition, we focus on the study of load balancing in the procedure of data (i. E. The sparse matrix rows) distribution on a LSDS. Concerning the processing phase, it consists in validating the previous study by a series of experimentations achieved on a volunteer distributed system we installed through using XtremWeb-CH middleware. As to the post-processing phase, it consists in interpreting the experimental results previously obtained in order to deduce adequate conclusions

APA, Harvard, Vancouver, ISO, and other styles

18

Boyer, Brice. "Multiplication matricielle efficace et conception logicielle pour la bibliothèque de calcul exact LinBox." Phd thesis, Université de Grenoble, 2012. http://tel.archives-ouvertes.fr/tel-00767915.

Full text

Abstract:

Dans ce mémoire de thèse, nous développons d'abord des multiplications matricielles efficaces. Nous créons de nouveaux ordonnancements qui permettent de réduire la taille de la mémoire supplémentaire nécessaire lors d'une multiplication du type Winograd tout en gardant une bonne complexité, grâce au développement d'outils externes ad hoc (jeu de galets), à des calculs fins de complexité et à de nouveaux algorithmes hybrides. Nous utilisons ensuite des technologies parallèles (multicœurs et GPU) pour accélérer efficacement la multiplication entre matrice creuse et vecteur dense (SpMV), essentielles aux algorithmes dits /boîte noire/, et créons de nouveaux formats hybrides adéquats. Enfin, nous établissons des méthodes de /design/ générique orientées vers l'efficacité, notamment par conception par briques de base, et via des auto-optimisations. Nous proposons aussi des méthodes pour améliorer et standardiser la qualité du code de manière à pérenniser et rendre plus robuste le code produit. Cela permet de pérenniser de rendre plus robuste le code produit. Ces méthodes sont appliquées en particulier à la bibliothèque de calcul exact LinBox.

APA, Harvard, Vancouver, ISO, and other styles

19

Andersson, Tobias, and Christoffer Brenden. "Parallelism in Go and Java : A Comparison of Performance Using Matrix Multiplication." Thesis, Blekinge Tekniska Högskola, Institutionen för programvaruteknik, 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:bth-16548.

Full text

Abstract:

This thesis makes a comparison between the performance of Go and Java using parallelizedimplementations of the Classic Matrix Multiplication Algorithm (CMMA). The comparisonattempts to only use features for parallelization, goroutines for Go and threads for Java,while keeping other parts of the code as generic and comparable as possible to accuratelymeasure the performance during parallelization.In this report we ask the question of how programming languages compare in terms of multi-threaded performance? In high-performance systems such as those designed for mathemati-cal calculations or servers meant to handle requests from millions of users, multithreadingand by extension performance are vital. We would like to find out if and how much of a dif-ference the choice of programming language could benefit these systems in terms of parallel-ism and multithreading.Another motivation is to analyze techniques and programming languages that have emergedthat hide the complexity of handling multithreading and concurrency from the user, lettingthe user specify keywords or commands from which the language takes over and creates andmanages the thread scheduling on its own. The Go language is one such example. Is this newtechnology an improvement over developers coding threads themselves or is the technologynot quite there yet?To these ends experiments were done with multithreaded matrix multiplication and was im-plemented using goroutines for Go and threads for Java and was performed with sets of4096x4096 matrices. Background programs were limited and each set of calculations wasthen run multiple times to get average values for each calculation which were then finallycompared to one another.Results from the study showed that Go had ~32-35% better performance than Java between 1and 4 threads, with the difference diminishing to ~2-5% at 8 to 16 threads. The differencehowever was believed to be mostly unrelated to parallelization as both languages maintainednear identical performance scaling as the number of threads increased until the scaling flat-lined for both languages at 8 threads and up. Java did continue to gain a slight increase goingfrom 4 to 8 threads, but this was believed to be due to inefficient resource utilization onJava’s part or due to Java having better utilization of hyper-threading than Go.In conclusion, Go was found to be considerably faster than Java when going from the mainthread and up to 4 threads. At 8 threads and onward Java and Go performed roughly equal.For performance difference between the number of threads in the languages themselves nonoticeable performance increase or decrease was found when creating 1 thread versus run-ning the matrix multiplication directly on the main thread for either of the two languages.Coding multithreading in Go was found to be easier than in Java while providing greater toequal performance. Go just requires the ‘go’ keyword while Java requires thread creation andmanagement. This would put Go in favor for those trying to avoid the complexity of multi-threading while also seeking its benefits.

APA, Harvard, Vancouver, ISO, and other styles

20

Sibut, Pinote Thomas. "Investigations in Computer-Aided Mathematics : Experimentation, Computation, and Certification." Thesis, Université Paris-Saclay (ComUE), 2017. http://www.theses.fr/2017SACLX086/document.

Full text

Abstract:

Cette thèse propose trois contributions aux preuves mathématiques assistées par ordinateur. On s'intéresse non seulement aux preuves reposant sur le calcul, mais aussi aux preuves formelles, qui sont àla fois produites et vérifiées à l'aide d'un logiciel appelé assistant à la preuve.Dans la première partie, nous illustrons le thème de l'expérimentation au service de la preuve en nous intéressant au problème de la complexité des algorithmes de multiplication matricielle. Cette question a historiquement été posée de manière de plus en plus abstraite: les approches modernes ne construisent pas d'algorithmes explicites mais utilisent des résultats théoriques pour améliorer la borne inférieure sur la célèbre constante oméga. Nous sommes revenus à une approche plus pratique en essayant de programmer certains des algorithmes impliqués par ces résultats théoriques. Cette approche expérimentale a révélé un motif inattendu dans des algorithmes existants. Alors que ces algorithmes contiennent une nouvelle variable epsilon dont la présence est réputée les rendre impraticables pour des tailles de matrices raisonnables, nous avons découvert que nous pouvions construire des algorithmes de multiplication matricielle en parallèle sans epsilon avec une complexité asymptotique qui peut théoriquement battre l'algorithme de Strassen pour les multiplications. Un sous-produit de cette exploration est un outil symbolique en Ocaml qui peut analyser, composer et exporter des algorithmes de multiplication matricielle. Nous pensons aussi qu'il pourrait être utilisé pour construire de nouveaux algorithmes pratiques de multiplication matricielle.Dans la deuxième partie, nous décrivons une preuve formelle de l'irrationalité de la constante zeta(3), en suivant la démonstration historique due à Apéry. L'étape cruciale de cette preuve est d'établir que deux suites de nombres rationnels satisfont une surprenante récurrence commune. Il est en fait possible de "découvrir"cette récurrence en utilisant des algorithmes symboliques, et leurs implémentations existantes dans un système de calcul formel. De fait,ce travail constitue un exemple d'une approche dite sceptique de la démonstration formelle de théorèmes, dans lequel des calculs sont principalement réalisés par un logiciel efficace de calcul formel puis vérifiés formellement dans un assistant à la preuve. Incidemment, ce travail questionne la valeur des certificats de télescopage créatif comme preuves complètes d'identités. Cette preuve formelle est également basée sur de nouvelles bibliothèques de mathématiques,formalisées pour ses besoins. En particulier, nous avons formalisé et simplifié une étude du comportement asymptotique de la suite ppcm(1,.., n). Ce travail est conduit dans l'assistant à la preuve Coq et prolonge les bibliothèques Mathematical Components.Dans la dernière partie, nous présentons une procédure qui calcule les approximations d'une classe d'intégrales propres et impropres tout en produisant simultanément un preuve formelle Coq de la correction du résultat de ce calcul. Cette procédure utilise une combinaison d'arithmétique d'intervalles et d'approximations polynomiales rigoureuses de fonctions. Ce travail utilise crucialement les possibilités de calculer efficacement à l'intérieur de la logique sous-jacente au système Coq. Il s'agit d'une extension de la bibliothèque CoqInterval d'approximation numérique d'une classe d'expressions réelles. Sa mise en œuvre a également donné lieu à des extensions de la bibliothèque Coquelicot d'analyse réelle, notamment pour améliorer le traitement des intégrales impropres. Nous illustrons l'intérêt de cet outil et ses performances en traitant des exemples standards mais non triviaux de la littérature, sur lesquels d'autres outils se sont en certains cas révélés incorrects
This thesis proposes three contributions to computer-aidedmathematical proofs. It deals, not only with proofs relying oncomputations, but also with formal proofs, which are both produced andverified using a piece of software called a proof assistant.In the first part, we illustrate the theme of experimentation at theservice of proofs by considering the problem of the complexity ofmatrix multiplication algorithms. This problem has historically beenapproached in an increasingly abstract way: modern approaches do notconstruct algorithms but use theoretical results to improve the lowerbound on the famous omega constant. We went back to a more practicalapproach by attempting to program some of the algorithms implied bythese theoretical results. This experimental approach reveals anunexpected pattern in some existing algorithms. While these algorithmscontain a new variable epsilon whose presence is reputed to renderthem inefficient for the purposes of reasonable matrix sizes, we havediscovered that we could build matrix multiplication algorithms inparallel without epsilon's with an asymptotic complexity which cantheoretically beat Strassen's algorithm in terms of the number ofmultiplications. A by-product of this exploration is a symbolic toolin Ocaml which can analyze, compose and export matrix multiplicationalgorithms. We also believe that it could be used to build newpractical algorithms for matrix multiplication.In the second part, we describe a formal proof of the irrationality ofthe constant zeta (3), following the historical demonstration due toApéry. The crucial step of this proof is to establish that twosequences of rational numbers satisfy a suprising commonrecurrence. It is in fact possible to "discover" this recurrence usingsymbolic algorithms, and their existing implementations in a computeralgebra system. In fact, this work is an example of a skepticalapproach to the formal proof of theorems, in which computations aremainly accomplished by an efficient computer algebra program, and thenformally verified in a proof assistant. Incidentally, this workquestions the value of creative telescoping certificates as completeproofs of identities. This formal proof is also based on newmathematical libraries, which were formalised for its needs. Inparticular, we have formalized and simplified a study of theasymptotic behaviour of the sequence lcm(1,..., n). This work isdeveloped in the Coq proof assistant and extends the MathematicalComponents libraries.In the last part, we present a procedure which computes approximationsof a class of proper and improper integrals while simultaneouslyproducing a Coq formal proof of the correction of the result of thiscomputation. This procedure uses a combination of interval arithmeticand rigorous polynomial approximations of functions. This work makescrucial use of the possibility to efficiently compute inside Coq'slogic. It is an extension of the CoqInterval library providingnumerical approximation of a class of real expressions. Itsimplementation has also resulted in extensions to the Coquelicotlibrary for real analysis, including a better treatment of improperintegrals. We illustrate the value of this tool and its performanceby dealing with standard but nontrivial examples from the literature,on which other tools have in some cases been incorrect

APA, Harvard, Vancouver, ISO, and other styles

21

DOUADI, KAMEL. "Etude et mise en oeuvre de logiciels rapides et numeriquement stables d'optimisation sans contraintes : cas de matrices de contraintes creuses." Paris 6, 1989. http://www.theses.fr/1989PA066155.

Full text

Abstract:

On considere le probleme d'optimisation non lineaire a contraintes lineaires. L'algorithme adopte est une variante de la methode de murtagh et saunders. La minimisation dans la direction de recherche est effectuee a l'aide d'une nouvelle methode d'optimisation monodimensionnelle due a abadie. La nouvelle matrice de base est actualisee a l'aide d'un nouvel algorithme de la methode de bartels et golub dans le cas de matrices creuses. La direction de recherche dans le sous-espace des variables superbasiques est calculee a l'aide de la methode des gradients conjugues version beale-powell

APA, Harvard, Vancouver, ISO, and other styles

22

De, Lara Nathan. "Algorithmic and software contributions to graph mining." Electronic Thesis or Diss., Institut polytechnique de Paris, 2020. http://www.theses.fr/2020IPPAT029.

Full text

Abstract:

Depuis l'invention du PageRank par Google pour les requêtes Web à la fin des années 1990, les algorithmes de graphe font partie de notre quotidien. Au milieu des années 2000, l'arrivée des réseaux sociaux a amplifié ce phénomène, élargissant toujours plus les cas d'usage de ces algorithmes. Les relations entre entités peuvent être de multiples sortes : relations symétriques utilisateur-utilisateur pour Facebook ou LinkedIn, relations asymétriques follower-followee pour Twitter, ou encore, relations bipartites utilisateur-contenu pour Netflix ou Amazon. Toutes soulèvent des problèmes spécifiques et les applications sont nombreuses : calcul de centralité pour la mesure d'influence, le partitionnement de nœuds pour la fouille de données, la classification de nœuds pour les recommandations ou l'embedding pour la prédiction de liens en sont quelques exemples.En parallèle, les conditions d'utilisation des algorithmes de graphe sont devenues plus contraignantes. D'une part, les jeux de données toujours plus gros avec des millions d'entités et parfois des milliards de relations limite la complexité asymptotique des algorithmes pour les applications industrielles. D'autre part, dans la mesure où ces algorithmes influencent nos vies, les exigences d'explicabilité et d'équité dans le domaine de l'intelligence artificielle augmentent. Les algorithmes de graphe ne font pas exception à la règle. L'Union européenne a par exemple publié un guide de conduite pour une IA fiable. Ceci implique de pousser encore plus loin l'analyse des modèles actuels, voire d'en proposer de nouveaux.Cette thèse propose des réponses ciblées via l'analyse d'algorithmes classiques, mais aussi de leurs extensions et variantes, voire d'algorithmes originaux. La capacité à passer à l'échelle restant un critère clé. Dans le sillage de ce que le projet Scikit-learn propose pour l'apprentissage automatique sur données vectorielles, nous estimons qu'il est important de rendre ces algorithmes accessibles au plus grand nombre et de démocratiser la manipulation de graphes. Nous avons donc développé un logiciel libre, Scikit-network, qui implémente et documente ces algorithmes de façon simple et efficace. Grâce à cet outil, nous pouvons explorer plusieurs tâches classiques telles que l'embedding de graphe, le partitionnement, ou encore la classification semi-supervisée
Since the introduction of Google's PageRank method for Web searches in the late 1990s, graph algorithms have been part of our daily lives. In the mid 2000s, the arrival of social networks has amplified this phenomenon, creating new use-cases for these algorithms. Relationships between entities can be of multiple types: user-user symmetric relationships for Facebook or LinkedIn, follower-followee asymmetric ones for Twitter or even user-content bipartite ones for Netflix or Amazon. They all come with their own challenges and the applications are numerous: centrality calculus for influence measurement, node clustering for knowledge discovery, node classification for recommendation or embedding for link prediction, to name a few.In the meantime, the context in which graph algorithms are applied has rapidly become more constrained. On the one hand, the increasing size of the datasets with millions of entities, and sometimes billions of relationships, bounds the asymptotic complexity of the algorithms for industrial applications. On the other hand, as these algorithms affect our daily lives, there is a growing demand for explanability and fairness in the domain of artificial intelligence in general. Graph mining is no exception. For example, the European Union has published a set of ethics guidelines for trustworthy AI. This calls for further analysis of the current models and even new ones.This thesis provides specific answers via a novel analysis of not only standard, but also extensions, variants, and original graph algorithms. Scalability is taken into account every step of the way. Following what the Scikit-learn project does for standard machine learning, we deem important to make these algorithms available to as many people as possible and participate in graph mining popularization. Therefore, we have developed an open-source software, Scikit-network, which implements and documents the algorithms in a simple and efficient way. With this tool, we cover several areas of graph mining such as graph embedding, clustering, and semi-supervised node classification

APA, Harvard, Vancouver, ISO, and other styles

23

Zhang, Ye. "Méthodes itératives hybrides asynchrones sur plateformes de calcul hétérogènes pour la résolution accélérée de grands systèmes linéaires." Thesis, Lille 1, 2009. http://www.theses.fr/2009LIL10129/document.

Full text

Abstract:

Nous étudions dans cette thèse une méthode hybride de résolution des systèmes linéaires GMRES/LS-Arnoldi qui accélère la convergence grâce à la connaissance des valeurs propres calculées parallèlement par la méthode d’Arnoldi dans les cas réels. Le caractère asynchrone de cette méthode présente l’avantage de fonctionner avec une architecture hétérogène. Une étude de cas complexe est également faite en effectuant la transformation de la matrice complexe en une matrice réelle de dimension double. Nous avons mis en oeuvre la méthode GMRES hybride ainsi que la méthode GMRES générale sur trois différents types de plates-formes matérielles. Il s’agit respectivement de supercalculateurs IBM série SP, plates-formes matérielles typiquement centralisées; de Grid5000, une plate-forme matérielle typiquement distribuée, et de Tsubame (Tokyo-tech Supercomputer and Ubiquitously Accessible Massstorage Environment) supercalculateur, dont certains noeuds sont munis d’une carte accélératrice. Nous avons testé les performances de GMRES général et de GMRES hybride sur ces trois plates-formes, en observant l’influence des nombreux paramètres sur les performances. Des résultats significatifs ont ainsi été obtenus, nous permettant non seulement d'améliorer les performances du calcul parallèle, mais aussi de préciser le sens de nos efforts futurs
In this thesis, we have studied an effective parallel hybrid method of solving linear systems, GMRES / LS-Arnoldi, which accelerates the convergence through knowledge of some eigenvalues calculated in paralled by the Arnoldi method in real cases. The asynchronous nature of this method has the advantage of working with a heterogeneous architecture. A study in complex cases is also done by transforming the complex matrix into a real matrix of double dimension. We have implemented our hybrid GMRES method and the general GMRES method on three different types of hardware platforms. They are respectively the IBM SP series supercomputer, a typically centralized hardware platform; Grid5000, a fully distributed hardware platform, and the Tsubame (Tokyo-tech Supercomputer and Ubiquitously Accessible Massstorage Environment) supercomputer, where some nodes are equipped with an accelerator card. We have tested the performance of general GMRES and hybrid GMRES on these three platforms, observing the influence of various parameters for the performance. A number of meaningful results have been obtained; we can not only improve the performance of parallel computing but also specify the direction of our future efforts

APA, Harvard, Vancouver, ISO, and other styles

24

Wu, Wenhao. "High-performance matrix multiplication hierarchical data structures, optimized kernel routines, and qualitative performance modeling /." Master's thesis, Mississippi State : Mississippi State University, 2003. http://library.msstate.edu/etd/show.asp?etd=etd-07092003-003633.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Covanov, Svyatoslav. "Algorithmes de multiplication : complexité bilinéaire et méthodes asymptotiquement rapides." Thesis, Université de Lorraine, 2018. http://www.theses.fr/2018LORR0057/document.

Full text

Abstract:

Depuis 1960 et le résultat fondateur de Karatsuba, on sait que la complexité de la multiplication (d’entiers ou de polynômes) est sous-quadratique : étant donné un anneau R quelconque, le produit sur R[X] des polynômes a_0 + a_1 X et b_0 + b_1 X, pour tous a_0, a_1, b_0 et b_1 dans R, peut être calculé en seulement trois et non pas quatre multiplications sur R : (a_0 + a_1 X)(b_0 + b_1 X) = m_0 + (m_2 - m_0 - m_1)X + m_1 X^2, avec les trois produits m_0 = a_0b_0, m_1 = a_1b_1 et m_2 = (a_0 + a_1)(b_0 + b_1). De la même manière, l’algorithme de Strassen permet de multiplier deux matrices 2nx2n en seulement sept produits de matrices nxn. Les deux exemples précédents tombent dans la catégorie des applications bilinéaires : des fonctions de la forme Phi : K^m x K^n -> K^l, pour un corps donné K, linéaires en chacune des deux variables. Parmi les applications bilinéaires les plus classiques, on trouve ainsi la multiplication de polynômes, de matrices, ou encore d’éléments d’extensions algébriques de corps finis. Étant donnée une application bilinéaire Phi, calculer le nombre minimal de multiplications nécessaires au calcul de cette application est un problème NP-difficile. L'objectif de cette thèse est de proposer des algorithmes minimisant ce nombre de multiplications. Deux angles d'attaques ont été suivis. Un premier aspect de cette thèse est l'étude du problème du calcul de la complexité bilinéaire sous l'angle de la reformulation de ce problème en termes de recherche de sous-espaces vectoriels de matrices de rang donné. Ce travail a donné lieu à un algorithme tenant compte de propriétés intrinsèques aux produits considérés tels que les produits matriciels ou polynomiaux sur des corps finis. Cet algorithme a permis de trouver toutes les décompositions possibles, sur F_2, pour le produit de polynômes modulo X^5 et le produit de matrices 3x2 par 2x3. Un autre aspect de ma thèse est celui du développement d’algorithmes asymptotiquement rapides pour la multiplication entière. Une famille particulière d'algorithmes récents ont été proposés suite à un article de Fürer publié en 2007, qui proposait un premier algorithme, reposant sur la transformée de Fourier rapide (FFT) permettant de multiplier des entiers de n bits en O(n log n 2^{O(log^* n)}), où log^* est la fonction logarithme itéré. Dans cette thèse, un algorithme dont la complexité dépend d'une conjecture de théorie des nombres est proposé, reposant sur la FFT et l'utilisation de premiers généralisés de Fermat. Une analyse de complexité permet d'obtenir une estimation en O(n log n 4^{log^* n})
Since 1960 and the result of Karatsuba, we know that the complexity of the multiplication (of integers or polynomials) is sub-quadratic: given a ring R, the product in R[X] of polynomials a_0 + a_1 X and b_0 + b_1 X, for any a_0, a_1, b_0 and b_1 in R, can be computed with three and not four multiplications over R: (a_0 + a_1X)(b_0 + b_1X) = m_0 + (m_2 - m_0 - m_1)X + m_1X^2, with the three multiplications m_0 = a_0b_0, m_1 = a_1b_1 et m_2 = (a_0 + a_1)(b_0 + b_1). In the same manner, Strassen's algorithm allows one to multiply two matrices 2nx2n with only seven products of matrices nxn. The two previous examples fall in the category of bilinear maps: these are functions of the form Phi : K^m x K^n -> K^l, given a field K, linear in each variable. Among the most classical bilinear maps, we have the multiplication of polynomials, matrices, or even elements of algebraic extension of finite fields. Given a bilinear map Phi, computing the minimal number of multiplications necessary to the evaluation of this map is a NP-hard problem. The purpose of this thesis is to propose algorithms minimizing this number of multiplications. Two angles of attack have been studied. The first aspect of this thesis is to study the problem of the computation of the bilinear complexity under the angle of the reformulation of this problem in terms of research of matrix subspaces of a given rank. This work led to an algorithm taking into account intrinsic properties of the considered products such as matrix or polynomial products over finite fields. This algorithm allows one to find all the possible decompositions, over F_2, for the product of polynomials modulo X^5 and the product of matrices 3x2 by 2x3. Another aspect of this thesis was the development of fast asymptotic methods for the integer multiplication. There is a particular family of algorithms that has been proposed after an article by Fürer published in 2007. This article proposed a first algorithm, relying on fast Fourier transform (FFT), allowing one to multiply n-bit integers in O(n log n 2^{O(log^* n)}), where log^* is the iterated logarithm function. In this thesis, an algorithm, relying on a number theoretical conjecture, has been proposed, involving the use of FFT and generalized Fermat primes. With a careful complexity analysis of this algorithm, we obtain a complexity in O(nlog n 4^{log^* n})

APA, Harvard, Vancouver, ISO, and other styles

26

Covanov, Svyatoslav. "Algorithmes de multiplication : complexité bilinéaire et méthodes asymptotiquement rapides." Electronic Thesis or Diss., Université de Lorraine, 2018. http://www.theses.fr/2018LORR0057.

Full text

Abstract:

Depuis 1960 et le résultat fondateur de Karatsuba, on sait que la complexité de la multiplication (d’entiers ou de polynômes) est sous-quadratique : étant donné un anneau R quelconque, le produit sur R[X] des polynômes a_0 + a_1 X et b_0 + b_1 X, pour tous a_0, a_1, b_0 et b_1 dans R, peut être calculé en seulement trois et non pas quatre multiplications sur R : (a_0 + a_1 X)(b_0 + b_1 X) = m_0 + (m_2 - m_0 - m_1)X + m_1 X^2, avec les trois produits m_0 = a_0b_0, m_1 = a_1b_1 et m_2 = (a_0 + a_1)(b_0 + b_1). De la même manière, l’algorithme de Strassen permet de multiplier deux matrices 2nx2n en seulement sept produits de matrices nxn. Les deux exemples précédents tombent dans la catégorie des applications bilinéaires : des fonctions de la forme Phi : K^m x K^n -> K^l, pour un corps donné K, linéaires en chacune des deux variables. Parmi les applications bilinéaires les plus classiques, on trouve ainsi la multiplication de polynômes, de matrices, ou encore d’éléments d’extensions algébriques de corps finis. Étant donnée une application bilinéaire Phi, calculer le nombre minimal de multiplications nécessaires au calcul de cette application est un problème NP-difficile. L'objectif de cette thèse est de proposer des algorithmes minimisant ce nombre de multiplications. Deux angles d'attaques ont été suivis. Un premier aspect de cette thèse est l'étude du problème du calcul de la complexité bilinéaire sous l'angle de la reformulation de ce problème en termes de recherche de sous-espaces vectoriels de matrices de rang donné. Ce travail a donné lieu à un algorithme tenant compte de propriétés intrinsèques aux produits considérés tels que les produits matriciels ou polynomiaux sur des corps finis. Cet algorithme a permis de trouver toutes les décompositions possibles, sur F_2, pour le produit de polynômes modulo X^5 et le produit de matrices 3x2 par 2x3. Un autre aspect de ma thèse est celui du développement d’algorithmes asymptotiquement rapides pour la multiplication entière. Une famille particulière d'algorithmes récents ont été proposés suite à un article de Fürer publié en 2007, qui proposait un premier algorithme, reposant sur la transformée de Fourier rapide (FFT) permettant de multiplier des entiers de n bits en O(n log n 2^{O(log^* n)}), où log^* est la fonction logarithme itéré. Dans cette thèse, un algorithme dont la complexité dépend d'une conjecture de théorie des nombres est proposé, reposant sur la FFT et l'utilisation de premiers généralisés de Fermat. Une analyse de complexité permet d'obtenir une estimation en O(n log n 4^{log^* n})
Since 1960 and the result of Karatsuba, we know that the complexity of the multiplication (of integers or polynomials) is sub-quadratic: given a ring R, the product in R[X] of polynomials a_0 + a_1 X and b_0 + b_1 X, for any a_0, a_1, b_0 and b_1 in R, can be computed with three and not four multiplications over R: (a_0 + a_1X)(b_0 + b_1X) = m_0 + (m_2 - m_0 - m_1)X + m_1X^2, with the three multiplications m_0 = a_0b_0, m_1 = a_1b_1 et m_2 = (a_0 + a_1)(b_0 + b_1). In the same manner, Strassen's algorithm allows one to multiply two matrices 2nx2n with only seven products of matrices nxn. The two previous examples fall in the category of bilinear maps: these are functions of the form Phi : K^m x K^n -> K^l, given a field K, linear in each variable. Among the most classical bilinear maps, we have the multiplication of polynomials, matrices, or even elements of algebraic extension of finite fields. Given a bilinear map Phi, computing the minimal number of multiplications necessary to the evaluation of this map is a NP-hard problem. The purpose of this thesis is to propose algorithms minimizing this number of multiplications. Two angles of attack have been studied. The first aspect of this thesis is to study the problem of the computation of the bilinear complexity under the angle of the reformulation of this problem in terms of research of matrix subspaces of a given rank. This work led to an algorithm taking into account intrinsic properties of the considered products such as matrix or polynomial products over finite fields. This algorithm allows one to find all the possible decompositions, over F_2, for the product of polynomials modulo X^5 and the product of matrices 3x2 by 2x3. Another aspect of this thesis was the development of fast asymptotic methods for the integer multiplication. There is a particular family of algorithms that has been proposed after an article by Fürer published in 2007. This article proposed a first algorithm, relying on fast Fourier transform (FFT), allowing one to multiply n-bit integers in O(n log n 2^{O(log^* n)}), where log^* is the iterated logarithm function. In this thesis, an algorithm, relying on a number theoretical conjecture, has been proposed, involving the use of FFT and generalized Fermat primes. With a careful complexity analysis of this algorithm, we obtain a complexity in O(nlog n 4^{log^* n})

APA, Harvard, Vancouver, ISO, and other styles

27

Bassomo, Pierre. "Contribution à la parallélisation de méthodes numériques à matrices creuses skyline. Application à un module de calcul de modes et fréquences propres de Systus." Phd thesis, Ecole Nationale Supérieure des Mines de Saint-Etienne, 1999. http://tel.archives-ouvertes.fr/tel-00822654.

Full text

Abstract:

L'augmentation continue de la puissance des ordinateurs personnels (stations de travail ou PCs) et l'émergence de réseaux à haut débits fournissent de nouvelle opportunités de réalisation de machines parallèle à faible coût, en comparaison des machines parallèles traditionnelles. On peut aujourd 'hui construire de véritables machines parallèles en interconnectant des processeurs standards. Le fonctionnement de cet ensemble de processeurs en tant que machines parallèle est alors assuré par des logiciels tels que PVM et MPI. Quelle que soit la machine parallèle considérée, concevoir des applications parallèles impose, soit des outils de parallélisation automatique, soit un effort du programmeur suivant des méthodologies de programmation. Dans cette thèse, nous proposons une méthodologie de parallélisation des méthodes numériques. En général les méthodes numériques sont une chaîne d'algorithmes s'appelant les uns après les autres tout au long de leur exécution. A moins d'aborder leur parallélisation à partir du problème physique qu'elles traitent, par exemple par des techniques de décomposition de domaines, l'approche de parallélisation la plus réaliste est celle de type client/serveur.

APA, Harvard, Vancouver, ISO, and other styles

28

Bassomo, Pierre. "Contribution à la parallélisation de méthodes numériques à matrices creuses skylines : application à un module de calcul de modes et fréquences propres de SYSTUS." Saint-Etienne, EMSE, 1999. http://tel.archives-ouvertes.fr/docs/00/82/26/54/PDF/1999_Bassomo_Pierre.pdf.

Full text

Abstract:

L'augmentation continue de la puissance des ordinateurs personnels (stations de travail ou PCs) et l'émergence de réseaux à haut débits fournissent de nouvelle opportunités de réalisation de machines parallèle à faible coût, en comparaison des machines parallèles traditionnelles. On peut aujourd 'hui construire de véritables machines parallèles en interconnectant des processeurs standards. Le fonctionnement de cet ensemble de processeurs en tant que machines parallèle est alors assuré par des logiciels tels que PVM et MPI. Quelle que soit la machine parallèle considérée, concevoir des applications parallèles impose, soit des outils de parallélisation automatique, soit un effort du programmeur suivant des méthodologies de programmation. Dans cette thèse, nous proposons une méthodologie de parallélisation des méthodes numériques. En général les méthodes numériques sont une chaîne d'algorithmes s'appelant les uns après les autres tout au long de leur exécution. A moins d'aborder leur parallélisation à partir du problème physique qu'elles traitent, par exemple par des techniques de décomposition de domaines, l'approche de parallélisation la plus réaliste est celle de type client/serveur
Distributed memory machines consisting of multiple autonomous processors connected by a network are becoming commonplace. Unlike specialized machines like systolic arrays, such systems of autonomous processors provide virtual parallelism through standard message passing libraries {PVM or MPI). In the area of parallelizing existing numerical algorithms, two main approaches have been proposed: automatic parallelization techniques and explicit parallelization. In the present work, we focus our studies on the second approach. The parallelization paradigm found to be most effective for numerical algorithms on distributed memory machine was to provide the user with a clientjserver architecture. The most difficult part to design is the SPMD code which is initiated by a client process to speedup the computing time. To do this, our methodology aims: at reusing the systolic model principles for the display of the potential parallelism inside nested loops, and justifying the the aggregation of iteration of loops so as to reduce communication overheads while exploiting coarse-grained parallelism. Each aggregation is a bloc of fine-grained computations not located in the same hyperplan of a given space. It also defines an atomic unit of computation i. E no synchronization or communication is necessary during the execution of the fine-grained computations inside a bloc. Thus all necessary data must be available before such atomic executions. This imposes the constraint that splitting the set of fine-grained computations does not result in deadlocks

APA, Harvard, Vancouver, ISO, and other styles

29

Welin-Berger, Robert, and Anton Bäckström. "Optimizing Strassen's multiplication algorithm for modern processors : A study in optimizing matrix multiplications for large matrices on modern CPUs." Thesis, KTH, Skolan för datavetenskap och kommunikation (CSC), 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-186418.

Full text

Abstract:

This paper examines how to write code to gain high performance on modern computers as well as the importance of well planned data structures. The experiments were run on a computer with an Intel i5-5200U CPU, 8GB of RAM running Linux Mint 17.For the measurements Winograd's variant of Strassen's matrix multiplication algorithm was implemented and eventually compared to Intel's math kernel library (MKL). A quadtree data structure was implemented to ensure good cache locality. Loop unrolling and tiling was combined to improve cache performance on both L1 and L2 cache taking into regard the out of order behavior of modern CPUs. Compiler hints were partially used but a large part of the time critical code was written in pure assembler. Measurements of the speed performance of both floats and doubles were performed and substantial differences in running times were found.While there was a substantial difference between the best implementation and MKL for both doubles and floats at smaller sizes, a difference of only 1\% in execution time was achieved for floats at the size of 2^14. This was achieved without any specific tuning and could be expected to be improved if more time was spent on the implementation.

APA, Harvard, Vancouver, ISO, and other styles

30

Falco, Aurélien. "Bridging the Gap Between H-Matrices and Sparse Direct Methods for the Solution of Large Linear Systems." Thesis, Bordeaux, 2019. http://www.theses.fr/2019BORD0090/document.

Full text

Abstract:

De nombreux phénomènes physiques peuvent être étudiés au moyen de modélisations et de simulations numériques, courantes dans les applications scientifiques. Pour être calculable sur un ordinateur, des techniques de discrétisation appropriées doivent être considérées, conduisant souvent à un ensemble d’équations linéaires dont les caractéristiques dépendent des techniques de discrétisation. D’un côté, la méthode des éléments finis conduit généralement à des systèmes linéaires creux, tandis que les méthodes des éléments finis de frontière conduisent à des systèmes linéaires denses. La taille des systèmes linéaires en découlant dépend du domaine où le phénomène physique étudié se produit et tend à devenir de plus en plus grand à mesure que les performances des infrastructures informatiques augmentent. Pour des raisons de robustesse numérique, les techniques de solution basées sur la factorisation de la matrice associée au système linéaire sont la méthode de choix utilisée lorsqu’elle est abordable. A cet égard, les méthodes hiérarchiques basées sur de la compression de rang faible ont permis une importante réduction des ressources de calcul nécessaires pour la résolution de systèmes linéaires denses au cours des deux dernières décennies. Pour les systèmes linéaires creux, leur utilisation reste un défi qui a été étudié à la fois par la communauté des matrices hiérarchiques et la communauté des matrices creuses. D’une part, la communauté des matrices hiérarchiques a d’abord exploité la structure creuse du problème via l’utilisation de la dissection emboitée. Bien que cette approche bénéficie de la structure hiérarchique qui en résulte, elle n’est pas aussi efficace que les solveurs creux en ce qui concerne l’exploitation des zéros et la séparation structurelle des zéros et des non-zéros. D’autre part, la factorisation creuse est accomplie de telle sorte qu’elle aboutit à une séquence d’opérations plus petites et denses, ce qui incite les solveurs à utiliser cette propriété et à exploiter les techniques de compression des méthodes hiérarchiques afin de réduire le coût de calcul de ces opérations élémentaires. Néanmoins, la structure hiérarchique globale peut être perdue si la compression des méthodes hiérarchiques n’est utilisée que localement sur des sous-matrices denses. Nous passons en revue ici les principales techniques employées par ces deux communautés, en essayant de mettre en évidence leurs propriétés communes et leurs limites respectives, en mettant l’accent sur les études qui visent à combler l’écart qui les séparent. Partant de ces observations, nous proposons une classe d’algorithmes hiérarchiques basés sur l’analyse symbolique de la structure des facteurs d’une matrice creuse. Ces algorithmes s’appuient sur une information symbolique pour grouper les inconnues entre elles et construire une structure hiérarchique cohérente avec la disposition des non-zéros de la matrice. Nos méthodes s’appuient également sur la compression de rang faible pour réduire la consommation mémoire des sous-matrices les plus grandes ainsi que le temps que met le solveur à trouver une solution. Nous comparons également des techniques de renumérotation se fondant sur des propriétés géométriques ou topologiques. Enfin, nous ouvrons la discussion à un couplage entre la méthode des éléments finis et la méthode des éléments finis de frontière dans un cadre logiciel unique
Many physical phenomena may be studied through modeling and numerical simulations, commonplace in scientific applications. To be tractable on a computer, appropriated discretization techniques must be considered, which often lead to a set of linear equations whose features depend on the discretization techniques. Among them, the Finite Element Method usually leads to sparse linear systems whereas the Boundary Element Method leads to dense linear systems. The size of the resulting linear systems depends on the domain where the studied physical phenomenon develops and tends to become larger and larger as the performance of the computer facilities increases. For the sake of numerical robustness, the solution techniques based on the factorization of the matrix associated with the linear system are the methods of choice when affordable. In that respect, hierarchical methods based on low-rank compression have allowed a drastic reduction of the computational requirements for the solution of dense linear systems over the last two decades. For sparse linear systems, their application remains a challenge which has been studied by both the community of hierarchical matrices and the community of sparse matrices. On the one hand, the first step taken by the community of hierarchical matrices most often takes advantage of the sparsity of the problem through the use of nested dissection. While this approach benefits from the hierarchical structure, it is not, however, as efficient as sparse solvers regarding the exploitation of zeros and the structural separation of zeros from non-zeros. On the other hand, sparse factorization is organized so as to lead to a sequence of smaller dense operations, enticing sparse solvers to use this property and exploit compression techniques from hierarchical methods in order to reduce the computational cost of these elementary operations. Nonetheless, the globally hierarchical structure may be lost if the compression of hierarchical methods is used only locally on dense submatrices. We here review the main techniques that have been employed by both those communities, trying to highlight their common properties and their respective limits with a special emphasis on studies that have aimed to bridge the gap between them. With these observations in mind, we propose a class of hierarchical algorithms based on the symbolic analysis of the structure of the factors of a sparse matrix. These algorithms rely on a symbolic information to cluster and construct a hierarchical structure coherent with the non-zero pattern of the matrix. Moreover, the resulting hierarchical matrix relies on low-rank compression for the reduction of the memory consumption of large submatrices as well as the time to solution of the solver. We also compare multiple ordering techniques based on geometrical or topological properties. Finally, we open the discussion to a coupling between the Finite Element Method and the Boundary Element Method in a unified computational framework

APA, Harvard, Vancouver, ISO, and other styles

31

L'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.

Full text

Abstract:

La résolution de systèmes linéaires creux est critique dans de nombreux domaines de la simulation numérique. Beaucoup d'applications, notamment industrielles, utilisent des méthodes directes en raison de leur précision et de leur robustesse. La qualité du résultat, les fonctionnalités numériques, ainsi que le temps de calcul sont critiques pour les applications. Par ailleurs, les ressources matérielles (nombre de processeurs, mémoire) doivent être utilisées de manière optimale. Dans cette habilitation, nous décrivons des travaux poursuivant ces objectifs dans le cadre de la plate-forme logicielle MUMPS, développée à Toulouse, Lyon-Grenoble et Bordeaux depuis une quinzaine d'années. Le cœur de l'approche repose sur une parallélisation originale de la méthode multifrontale : une gestion asynchrone du parallélisme, associée à des ordonnanceurs distribués, permet de traiter des structures de données dynamiques et autorise ainsi le pivotage numérique. Nous nous intéressons à l'ordonnancement des tâches, à l'optimisation de la mémoire et à différentes fonctionnalités numériques. Les travaux en cours et les objectifs futurs visent à résoudre efficacement des problèmes de plus en plus gros, sans perte sur les aspects numériques, et tout en adaptant nos approches aux évolutions rapides des calculateurs. Dans ce contexte, les aspects génie logiciel et transfert deviennent critiques afin de maintenir sur le long terme une plate-forme logicielle comme MUMPS. Cette plate-forme est à la fois nécessaire à nos travaux de recherche et utilisée en production ; elle maximise ainsi les retours applicatifs qui valident nos travaux et permettent d'orienter nos recherches futures.

APA, Harvard, Vancouver, ISO, and other styles

32

Ferreira, Silvia da Rocha Izidoro. "Aplicações de matrizes no ensino médio." Universidade de São Paulo, 2013. http://www.teses.usp.br/teses/disponiveis/55/55136/tde-07062013-100316/.

Full text

Abstract:

Esta dissertação tem como objetivo salientar a utilidade e importância de cálculos matriciais no ensino médio. Para tanto, foram estudados alguns tópicos que descrevem situações que necessitam de recursos gerados por operações matriciais. Foi observado que esses tópicos apresentam situações que evidenciam a utilidade da multiplicação de matrizes não somente no desenvolvimento teórico, mas também nas aplicações de matrizes, e têm potencial para serem abordados no ensino médio
The aim is this work is to stress on the use of algebraic operations with matrices in the mathematics teaching for secondary school students. For this purpose, we studied some topics that require algebraic operations with matrices. It was observed that these topics reveal circumstances in which the matrix multiplication is not only useful in the theoretical development but also in the applications. In addition, the studied showed that these themes have potential to be considered in the secondary school

APA, Harvard, Vancouver, ISO, and other styles

33

Agullo, Emmanuel. "Méthodes directes hors-mémoire (out-of-core) pour la résolution de systèmes linéaires creux de grande taille." Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2008. http://tel.archives-ouvertes.fr/tel-00563463.

Full text

Abstract:

La factorisation d'une matrice creuse est une approche robuste pour la résolution de systèmes linéaires creux de grande taille. Néanmoins, une telle factorisation est connue pour être coûteuse aussi bien en temps de calcul qu'en occupation mémoire. Quand l'espace mémoire nécessaire au traitement d'une matrice est plus grand que la quantité de mémoire disponible sur la plate-forme utilisée, des approches dites hors-mémoire (out-of-core) doivent être employées : les disques étendent la mémoire centrale pour fournir une capacité de stockage suffisante. Dans cette thèse, nous nous intéressons à la fois aux aspects théoriques et pratiques de telles factorisations hors-mémoire. Les environnements logiciel MUMPS et SuperLU sont utilisés pour illustrer nos discussions sur des matrices issues du monde industriel et académique. Tout d'abord, nous proposons et étudions dans un cadre séquentiel différents modèles hors-mémoire qui ont pour but de limiter le surcoût dû aux transferts de données entre la mémoire et les disques. Pour ce faire, nous revisitons les algorithmes qui ordonnancent les opérations de la factorisation et proposons de nouveaux schémas de gestion mémoire s'accommodant aux contraintes hors-mémoire. Ensuite, nous nous focalisons sur une méthode de factorisation particulière, la méthode multifrontale, que nous poussons aussi loin que possible dans un contexte parallèle hors-mémoire. Suivant une démarche pragmatique, nous montrons que les techniques hors-mémoire permettent de résoudre efficacement des systèmes linéaires creux de grande taille. Quand seuls les facteurs sont stockés sur disque, une attention particulière doit être portée aux données temporaires, qui restent en mémoire centrale. Pour faire décroître efficacement l'occupation mémoire associée à ces données temporaires avec le nombre de processeurs, nous repensons l'ordonnancement de la factorisation parallèle hors-mémoire dans son ensemble.

APA, Harvard, Vancouver, ISO, and other styles

34

Negre, Stéphane. "Optimisation de la méthode multifrontale en vue de sa parallélisation." Compiègne, 1997. http://www.theses.fr/1997COMP1045.

Full text

Abstract:

Cette thèse parie sur l'optimisation du traitement parallèle de calcul par éléments finis en utilisant une méthode de résolution par sous-structure particulière appelée méthode multifrontale. L'objectif était de construire un ensemble de méthodes et d'outils pour permettre une parallélisation efficace de cette méthode de résolution. La problématique revêt plusieurs aspects liés à l'optimisation combinatoire et aux graphes. En effet, un maillage par éléments finis peut être vu comme un graphe. Or le temps de calcul pour résoudre le problème dépend directement de la numérotation des éléments finis et donc du graphe associé. La qualité d'une solution doit pouvoir être mesurée. Nous avons donc mis au point des estimateurs de temps de calcul précis pour mesurer les solutions calculées. Nous comparons différentes méthodes heuristiques de la littérature. Nous en proposons plusieurs améliorations performantes et développons deux nouvelles méthodes. La première est une méthode qui hybride plusieurs heuristiques gloutonnes de la littérature. La seconde est basée sur la métaheuristique Tabou. Une autre partie du problème concerne le découpage du maillage en sous-domaines, ce qui revient à réaliser le partitionnement d'un graphe en considérant plusieurs critères. Nous comparons différentes méthodes de la littérature et proposons une nouvelle méthode de découpage. Cette méthode améliore itérativement un découpage initial du maillage par des échanges d'éléments finis entre les sous-domaines. La méthode vise à équilibrer la charge de travail des processeurs en estimant le temps de calcul de chaque sous-domaine. Le temps de calcul d'un sous-domaine dépend lui aussi de la numérotation des éléments finis du sous-domaine correspondant. Cependant, il faut en plus tenir compte des noeuds interfaces entre les sous-domaines. Nous proposons donc des méthodes de numérotation particulières pour pouvoir prendre en compte ce problème supplémentaire. Enfin, quand on effectue un calcul parallèle, il est important de plannifier l'affectation des tâches aux processeurs. Nous avons donc construit et étudié un modèle plus formel en émettant des hypothèses sur les temps de calcul et les temps de fusion des données et nous avons montré qu'une stratégie d'affectation des tâches aux processeurs en domine une autre, communément utilisée dans la communauté de la mécanique numérique. Les résultats de tous les algorithmes exposés sont comparés sur la collection Everstine composée de trente maillages considérés comme représentatifs. Ces résultats montrent la pertinence de nos algorithmes
This work is concerned with the optimization of the parallelization of a particular finite element resolution method based on a substructuring principle and called the multifrontal method. Our aim was to build a set of methods and tools in order to parallelize this method efficiently. The problem is concerned with combinatorial optimization and graph theory. Indeed a finite element mesh can be modelized as a graph. The computing times spent to solve the problem directly depend on the reordering of an associated graph. Because the quality of a solution has to be measured, we propose accurate computing times estimators to measure our solutions. We compare different heuristics we have found in the litterature. We propose efficient improvements of these heuristics and two original reordering methods. The first one is an hybrid method which interleaves greedy algorithms. The second one is based on the tabu search method which is a metaheuristic. Another problem we are concerned with is the mesh decomposition into substructures. Different methods are compared and a new one is proposed. This method iteratively improves initial mesh decomposition by applying an exchanging principle of the finite elements between substructures. In this way we aim to optimize the load balancing on the processors by estimating the computing times of each substructure. The computing times of a substructure also depend on the finite element reordering of the corresponding substructure. However we have to take into account in addition the boundary nodes between the substructures. We then propose particular reordering methods which take into account this additional problem. When a parallel treatment is performed, it is important to schedule the tasks on the processors. We have proposed and studied a theoretical model assuming some assumptions concerning the computing times (the communications delays and the merging tasks). We have shown that a scheduling strategy dominates another one, widely used in the mechanical and numerical community. The results are compared on the thirty meshes of the Everstine's collection and show the efficiency of our algorithms

APA, Harvard, Vancouver, ISO, and other styles

35

Hofmann, B., and G. Fleischer. "Stability Rates for Linear Ill-Posed Problems with Convolution and Multiplication Operators." Universitätsbibliothek Chemnitz, 1998. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-199800987.

Full text

Abstract:

In this paper we deal with the `strength' of ill-posedness for ill-posed linear operator equations Ax = y in Hilbert spaces, where we distinguish according_to_M. Z. Nashed [15] the ill-posedness of type I if A is not compact, but we have R(A) 6= R(A) for the range R(A) of A; and the ill-posedness of type II for compact operators A: From our considerations it seems to follow that the problems with noncompact operators A are not in general `less' ill-posed than the problems with compact operators. We motivate this statement by comparing the approximation and stability behaviour of discrete least-squares solutions and the growth rate of Galerkin matrices in both cases. Ill-posedness measures for compact operators A as discussed in [10] are derived from the decay rate of the nonincreasing sequence of singular values of A. Since singular values do not exist for noncompact operators A; we introduce stability rates in order to have a common measure for the compact and noncompact cases. Properties of these rates are illustrated by means of convolution equations in the compact case and by means of equations with multiplication operators in the noncompact case. Moreover using increasing rearrangements of the multiplier functions specific measures of ill-posedness called ill-posedness rates are considered for the multiplication operators. In this context, the character of sufficient conditions providing convergence rates of Tikhonov regularization are compared for compact operators and multiplication operators.

APA, Harvard, Vancouver, ISO, and other styles

36

Weisbecker, 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.

Full text

Abstract:

We consider the solution of large sparse linear systems by means of direct factorization based on a multifrontal approach. Although numerically robust and easy to use (it only needs algebraic information: the input matrix A and a right-hand side b, even if it can also digest preprocessing strategies based on geometric information), direct factorization methods are computationally intensive both in terms of memory and operations, which limits their scope on very large problems (matrices with up to few hundred millions of equations). This work focuses on exploiting low-rank approximations on multifrontal based direct methods to reduce both the memory footprints and the operation count, in sequential and distributed-memory environments, on a wide class of problems. We first survey the low-rank formats which have been previously developed to efficiently represent dense matrices and have been widely used to design fast solutions of partial differential equations, integral equations and eigenvalue problems. These formats are hierarchical (H and Hierarchically Semiseparable matrices are the most common ones) and have been (both theoretically and practically) shown to substantially decrease the memory and operation requirements for linear algebra computations. However, they impose many structural constraints which can limit their scope and efficiency, especially in the context of general purpose multifrontal solvers. We propose a flat format called Block Low-Rank (BLR) based on a natural blocking of the matrices and explain why it provides all the flexibility needed by a general purpose multifrontal solver in terms of numerical pivoting for stability and parallelism. We compare BLR format with other formats and show that BLR does not compromise much the memory and operation improvements achieved through low-rank approximations. A stability study shows that the approximations are well controlled by an explicit numerical parameter called low-rank threshold, which is critical in order to solve the sparse linear system accurately. Details on how Block Low-Rank factorizations can be efficiently implemented within multifrontal solvers are then given. We propose several Block Low-Rank factorization algorithms which allow for different types of gains. The proposed algorithms have been implemented within the MUMPS (MUltifrontal Massively Parallel Solver) solver. We first report experiments on standard partial differential equations based problems to analyse the main features of our BLR algorithms and to show the potential and flexibility of the approach; a comparison with a Hierarchically SemiSeparable code is also given. Then, Block Low-Rank formats are experimented on large (up to a hundred millions of unknowns) and various problems coming from several industrial applications. We finally illustrate the use of our approach as a preconditioning method for the Conjugate Gradient.

APA, Harvard, Vancouver, ISO, and other styles

37

Murphy, Steven. "Methods for solving discontinuous-Galerkin finite element equations with application to neutron transport." Phd thesis, Toulouse, INPT, 2015. http://oatao.univ-toulouse.fr/14650/1/murphy.pdf.

Full text

Abstract:

We consider high order discontinuous-Galerkin finite element methods for partial differential equations, with a focus on the neutron transport equation. We begin by examining a method for preprocessing block-sparse matrices, of the type that arise from discontinuous-Galerkin methods, prior to factorisation by a multifrontal solver. Numerical experiments on large two and three dimensional matrices show that this pre-processing method achieves a significant reduction in fill-in, when compared to methods that fail to exploit block structures. A discontinuous-Galerkin finite element method for the neutron transport equation is derived that employs high order finite elements in both space and angle. Parallel Krylov subspace based solvers are considered for both source problems and $k_{eff}$-eigenvalue problems. An a-posteriori error estimator is derived and implemented as part of an h-adaptive mesh refinement algorithm for neutron transport $k_{eff}$-eigenvalue problems. This algorithm employs a projection-based error splitting in order to balance the computational requirements between the spatial and angular parts of the computational domain. An hp-adaptive algorithm is presented and results are collected that demonstrate greatly improved efficiency compared to the h-adaptive algorithm, both in terms of reduced computational expense and enhanced accuracy. Computed eigenvalues and effectivities are presented for a variety of challenging industrial benchmarks. Accurate error estimation (with effectivities of 1) is demonstrated for a collection of problems with inhomogeneous, irregularly shaped spatial domains as well as multiple energy groups. Numerical results are presented showing that the hp-refinement algorithm can achieve exponential convergence with respect to the number of degrees of freedom in the finite element space

APA, Harvard, Vancouver, ISO, and other styles

38

Ailem, Melissa. "Sparsity-sensitive diagonal co-clustering algorithms for the effective handling of text data." Thesis, Sorbonne Paris Cité, 2016. http://www.theses.fr/2016USPCB087.

Full text

Abstract:

Dans le contexte actuel, il y a un besoin évident de techniques de fouille de textes pour analyser l'énorme quantité de documents textuelles non structurées disponibles sur Internet. Ces données textuelles sont souvent représentées par des matrices creuses (sparses) de grande dimension où les lignes et les colonnes représentent respectivement des documents et des termes. Ainsi, il serait intéressant de regrouper de façon simultanée ces termes et documents en classes homogènes, rendant ainsi cette quantité importante de données plus faciles à manipuler et à interpréter. Les techniques de classification croisée servent justement cet objectif. Bien que plusieurs techniques existantes de co-clustering ont révélé avec succès des blocs homogènes dans plusieurs domaines, ces techniques sont toujours contraintes par la grande dimensionalité et la sparsité caractérisant les matrices documents-termes. En raison de cette sparsité, plusieurs co-clusters sont principalement composés de zéros. Bien que ces derniers soient homogènes, ils ne sont pas pertinents et doivent donc être filtrés en aval pour ne garder que les plus importants. L'objectif de cette thèse est de proposer de nouveaux algorithmes de co-clustering conçus pour tenir compte des problèmes liés à la sparsité mentionnés ci-dessus. Ces algorithmes cherchent une structure diagonale par blocs et permettent directement d'identifier les co-clusters les plus pertinents, ce qui les rend particulièrement efficaces pour le co-clustering de données textuelles. Dans ce contexte, nos contributions peuvent être résumées comme suit: Tout d'abord, nous introduisons et démontrons l'efficacité d'un nouvel algorithme de co-clustering basé sur la maximisation directe de la modularité de graphes. Alors que les algorithmes de co-clustering existants qui se basent sur des critères de graphes utilisent des approximations spectrales, l'algorithme proposé utilise une procédure d'optimisation itérative pour révéler les co-clusters les plus pertinents dans une matrice documents-termes. Par ailleurs, l'optimisation proposée présente l'avantage d'éviter le calcul de vecteurs propres, qui est une tâche rédhibitoire lorsque l'on considère des données de grande dimension. Ceci est une amélioration par rapport aux approches spectrales, où le calcul des vecteurs propres est nécessaire pour effectuer le co-clustering. Dans un second temps, nous utilisons une approche probabiliste pour découvrir des structures en blocs homogènes diagonaux dans des matrices documents-termes. Nous nous appuyons sur des approches de type modèles de mélanges, qui offrent de solides bases théoriques et une grande flexibilité qui permet de découvrir diverses structures de co-clusters. Plus précisément, nous proposons un modèle de blocs latents parcimonieux avec des distributions de Poisson sous contraintes. De façon intéressante, ce modèle comprend la sparsité dans sa formulation, ce qui le rend particulièrement adapté aux données textuelles. En plaçant l'estimation des paramètres de ce modèle dans le cadre du maximum de vraisemblance et du maximum de vraisemblance classifiante, quatre algorithmes de co-clustering ont été proposées, incluant une variante dure, floue, stochastique et une quatrième variante qui tire profit des avantages des variantes floue et stochastique simultanément. Pour finir, nous proposons un nouveau cadre de fouille de textes biomédicaux qui comprend certains algorithmes de co-clustering mentionnés ci-dessus. Ce travail montre la contribution du co-clustering dans une problématique réelle de fouille de textes biomédicaux. Le cadre proposé permet de générer de nouveaux indices sur les résultats retournés par les études d'association pan-génomique (GWAS) en exploitant les abstracts de la base de données PUBMED. (...)
In the current context, there is a clear need for Text Mining techniques to analyse the huge quantity of unstructured text documents available on the Internet. These textual data are often represented by sparse high dimensional matrices where rows and columns represent documents and terms respectively. Thus, it would be worthwhile to simultaneously group these terms and documents into meaningful clusters, making this substantial amount of data easier to handle and interpret. Co-clustering techniques just serve this purpose. Although many existing co-clustering approaches have been successful in revealing homogeneous blocks in several domains, these techniques are still challenged by the high dimensionality and sparsity characteristics exhibited by document-term matrices. Due to this sparsity, several co-clusters are primarily composed of zeros. While homogeneous, these co-clusters are irrelevant and must be filtered out in a post-processing step to keep only the most significant ones. The objective of this thesis is to propose new co-clustering algorithms tailored to take into account these sparsity-related issues. The proposed algorithms seek a block diagonal structure and allow to straightaway identify the most useful co-clusters, which makes them specially effective for the text co-clustering task. Our contributions can be summarized as follows: First, we introduce and demonstrate the effectiveness of a novel co-clustering algorithm based on a direct maximization of graph modularity. While existing graph-based co-clustering algorithms rely on spectral relaxation, the proposed algorithm uses an iterative alternating optimization procedure to reveal the most meaningful co-clusters in a document-term matrix. Moreover, the proposed optimization has the advantage of avoiding the computation of eigenvectors, a task which is prohibitive when considering high dimensional data. This is an improvement over spectral approaches, where the eigenvectors computation is necessary to perform the co-clustering. Second, we use an even more powerful approach to discover block diagonal structures in document-term matrices. We rely on mixture models, which offer strong theoretical foundations and considerable flexibility that makes it possible to uncover various specific cluster structure. More precisely, we propose a rigorous probabilistic model based on the Poisson distribution and the well known Latent Block Model. Interestingly, this model includes the sparsity in its formulation, which makes it particularly effective for text data. Setting the estimate of this model’s parameters under the Maximum Likelihood (ML) and the Classification Maximum Likelihood (CML) approaches, four co-clustering algorithms have been proposed, including a hard, a soft, a stochastic and a fourth algorithm which leverages the benefits of both the soft and stochastic variants, simultaneously. As a last contribution of this thesis, we propose a new biomedical text mining framework that includes some of the above mentioned co-clustering algorithms. This work shows the contribution of co-clustering in a real biomedical text mining problematic. The proposed framework is able to propose new clues about the results of genome wide association studies (GWAS) by mining PUBMED abstracts. This framework has been tested on asthma disease and allowed to assess the strength of associations between asthma genes reported in previous GWAS as well as discover new candidate genes likely associated to asthma. In a nutshell, while several text co-clustering algorithms already exist, their performance can be substantially increased if more appropriate models and algorithms are available. According to the extensive experiments done on several challenging real-world text data sets, we believe that this thesis has served well this objective

APA, Harvard, Vancouver, ISO, and other styles

39

Slavova, Tzvetomila. "Résolution triangulaire de systèmes linéaires creux de grande taille dans un contexte parallèle multifrontal et hors-mémoire." Thesis, Toulouse, INPT, 2009. http://www.theses.fr/2009INPT016H/document.

Full text

Abstract:

Nous nous intéressons à la résolution de systèmes linéaires creux de très grande taille par des méthodes directes de factorisation. Dans ce contexte, la taille de la matrice des facteurs constitue un des facteurs limitants principaux pour l'utilisation de méthodes directes de résolution. Nous supposons donc que la matrice des facteurs est de trop grande taille pour être rangée dans la mémoire principale du multiprocesseur et qu'elle a donc été écrite sur les disques locaux (hors-mémoire : OOC) d'une machine multiprocesseurs durant l'étape de factorisation. Nous nous intéressons à l'étude et au développement de techniques efficaces pour la phase de résolution après une factorization multifrontale creuse. La phase de résolution, souvent négligée dans les travaux sur les méthodes directes de résolution directe creuse, constitue alors un point critique de la performance de nombreuses applications scientifiques, souvent même plus critique que l'étape de factorisation. Cette thèse se compose de deux parties. Dans la première partie nous nous proposons des algorithmes pour améliorer la performance de la résolution hors-mémoire. Dans la deuxième partie nous pousuivons ce travail en montrant comment exploiter la nature creuse des seconds membres pour réduire le volume de données accédées en mémoire. Dans la première partie de cette thèse nous introduisons deux approches de lecture des données sur le disque dur. Nous montrons ensuite que dans un environnement parallèle le séquencement des tâches peut fortement influencer la performance. Nous prouvons qu'un ordonnancement contraint des tâches peut être introduit; qu'il n'introduit pas d'interblocage entre processus et qu'il permet d'améliorer les performances. Nous conduisons nos expériences sur des problèmes industriels de grande taille (plus de 8 Millions d'inconnues) et utilisons une version hors-mémoire d'un code multifrontal creux appelé MUMPS (solveur multifrontal parallèle). Dans la deuxième partie de ce travail nous nous intéressons au cas de seconds membres creux multiples. Ce problème apparaît dans des applications en electromagnétisme et en assimilation de données et résulte du besoin de calculer l'espace propre d'une matrice fortement déficiente, du calcul d'éléments de l'inverse de la matrice associée aux équations normales pour les moindres carrés linéaires ou encore du traitement de matrices fortement réductibles en programmation linéaire. Nous décrivons un algorithme efficace de réduction du volume d'Entrées/Sorties sur le disque lors d'une résolution hors-mémoire. Plus généralement nous montrons comment le caractère creux des seconds -membres peut être exploité pour réduire le nombre d'opérations et le nombre d'accès à la mémoire lors de l'étape de résolution. Le travail présenté dans cette thèse a été partiellement financé par le projet SOLSTICE de l'ANR (ANR-06-CIS6-010)
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 out-of-core performance of the solution phase. The focus of the second part is to further improve the performance by exploiting the sparsity of the right-hand 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 out-of-core 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 right-hand 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 least-squares problems. We cast both of these problems as linear systems with multiple right-hand side vectors, each containing a single nonzero entry. We describe, implement and comment on efficient algorithms to reduce the input-output cost during an outof- core execution. We show how the sparsity of the right-hand 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 (ANR-06-CIS6-010)

APA, Harvard, Vancouver, ISO, and other styles

40

Ailem, Melissa. "Sparsity-sensitive diagonal co-clustering algorithms for the effective handling of text data." Electronic Thesis or Diss., Sorbonne Paris Cité, 2016. http://www.theses.fr/2016USPCB087.

Full text

Abstract:

Dans le contexte actuel, il y a un besoin évident de techniques de fouille de textes pour analyser l'énorme quantité de documents textuelles non structurées disponibles sur Internet. Ces données textuelles sont souvent représentées par des matrices creuses (sparses) de grande dimension où les lignes et les colonnes représentent respectivement des documents et des termes. Ainsi, il serait intéressant de regrouper de façon simultanée ces termes et documents en classes homogènes, rendant ainsi cette quantité importante de données plus faciles à manipuler et à interpréter. Les techniques de classification croisée servent justement cet objectif. Bien que plusieurs techniques existantes de co-clustering ont révélé avec succès des blocs homogènes dans plusieurs domaines, ces techniques sont toujours contraintes par la grande dimensionalité et la sparsité caractérisant les matrices documents-termes. En raison de cette sparsité, plusieurs co-clusters sont principalement composés de zéros. Bien que ces derniers soient homogènes, ils ne sont pas pertinents et doivent donc être filtrés en aval pour ne garder que les plus importants. L'objectif de cette thèse est de proposer de nouveaux algorithmes de co-clustering conçus pour tenir compte des problèmes liés à la sparsité mentionnés ci-dessus. Ces algorithmes cherchent une structure diagonale par blocs et permettent directement d'identifier les co-clusters les plus pertinents, ce qui les rend particulièrement efficaces pour le co-clustering de données textuelles. Dans ce contexte, nos contributions peuvent être résumées comme suit: Tout d'abord, nous introduisons et démontrons l'efficacité d'un nouvel algorithme de co-clustering basé sur la maximisation directe de la modularité de graphes. Alors que les algorithmes de co-clustering existants qui se basent sur des critères de graphes utilisent des approximations spectrales, l'algorithme proposé utilise une procédure d'optimisation itérative pour révéler les co-clusters les plus pertinents dans une matrice documents-termes. Par ailleurs, l'optimisation proposée présente l'avantage d'éviter le calcul de vecteurs propres, qui est une tâche rédhibitoire lorsque l'on considère des données de grande dimension. Ceci est une amélioration par rapport aux approches spectrales, où le calcul des vecteurs propres est nécessaire pour effectuer le co-clustering. Dans un second temps, nous utilisons une approche probabiliste pour découvrir des structures en blocs homogènes diagonaux dans des matrices documents-termes. Nous nous appuyons sur des approches de type modèles de mélanges, qui offrent de solides bases théoriques et une grande flexibilité qui permet de découvrir diverses structures de co-clusters. Plus précisément, nous proposons un modèle de blocs latents parcimonieux avec des distributions de Poisson sous contraintes. De façon intéressante, ce modèle comprend la sparsité dans sa formulation, ce qui le rend particulièrement adapté aux données textuelles. En plaçant l'estimation des paramètres de ce modèle dans le cadre du maximum de vraisemblance et du maximum de vraisemblance classifiante, quatre algorithmes de co-clustering ont été proposées, incluant une variante dure, floue, stochastique et une quatrième variante qui tire profit des avantages des variantes floue et stochastique simultanément. Pour finir, nous proposons un nouveau cadre de fouille de textes biomédicaux qui comprend certains algorithmes de co-clustering mentionnés ci-dessus. Ce travail montre la contribution du co-clustering dans une problématique réelle de fouille de textes biomédicaux. Le cadre proposé permet de générer de nouveaux indices sur les résultats retournés par les études d'association pan-génomique (GWAS) en exploitant les abstracts de la base de données PUBMED. (...)
In the current context, there is a clear need for Text Mining techniques to analyse the huge quantity of unstructured text documents available on the Internet. These textual data are often represented by sparse high dimensional matrices where rows and columns represent documents and terms respectively. Thus, it would be worthwhile to simultaneously group these terms and documents into meaningful clusters, making this substantial amount of data easier to handle and interpret. Co-clustering techniques just serve this purpose. Although many existing co-clustering approaches have been successful in revealing homogeneous blocks in several domains, these techniques are still challenged by the high dimensionality and sparsity characteristics exhibited by document-term matrices. Due to this sparsity, several co-clusters are primarily composed of zeros. While homogeneous, these co-clusters are irrelevant and must be filtered out in a post-processing step to keep only the most significant ones. The objective of this thesis is to propose new co-clustering algorithms tailored to take into account these sparsity-related issues. The proposed algorithms seek a block diagonal structure and allow to straightaway identify the most useful co-clusters, which makes them specially effective for the text co-clustering task. Our contributions can be summarized as follows: First, we introduce and demonstrate the effectiveness of a novel co-clustering algorithm based on a direct maximization of graph modularity. While existing graph-based co-clustering algorithms rely on spectral relaxation, the proposed algorithm uses an iterative alternating optimization procedure to reveal the most meaningful co-clusters in a document-term matrix. Moreover, the proposed optimization has the advantage of avoiding the computation of eigenvectors, a task which is prohibitive when considering high dimensional data. This is an improvement over spectral approaches, where the eigenvectors computation is necessary to perform the co-clustering. Second, we use an even more powerful approach to discover block diagonal structures in document-term matrices. We rely on mixture models, which offer strong theoretical foundations and considerable flexibility that makes it possible to uncover various specific cluster structure. More precisely, we propose a rigorous probabilistic model based on the Poisson distribution and the well known Latent Block Model. Interestingly, this model includes the sparsity in its formulation, which makes it particularly effective for text data. Setting the estimate of this model’s parameters under the Maximum Likelihood (ML) and the Classification Maximum Likelihood (CML) approaches, four co-clustering algorithms have been proposed, including a hard, a soft, a stochastic and a fourth algorithm which leverages the benefits of both the soft and stochastic variants, simultaneously. As a last contribution of this thesis, we propose a new biomedical text mining framework that includes some of the above mentioned co-clustering algorithms. This work shows the contribution of co-clustering in a real biomedical text mining problematic. The proposed framework is able to propose new clues about the results of genome wide association studies (GWAS) by mining PUBMED abstracts. This framework has been tested on asthma disease and allowed to assess the strength of associations between asthma genes reported in previous GWAS as well as discover new candidate genes likely associated to asthma. In a nutshell, while several text co-clustering algorithms already exist, their performance can be substantially increased if more appropriate models and algorithms are available. According to the extensive experiments done on several challenging real-world text data sets, we believe that this thesis has served well this objective

APA, Harvard, Vancouver, ISO, and other styles

41

Rouet, François-Henry. "Memory and performance issues in parallel multifrontal factorizations and triangular solutions with sparse right-hand sides." Thesis, Toulouse, INPT, 2012. http://www.theses.fr/2012INPT0070/document.

Full text

Abstract:

Nous nous intéressons à la résolution de systèmes linéaires creux de très grande taille sur des machines parallèles. Dans ce contexte, la mémoire est un facteur qui limite voire empêche souvent l’utilisation de solveurs directs, notamment ceux basés sur la méthode multifrontale. Cette étude se concentre sur les problèmes de mémoire et de performance des deux phases des méthodes directes les plus coûteuses en mémoire et en temps : la factorisation numérique et la résolution triangulaire. Dans une première partie nous nous intéressons à la phase de résolution à seconds membres creux, puis, dans une seconde partie, nous nous intéressons à la scalabilité mémoire de la factorisation multifrontale. La première partie de cette étude se concentre sur la résolution triangulaire à seconds membres creux, qui apparaissent dans de nombreuses applications. En particulier, nous nous intéressons au calcul d’entrées de l’inverse d’une matrice creuse, où les seconds membres et les vecteurs solutions sont tous deux creux. Nous présentons d’abord plusieurs schémas de stockage qui permettent de réduire significativement l’espace mémoire utilisé lors de la résolution, dans le cadre d’exécutions séquentielles et parallèles. Nous montrons ensuite que la façon dont les seconds membres sont regroupés peut fortement influencer la performance et nous considérons deux cadres différents : le cas "hors-mémoire" (out-of-core) où le but est de réduire le nombre d’accès aux facteurs, qui sont stockés sur disque, et le cas "en mémoire" (in-core) où le but est de réduire le nombre d’opérations. Finalement, nous montrons comment améliorer le parallélisme. Dans la seconde partie, nous nous intéressons à la factorisation multifrontale parallèle. Nous montrons tout d’abord que contrôler la mémoire active spécifique à la méthode multifrontale est crucial, et que les technique de "répartition" (mapping) classiques ne peuvent fournir une bonne scalabilité mémoire : le coût mémoire de la factorisation augmente fortement avec le nombre de processeurs. Nous proposons une classe d’algorithmes de répartition et d’ordonnancement "conscients de la mémoire" (memory-aware) qui cherchent à maximiser la performance tout en respectant une contrainte mémoire fournie par l’utilisateur. Ces techniques ont révélé des problèmes de performances dans certains des noyaux parallèles denses utilisés à chaque étape de la factorisation, et nous avons proposé plusieurs améliorations algorithmiques. Les idées présentées tout au long de cette étude ont été implantées dans le solveur MUMPS (Solveur MUltifrontal Massivement Parallèle) et expérimentées sur des matrices de grande taille (plusieurs dizaines de millions d’inconnues) et sur des machines massivement parallèles (jusqu’à quelques milliers de coeurs). Elles ont permis d’améliorer les performances et la robustesse du code et seront disponibles dans une prochaine version. Certaines des idées présentées dans la première partie ont également été implantées dans le solveur PDSLin (solveur linéaire hybride basé sur une méthode de complément de Schur)
We consider the solution of very large sparse systems of linear equations on parallel architectures. In this context, memory is often a bottleneck that prevents or limits the use of direct solvers, especially those based on the multifrontal method. This work focuses on memory and performance issues of the two memory and computationally intensive phases of direct methods, that is, the numerical factorization and the solution phase. In the first part we consider the solution phase with sparse right-hand sides, and in the second part we consider the memory scalability of the multifrontal factorization. In the first part, we focus on the triangular solution phase with multiple sparse right-hand sides, that appear in numerous applications. We especially emphasize the computation of entries of the inverse, where both the right-hand sides and the solution are sparse. We first present several storage schemes that enable a significant compression of the solution space, both in a sequential and a parallel context. We then show that the way the right-hand sides are partitioned into blocks strongly influences the performance and we consider two different settings: the out-of-core case, where the aim is to reduce the number of accesses to the factors, that are stored on disk, and the in-core case, where the aim is to reduce the computational cost. Finally, we show how to enhance the parallel efficiency. In the second part, we consider the parallel multifrontal factorization. We show that controlling the active memory specific to the multifrontal method is critical, and that commonly used mapping techniques usually fail to do so: they cannot achieve a high memory scalability, i.e. they dramatically increase the amount of memory needed by the factorization when the number of processors increases. We propose a class of "memory-aware" mapping and scheduling algorithms that aim at maximizing performance while enforcing a user-given memory constraint and provide robust memory estimates before the factorization. These techniques have raised performance issues in the parallel dense kernels used at each step of the factorization, and we have proposed some algorithmic improvements. The ideas presented throughout this study have been implemented within the MUMPS (MUltifrontal Massively Parallel Solver) solver and experimented on large matrices (up to a few tens of millions unknowns) and massively parallel architectures (up to a few thousand cores). They have demonstrated to improve the performance and the robustness of the code, and will be available in a future release. Some of the ideas presented in the first part have also been implemented within the PDSLin (Parallel Domain decomposition Schur complement based Linear solver) solver

APA, Harvard, Vancouver, ISO, and other styles

42

Mary, 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.

Full text

Abstract:

Nous nous intéressons à l'utilisation d'approximations de rang faible pour réduire le coût des solveurs creux directs multifrontaux. Parmi les différents formats matriciels qui ont été proposés pour exploiter la propriété de rang faible dans les solveurs multifrontaux, nous nous concentrons sur le format Block Low-Rank (BLR) dont la simplicité et la flexibilité permettent de l'utiliser facilement dans un solveur multifrontal algébrique et généraliste. Nous présentons différentes variantes de la factorisation BLR, selon comment les mises à jour de rang faible sont effectuées, et comment le pivotage numérique est géré. D'abord, nous étudions la complexité théorique du format BLR qui, contrairement à d'autres formats comme les formats hiérarchiques, était inconnue jusqu'à présent. Nous prouvons que la complexité théorique de la factorisation multifrontale BLR est asymptotiquement inférieure à celle du solveur de rang plein. Nous montrons ensuite comment les variantes BLR peuvent encore réduire cette complexité. Nous étayons nos bornes de complexité par une étude expérimentale. Après avoir montré que les solveurs multifrontaux BLR peuvent atteindre une faible complexité, nous nous intéressons au problème de la convertir en gains de performance réels sur les architectures modernes. Nous présentons d'abord une factorisation BLR multithreadée, et analysons sa performance dans des environnements multicœurs à mémoire partagée. Nous montrons que les variantes BLR sont cruciales pour exploiter efficacement les machines multicœurs en améliorant l'intensité arithmétique et la scalabilité de la factorisation. Nous considérons ensuite à la factorisation BLR sur des architectures à mémoire distribuée. Les algorithmes présentés dans cette thèse ont été implémentés dans le solveur MUMPS. Nous illustrons l'utilisation de notre approche dans trois applications industrielles provenant des géosciences et de la mécanique des structures. Nous comparons également notre solveur avec STRUMPACK, basé sur des approximations Hierarchically Semi-Separable. Nous concluons cette thèse en rapportant un résultat sur un problème de très grande taille (130 millions d'inconnues) qui illustre les futurs défis posés par le passage à l'échelle des solveurs multifrontaux BLR
We 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

APA, Harvard, Vancouver, ISO, and other styles

43

Theveny, Philippe. "Numerical Quality and High Performance In Interval Linear Algebra on Multi-Core Processors." Thesis, Lyon, École normale supérieure, 2014. http://www.theses.fr/2014ENSL0941/document.

Full text

Abstract:

L'objet est de comparer des algorithmes de multiplication de matrices à coefficients intervalles et leurs implémentations.Le premier axe est la mesure de la précision numérique. Les précédentes analyses d'erreur se limitent à établir une borne sur la surestimation du rayon du résultat en négligeant les erreurs dues au calcul en virgule flottante. Après examen des différentes possibilités pour quantifier l'erreur d'approximation entre deux intervalles, l'erreur d'arrondi est intégrée dans l'erreur globale. À partir de jeux de données aléatoires, la dispersion expérimentale de l'erreur globale permet d'éclairer l'importance des différentes erreurs (de méthode et d'arrondi) en fonction de plusieurs facteurs : valeur et homogénéité des précisions relatives des entrées, dimensions des matrices, précision de travail. Cette démarche conduit à un nouvel algorithme moins coûteux et tout aussi précis dans certains cas déterminés.Le deuxième axe est d'exploiter le parallélisme des opérations. Les implémentations précédentes se ramènent à des produits de matrices de nombres flottants. Pour contourner les limitations d'une telle approche sur la validité du résultat et sur la capacité à monter en charge, je propose une implémentation par blocs réalisée avec des threads OpenMP qui exécutent des noyaux de calcul utilisant les instructions vectorielles. L'analyse des temps d'exécution sur une machine de 4 octo-coeurs montre que les coûts de calcul sont du même ordre de grandeur sur des matrices intervalles et numériques de même dimension et que l'implémentation par bloc passe mieux à l'échelle que l'implémentation avec plusieurs appels aux routines BLAS
This work aims at determining suitable scopes for several algorithms of interval matrices multiplication.First, we quantify the numerical quality. Former error analyses of interval matrix products establish bounds on the radius overestimation by neglecting the roundoff error. We discuss here several possible measures for interval approximations. We then bound the roundoff error and compare experimentally this bound with the global error distribution on several random data sets. This approach enlightens the relative importance of the roundoff and arithmetic errors depending on the value and homogeneity of relative accuracies of inputs, on the matrix dimension, and on the working precision. This also leads to a new algorithm that is cheaper yet as accurate as previous ones under well-identified conditions.Second, we exploit the parallelism of linear algebra. Previous implementations use calls to BLAS routines on numerical matrices. We show that this may lead to wrong interval results and also restrict the scalability of the performance when the core count increases. To overcome these problems, we implement a blocking version with OpenMP threads executing block kernels with vector instructions. The timings on a 4-octo-core machine show that this implementation is more scalable than the BLAS one and that the cost of numerical and interval matrix products are comparable

APA, Harvard, Vancouver, ISO, and other styles

44

Weisbecker, 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.

Full text

Abstract:

Nous considérons la résolution de très grands systèmes linéaires creux à l'aide d'une méthode de factorisation directe appelée méthode multifrontale. Bien que numériquement robustes et faciles à utiliser (elles ne nécessitent que des informations algébriques : la matrice d'entrée A et le second membre b, même si elles peuvent exploiter des stratégies de prétraitement basées sur des informations géométriques), les méthodes directes sont très coûteuses en termes de mémoire et d'opérations, ce qui limite leur applicabilité à des problèmes de taille raisonnable (quelques millions d'équations). Cette étude se concentre sur l'exploitation des approximations de rang-faible dans la méthode multifrontale, pour réduire sa consommation mémoire et son volume d'opérations, dans des environnements séquentiel et à mémoire distribuée, sur une large classe de problèmes. D'abord, nous examinons les formats rang-faible qui ont déjà été développé pour représenter efficacement les matrices denses et qui ont été utilisées pour concevoir des solveur rapides pour les équations aux dérivées partielles, les équations intégrales et les problèmes aux valeurs propres. Ces formats sont hiérarchiques (les formats H et HSS sont les plus répandus) et il a été prouvé, en théorie et en pratique, qu'ils permettent de réduire substantiellement les besoins en mémoire et opération des calculs d'algèbre linéaire. Cependant, de nombreuses contraintes structurelles sont imposées sur les problèmes visés, ce qui peut limiter leur efficacité et leur applicabilité aux solveurs multifrontaux généraux. Nous proposons un format plat appelé Block Rang-Faible (BRF) basé sur un découpage naturel de la matrice en blocs et expliquons pourquoi il fournit toute la flexibilité nécéssaire à son utilisation dans un solveur multifrontal général, en terme de pivotage numérique et de parallélisme. Nous comparons le format BRF avec les autres et montrons que le format BRF ne compromet que peu les améliorations en mémoire et opération obtenues grâce aux approximations rang-faible. Une étude de stabilité montre que les approximations sont bien contrôlées par un paramètre numérique explicite appelé le seuil rang-faible, ce qui est critique dans l'optique de résoudre des systèmes linéaires creux avec précision. Ensuite, nous expliquons comment les factorisations exploitant le format BRF peuvent être efficacement implémentées dans les solveurs multifrontaux. Nous proposons plusieurs algorithmes de factorisation BRF, ce qui permet d'atteindre différents objectifs. Les algorithmes proposés ont été implémentés dans le solveur multifrontal MUMPS. Nous présentons tout d'abord des expériences effectuées avec des équations aux dérivées partielles standardes pour analyser les principales propriétés des algorithms BRF et montrer le potentiel et la flexibilité de l'approche ; une comparaison avec un code basé sur le format HSS est également fournie. Ensuite, nous expérimentons le format BRF sur des problèmes variés et de grande taille (jusqu'à une centaine de millions d'inconnues), provenant de nombreuses applications industrielles. Pour finir, nous illustrons l'utilisation de notre approche en tant que préconditionneur pour la méthode du Gradient Conjugué.

APA, Harvard, Vancouver, ISO, and other styles

45

Zenadi, Mohamed. "Méthodes hybrides pour la résolution de grands systèmes linéaires creux sur calculateurs parallèles." Thesis, Toulouse, INPT, 2013. http://www.theses.fr/2013INPT0126/document.

Full text

Abstract:

Nous nous intéressons à la résolution en parallèle de système d’équations linéaires creux et de large taille. Le calcul de la solution d’un tel type de système requiert un grand espace mémoire et une grande puissance de calcul. Il existe deux principales méthodes de résolution de systèmes linéaires. Soit la méthode est directe et de ce fait est rapide et précise, mais consomme beaucoup de mémoire. Soit elle est itérative, économe en mémoire, mais assez lente à atteindre une solution de qualité suffisante. Notre travail consiste à combiner ces deux techniques pour créer un solveur hybride efficient en consommation mémoire tout en étant rapide et robuste. Nous essayons ensuite d’améliorer ce solveur en introduisant une nouvelle méthode pseudo directe qui contourne certains inconvénients de la méthode précédente. Dans les premiers chapitres nous examinons les méthodes de projections par lignes, en particulier la méthode Cimmino en bloc, certains de leurs aspects numériques et comment ils affectent la convergence. Ensuite, nous analyserons l’accélération de ces techniques avec la méthode des gradients conjugués et comment cette accélération peut être améliorée avec une version en bloc du gradient conjugué. Nous regarderons ensuite comment le partitionnement du système linéaire affecte lui aussi la convergence et comment nous pouvons améliorer sa qualité. Finalement, nous examinerons l’implantation en parallèle du solveur hybride, ses performances ainsi que les améliorations possible. Les deux derniers chapitres introduisent une amélioration à ce solveur hybride, en améliorant les propriétés numériques du système linéaire, de sorte à avoir une convergence en une seule itération et donc un solveur pseudo direct. Nous commençons par examiner les propriétés numériques du système résultants, analyser la solution parallèle et comment elle se comporte face au solveur hybride et face à un solveur direct. Finalement, nous introduisons de possible amélioration au solveur pseudo direct. Ce travail a permis d’implanter un solveur hybride "ABCD solver" (Augmented Block Cimmino Distributed solver) qui peut soit fonctionner en mode itératif ou en mode pseudo direct
We are interested in solving large sparse systems of linear equations in parallel. Computing the solution of such systems requires a large amount of memory and computational power. The two main ways to obtain the solution are direct and iterative approaches. The former achieves this goal fast but with a large memory footprint while the latter is memory friendly but can be slow to converge. In this work we try first to combine both approaches to create a hybrid solver that can be memory efficient while being fast. Then we discuss a novel approach that creates a pseudo-direct solver that compensates for the drawback of the earlier approach. In the first chapters we take a look at row projection techniques, especially the block Cimmino method and examine some of their numerical aspects and how they affect the convergence. We then discuss the acceleration of convergence using conjugate gradients and show that a block version improves the convergence. Next, we see how partitioning the linear system affects the convergence and show how to improve its quality. We finish by discussing the parallel implementation of the hybrid solver, discussing its performance and seeing how it can be improved. The last two chapters focus on an improvement to this hybrid solver. We try to improve the numerical properties of the linear system so that we converge in a single iteration which results in a pseudo-direct solver. We first discuss the numerical properties of the new system, see how it works in parallel and see how it performs versus the iterative version and versus a direct solver. We finally consider some possible improvements to the solver. This work led to the implementation of a hybrid solver, our "ABCD solver" (Augmented Block Cimmino Distributed solver), that can either work in a fully iterative mode or in a pseudo-direct mode

APA, Harvard, Vancouver, ISO, and other styles

46

Rouet, François-Henry. "Problèmes de mémoire et de performance de la factorisation multifrontale parallèle et de la résolution triangulaire à seconds membres creux." Phd thesis, Institut National Polytechnique de Toulouse - INPT, 2012. http://tel.archives-ouvertes.fr/tel-00785748.

Full text

Abstract:

Nous nous intéressons à la résolution de systèmes linéaires creux de très grande taille sur des machines parallèles. Dans ce contexte, la mémoire est un facteur qui limite voire empêche souvent l'utilisation de solveurs directs, notamment ceux basés sur la méthode multifrontale. Cette étude se concentre sur les problèmes de mémoire et de performance des deux phases des méthodes directes les plus coûteuses en mémoire et en temps : la factorisation numérique et la résolution triangulaire. Dans une première partie nous nous intéressons à la phase de résolution à seconds membres creux, puis, dans une seconde partie, nous nous intéressons à la scalabilité mémoire de la factorisation multifrontale. La première partie de cette étude se concentre sur la résolution triangulaire à seconds membres creux, qui apparaissent dans de nombreuses applications. En particulier, nous nous intéressons au calcul d'entrées de l'inverse d'une matrice creuse, où les seconds membres et les vecteurs solutions sont tous deux creux. Nous présentons d'abord plusieurs schémas de stockage qui permettent de réduire significativement l'espace mémoire utilisé lors de la résolution, dans le cadre d'exécutions séquentielles et parallèles. Nous montrons ensuite que la façon dont les seconds membres sont regroupés peut fortement influencer la performance et nous considérons deux cadres différents : le cas "hors-mémoire" (out-of-core) où le but est de réduire le nombre d'accès aux facteurs stockés sur disque, et le cas "en mémoire" (in-core) où le but est de réduire le nombre d'opérations. Finalement, nous montrons comment améliorer le parallélisme. Dans la seconde partie, nous nous intéressons à la factorisation multifrontale parallèle. Nous montrons tout d'abord que contrôler la mémoire active spécifique à la méthode multifrontale est crucial, et que les techniques de "répartition" (mapping) classiques ne peuvent fournir une bonne scalabilité mémoire : le coût mémoire de la factorisation augmente fortement avec le nombre de processeurs. Nous proposons une classe d'algorithmes de répartition et d'ordonnancement "conscients de la mémoire" (memory-aware) qui cherchent à maximiser la performance tout en respectant une contrainte mémoire fournie par l'utilisateur. Ces techniques ont révélé des problèmes de performances dans certains des noyaux parallèles denses utilisés à chaque étape de la factorisation, et nous avons proposé plusieurs améliorations algorithmiques. Les idées présentées tout au long de cette étude ont été implantées dans le solveur MUMPS (Solveur MUltifrontal Massivement Parallèle) et expérimentées sur des matrices de grande taille (plusieurs dizaines de millions d'inconnues) et sur des machines massivement parallèles (jusqu'à quelques milliers de coeurs). Elles ont permis d'améliorer les performances et la robustesse du code et seront disponibles dans une prochaine version. Certaines des idées présentées dans la première partie ont également été implantées dans le solveur PDSLin (solveur linéaire hybride basé sur une méthode de complément de Schur).

APA, Harvard, Vancouver, ISO, and other styles

47

He, Haiwu. "ANALYSES AVANCÉES DE LA MÉTHODE HYBRIDE GMRES/LS-ARNOLDI ASYNCHRONE PARALLÈLE ET DISTRIBUÉE POUR LES GRILLES DE CALCUL ET LES SUPERCALCULATEURS." Phd thesis, Université des Sciences et Technologie de Lille - Lille I, 2005. http://tel.archives-ouvertes.fr/tel-00431124.

Full text

Abstract:

De nombreux problèmes scientifiques et industriels ont besoin de la résolution de systèmes linéaires non symétriques à grande échelle, qui sont décrits par des matrices creuses de très grande taille. On utilise fréquemment dans ce cas des méthodes numériques itératives et on fait appel au parallélisme pour une résolution rapide et efficace. L'algorithme GMRES(m) est une méthode itérative qui donne de bons résultats dans la plupart des cas. Mais on observe une limitation à sa parallélisation en raison des nombreuses communications produites. Dans quelques cas, la convergence est atteinte très lentement, voire jamais. Nous présentons dans cette thèse une méthode hybride GMRES(m)/LS-Arnoldi qui accélère la convergence grâce à la connaissance des valeurs propres calculées parallèlement par la méthode d'Arnoldi pour les cas réels, avec son implantation sur des supercalculateurs. Une extension aux cas complexes est également étudiée. La dernière tendance du calcul global, le calcul de grille, propose l'exploitation massive des ressources vacantes des réseaux locaux ainsi que sur Internet. Son avantage peut être énorme pour l'exécution d'applications parallèles. L'environnement XtremWeb est un système de grille léger, tolérant aux défaillances et sécurisé pour l'exécution d'applications parallèles. Il est un environnement de calcul haute-performance, une plate- forme de grille logicielle d'expérimentation pour des institutions académiques ou industrielles. Nous présentons dans cette thèse les implantations de la méthode GMRES(m) sur ce système de grille XtremWeb ainsi que sur un environnement distribué de calcul LAM-MPI. Nous avons fait de multiples tests sur grille et supercalculateur. Des performances que nous avons obtenues, nous constatons les avantages et les inconvénients de ces plates-formes de calcul différentes.

APA, Harvard, Vancouver, ISO, and other styles

48

Loulidi, Sanae. "Modélisation stochastique en finance, application à la construction d’un modèle à changement de régime avec des sauts." Thesis, Bordeaux 1, 2008. http://www.theses.fr/2008BOR13675/document.

Full text

Abstract:

Le modèle de Blacket Scholes reste le modèle de référence sur les marchés des dérivés. Sa parcimonie et sa maniabilité sont certes attractives. Il ne faut cependant pas perdre de vue les hypothèses restrictives, voire simplistes, qui lui servent de base et qui limitent sa capacité à reproduire la dynamique du marché. Afin de refléter un peu mieux cette dynamique, nous introduisons un modèle d’évaluation des options à changement de régime avec sauts. Sous ce modèle, l’hypothèse de complétude des marchés n’est plus valable. Les sources d’incertitude sont plus nombreuses que les instruments disponibles à la couverture. On ne parle plus de réplication/couverture parfaite mais plutôt de réplication optimale dans un sens à définir. Dans cette thèse, on suppose que le marché peut être décrit par plusieurs «régimes» (ou encore par des «modes») re?étant l’état de l’économie, le comportement général des investisseurs et leurs tendances. Pour chacun de ces régimes, le sous-jacent est caractérisé par un niveau de volatilité et de rendement donné. Avec en plus, et a priori des discontinuités du prix du sous-jacent à chaque fois qu’une transition d’un régime à un autre a lieu. La thèse comprend trois parties: 1.Modélisation du problème et application de la théorie du contrôle stochastique. Par l’utilisation du principe de programmation dynamique et la considération des différents régimes de marché, on aboutit à un système de M (le nombre de régimes) équations de Hamilton Jacobi Bellman «HJB» couplées. 2.La résolution numérique de l’équation HJB pour l’évolution d’options, par différences finies généralisées. 3.L’estimation des paramètres du modèle par un filtre récursif, qui produit une estimation récursive d’un état inconnu au vu d’observation bruitée supposée continue, dans le cas où l’état inconnu serait modélisé par une chaîne de Markov à temps discret et espace d’état fini
Abstract

APA, Harvard, Vancouver, ISO, and other styles

49

Garnier, Romain. "Contribution à la résolution des équations de Maxwell dans les structures périodiques par la méthode des éléments finis." Phd thesis, Toulouse 3, 2013. http://thesesups.ups-tlse.fr/1944/.

Full text

Abstract:

En électromagnétisme les structures périodiques suscitent un grand intérêt. Ces structures agissent ainsi comme des filtres fréquentiels et permettent la fabrication de méta-matériaux, composites et artificiels. Elles présentent des propriétés électromagnétiques inédites pour les matériaux naturels telles que des bandes interdites. On a ainsi pu fabriquer de nouveaux dispositifs permettant de guider, de focaliser ou de stopper la propagation. C'est par exemple utile pour éviter le couplage entre différents éléments rayonnants notamment via la caractérisation des ondes de surface qui se propagent à l'interface entre l'air et la structure périodique. Ce travail de thèse s'inscrit dans ce contexte et propose une description de la méthode des éléments finis dédiée à la caractérisation des structures périodiques. La modélisation numérique aboutit à des problèmes de valeurs propres de grandes tailles. Elle implique la résolution de systèmes linéaires composés de matrices creuses. Une méthode est abordée pour résoudre ce type de problème, en optimisant et combinant différents algorithmes. Avant d'aborder les différents aspects de la méthode développée, nous établissons une liste exhaustive de l'ensemble des méthodes qui existent en énonçant leurs avantages et leurs inconvénients. Nous constatons notamment que la méthode des éléments finis permet de traiter un large éventail de structures périodiques en trois dimensions sans limitation sur leur forme géométrique. Nous présentons alors les différentes formulations de cette méthode. Ensuite les aspects algorithmiques de la méthode sont détaillés. Nous montrons notamment qu'une analyse des paramètres de résolution permet de préciser les interprétations physiques des résultats obtenus. Finalement nous présentons les performances de notre outil sur des cas d'applications issus de la littérature et nous abordons la caractérisation des ondes de surface. Pour cela, l'étude d'un réseau d'antennes patchs insérées dans des cavités métalliques est conduite. Notons pour conclure que les études conduites au cours de cette thèse ont abouti à la production d'un code utilisable dans un environnement de calcul initialement présent à l'ONERA
Electromagnetic periodic structures are of great interest. These structures act as frequency filters and allow the manufacturing of meta-materials which appear to be composite and artificial. They exhibit electromagnetic properties that are unusual to natural materials such as band gaps. This allows new devices to guide, focus or stop the propagation. This is for example useful to avoid coupling between various radiating elements via the characterization of the surface waves which propagate at the interface between air and the periodic structure. This thesis provides a description of the finite element method dedicated to the characterization of periodic structures. Numerical modelling results in eigenvalue problems of large sizes. It involves solving linear systems compounds of sparse matrices. A method is therefore discussed for solving this type of problem, optimizing and combining different algorithms. Before discussing the different aspects of the developed method, we establish an exhaustive list of all the existing methods by stating their advantages and drawbacks. We note that the finite element method can handle a wide range of periodic structures in three dimensions without limitation on their shape. We present different formulations of this method. Then the algorithmic aspects of the method are detailed. We show that an analysis of the resolution settings can impact the physical interpretations of the results. Finally we show the performance of our tool on classical validation results from the bibliography and we discuss the characterization of surface waves. Therefore, the study of a patch antenna array included in metal cavities is conducted. To conclude we can say that the studies conducted in this thesis have resulted in the production of a code used in an environment calculation initially present at ONERA

APA, Harvard, Vancouver, ISO, and other styles

50

Garnier, Romain. "Contribution à la résolution des équations de Maxwell dans les structures périodiques par la méthode des éléments finis." Phd thesis, Université Paul Sabatier - Toulouse III, 2013. http://tel.archives-ouvertes.fr/tel-00878558.

Full text

Abstract:

En électromagnétisme les structures périodiques suscitent un grand intérêt. Ces structures agissent ainsi comme des filtres fréquentiels et permettent la fabrication de méta-matériaux, composites et artificiels. Elles présentent des propriétés électromagnétiques inédites pour les matériaux naturels telles que des bandes interdites. On a ainsi pu fabriquer de nouveaux dispositifs permettant de guider, de focaliser ou de stopper la propagation. C'est par exemple utile pour éviter le couplage entre différents éléments rayonnants notamment via la caractérisation des ondes de surface qui se propagent à l'interface entre l'air et la structure périodique. Ce travail de thèse s'inscrit dans ce contexte et propose une description de la méthode des éléments finis dédiée à la caractérisation des structures périodiques. La modélisation numérique aboutit à des problèmes de valeurs propres de grandes tailles. Elle implique la résolution de systèmes linéaires composés de matrices creuses. Une méthode est abordée pour résoudre ce type de problème, en optimisant et combinant différents algorithmes. Avant d'aborder les différents aspects de la méthode développée, nous établissons une liste exhaustive de l'ensemble des méthodes qui existent en énonçant leurs avantages et leurs inconvénients. Nous constatons notamment que la méthode des éléments finis permet de traiter un large éventail de structures périodiques en trois dimensions sans limitation sur leur forme géométrique. Nous présentons alors les différentes formulations de cette méthode. Ensuite les aspects algorithmiques de la méthode sont détaillés. Nous montrons notamment qu'une analyse des paramètres de résolution permet de préciser les interprétations physiques des résultats obtenus. Finalement nous présentons les performances de notre outil sur des cas d'applications issus de la littérature et nous abordons la caractérisation des ondes de surface. Pour cela, l'étude d'un réseau d'antennes patchs insérées dans des cavités métalliques est conduite. Notons pour conclure que les études conduites au cours de cette thèse ont abouti à la production d'un code utilisable dans un environnement de calcul initialement présent à l'ONERA.

APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic 'Multiplication de matrices creuses'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles