Preconference Workshop Is Third in Series on Combinatorial Scientific Computing

May 1, 2007


CSC07 workshop co-chair Alex Pothen (left) with Iain Duff, who discussed multifrontal methods for factorization of sparse matrices, in one of the two invited talks on the program. At a dinner held to celebrate his 60th birthday, Duff was honored for his many contributions to CSC.

A Highlight of the 2007 SIAM Conference on CSE

Assefaw Gebremedhin

Close to a hundred researchers from different parts of the world gathered in Costa Mesa, California, for the SIAM Workshop on Combinatorial Scientific Computing (CSC07), held February 17�19, 2007. For most attendees, the chance to escape the freezing temperatures in their home towns was certainly a delight, but the warmth of the meeting alone, both scientifically and socially, made the trip well worth their while. The meeting, organized in cooperation with the SIAM Activity Groups on Computational Science and Engineering and on Supercomputing, took place immediately preceding the 2007 SIAM Conference on CSE.

CSC07 was the third in a series of international meetings on combinatorial scientific computing. It is fair to view the first, sponsored by SIAM and held in San Francisco in 2004, as the occasion of the "formal" founding of the CSC research community, which historically was rather scattered across several sub-communities. Although the name CSC is fairly recent, the research area, grounded in the enabling role of combinatorial algorithms in CSE, has been active and fruitful for several decades. As problems and data sets increase in size and complexity, this role will continue to grow in importance. The creators of the CSC workshop series envision the meetings as a forum for researchers interested in exploring and defining this opportunity.

Each of the workshops attracted around a hundred participants and featured about twenty-five invited and contributed talks, along with about the same number of posters. Workshop themes have included parallel computing, high-performance algorithms, sparse matrix computation, optimization, automatic differentiation, mesh generation, computational biology, and combinatorial matrix theory. An additional theme at CSC07---combinatorial algorithms in statistical physics---was the subject of an invited talk by Phillip Duxbury of Michigan State University. Unifying the diverse themes is a common set of abstractions that can be expressed in terms of graphs and hypergraphs---a description, in fact, of the hallmark of the CSC research area.

The workshop program featured two invited speakers---Duxbury and Iain Duff (Rutherford Appleton Laboratory and CERFACS). Duff helped set the tone of CSC07 with an entertaining opening talk on multifrontal methods for factorization of sparse matrices, an area in which he has made pioneering contributions in terms of both algorithms and software.

Beginning with a historical survey of multifrontal algorithms for solving large, sparse systems of linear equations, Duff situated the origins of the multifrontal method in the finite element method and the frontal method used by structural engineers; the latter would pre-order the rows and columns of a matrix to reduce its bandwidth, and then treat all elements within the band as non-zero during the factorization. In 1973 (in work published only five years later, in a technical report), Bert Speelpenning proposed that the storage and computational effort required for the sparse factorization could be reduced by working simultaneously with multiple fronts rather than a single front. He suggested performing multiple column eliminations within a front, combining elements as some of their nodes are eliminated, and storing the partially factored fronts until they were ready for further factorization.

Duff and John Reid, in a 1983 paper on the multifrontal method and their MA_27 code, used an assembly tree for organizing the computations on the multiple fronts, stored the intermediate frontal matrices in a stack, and extended the method to symmetric indefinite problems via block two-by-two pivots. Many of these innovations continue to be used in most multifrontal codes available today. In his talk, Duff also described the use of the multifrontal method in solving two more recent problems. The first is limit analysis calculations from geo-technical engineering in which the submatrices corresponding to equality constraints are highly rank-deficient. In the second, a multifrontal method developed for skew-symmetric systems of equations was used as a preconditioner within a Krylov space iterative solver.

