Gerald Jean-Baptiste

Dans le prolongement des deux premiers traités sur la programmation fonctionnelle : « Programmation Fonctionnelle Appliquée à l'Analyse Numérique Matricielle » et « Programmation fonctionnelle - Spécifications et Applications », cet ouvrage présente un panel de méthodes numériques nécessaires à l'utilisation des mathématiques employées dans les sciences de l'ingénieur. Axé sur le langage Ocaml, cet ouvrage se veut à la fois pédagogique et pratique. Chaque chapitre présente un exemple de programmes associés aux méthodes numériques de résolution de problèmes scientifiques particuliers. L'accent porte sur le paradigme de la programmation fonctionnelle. Seules les fonctions récursives et les listes y sont employées pour résoudre la méthode considérée. Ce livre n'est pas un ouvrage d'analyse numérique ; nombreuses littératures et sites Internet traitant des démonstrations des méthodes employées peuvent compléter les connaissances du lecteur ; ce dernier pourra consulter en fin de chapitre, de nombreuses références et des liens Internet, permettant de trouver rapidement la plupart des méthodes évoquées ayant inspiré la rédaction du chapitre. Par sa nature didactique et ses applications, puis, par la diversité des méthodes abordées, la démarche se veut avant tout pédagogique, et démontre que la programmation fonctionnelle s'intègre totalement à l'univers des calculs scientifiques. L'objectif principal de ce livre est d'abord de fournir à un public le plus large possible un ouvrage qui pourra servir à comprendre les bases du domaine fonctionnel et à mettre en oeuvre l'application des listes, la récursivité et le pattern-matching, afin de résoudre différents problèmes scientifiques. Les programmes de ces méthodes et techniques ont vocation à intervenir dans la quasi-totalité des domaines de la science ; ce livre s'adresse donc particulièrement aux étudiants scientifiques d'IUT ou de la formation continue, ainsi qu'aux élèves d'école d'Ingénieur confrontés au codage d'un problème numérique, aux doctorants à la recherche d'une solution sur un sujet particulier ; il constitue aussi une information pour les enseignants des grandes écoles et universités. Le contenu de l'ouvrage a été enseigné et a été l'objet de projets dans le cadre de plusieurs formations de mathématiques appliquées ; citons parmi celles-ci, différentes unités d'enseignement du premier et second cycle du Conservatoire National des Arts et Métiers (CNAM Nantes), l'Institut Catholique d'Études Supérieures (ICES Roche sur Yon), ainsi que la licence de Mathématiques et Informatique et miniprojets de recherche à l'École Polytechnique de l'Université de Nantes (EPUN).

