Improved physarum polycephalum shortest path algorithm with preconditioned iterative methods

Download
2015
Keskiner, Hamide Hande
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.

Suggestions

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...
Using collaboration diagrams in component oriented modelin
Tuncel, Mehmet Burhan; Doğru, Ali Hikmet; Department of Computer Engineering (2006)
Component Oriented Software Engineering (COSE) seems to be the future of software engineering. Currently, COSEML is the only modeling language that completely supports the COSE approach. Abstract decomposition of the system and their representing components are shown in a hierarchy diagram to support the COSE process model. In COSEML, only static modeling is supported through this single diagram. However, software is about behavior and static modeling is not sufficient to describe the system. The aim of thi...
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...
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)...
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...
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.