Simulation and Analysis of Large Scale Complex Systems

Rensselaer Polytechnic Institute, Troy NY

Investigators

Abstract

This project, building a shared computational infrastructure to conduct experimental research in the areas of simulation analysis of large scale complex systems, boosts research in a variety of fields, including bioinformatics, social network analysis, geometrical and combinatorial algorithms, parallel and distributed computation, and the theory of computation. The infrastructure, consisting of a powerful high speed cluster (for intensive and distributed computation) and 64bit machines (for memory intensive computation), services the following projects: Learning for Algorithm Design in Complex Systems, Geometric and Combinatorial Computations on Large Random Objects, Parallel and Distributed Algorithms, and Exploring the Limits of Computation. The first project develops a general learning paradigm for designing efficient algorithms to solve large-scale optimization problems. For the many complex systems where the relevant task leads to combinatorial problems that are computationally intractable, an alternative to find a solution is to learn an algorithm which is efficient for a specific problem of domain interest (in bioinfomatics, DNA assembly and alignment and protein folding, and in social networks, reverse engineering laws observed in society's communication). The second computes geometric properties of a large number of objects such as union of a large number of polygons. Techniques are applicable to VLSI, computational cartography, environmental planning, radio communication of the Moon and Mars as well as on earth, national defense, etc. Using experiments, new algorithms are developed by learning where to search in the combinatorial search space, for finding the maximum number of cliques in a graph (a classical NP-hard optimization problem with applications in cryptography and the study of protein networks with implications in physiology). The third develops and tests algorithms for the parallel simulation of large networks, and for distributed computing on large data sets. Loosely coordinated distributed network simulation and scientific computing on reconfigurable dynamic clusters are used respectively to achieve real-time simulation of large networks at the packet level and to develop a scalable computing system built from autonomous agents. The last, related to issues of computability and solvability, computes the Busy Beaver function, a heuristically productive n-state Turing machine. The infrastructure also impacts education. Rather than the usual small artificial course projects, students will now be able to attack large practical problems. Moreover, the general algorithms will be made public to a wide audience for a wide range of applications.