Avant-propos I Remerciements CHAPITRE 11 - Introduction aux Processus 1. Définition 2. Problèmes rencontrés. 3. Modélisation de problèmes concrets courants 4. Bibliographie CHAPITRE 12 - La communication entre processus 1. Une première réalisation 2. Une seconde réalisation - Le produit matriciel 3. Une troisième réalisation - La suite de Fibonacci 4. Calcul du tri rapide(QSORT) par tâches réplicatives 5. Parallèlisation du tri par fusion CHAPITRE 13 - Architecture Client-Serveur 1. Définition 2. Le modèle Client/Serveur 3. Une réalisation : Le produit matriciel sur un serveur distant via le protocole TCP/IP 4. Bibliographie CHAPITRE 14 - Les objets fractals 1. Définition 2. Dimension fractale 3. Différentes fractales 4. L'ensemble de Mandelbrot 5. Bibliographie CHAPITRE 15 - Le Clustering 1. Définition 2. Une première réalisation-Calcul d'un produit matriciel en parallèle 3. Une seconde réalisation-Calcul d'une image fractale sur un LAN 4. Courbe de speed-up 5. Bibliographie CHAPITRE 16 - Le Clustering Client-Serveur Objets 1. Introduction au client-serveur objets 2. Calcul d'un produit matriciel parallélisé à partir d'un serveur d'objets CHAPITRE 17 - Transformée en Cosinus Discrète(DCT) 1. Introduction 2. Transformation DCT sur un signal 3. La DCT 2D 4. Un exemple pédagogique 5. Bibliographie CHAPITRE 18 - Résolution des équations aux dérivées partielles 1. Introduction 2. Exemple simple 3. Résolution de l'équation de Poisson 4. Résolution de l'équation des ondes 5. Résolution de l'équation de transport 6. Résolution de l'équation de convection- diffusion 7. Résolution d'un Laplacien 2D par différences finies 8. Résolution de l'équation de convection-diffusion 9. Equation de convection-diffusion en 2D 10. Etude de la parallèlisation de l'équation de convection-diffusion instationnaire en 2D 11. Analyse des performances 12. Bibliographie CHAPITRE 19 - Transformée en ondelettes 1D 1. Théorie des ondelettes 2. Différents types d'ondelettes 3. Compression par seuillage des coefficients d'ondelettes 4. Calcul de l'estimation par corrélation entre seuil et niveau. Compression avec perte - Ondelettes de Haar 5. Débruitage linéaire et compression en sélectionnant les N premiers coefficients d'ondelettes de Haar - Reconstruction par splines cubiques 6. Débruitage non linéaire par seuillage des coefficients d'ondelettes de Haar 7. Le théorème de DONOHO-JOHNSTONE 8. Base d'ondelettes de Daubechies 9. Bibliographie CHAPITRE 20 - Transformée en ondelettes 2D 1. Introduction 2. Récupérer une image sous la fenêtre Ocaml Graphics 3. Bibliographie CHAPITRE 21 - Application de l'équation de diffusion sur une image 1. Introduction 2. Le processus de diffusion 3. Application sur l'image de LENA 4. Application sur l'image de OUILLY 5. Bibliographie CHAPITRE 22 - Dynamique des fluides 1. Introduction 2. Dynamique des fluides parfaits incompressibles 3. Dynamique des fluides visqueux incompressibles 4. Méthode de calcul dans le plan complexe 5. Position et création des tourbillons 6. Potentiel complexe induit par un tourbillon ponctuel 7. Vitesse induite par un tourbillon ponctuel 8. Convection et diffusion 9. Suppression des tourbillons entrant dans le solide 10. Algorithmes séquentiels 11. Réalisation séquentielle 12. Projet de la parallèlisation de la simulation de l'écoulement sur une grappe de processeurs 13. Conclusion 14. Bibliographie ANNEXES TABLE DES MATIÈRES DÉTAILLÉE : Avant-propos I Remerciements CHAPITRE 11 - Introduction aux Processus 1. Définition 2. Problèmes rencontrés. 2.1. Exemple de synchronisation avec l'utilisation de condition 2.2. La fonction : Thread.join 2.3. Exercices 3. Modélisation de problèmes concrets courants 3.1. Le modèle Producteur-consommateur 3.1.1. Modèle Producteur-consommateur - Retrait à l'ancienneté avec tampon linéaire 3.1.2. Modèle Producteur-consommateur - Retrait à l'ancienneté avec tampon circulaire 3.1.3. Couple Producteur-consommateur en programmation concurrente - Utilisation d'une file d'attente manipulée en exclusion mutuelle 3.1.4. Couple Producteur-consommateur en programmation concurrente - Attente et synchronisation en exclusion mutuelle avec communication - Utilisation de verrous et conditions 3.2. Le modèle Lecteur-rédacteur 3.2.1. Modèle Lecteur-rédacteur avec priorité aux lecteurs 3.2.2. Modèle Lecteur-rédacteur avec équité lecteurs-rédacteurs 3.2.3. Modèle Lecteur-rédacteur avec priorité aux rédacteurs 3.3. Le dîner des philosophes orientaux 4. Bibliographie CHAPITRE 12 - La communication entre processus 1. Une première réalisation 2. Une seconde réalisation - Le produit matriciel 2.1. Une première écriture en langage Ocaml 2.2. Une deuxième écriture 3. Une troisième réalisation - La suite de Fibonacci 3.1. Répartition des données et codage Ocaml 3.2. Programmation par réplication du code sur un ensemble de données différentes 4. Calcul du tri rapide(QSORT) par tâches réplicatives 4.1. Ecriture en langage Ocaml - Cas des vecteurs 4.2. Ecriture en langage Ocaml - Cas des suites 5. Parallèlisation du tri par fusion 5.1. Echange de deux éléments dans deux suites séparées 5.2. Approche itérative séquentielle du tri par remontée 5.3. Approche récursive par tâches du tri par remontée CHAPITRE 13 - Architecture Client-Serveur 1. Définition 2. Le modèle Client/Serveur 2.1. Les sockets 3. Une réalisation : Le produit matriciel sur un serveur distant via le protocole TCP/IP 3.1. Implémentation du serveur 3.2. Implémentation d'un client (tâche répliquée sur chaque poste client) 4. Bibliographie CHAPITRE 14 - Les objets fractals 1. Définition 2. Dimension fractale 2.1. Dimension de Mandelbrot 2.2. L'autosimilarité 2.3. Le rôle du hasard 3. Différentes fractales 3.1. Les I.F.S 3.1.1. Notion d'attracteur 3.1.2. Définition d'un IFS 3.2. Courbe du dragon 3.3. Triangle de Sierpinski 3.4. Arbres fractals 3.5. La fougère de Barnsley 4. L'ensemble de Mandelbrot 4.1. Monoprogrammation - L'approche impérative 4.2. Monoprogrammation - L'approche fonctionnelle 4.3. Multiprogrammation - Approche fonctionnelle 5. Bibliographie CHAPITRE 15 - Le Clustering 1. Définition 2. Une première réalisation-Calcul d'un produit matriciel en parallèle 2.1. Algorithme de répartition d'une boucle sur plusieurs serveurs 2.2. Fonction de répartition en Ocaml. 2.3. Découpage des matrices A et B 2.4. Le programme serveur dupliqué sur toutes les stations 2.5. Le programme client 3. Une seconde réalisation-Calcul d'une image fractale sur un LAN 3.1. Recherche des serveurs connectés sur le réseau 3.2. Implémentation du programme complet d'un noeud 3.3. Implémentation du programme du loadbalanced 4. Courbe de speed-up 5. Bibliographie CHAPITRE 16 - Le Clustering Client-Serveur Objets 1. Introduction au client-serveur objets 2. Calcul d'un produit matriciel parallélisé à partir d'un serveur d'objets 2.1. Sommaire et introduction 2.2. Le projet 2.3. Spécification 2.3.1. Architecture du projet 2.3.2. Structure du programme : processus et co-processus 2.3.3. Structure du client 2.3.4. Structure du serveur 2.3.5. Structure du serveur d'IP 2.3.6. Structure d'une connexion d'un client avec un serveur 2.4. Concepts et programmation 2.4.1. fonctions 2.4.2. Les classes 2.4.2.1. Description des classes principales 2.4.2.2. Modularisation 2.5. Installation et exécution 2.6. Impressions d'écrans 2.7. Conclusion 2.8. Remerciements 2.9. Programmes sources 2.9.1. Programmes communs à la station cliente et aux stations serveurs 2.9.2. Programmes communs aux stations serveurs et serveur IP 2.9.3. Programmes station client 2.9.4. Programmes serveurs 2.9.5. Programmes serveur IP CHAPITRE 17 - Transformée en Cosinus Discrète(DCT) 1. Introduction 2. Transformation DCT sur un signal 2.1. Exemple DCT 1D avec différents seuillages sur le signal 3. La DCT 2D 3.1. La compression JPEG 3.2. La quantification 3.3. Algorithme zigzag 3.3.1. Principe de l'algorithme 3.3.1.1. Cas du balayage de la partie supérieure 3.3.1.2. Cas du balayage de la partie inférieure 4. Un exemple pédagogique 4.1. Gestion de l'image 4.2. Application de la DCT 4.2.1. Fonctions de base de la DCT 5. Bibliographie CHAPITRE 18 - Résolution des équations aux dérivées partielles 1. Introduction 2. Exemple simple 3. Résolution de l'équation de Poisson 3.1. Résolution par la méthode itérative de Jacobi 3.2. Implémentation 3.3. Résolution par différences finies dans la base des vecteurs propres du Laplacien 3.3.1. Implémentation 4. Résolution de l'équation des ondes 4.1. Implémentation équation des ondes - propagation d'une harmonique 5. Résolution de l'équation de transport 5.1. Implémentation équation de transport - Schéma de LAX 5.2. Implémentation équation de transport - Schéma de Crank-Nicholson centré 5.3. Implémentation équation de transport - Schéma de Crank-Nicholson décentré 6. Résolution de l'équation de convection- diffusion 6.1. Implémentation équation de convection-diffusion - Schéma de Crank-Nicholson décentré 6.1.1. Dicrétisation 6.2. Résolution par le schéma d'Euler progressif 6.3. Implémentation schéma stable 6.4. Graphe des courbes obtenues pour une discrétisation en 20 points et 20 itérations 6.5. Résolution par le schéma d'Euler rétrograde 6.6. Implémentation schéma stable 6.7. Graphe des courbes obtenues pour une discrétisation en 20 points et 20 itérations 6.8. Résolution par le schéma de Cranck-Nicholson 6.9. Implémentation 6.10. Résolution par éléments finis-Equation de la chaleur 1D 6.11. Implémentation 6.12. Graphe des courbes obtenues pour une discrétisation en 20 points et 20 itérations 6.13. Résolution par la FFT (Transformée de Fourrier) 6.14. Implémentation 6.15. Résolution de l'équation de la chaleur en 1D avec pour CI : y=sin(?.x) - Résolution par différences 6.16. Résolution par différences finies - Equation de la chaleur en 1D - Diffusion traitée en explicite - Condition de Dirichlet à la frontière - Comparaison avec la solution exacte 6.17. Résolution par différences finies - Equation de la chaleur en 1D - Diffusion traitée en implicite - condition de Dirichlet à la frontière - Comparaison avec la solution exacte 6.18. Equation de la chaleur en 1D - Schéma d'Euler implicite conditions aux limites de Dirichlet - Conditions initiales aléatoires 6.19. Equation de la chaleur en 1D - Schéma d'Euler explicite conditions aux limites de Dirichlet - Conditions initiales aléatoires 7. Résolution d'un Laplacien 2D par différences finies 8. Résolution de l'équation de convection-diffusion 8.1. Les différentes méthodes de résolution par différences finies 8.1.1 Convection explicite (centrée ou upwind) avec diffusion implicite 8.1.2 Discrétisation par différences finies-Schéma d'Euler décentré 8.1.3 Exemple d'implémentation d'un schéma décentré à gauche 8.2. Discrétisation par différences finies-Schéma centré 8.2.1 Exemple d'implémentation d'un schéma centré 9. Equation de convection-diffusion en 2D 10. Etude de la parallèlisation de l'équation de convection-diffusion instationnaire en 2D 10.1 Parallélisation de la méthode du gradient bi-conjuguée sur 3 processeurs 10.1.1 Implémentation du LOADBALANCED 10.1.2 Implémentation NoeUD n°1 10.1.3 Implémentation NoeUD n°2 10.2 Extension de la méthode sur 5 pc (extensible à N pc) 11. Analyse des performances 12. Bibliographie CHAPITRE 19 - Transformée en ondelettes 1D 1. Théorie des ondelettes 2. Différents types d'ondelettes 2.1. L'ondelette de Morlet 2.2. Implémentation ondelette de Morlet 1D 2.3. Autre famille de fonctions, les dérivées de la Gaussienne 2.4. Implémentation Mexicain Hat - 2D 2.5. La famille des ondelettes de Gabor 2.6. Implémentation ondelette de Gabor 2.7. Ondelette d'Ingrid Daubechies 2.8. Implémentation ondelette d'Ingrid Daubechies 2.9. Ondelette de Haar 3.2.1 Implémentation recherche des coefficients d'ondelette de Haar en 2D 2.9.2 Implémentation de la transformée inverse 2.9.3 Application sur un signal (restitution sans perte de l'échantillon) 2.9.4 Représentation matricielle -ondelettes de Haar 2.9.5 Implémentation de la méthode des ondelettes de Haar par le produit matriciel 3. Compression par seuillage des coefficients d'ondelettes 3.1. Recherche de différents seuillages appliqués aux coefficients d'ondelettes de Haar 3.1.1. Seuil log ?=Tavec ? calculé sur la totalité des coefficients 3.1.2. Seuil T=ondelettesd'tscoefficienles et avec y2/NymNln.26745.0.miN2/Ni?=760 4. Calcul de l'estimation par corrélation entre seuil et niveau. Compression avec perte - Ondelettes de Haar 4.1 Implémentation de l'algorithme 4.2 Mélange de trois fréquences 4.3 Application au Théorème de Shannon : 5. Débruitage linéaire et compression en sélectionnant les N premiers coefficients d'ondelettes de Haar - Reconstruction par splines cubiques 5.1 Recherche sur un passage d'ondelettes 6. Débruitage non linéaire par seuillage des coefficients d'ondelettes de Haar 6.1 Seuillage dur - un seul niveau - compression et reconstruction par splines cubiques 6.2 Implémentation seuillage dur - Reconstruction par splines cubiques 6.3 Seuillage doux - Lissage par morceaux en moindres carrés 6.4 Implémentation seuillage doux - Lissage par moindres carrés 6.5 Seuillage - Multi-passages - Recherche du nombre de passages 6.6 Implémentation seuillage doux - multi-passages 6.7 Implémentation seuillage dur - multi-passages 7. Le théorème de DONOHO-JOHNSTONE 7.1 Débruitage - seuillage dur par estimation de l'écart type matrice de Haar 7.2 Débruitage multi-niveaux - seuillage dur par estimation de l'écart-type 8. Base d'ondelettes de Daubechies 8.1 Comparaison entre Daubechies 4 et Haar - Seuillage linéaire en sélectionnant les N premiers coefficients 8.2 Seuillage dur et seuillage doux en sélectionnant les N/2 éléments de l'échelle la plus fine pour le calcul du seuil 8.3 Débruitage par seuillage estimateur de l'écart-type 9. Bibliographie CHAPITRE 20 - Transformée en ondelettes 2D 1. Introduction 2. Récupérer une image sous la fenêtre Ocaml Graphics 2.1 Récupération de la valeur des pixels à partir d'un fichier HTML 2.2 Sauvegarde de l'image à partir de la fenêtre graphique OCAML 2.3 La méthode des ondelettes en 2D 2.4 Implémentation de la méthode 3. Bibliographie CHAPITRE 21 - Application de l'équation de diffusion sur une image 1. Introduction 2. Le processus de diffusion 3. Application sur l'image de LENA 3.1 Restitution de l'image par approximations successives 3.2 Améliorations possibles884 3.3 Cas de blocs trop volumineux (32x32) 4. Application sur l'image de OUILLY 4.1 Implémentation Ocaml 4.2 Quelques autres résultats 5. Bibliographie CHAPITRE 22 - Dynamique des fluides 1. Introduction 2. Dynamique des fluides parfaits incompressibles 2.1 Le problème de NEUMANN 2.1.1 Equations générales 2.1.2 Conditions aux limites 2.2 Calcul du potentiel de l'écoulement 2.3 Discrétisation de l'équation 3. Dynamique des fluides visqueux incompressibles 3.1 Simulation d'écoulement par une méthode de tourbillons discrets 3.2 La méthode des tourbillons particulaires 3.2.1 Simulation de la diffusion visqueuse 3.2.2 Résolution de l'équation de convection 3.2.3 Résolution de l'équation de diffusion 3.2.4 Création des tourbillons 4. Méthode de calcul dans le plan complexe 4.1 Détermination des coefficients d'influences en sources ponctuelles 4.2 Répartition uniforme de sources 4.2.1 Transcription en réel 4.3 Solution analytique de la répartition de sources sur un cylindre circulaire bidimensionnel 4.4 Calcul du potentiel complexe 4.4.1 Potentiel complexe d'une source placée à l'origine 4.4.2 Potentiel complexe d'une source placée en z0 4.4.3 Potentiel complexe créé par des sources uniformément réparties sur un segment 4.4.3.1 Transcription en réel 4.4.4 Solution analytique de la fonction de courant de l'écoulement autour du cylindre circulaire bidimensionnel 4.5 Vitesse complexe 4.5.1 Vitesse complexe- source ponctuelle 4.5.2 Vitesse complexe- source répartie sur un segment 4.5.2.1 Vitesse sur le segment- définition par continuité 4.5.3 Transcription en réel 4.5.3.1 Calcul dans le repère principal (x,y) 4.5.3.2 Calcul direct dans le repère élémentaire (axe t,n) 5. Position et création des tourbillons 5.1 Intensité du tourbillon 5.2 Position du tourbillon 6. Potentiel complexe induit par un tourbillon ponctuel 7. Vitesse induite par un tourbillon ponctuel 8. Convection et diffusion 9. Suppression des tourbillons entrant dans le solide 10. Algorithmes séquentiels 10.1 Cas de la simulation par sources ponctuelles 10.2 Cas de la simulation par répartition uniforme de source 11. Réalisation séquentielle 11.1 Définition et signature des fonctions 11.2 Code Ocaml des fonctions 11.3 Implémentation Séquentielle - Sources ponctuelles 11.4 Implémentation Séquentielle - Répartition uniforme de source - Traitement en réel 11.5 Enregistrement des tourbillons dans un fichier 11.6 Implémentation en complexe 11.7 Conclusion sur le déroulement séquentiel de la simulation 12. Projet de la parallèlisation de la simulation de l'écoulement sur une grappe de processeurs 12.1 Introduction 12.2 Présentation du projet et de ses spécifications 12.2.1 Nature du projet 12.2.2 Les contraintes du projet 12.2.3 Exigences fonctionnelles 12.2.4 Autres exigences 12.3 Organisation 12.3.1 Approche méthodologique 12.3.2 Pilotage 12.3.2.1 Le PAQ (plan qualité) 12.3.2.2 La gestion des risques 12.3.2.3 Réunions de pilotage 12.3.2.4 Le suivi des anomalies 12.3.2.5 Les procès verbaux de recette 12.3.2.6 Le bilan du projet 12.4 Etude préalable de la simulation 12.4.1 Discrétisation (Méthode de Chorin) 12.4.2 Vorticités 12.4.3 Nombre de Reynolds 12.4.4 Convection-diffusion 12.4.5 Résolution du système linéaire 12.5 Conception 12.5.1 Réseau, matériel et environnement 12.6 Plan de développement 12.6.1 Hypothèses de parallèlisation retenues 12.6.2 Détail des blocs à parallèliser 12.7 Implémentation 12.7.1 La bibliothèque des primitives ENVOI et RECEPTION des messages 12.7.2 Implémentation du Loadbalenced 12.7.3 Implémentation d'un noeud 12.8 Charge réseau 12.9 Mesure de performance 12.9.1 Evaluation des performances (Speed-up) 12.9.2 L'efficacité 13. Conclusion 14. Bibliographie ANNEXES