In the second invited talk, Phillip Duxbury considered the key role of combina-torial algorithms in statistical physics, emphasizing applications to material science and molecular biology. Duxbury cited numerous concepts highly familiar to the audience, whose expertise is largely in applied mathematics and computer science. On the list were minimum spanning trees, shortest paths, maximum flow in a network, graph searches, and matching algorithms, among others. The role played by these combinatorial concepts in physics, however, was new and fascinating to many. Duxbury didn't fail to point out the impact in the other direction as well: The influence of physics on algorithms and complexity theory, he said, is exemplified by simulated annealing techniques and the study of phase transitions. Clearly, much can be achieved through richer interactions among physicists, mathematicians, and computer scientists. Previous efforts to cultivate such interactions include the Dagstuhl Seminars "Algorithmic Techniques in Physics" held in 1997 and 2001 (http://www.dagstuhl.de/de/program/calendar/semhp/?semnr=01091).

***

The program also featured overviews of two SciDAC (Scientific Discovery through Advanced Computing) centers: TOPS (Towards Optimal Petascale Simulation), presented by Esmond Ng (Lawrence Berkeley National Lab), and ITAPS (Interoperable Technologies for Advanced Petascale Simulations), by Lori Diachin (Lawrence Livermore National Lab). In another overview, Laura Frink (Sandia National Labs) highlighted some of the algorithmic challenges in solving density functional theories for fluids at interfaces in the context of a Sandia project.

Several members of the program committee and a few of the speakers at CSC07 (including the author of this article) are members of a more recently funded
SciDAC project, the "Combinatorial Scientific Computing and Petascale Simula-tions" (CSCAPES) institute, which hopes to contribute to the SciDAC effort by accelerating the development and deployment of fundamental enabling technologies in high-performance computing. The main research areas at CSCAPES are load-balancing in parallel computing, automatic differentiation, and large-scale graph and sparse matrix computation; further information can be found at http://www.cscapes.org.

CSC07 was a major outreach activity for CSCAPES, which provided financial support for ten graduate students and postdoctoral fellows to attend the workshop. The overview talks presented at the workshop were helpful in terms of fostering interactions between CSCAPES and the various SciDAC-affiliated projects.

In a final workshop highlight, Iain Duff was honored for his many contributions to CSC at a dinner celebrating his 60th birthday. Along with dessert, guests were served a slide show from Iain's career, going as far back as his twenties. John Reid, also from Rutherford Appleton Laboratory and a long-time colleague of Iain's, acted as navigator, carefully pointing out who is who in the slides. Several speakers at the dinner expressed their appreciation both for Iain's scientific work and for his warm personality. For his part, Iain encouraged young researchers to probe new boundaries while having fun at the same time; he also reminded them to cherish the friendly spirit of the CSC community.

The talks and posters presented at CSC07 were in general of very high technical quality. In the absence of parallel sessions, participants had the opportunity to attend all presentations. Discussions at the end of talks were frequently followed up, pretty seriously, during coffee breaks and meals. The abstracts of talks and posters presented at the CSC07 workshop as well as pictures taken during the meeting are available at http://www.cscapes.org/csc07/.

The workshop co-chairs were Alex Pothen (Old Dominion University) and Bruce Hendrickson (Sandia National Labs); Erik Boman (Sandia) led the organizational effort. The other members of the program committee were Srinivas Aluru, John Gilbert, Paul Hovland, Ravi Kumar, Fredrik Manne, Esmond Ng, Jean Roman, Jennifer Scott, Daniel Spielman, and Sivan Toledo, representing various labs and universities in the U.S. and Europe. Many in the group, including the co-chairs, contributed to the organization of all three CSC workshops.

CSC07 was supported by the Office of Advanced Computing Research in the Department of Energy, and by the College of Science and Office of Research, Old Dominion University. The next meeting in the series is planned for sometime in 2009. Stay tuned!

Assefaw Gebremedhin is a research scientist in the Computer Science Department and the Center for Computational Sciences at Old Dominion University.


Donate · Contact Us · Site Map · Join SIAM · My Account
Facebook Twitter Youtube linkedin google+