Combinatorial Scientific Computing
Combinatorial algorithms are an important enabling technology for scientific computing, especially for large-scale problems and high performance computing. The overarching goals of this project are development of 1) a mathematical and computational infrastructure for solving graph and hypergraph-based combinatorial problems on extreme-scale architectures and 2) techniques and tools for analysis of complex and multivalent interaction networks.
In this project, effective novel combinatorial models, such as hypergraph, k-partite hypergraph and directed hypergraph models, are developed for modeling complex workflows (computation, communication and data dependencies, and data access patterns) of large-scale scientific applications and the complicated interactions of chemical and biological entities. New scalable algorithms, based on a multi-level framework, are designed for graph and hypergraph clustering and partitioning, and dynamic load balancing problems. Scalable graph coloring techniques and graph search-based analysis techniques for semantic graphs are developed on top of an extensible distributed memory graph/hypergraph runtime middleware.
Project Researchers
Umit Catalyurek, Ph.D.
Doruk Bozdag
Timothy Hartley
Project Funding Participation
CAREER: Scalable Combinatorial Scientific Computing
SciDAC Institute: Combinatorial Scientific Computing and Petascale Simulations
Massive-Scale Semantic Graphs
Project Publications
Publications |
Umit V. Catalyurek, Erik G. Boman, K. Devine, Doruk Bozdag, R. Heaphy, Lee Ann Riesen, "Hypergraph-based Dynamic Load Balancing for Adaptive Scientific Computations", Proceedings of 21st IEEE International Parallel & Distributed Processing Symposium (IPDPS 07), 2007: pp. 68. |
S. Krishnamoorthy, Umit V. Catalyurek, J. Nieplocha, A. Rountev, P. Sadayappan, "Hypergraph Partitioning for Automatic Memory Hierarchy Management", Proceedings of the 2006 ACM/IEEE conference on Supercomputing (SC2006), 2006: pp. 34. |
Duygu Ucar, Sitaram Asur, Umit V. Catalyurek, Srini Parthasarathy, "Improving Functional Modularity in Protein-Protein Interactions Graphs Using Hub-induced Subgraphs", Knowledge Discovery in Databases: PKDD 2006, 2006: pp. 371-382. |
K. Devine, Erik G. Boman, R. Heaphy, R. Bisseling, Umit V. Catalyurek, "Parallel Hypergraph Partitioning for Scientific Computing", Proceedings of 20th International Parallel and Distributed Processing Symposium (IPDPS), 2006: pp. 10. |
Andy Yoo, Edmond Chow, Keith Henderson, William McLendon, Bruce Hendrickson, Umit V. Catalyurek, "A Scalable Distributed Parallel Breadth-First Search Algorithm on BlueGene/L", Proceedings of the International Conference for High Performance Computing, Networking, and Storage (SC05), 2005: pp. 25. |
Doruk Bozdag, Umit V. Catalyurek, Assefaw H. Gebremedhin, Fredrik Manne, Erik G. Boman, Fusun Ozguner, "A Parallel Distance-2 Graph Coloring Algorithm for Distributed Memory Computers", Proceedings of the 2005 International Conference on High Performance Computing and Communications (HPCC-05), 2005. |
Erik G. Boman, Doruk Bozdag, Umit V. Catalyurek, Assefaw H. Gebremedhin, Fredrik Manne, "An Efficient Parallel Graph Coloring Algorithm for Distributed Memory Computers", 2005: pp. 241-250. |
Doruk Bozdag, Fusun Ozguner, Eylem Ekici, Umit V. Catalyurek, "A Task Duplication Based Scheduling Algorithm Using Partial Schedules", Proceedings of the 2005 International Conference on Parallel Processing (ICPP-05), 2005: pp. 630-637. |
Cevdet Aykanat, Ali Pinar, Umit V. Catalyurek, "Permuting Sparse Rectangular Matrices into Block-Diagonal Form", SIAM Journal on Scientific Computing, 2004: pp. 1860-1879. |
Umit V. Catalyurek, Cevdet Aykanat, "A Hypergraph-Partitioning Approach for Coarse-Grain Decomposition", Proceedings of the ACM/IEEE SC2001 Conference (SC'01), 2001: pp. 42. |
Umit V. Catalyurek, Cevdet Aykanat, "A Fine-Grain Hypergraph Model for 2D Decomposition of Sparse Matrices", Proceedings of International Parallel and Distributed Processing Symposium (IPDPS), 8th International Workshop on Solving Irregularly structured Problems in Parallel (Irregular 2001), 2001: pp. 1199-1204. |
Chialin Chang, Tahsin M. Kurc, Alan Sussman, Umit V. Catalyurek, Joel H. Saltz, "A Hypergraph-Based Workload Partitioning Strategy for Parallel Data Aggregation", Proceedings of the Tenth SIAM Conference on Parallel Processing for Scientific Computing, 2001. |
Umit V. Catalyurek, Cevdet Aykanat, "Hypergraph-Partitioning-Based Decomposition for Parallel Sparse-Matrix Vector Multiplication", IEEE Transactions on Parallel and Distributed Systems, 1999: pp. 673-693. |
Tech Reports |
Timothy DR Hartley, Umit V. Catalyurek, Fusun Ozguner, Andy Yoo, S. Kohn, Keith Henderson, "MSSG: A Framework for Massive Scale Semantic Graphs", Issued: 2006-09-28 |