A parallel bio-inspried shortest path algorithm

Date

2019-08-01

Author

arslan, hilal
Manguoğlu, Murat

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

68
views

0
downloads

Physarum polycephalum is an amoeba-like organism and is able to find the shortest path in a labyrinth. Inspired by P. polycephalum, recently, a mathematical model and an algorithm (Physarum Solver) was developed. There are, however, only sequential implementations of this algorithm. In this paper, a fast and efficient parallel Physarum Solver is proposed. The proposed algorithm requires the solution of linear systems whose coefficient matrix is a symmetric M-matrix. The solution of the linear system is the most time consuming step of the Physarum Solver which is classically handled by direct solvers without taking advantage of the fact that the coefficient matrix is an M-matrix. However, direct solvers are infeasible for solving large real-world problems. In the proposed parallel Physarum Solver, an effective parallel iterative linear solver with a parallel preconditioner for M-matrices is used. The parallel scalability, solution time, and accuracy of the proposed algorithm are presented and compared to a state-of-the-art parallel implementation of -stepping shortest path algorithm in the Parallel Boost Graph Library. Our implementation exhibits a remarkable parallel speedup with comparable accuracy for synthetic and real world applications.

Subject Keywords

Theoretical Computer Science, Computational Theory and Mathematics, Software, Numerical Analysis, Computational Mathematics, Computer Science Applications

URI

https://hdl.handle.net/11511/43213

Journal

COMPUTING

DOI

https://doi.org/10.1007/s00607-018-0621-x

Collections

Department of Computer Engineering, Article

Suggestions

OpenMETU
Core

A nested iterative scheme for computation of incompressible flows in long domains Manguoğlu, Murat; Tezduyar, Tayfun E.; Sathe, Sunil (Springer Science and Business Media LLC, 2008-12-01) We present an effective preconditioning technique for solving the nonsymmetric linear systems encountered in computation of incompressible flows in long domains. The application category we focus on is arterial fluid mechanics. These linear systems are solved using a nested iterative scheme with an outer Richardson scheme and an inner iteration that is handled via a Krylov subspace method. Test computations that demonstrate the robustness of our nested scheme are presented.
An Intelligent Inference System for Robot Hand Optimal Grasp Preshaping BAYSAL, CABBAR VEYSEL; Erkmen, Aydan Müşerref (Atlantis Press, 2010-10-01) This paper presents a novel Intelligent Inference System (IIS) for the determination of an optimum preshape for multifingered robot hand grasping, given object under a manipulation task. The IIS is formed as hybrid agent architecture, by the synthesis of object properties, manipulation task characteristics, grasp space partitioning, low-level kinematical analysis, evaluation of contact wrench patterns via fuzzy approximate reasoning and ANN structure for incremental learning. The IIS is implemented in softw...
A Favorable Weight-Based Evolutionary Algorithm for Multiple Criteria Problems SOYLU, Banu; Köksalan, Mustafa Murat (Institute of Electrical and Electronics Engineers (IEEE), 2010-04-01) In this paper, we present a favorable weight-based evolutionary algorithm for multiple criteria problems. The algorithm tries to both approximate the Pareto frontier and evenly distribute the solutions over the frontier. These two goals are common for many multiobjective evolutionary algorithms. To achieve these goals in our algorithm, each member selects its own weights for a weighted Tchebycheff distance function to define its fitness score. The fitness scores favor solutions that are closer to the Pareto...
A temporal neural network model for constructing connectionist expert system knowledge bases Alpaslan, Ferda Nur (Elsevier BV, 1996-04-01) This paper introduces a temporal feedforward neural network model that can be applied to a number of neural network application areas, including connectionist expert systems. The neural network model has a multi-layer structure, i.e. the number of layers is not limited. Also, the model has the flexibility of defining output nodes in any layer. This is especially important for connectionist expert system applications.
A Hopfield neural network with multi-compartmental activation Akhmet, Marat (Springer Science and Business Media LLC, 2018-05-01) The Hopfield network is a form of recurrent artificial neural network. To satisfy demands of artificial neural networks and brain activity, the networks are needed to be modified in different ways. Accordingly, it is the first time that, in our paper, a Hopfield neural network with piecewise constant argument of generalized type and constant delay is considered. To insert both types of the arguments, a multi-compartmental activation function is utilized. For the analysis of the problem, we have applied the ...

Citation Formats

h. arslan and M. Manguoğlu, “A parallel bio-inspried shortest path algorithm,” COMPUTING, pp. 969–988, 2019, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/43213.