Improved physarum polycephalum shortest path algorithm with preconditioned iterative methods

Download

index.pdf

Date

2015

Author

Keskiner, Hamide Hande

Metadata

Show full item record

Item Usage Stats

165
views

55
downloads

Algorithms for finding the shortest path has many applications in Computer Science, or in other areas of science and engineering. Network optimizations, artificial intelligence and robotics are just a few examples where efficient computation of the shortest path is needed. Various algorithms have been proposed to solve this fundamental problem. Physarum Solver is biologically inspired method that deals with this problem. In the end, a sparse linear system needs to be solved at each iteration of the algorithm. Direct and iterative solvers are two main classes of algorithms for solving sparse linear systems. Direct solvers are robust but they could consume a lot memory due to fill-in. In this thesis, Physarum Polycephalum Shortest Path algorithm is improved using preconditioned iterative methods. We study the convergence behavior as well as memory consumption of various solvers and preconditioners. We show that preconditioned iterative solvers are quite robust and requires much less memory and solution time.

Subject Keywords

Computer programming., Computer algorithms., Computer software., Iterative methods (Mathematics).

URI

http://etd.lib.metu.edu.tr/upload/12619436/index.pdf
https://hdl.handle.net/11511/25032

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

Modelling and predicting binding affinity of PCP-like compounds using machine learning methods Erdaş, Özlem; Alpaslan, Ferda Nur; Department of Computer Engineering (2007) Machine learning methods have been promising tools in science and engineering fields. The use of these methods in chemistry and drug design has advanced after 1990s. In this study, molecular electrostatic potential (MEP) surfaces of PCP-like compounds are modelled and visualized in order to extract features which will be used in predicting binding affinity. In modelling, Cartesian coordinates of MEP surface points are mapped onto a spherical self-organizing map. Resulting maps are visualized by using values...
Improved probabilistic decoding of interleaved Reed-Solomon codes and folded Hermitian codes Özbudak, Ferruh (Elsevier BV, 2014-02-06) Probabilistic simultaneous polynomial reconstruction algorithm of Bleichenbacher, Kiayias, and Yung is extended to the polynomials whose degrees are allowed to be distinct. Specifically, for a finite field F, positive integers n, r, t and distinct elements z(1), z(2), ... , z(n) is an element of F, we present a probabilistic algorithm which can recover polynomials p(1), p(2), p(r) is an element of F[x] of degree less than k(1), k(2), ... , k(r) respectively for a given instance < y(i), (1, ... ,) y(i,r)>(n)...
FGPA based cryptography computation platform and the basis conversion in composite finite fields Sial, Muhammad Riaz; Akyıldız, Ersan; Department of Cryptography (2013) In the study of this thesis work we focused on the hardware based cryptographic algorithms computation platform, especially for elliptic-curve and hyper-elliptic curve based protocols. We worked for making the hyperelliptic curve based Tate Pairing computation efficient specially for hardware implementations. To achieve this one needs to make the underlying finite field arithmetic implementations efficient. For this we study the finite fields of type $\mathbb{F}_q, q=p^{2pn}$ from the efficient implementati...
Computational representation of protein sequences for homology detection and classification Oğul, Hasan; Mumcuoğlu, Ünal Erkan; Department of Information Systems (2006) Machine learning techniques have been widely used for classification problems in computational biology. They require that the input must be a collection of fixedlength feature vectors. Since proteins are of varying lengths, there is a need for a means of representing protein sequences by a fixed-number of features. This thesis introduces three novel methods for this purpose: n-peptide compositions with reduced alphabets, pairwise similarity scores by maximal unique matches, and pairwise similarity scores by...
Reinforcement learning using potential field for role assignment in a multi-robot two-team game Fidan, Özgül; Erkmen, İsmet; Department of Electrical and Electronics Engineering (2004) In this work, reinforcement learning algorithms are studied with the help of potential field methods, using robosoccer simulators as test beds. Reinforcement Learning (RL) is a framework for general problem solving where an agent can learn through experience. The soccer game is selected as the problem domain a way of experimenting multi-agent team behaviors because of its popularity and complexity.

Citation Formats

H. H. Keskiner, “Improved physarum polycephalum shortest path algorithm with preconditioned iterative methods,” M.S. - Master of Science, Middle East Technical University, 2015.