Graph Based Optimization For Scientific Computing

<p>This work investigates transforming scientific computing problems such as phylogenetic analysis, system simulation into abstract graph problems and developing algorithms for optimization. First, we investigate an efficient algorithm for unequal genome phylogeny reconstruction. Currently few methods can solve the median problem for unequal genomes which is essential in evolution tree and ancestral genome reconstruction. We present a new distance measurement model for unequal genomes and develop a branch-and-bound algorithm based on multiple breakpoint graph to calculate the median for unequal genomes. We also present a mixture method to infer the ancestral gene order based on maximum likelihood approach and adequate graph median solver. The median solver is extremely time consuming under high rearrangement rate compared with maximum likelihood approach but it gives better accuracy. So our mixture method aims to increase both the speed and accuracy for ancestral genome reconstruction. We also investigate the method to improve the simulation problem for large systems. The Modified Nodal Analysis (MNA) simulation method is widely used to solve electrical system networks. It has the disadvantage that the simulation time increases disproportionally with system size. To accelerate the simulation, latency insertion method has been introduced to partition the original system into a number of smaller sub-systems so that computation will be reduced. But so far there is no automatic method to optimally exploit the existing latency in the system. Our work focuses on an algorithm based on graph search to optimally activate the optional latency decouplers in the network. With the optimal activation, the system is partitioned in the way that maximum simulation speed up will be achieved.</p>

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Campus Access Dissertation

Discipline thesis:degree_discipline

Computer Science and Engineering

Year

2012

Author dc:creator

• Zhang, Yiwei

Contributors dc:contributor

• Jijun Tang

• Computer Sciences
• Electrical and Computer Engineering
• Engineering
• Physical Sciences and Mathematics
• graph
• optimization
• phylogeny
• simulation

Statement dc:rights

• © 2012, Yiwei Zhang

Repository record dc:identifier

https://scholarcommons.sc.edu/etd/807

OAI identifier oai:identifier

oai:scholarcommons.sc.edu:etd-1808