SIAM News Blog

SIAM Workshop on Combinatorial Scientific Computing Inaugurates Proceedings and Best Paper Award

By Erik Boman, Assefaw Gebremedhin, and Sivan Toledo

The 2016 SIAM Workshop on Combinatorial Scientific Computing (CSC16), held this past October in Albuquerque, New Mexico, brought together approximately 70 leading researchers from around the world interested in the interaction of combinatorial (discrete) mathematics and algorithms with computational science and engineering. 

CSC16 follows six previous CSC workshops held roughly biennially since 2004. A new feature of CSC16 is the introduction of a peer-reviewed proceedings, published by SIAM. Past CSC workshops focused on presentation (in the form of talks and posters) and discussion of recent advances in the area, but did not have an associated proceedings. While that format has served the CSC community well, we feel it is time to allow attendees to publish extended abstracts (10 page papers) to facilitate wide and rapid dissemination of top-quality research results in the field. 

In order to integrate the new paper option with the traditional get-together atmosphere of previous workshops (and many other SIAM meetings), CSC16 invited two types of submissions: traditional two-page abstract submissions for oral presentation consideration, and 10-page paper submissions describing original research for both publication and oral presentation consideration. The program committee accepted 11 papers for inclusion in the proceedings and for presentation, and an additional 19 contributions for oral presentation only. 

The CSC16 program also featured three invited talks delivered by Srinivas Aluru (Georgia Institute of Technology), John Gilbert (University of California, Santa Barbara), and Gary Miller (Carnegie Mellon University). The invited talks provided inspiring overviews of three key themes in combinatorial scientific computing. 

In his talk titled "Graphs and Sparse Matrices: There and Back Again," John Gilbert guided workshop attendees through a fascinating set of topics in a link running both ways between graph theory and linear algebra. He highlighted the depth of the mathematical and computational relationship between the two, and discussed how graphs served numerical linear algebra by enabling efficient sparse matrix computations in the first 50 years of this computational relationship; now matrix computations have recently started returning the favor. His speculation on how the relationship will look in the future invited an interesting philosophical discussion with the audience. 

CSC16 Best Paper Award Committee members Sivan Toledo (left) and Alex Pothen (middle) congratulating Fredrik Manne (right) on receiving the award for his paper “On Stable Marriages and Greedy Matchings,” co-authored with Md. Naim, Haakon Lerring, and Mahantesh Halappanavar.
The subject of Gary Miller’s talk was the powerful role of spectral graph theory in creating exciting new algorithms for longstanding and challenging graph theoretic optimization problems. His talk, entitled "The Revolution in Graph Theoretic Optimization," used several examples to drive his point home. As a prime example, Miller described a nearly linear time solver for Symmetric Diagonally Dominant (SDD) systems, and explained how a wide range of problems—including image segmentation, solutions of elliptic equations, computation of maximum flow in a graph, and graph sparsification—can all be addressed by SDD solvers.    

Srinivas Aluru focused on applications and spoke on parallel machine learning approaches for reverse engineering genome-scale networks. In particular, he discussed his work on the development of parallel mutual information and Bayesian network-based structural learning methods, which helped overcome the typical scalability bottlenecks of simpler models when handling genome-scale networks.

The contributed papers spanned a wide spectrum of topics, including the following: network analysis algorithms via Laplacian solvers, multithreaded algorithms for triangular solvers, graph partitioning for molecular dynamics applications, approximation algorithms for matching and edge cover problems, partial coloring approaches for preconditioning, graph algorithms and models for Hessian computation via algorithmic differentiation (AD), integer programming for call tree transversal, combinatorial optimization methods for coordinated vehicle routing, and optimization algorithms for pairwise comparisons. 

The paper, “On Stable Marriages and Greedy Matchings," authored by Fredrik Manne, Md. Naim and Haakon Lerring (University of Bergen, Norway) and Mahantesh Halappanavar (Pacific Northwest National Laboratory), was selected as a recipient of the CSC16 Best Paper Award.  

At the workshop dinner on the opening day, attendees had the pleasure of celebrating the 60th birthdays of Alex Pothen and Rob Bisseling, both of whom were recognized for their many contributions to CSC. They also served on the CSC steering committee.

A record of the CSC16 program, including abstracts and slides of talks, pictures from the dinner and other meeting moments, and information on the organization of the meeting is available at the workshop's website. The conference proceedings has just appeared on SIAM’s publication platform.

CSC16 was sponsored by SIAM and hosted by Sandia National Laboratories, in collaboration with the Association for High Speed Computing, in Albuquerque, New Mexico. The next CSC meeting will be held in 2018, and Bergen, Norway is being considered as a possible venue. Stay tuned!

Erik Boman is a scientist in the Scalable Algorithms Department at the Center for Computing Research at Sandia National Laboratories. He served as a co-chair of CSC16. Assefaw Gebremedhin is an assistant professor in the School of Electrical Engineering and Computer Science at Washington State University. He also served as a co-chair of CSC16. Sivan Toledo is a professor in the Blavatnic School of Computer Science at Tel-Aviv University. He served as a member of the program committee and the Best Paper Selection Committee of CSC16.

blog comments powered by Disqus