Show/Hide Menu
Hide/Show Apps
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Communities & Collections
Communities & Collections
Help
Help
Frequently Asked Questions
Frequently Asked Questions
Guides
Guides
Thesis submission
Thesis submission
MS without thesis term project submission
MS without thesis term project submission
Publication submission with DOI
Publication submission with DOI
Publication submission
Publication submission
Supporting Information
Supporting Information
General Information
General Information
Copyright, Embargo and License
Copyright, Embargo and License
Contact us
Contact us
Parallel bio-inspired single source shortest path algorithms
Date
2017
Author
Arslan, Hilal
Metadata
Show full item record
Item Usage Stats
100
views
0
downloads
Cite This
Real-world shortest path problems that usually dynamically change are challeng- ing and computationally expensive, and earlier studies in the literature require pro- hibitively long time to obtain the solution. To cope with such problems, we introduce novel bio-inspired parallel algorithms based on Physarum Solver. The first proposed algorithm is a fast and efficient parallel Physarum Solver with the objective to find the shortest path for static graphs with positive edge weights. Next, we propose a novel fully-dynamic bio-inspired parallel algorithm in order to find the shortest path on dynamically changing graphs with positive edge weights. The proposed dynamic algorithm efficiently computes the shortest path when the edge weights of the graph increases, decreases, or both over time. The proposed algorithms include various improvements and optimizations for Physarum Solver. We parallelize the sequential Physarum Solver proposed by Tero, Kobayashi and Nakagaki in 2006. Furthermore, Physarum Solver requires the solution of linear systems whose coefficient matrix is a symmetric M-matrix and we note that this step is the most time consuming step. In the literature, however, there are not any studies that take an advantage of M-matrix property of the coefficient matrix to solve the linear systems efficiently in Physarum Solver and they are often solved by using a direct method, which is infeasible for large scale problems. We efficiently solve such linear systems using a parallel it- erative solver with a preconditioner based on M-matrix property of the coefficient matrix. Finally, we propose a novel hybrid algorithm in order to compute the shortest path exactly since Physarum Solver is not guaranteed to find the exact shortest path. This underlines the accuracy of the hybrid method to compute the shortest path ex- actly. In the hybrid algorithm, Physarum Solver is used in order to detect the edges which cannot form the shortest path tree. The algorithm, first, sparsifies a given graph by removing the edges which cannot form the shortest path tree and then we apply a classical shortest path algorithm, such as Dijkstra, or Breadth First Search (if the graph is unweighted) on the sparser graph with positive edge weights. The proposed method is, therefore, a two stage hybrid algorithm. The accuracy and the required solution time by the proposed hybrid method are compared against a state-of-the-art implementation of the Dijkstra’s algorithm on the original graph as the baseline. The results show that the proposed hybrid method achieves a significant speed improve- ment compared to the baseline. In order to evaluate the parallel algorithms, we use three different large graph models representing diverse real life applications. The par- allel scalability, running time and accuracy of the proposed algorithms are presented and compared against ∆-stepping which is the most representative parallel implemen- tation of Dijkstra’s algorithm. The proposed algorithms exhibit remarkable parallel speedup with comparable accuracy for sparse large graphs. This underlines the effec- tiveness of the proposed algorithm to deal with hard real-life problems requiring long running time using classical algorithms.
Subject Keywords
Algorithms.
,
Symmetric matrices.
,
Matrices.
URI
http://etd.lib.metu.edu.tr/upload/12621864/index.pdf
https://hdl.handle.net/11511/27080
Collections
Graduate School of Natural and Applied Sciences, Thesis
Suggestions
OpenMETU
Core
Parallel sparse and banded matrix – multiple vectors multiplication
Cincioğlu, Meftun; Manguoğlu, Murat; Department of Computer Engineering (2014)
In this thesis, performance of two important primitives, namely sparse and banded matrix – multiple vectors multiplication are studied. Sparse matrix – multiple vectors multiplication (SpMM) is one of the basic and most time consuming operations in many problems in science and engineering. Hence, any improvement in the performance of SpMM operations has a great impact on the wide spectrum of problems. One of the objectives of this thesis is to improve the performance of parallel SpMM operation by reducing i...
Parallel Minimum Norm Solution of Sparse Block Diagonal Column Overlapped Underdetermined Systems
Torun, F. Sukru; Manguoğlu, Murat; Aykanat, Cevdet (2017-03-01)
Underdetermined systems of equations in which the minimum norm solution needs to be computed arise in many applications, such as geophysics, signal processing, and biomedical engineering. In this article, we introduce a new parallel algorithm for obtaining the minimum 2-norm solution of an underdetermined system of equations. The proposed algorithm is based on the Balance scheme, which was originally developed for the parallel solution of banded linear systems. The proposed scheme assumes a generalized band...
Domain adaptation on graphs by learning aligned graph bases
Pilancı, Mehmet; Vural, Elif; Department of Electrical and Electronics Engineering (2018)
In this thesis, the domain adaptation problem is studied and a method for domain adaptation on graphs is proposed. Given sufficiently many observations of the label function on a source graph, we study the problem of transferring the label information from the source graph to a target graph for estimating the target label function. Our assumption about the relation between the two domains is that the frequency content of the label function, regarded as a graph signal, has similar characteristics over the so...
PARALLEL MULTILEVEL FAST MULTIPOLE ALGORITHM FOR COMPLEX PLASMONIC METAMATERIAL STRUCTURES
Ergül, Özgür Salih (2013-11-09)
A parallel implementation of the multilevel fast multipole algorithm (MLFMA) is developed for fast and accurate solutions of electromagnetics problems involving complex plasmonic metamaterial structures. Composite objects that consist of multiple penetrable regions, such as dielectric, lossy, and plasmonic parts, are formulated rigorously with surface integral equations and solved iteratively via MLFMA. Using the hierarchical strategy for the parallelization, the developed implementation is capable of simul...
Pareto Front Particle Swarm Optimizer for Discrete Time-Cost Trade-Off Problem
Aminbakhsh, Saman; Sönmez, Rifat (2017-01-01)
Intensive heuristic and metaheuristic research efforts have focused on the Pareto front optimization of discrete time-cost trade-off problem (DTCTP). However, very little success has been achieved in solving the problem for medium and large-scale projects. This paper presents a new particle swarm optimization method to achieve an advancement in the Pareto front optimization of medium and large-scale construction projects. The proposed Pareto front particle swarm optimizer (PFPSO) is based on a multiobjectiv...
Citation Formats
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
H. Arslan, “Parallel bio-inspired single source shortest path algorithms,” Ph.D. - Doctoral Program, Middle East Technical University, 2017.