101 |
Razvoj serijskog i paralelnog algoritma za računanje elektronske strukture materijala metodom sklapanja naelektrisanja / Development of Serial and Parallel Algorithms forComputing the Electronic Structure of MaterialsUsing the Charge Patching MethodBodroški Žarko 04 November 2020 (has links)
<p>U tezi je predstavljena implementacija metode teorija funkcionala gustine (DFT) bazirana na metodi za sklapanje naelektrisanja (CPM) koja koristi bazise gausijanskih funkcija. Metod je baziran na pretpostavci da se elektronska gustina naelektrisanja velikih sistema, može predstaviti kao suma doprinosa pojedinačnih atoma, takozvanih motiva gustine naelektrisanja, koji se dobijaju računanjem malog prototip sistema. Talasna funkcija,<br />kao i gustina naelektrisanja, se u našoj implementaciji reprezentuju uz pomoć bazise gausijanskih funkcija, dok se motivi opisuju korišćenjem prostornih koordinata. Uz pomoć procedure za minimizaciju se iz motiva opisanih koordinatama, dobija gustina naelektrisanja predstavljena u bazisu Gausijana. Implementacija serijskog programa pokazuje značajno poboljšanje u performansama u odnosu na prethodne implementacije bazirane na ravnim talasima. Ova implementacija rešava sistem od približno 1000 atoma na jednom procesorskom jezgru za svega nekoliko sati. Paralelna implementacija uz pomoć naprednih metoda paralelizacije i distribucije podataka omogućava rešavanje sistema od više desetina hiljada atoma. Najveći testirani sistem ima približno<br />20000 atoma i testiran je na 256 paralelnih procesa.</p> / <p>We present the implementation of the density functional theory (DFT) based charge patching method (CPM) using the basis of Gaussian functions. The method is based on the assumption that the electronic charge density of a large system is the sum of contributions of individual atoms, so called charge density motifs, that are obtained from calculations of small prototype systems.In our implementation wave functions and electronic charge density are represented using the basis of Gaussian functions, while charge density motifs are represented using a real space grid. A constrained minimization procedure is used to obtain Gaussian basis representation of charge density from real space representation of motifs. The code based on this implementation exhibits superior performance in comparison to previous implementation of the charge patching method using the basis of plane waves. It enables calculations of electronic structure of systems with around 1000 atoms on a single CPU core with computational time of just several hours. The parallel implementation enables calculations for the system with more than ten thousand atoms. The largest system tested has around 20000 atoms and was computed on 256 parallel processes.</p>
|
102 |
Parallel optimization based operational planning to enhance the resilience of large-scale power systemsGong, Lin 01 May 2020 (has links)
The resilience of power systems is attracting extensive attention in recent years and needs to be further enhanced in the future, as potential threats from severe events such as extreme weather, geomagnetic storm, as well as extended fuel disruption, which are not easy to be quantified, predicted, or anticipated, are still challenging the modern power industry. To increase the resilience, proper operational planning considering potential impacts of severe events could effectively enable power systems to prepare for, operate through, and recover from those events and mitigate their negative economic, social, and humanitarian consequences by fully deploying existing system resources and operational measures. In this dissertation, operational planning problems in the bulk power system considering potential threats from severe events are focused, including the co-optimization of security-constrained unit commitment and transmission switching with consideration of transmission line outages probably caused by severe weather events, the security-constrained optimal power flow under potential impacts from geomagnetic storms, and the optimal operational planning to prevent electricity-natural gas systems from possible risks of natural gas supply disruptions. Notice that systematic, comprehensive, and consistent operational strategies should be conducted across the entire system to achieve superior resilience enhancement solution, which, along with increased size and complexity of modern energy systems, makes the proposed operational planning problems mathematically large-size and computationally complex optimization problems, and practically difficult to solve, especially when comprehensive operational measures and resourceful components are incorporated. In order to tackle such a challenge, the parallel optimization based approaches are developed in the proposed research, which fully decompose an originally large and complex problem into multiple independent small subproblems, simultaneously solve them in a fully parallel manner on scalable multiple-core computing platforms, and iteratively coordinate their results by using mathematical programming methods to achieve optimal solutions that satisfy engineering requirements of power system operations in practice. As a result, by efficiently solving optimal operational planning problems of large-scale power systems, their secure and economic operations in the presence of severe events like hurricanes, geomagnetic storms, and natural gas supply disruptions can be ensured, which indicates the resilience of power systems is effectively enhanced.
|
103 |
Algorithms and Library Software for Periodic and Parallel Eigenvalue Reordering and Sylvester-Type Matrix Equations with Condition EstimationGranat, Robert January 2007 (has links)
This Thesis contains contributions in two different but closely related subfields of Scientific and Parallel Computing which arise in the context of various eigenvalue problems: periodic and parallel eigenvalue reordering and parallel algorithms for Sylvestertype matrix equations with applications in condition estimation. Many real world phenomena behave periodically, e.g., helicopter rotors, revolving satellites and dynamic systems corresponding to natural processes, like the water flow in a system of connected lakes, and can be described in terms of periodic eigenvalue problems. Typically, eigenvalues and invariant subspaces (or, specifically, eigenvectors) to certain periodic matrix products are of interest and have direct physical interpretations. The eigenvalues of a matrix product can be computed without forming the product explicitly via variants of the periodic Schur decomposition. In the first part of the Thesis, we propose direct methods for eigenvalue reordering in the periodic standard and generalized real Schur forms which extend earlier work on the standard and generalized eigenvalue problems. The core step of the methods consists of solving periodic Sylvester-type equations to high accuracy. Periodic eigenvalue reordering is vital in the computation of periodic eigenspaces corresponding to specified spectra. The proposed direct reordering methods rely on orthogonal transformations and can be generalized to more general periodic matrix products where the factors have varying dimensions and ±1 exponents of arbitrary order. In the second part, we consider Sylvester-type matrix equations, like the continuoustime Sylvester equation AX −XB =C, where A of size m×m, B of size n×n, and C of size m×n are general matrices with real entries, which have applications in many areas. Examples include eigenvalue problems and condition estimation, and several problems in control system design and analysis. The parallel algorithms presented are based on the well-known Bartels–Stewart’s method and extend earlier work on triangular Sylvester-type matrix equations resulting in a novel software library SCASY. The parallel library provides robust and scalable software for solving 44 sign and transpose variants of eight common Sylvester-type matrix equations. SCASY also includes a parallel condition estimator associated with each matrix equation. In the last part of the Thesis, we propose parallel variants of the direct eigenvalue reordering method for the standard and generalized real Schur forms. Together with the existing and future parallel implementations of the non-symmetric QR/QZ algorithms and the parallel Sylvester solvers presented in the Thesis, the developed software can be used for parallel computation of invariant and deflating subspaces corresponding to specified spectra and associated reciprocal condition number estimates.
|
104 |
Structure-Exploiting Numerical Algorithms for Optimal ControlNielsen, Isak January 2017 (has links)
Numerical algorithms for efficiently solving optimal control problems are important for commonly used advanced control strategies, such as model predictive control (MPC), but can also be useful for advanced estimation techniques, such as moving horizon estimation (MHE). In MPC, the control input is computed by solving a constrained finite-time optimal control (CFTOC) problem on-line, and in MHE the estimated states are obtained by solving an optimization problem that often can be formulated as a CFTOC problem. Common types of optimization methods for solving CFTOC problems are interior-point (IP) methods, sequential quadratic programming (SQP) methods and active-set (AS) methods. In these types of methods, the main computational effort is often the computation of the second-order search directions. This boils down to solving a sequence of systems of equations that correspond to unconstrained finite-time optimal control (UFTOC) problems. Hence, high-performing second-order methods for CFTOC problems rely on efficient numerical algorithms for solving UFTOC problems. Developing such algorithms is one of the main focuses in this thesis. When the solution to a CFTOC problem is computed using an AS type method, the aforementioned system of equations is only changed by a low-rank modification between two AS iterations. In this thesis, it is shown how to exploit these structured modifications while still exploiting structure in the UFTOC problem using the Riccati recursion. Furthermore, direct (non-iterative) parallel algorithms for computing the search directions in IP, SQP and AS methods are proposed in the thesis. These algorithms exploit, and retain, the sparse structure of the UFTOC problem such that no dense system of equations needs to be solved serially as in many other algorithms. The proposed algorithms can be applied recursively to obtain logarithmic computational complexity growth in the prediction horizon length. For the case with linear MPC problems, an alternative approach to solving the CFTOC problem on-line is to use multiparametric quadratic programming (mp-QP), where the corresponding CFTOC problem can be solved explicitly off-line. This is referred to as explicit MPC. One of the main limitations with mp-QP is the amount of memory that is required to store the parametric solution. In this thesis, an algorithm for decreasing the required amount of memory is proposed. The aim is to make mp-QP and explicit MPC more useful in practical applications, such as embedded systems with limited memory resources. The proposed algorithm exploits the structure from the QP problem in the parametric solution in order to reduce the memory footprint of general mp-QP solutions, and in particular, of explicit MPC solutions. The algorithm can be used directly in mp-QP solvers, or as a post-processing step to an existing solution. / Numeriska algoritmer för att effektivt lösa optimala styrningsproblem är en viktig komponent i avancerade regler- och estimeringsstrategier som exempelvis modellprediktiv reglering (eng. model predictive control (MPC)) och glidande horisont estimering (eng. moving horizon estimation (MHE)). MPC är en reglerstrategi som kan användas för att styra system med flera styrsignaler och/eller utsignaler samt ta hänsyn till exempelvis begränsningar i styrdon. Den grundläggande principen för MPC och MHE är att styrsignalen och de estimerade variablerna kan beräknas genom att lösa ett optimalt styrningsproblem. Detta optimeringsproblem måste lösas inom en kort tidsram varje gång som en styrsignal ska beräknas eller som variabler ska estimeras, och således är det viktigt att det finns effektiva algoritmer för att lösa denna typ av problem. Två vanliga sådana är inrepunkts-metoder (eng. interior-point (IP)) och aktivmängd-metoder (eng. active-set (AS)), där optimeringsproblemet löses genom att lösa ett antal enklare delproblem. Ett av huvudfokusen i denna avhandling är att beräkna lösningen till dessa delproblem på ett tidseffektivt sätt genom att utnyttja strukturen i delproblemen. Lösningen till ett delproblem beräknas genom att lösa ett linjärt ekvationssystem. Detta ekvationssystem kan man exempelvis lösa med generella metoder eller med så kallade Riccatirekursioner som utnyttjar strukturen i problemet. När man använder en AS-metod för att lösa MPC-problemet så görs endast små strukturerade ändringar av ekvationssystemet mellan varje delproblem, vilket inte har utnyttjats tidigare tillsammans med Riccatirekursionen. I denna avhandling presenteras ett sätt att utnyttja detta genom att bara göra små förändringar av Riccatirekursionen för att minska beräkningstiden för att lösa delproblemet. Idag har behovet av parallella algoritmer för att lösa MPC och MHE problem ökat. Att algoritmerna är parallella innebär att beräkningar kan ske på olika delar av problemet samtidigt med syftet att minska den totala verkliga beräkningstiden för att lösa optimeringsproblemet. I denna avhandling presenteras parallella algoritmer som kan användas i både IP- och AS-metoder. Algoritmerna beräknar lösningen till delproblemen parallellt med ett förutbestämt antal steg, till skillnad från många andra parallella algoritmer där ett okänt (ofta stort) antal steg krävs. De parallella algoritmerna utnyttjar problemstrukturen för att lösa delproblemen effektivt, och en av dem har utvärderats på parallell hårdvara. Linjära MPC problem kan också lösas genom att utnyttja teori från multiparametrisk kvadratisk programmering (eng. multiparametric quadratic programming (mp-QP)) där den optimala lösningen beräknas i förhand och lagras i en tabell, vilket benämns explicit MPC. I detta fall behöver inte MPC problemet lösas varje gång en styrsignal beräknas, utan istället kan den förberäknade optimala styrsignalen slås upp. En nackdel med mp-QP är att det krävs mycket plats i minnet för att spara lösningen. I denna avhandling presenteras en strukturutnyttjande algoritm som kan minska behovet av minne för att spara lösningen, vilket kan öka det praktiska användningsområdet för mp-QP och explicit MPC.
|
105 |
Parallélisation de la ligne de partage des eaux dans le cadre des graphes à arêtes valuées sur architecture multi-cœurs / Parallelization of the watershed transform in weighted graphs on multicore architectureBraham, Yosra 24 November 2018 (has links)
Notre travail s'inscrit dans le cadre de la parallélisation d’algorithmes de calcul de la Ligne de Partage des Eaux (LPE) en particulier la LPE d’arêtes qui est une notion de la LPE introduite dans le cadre des Graphes à Arêtes Valuées. Nous avons élaboré un état d'art sur les algorithmes séquentiels de calcul de la LPE afin de motiver le choix de l'algorithme qui fait l'objet de notre étude qui est l'algorithme de calcul de noyau par M-bord. L'objectif majeur de cette thèse est de paralléliser cet algorithme afin de réduire son temps de calcul. En premier lieu, nous avons présenté les travaux qui se sont intéressés à la parallélisation des différentes variantes de la LPE et ce afin de dégager les problématiques que soulèvent cette tâche et les solutions adéquates à notre contexte. Dans un second lieu, nous avons montré que malgré la localité de l'opération de base de cet algorithme qui est l’abaissement de la valeur de certaines arêtes nommées arêtes M-bord, son exécution parallèle se trouve pénaliser par un problème de dépendance de données, en particulier au niveau des arêtes M-bord qui ont un sommet non minimum commun. Dans ce contexte, nous avons proposé trois stratégies de parallélisation de cet algorithme visant à résoudre ce problème de dépendance de données. La première stratégie consiste à diviser le graphe de départ en des bandes appelées partitions, et les traiter en parallèle sur P processeurs. La deuxième stratégie consiste à diviser les arêtes du graphe de départ en alternance en des sous-ensembles d’arêtes indépendantes. La troisième stratégie consiste à examiner les sommets au lieu des arêtes du graphe initial tout en préservant le paradigme d’amincissement sur lequel est basé l’algorithme séquentiel initial. Par conséquent, l’ensemble des sommets non-minima adjacents aux sommets minima sont traités en parallèle. En dernier lieu, nous avons étudié la parallélisation d'une technique de segmentation basée sur l'algorithme de calcul de noyau par M-bord. Cette technique comprend les étapes suivantes : la recherche des minima régionaux, la pondération des sommets et le calcul des sommets minima et enfin calcul du noyau par M-bord. A cet égard, nous avons commencé par faire une étude relative à la dépendance des données des différentes étapes qui la constituent et nous avons proposé des algorithmes parallèles pour chacune d'entre elles. Afin d'évaluer nos contributions, nous avons implémenté les différents algorithmes parallèles proposés dans le cadre de cette thèse sur une architecture multi-cœurs à mémoire partagée. Les résultats obtenus ont montré des gains en termes de temps d’exécution. Ce gain est traduit par des facteurs d’accélération qui augmentent avec le nombre de processeurs et ce quel que soit la taille des images à segmenter / Our work is a contribution of the parallelization of the Watershed Transform in particular the Watershed cuts which are a notion of watershed introduced in the framework of Edge Weighted Graphs. We have developed a state of art on the sequential watershed algorithms in order to motivate the choice of the algorithm that is the subject of our study, which is the M-border Kernel algorithm. The main objective of this thesis is to parallelize this algorithm in order to reduce its running time. First, we presented a review on the works that have treated the parallelization of the different types of Watershed in order to identify the issues raised by this task and the appropriate solutions to our context. In a second place, we have shown that despite the locality of the basic operation of this algorithm which is the lowering of some edges named the M-border edges; its parallel execution raises a data dependency problem, especially at the M-border edges which have a common non-minimum vertex. In this context, we have proposed three strategies of parallelization of this algorithm that solve this problematic: the first strategy consists of dividing the initial graph into bands called partitions processed in parallel by P processors. The second strategy is to divide the edges of the initial graph alternately into subsets of independent edges. The third strategy consists in examining the vertices instead of the edges of the initial graph while preserving the thinning paradigm on which the sequential algorithm is based. Therefore, the set of non-minima vertices adjacent to the minima ones are processed in parallel. Finally, we studied the parallelization of a segmentation technique based on the M-border kernel algorithm. This technique consists of three main steps which are: regional minima detection, vertices valuation and M-border kernel computation. For this purpose, we began by studying the data dependency of the different stages of this technique and we proposed parallel algorithms for each one of them. In order to evaluate our contributions, we implemented the parallel algorithms proposed in this thesis, on a shared memory multi-core architecture. The results obtained showed a notable gain in terms of execution time. This gain is translated by speedup factors that increase with the number of processors whatever is the resolution of the input images
|
106 |
Deadline-ordered burst-based parallel scheduling strategy for IP-over-ATM with QoS support.January 2001 (has links)
Siu Chun. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2001. / Includes bibliographical references (leaves 66-68). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Thesis Overview --- p.3 / Chapter 2 --- Background and Related work --- p.4 / Chapter 2.1 --- Emergence of IP-over-ATM --- p.4 / Chapter 2.2 --- ATM architecture --- p.5 / Chapter 2.3 --- Scheduling issues in output-queued switch --- p.6 / Chapter 2.4 --- Scheduling issues in input-queued switch --- p.18 / Chapter 3 --- The Deadline-ordered Burst-based Parallel Scheduling Strategy --- p.23 / Chapter 3.1 --- Introduction --- p.23 / Chapter 3.2 --- Switch and queueing model --- p.24 / Chapter 3.2.1 --- Switch model --- p.24 / Chapter 3.2.2 --- Queueing model --- p.25 / Chapter 3.3 --- The DBPS Strategy --- p.26 / Chapter 3.3.1 --- Motivation --- p.26 / Chapter 3.3.2 --- Strategy --- p.31 / Chapter 3.4 --- The Deadline-ordered Burst-based Parallel Iterative Matching --- p.33 / Chapter 3.4.1 --- Algorithm --- p.34 / Chapter 3.4.2 --- An example of DBPIM --- p.35 / Chapter 3.5 --- Simulation results --- p.33 / Chapter 3.6 --- Discussions --- p.46 / Chapter 3.7 --- Future work --- p.47 / Chapter 4 --- The Quasi-static DBPIM Algorithm --- p.50 / Chapter 4.1 --- Introduction --- p.50 / Chapter 4.2 --- Quasi-static path scheduling principle --- p.51 / Chapter 4.3 --- Quasi-static DBPIM algorithm --- p.56 / Chapter 4.4 --- An example of Quasi-static DBPIM --- p.59 / Chapter 5 --- Conclusion --- p.63 / Bibliography --- p.65
|
107 |
Numerical algorithms for the mathematics of informationMendoza-Smith, Rodrigo January 2017 (has links)
This thesis presents a series of algorithmic innovations in Combinatorial Compressed Sensing and Persistent Homology. The unifying strategy across these contributions is in translating structural patterns in the underlying data into specific algorithmic designs in order to achieve: better guarantees in computational complexity, the ability to operate on more complex data, highly efficient parallelisations, or any combination of these.
|
108 |
Hybrid parallel algorithms for solving nonlinear Schrödinger equation / Hibridni paralelni algoritmi za rešavanje nelinearne Šredingerove jednačineLončar Vladimir 17 October 2017 (has links)
<p>Numerical methods and algorithms for solving of partial differential equations, especially parallel algorithms, are an important research topic, given the very broad applicability range in all areas of science. Rapid advances of computer technology open up new possibilities for development of faster algorithms and numerical simulations of higher resolution. This is achieved through paralleliza-tion at different levels that practically all current computers support.</p><p>In this thesis we develop parallel algorithms for solving one kind of partial differential equations known as nonlinear Schrödinger equation (NLSE) with a convolution integral kernel. Equations of this type arise in many fields of physics such as nonlinear optics, plasma physics and physics of ultracold atoms, as well as economics and quantitative finance. We focus on a special type of NLSE, the dipolar Gross-Pitaevskii equation (GPE), which characterizes the behavior of ultracold atoms in the state of Bose-Einstein condensation.</p><p>We present novel parallel algorithms for numerically solving GPE for a wide range of modern parallel computing platforms, from shared memory systems and dedicated hardware accelerators in the form of graphics processing units (GPUs), to heterogeneous computer clusters. For shared memory systems, we provide an algorithm and implementation targeting multi-core processors us-ing OpenMP. We also extend the algorithm to GPUs using CUDA toolkit and combine the OpenMP and CUDA approaches into a hybrid, heterogeneous al-gorithm that is capable of utilizing all available resources on a single computer. Given the inherent memory limitation a single computer has, we develop a distributed memory algorithm based on Message Passing Interface (MPI) and previous shared memory approaches. To maximize the performance of hybrid implementations, we optimize the parameters governing the distribution of data and workload using a genetic algorithm. Visualization of the increased volume of output data, enabled by the efficiency of newly developed algorithms, represents a challenge in itself. To address this, we integrate the implementations with the state-of-the-art visualization tool (VisIt), and use it to study two use-cases which demonstrate how the developed programs can be applied to simulate real-world systems.</p> / <p>Numerički metodi i algoritmi za rešavanje parcijalnih diferencijalnih jednačina, naročito paralelni algoritmi, predstavljaju izuzetno značajnu oblast istraživanja, uzimajući u obzir veoma široku primenljivost u svim oblastima nauke. Veliki napredak informacione tehnologije otvara nove mogućnosti za razvoj bržih al-goritama i numeričkih simulacija visoke rezolucije. Ovo se ostvaruje kroz para-lelizaciju na različitim nivoima koju poseduju praktično svi moderni računari. U ovoj tezi razvijeni su paralelni algoritmi za rešavanje jedne vrste parcijalnih diferencijalnih jednačina poznate kao nelinearna Šredingerova jednačina sa inte-gralnim konvolucionim kernelom. Jednačine ovog tipa se javljaju u raznim oblas-tima fizike poput nelinearne optike, fizike plazme i fizike ultrahladnih atoma, kao i u ekonomiji i kvantitativnim finansijama. Teza se bavi posebnim oblikom nelinearne Šredingerove jednačine, Gros-Pitaevski jednačinom sa dipol-dipol in-terakcionim članom, koja karakteriše ponašanje ultrahladnih atoma u stanju Boze-Ajnštajn kondenzacije.<br />U tezi su predstavljeni novi paralelni algoritmi za numeričko rešavanje Gros-Pitaevski jednačine za širok spektar modernih računarskih platformi, od sis-tema sa deljenom memorijom i specijalizovanih hardverskih akceleratora u ob-liku grafičkih procesora, do heterogenih računarskih klastera. Za sisteme sa deljenom memorijom, razvijen je algoritam i implementacija namenjena više-jezgarnim centralnim procesorima korišćenjem OpenMP tehnologije. Ovaj al-goritam je proširen tako da radi i u okruženju grafičkih procesora korišćenjem CUDA alata, a takođe je razvijen i predstavljen hibridni, heterogeni algoritam koji kombinuje OpenMP i CUDA pristupe i koji je u stanju da iskoristi sve raspoložive resurse jednog računara.<br />Imajući u vidu inherentna ograničenja raspoložive memorije koju pojedinačan računar poseduje, razvijen je i algoritam za sisteme sa distribuiranom memorijom zasnovan na Message Passing Interface tehnologiji i prethodnim algoritmima za sisteme sa deljenom memorijom. Da bi se maksimalizovale performanse razvijenih hibridnih implementacija, parametri koji određuju raspodelu podataka i računskog opterećenja su optimizovani korišćenjem genetskog algoritma. Poseban izazov je vizualizacija povećane količine izlaznih podataka, koji nastaju kao rezultat efikasnosti novorazvijenih algoritama. Ovo je u tezi rešeno kroz inte-graciju implementacija sa najsavremenijim alatom za vizualizaciju (VisIt), što je omogućilo proučavanje dva primera koji pokazuju kako razvijeni programi mogu da se iskoriste za simulacije realnih sistema.</p>
|
109 |
Interaktivní zpracování objemových dat / Interactive Processing of Volumetric DataKolomazník, Jan January 2018 (has links)
Title: Interactive Processing of Volumetric Data Author: Jan Kolomazník Department: Department of Software and Computer Science Education Supervisor: RNDr. Josef Pelikán, Department of Software and Computer Science Education Abstract: Interactive visualization and segmentation of volumetric data are quite lim- ited due to the increased complexity of the task and size of the input data in comparison to two-dimensional processing. A special interactive segmentation workflow is presented, based on minimal graph-cut search. The overall execution time was lowered by implementing all the computational steps on GPU, which required a design of massively parallel algorithms (using thousands of threads). To lower the computational burden even further the graph is constructed over the image subregions com- puted by parallel watershed transformation. As a suitable formalism for a range of massively parallel algorithms was chosen cellular automata. A set of cellular automata extensions was defined, which allows efficient mapping and computation on GPU. Several variants of parallel watershed transformation are then defined in the form of cellular automaton. A novel form of 2D transfer function was presented, to improve direct volume visualization of the input data, suited for discriminating image features by their shape and...
|
110 |
Métaheuristiques hybrides distribuées et massivement parallèles / Hybrid metaheuristics distributed and massively parallelAbdelkafi, Omar 07 November 2016 (has links)
De nombreux problèmes d'optimisation propres à différents secteurs industriels et académiques (énergie, chimie, transport, etc.) nécessitent de concevoir des méthodes de plus en plus efficaces pour les résoudre. Afin de répondre à ces besoins, l'objectif de cette thèse est de développer une bibliothèque composée de plusieurs métaheuristiques hybrides distribuées et massivement parallèles. Dans un premier temps, nous avons étudié le problème du voyageur de commerce et sa résolution par la méthode colonie de fourmis afin de mettre en place les techniques d'hybridation et de parallélisation. Ensuite, deux autres problèmes d'optimisation ont été traités, à savoir, le problème d'affectation quadratique (QAP) et le problème de la résolution structurale des zéolithes (ZSP). Pour le QAP, plusieurs variantes basées sur une recherche taboue itérative avec des diversifications adaptatives ont été proposées. Le but de ces propositions est d'étudier l'impact de : l'échange des données, des stratégies de diversification et des méthodes de coopération. Notre meilleure variante est comparée à six des meilleurs travaux de la littérature. En ce qui concerne le ZSP, deux nouvelles formulations de la fonction objective sont proposées pour évaluer le potentiel des structures zéolitiques trouvées. Ces formulations sont basées sur le principe de pénalisation et de récompense. Deux algorithmes génétiques hybrides et parallèles sont proposés pour générer des structures zéolitiques stables. Nos algorithmes ont généré actuellement six topologies stables, parmi lesquelles trois ne sont pas répertoriées sur le site Web du SC-IZA ou dans l'Atlas of Prospective Zeolite Structures. / Many optimization problems specific to different industrial and academic sectors (energy, chemicals, transportation, etc.) require the development of more effective methods in resolving. To meet these needs, the aim of this thesis is to develop a library of several hybrid metaheuristics distributed and massively parallel. First, we studied the traveling salesman problem and its resolution by the ant colony method to establish hybridization and parallelization techniques. Two other optimization problems have been dealt, which are, the quadratic assignment problem (QAP) and the zeolite structure problem (ZSP). For the QAP, several variants based on an iterative tabu search with adaptive diversification have been proposed. The aim of these proposals is to study the impact of: the data exchange, the diversification strategies and the methods of cooperation. Our best variant is compared with six from the leading works of the literature. For the ZSP two new formulations of the objective function are proposed to evaluate the potential of the zeolites structures founded. These formulations are based on reward and penalty evaluation. Two hybrid and parallel genetic algorithms are proposed to generate stable zeolites structures. Our algorithms have now generated six stable topologies, three of them are not listed in the SC-JZA website or in the Atlas of Prospective Zeolite Structures.
|
Page generated in 0.1046 seconds