CSC 2007: The SIAM Workshop on Combinatorial Scientific Computing

Combinatorial algorithms play a crucial enabling role in computational science and engineering (CSE), and as problems and data sets increase in size and complexity, this role continues to grow. To provide a forum for researchers interested in the interaction of combinatorial mathematics and algorithms with CSE, the SIAM Workshop on Combinatorial Scientific Computing (CSC07) was organized in Costa Mesa, CA, on Feb 17-19, 2007.The CSC07 workshop preceded the 2007 SIAM Conference on Computational Science and Engineering, and was organized in co-operation with the SIAM Activity Groups on Computational Science and Engineering, and Supercomputing.

CSC07 followed two earlier CSC workshops held in 2004 and 2005. The First SIAM Workshop on Combinatorial Scientific Computing (CSC04) was held at San Francisco in February 2004, and the Second International Workshop on CSC (CSC05) was held at Toulouse, France in June 2005. Each of these workshops was attended by close to a hundred participants, and featured about twenty-five plenary and selected talks on the themes of parallel computing, high-performance algorithms, sparse matrix computations, combinatorial problems in optimization, automatic differentiation, mesh generation, computational biology, and combinatorial matrix theory. The CSC07 Workshop brought together researchers interested in these themes as well as other aspects of combinatorial mathematics and algorithms in scientific computing, broadly interpreted.

SIAM News Article

Program

The list that follows includes invited talks and contributed talks that were presented.

SATURDAY


February 17, 2007


Photo Slide Show


8:00-8:45
Registration

8:45-9:00
Welcome


Session I: SPARSE MATRIX COMPUTATIONS
Chair: Alex Pothen (Old Dominion)
9:00-10:00
Recent developments in multifrontal codes (Invited Talk)
Iain Duff (Rutherford Appleton Lab and CERFACS)
10:00-10:30
Inertia revealing preconditioner for optimization
Olaf Schenk (University of Basel)
10:30-11:00
Coffee Break


Session II: PARALLEL COMPUTING
Chair: Fredrik Manne (University of Bergen)
11:00-11:30
The PT-Scotch project
Cedric Chevalier (LaBRI and INRIA Futurs)
11:30-12:00
Fine-grain parallel sparse matrix distribution
Erik Boman (Sandia National Lab)
12:00-1:30
Lunch


Session III: PARTITIONING and ORDERING
Chair: Sivan Toledo (Tel Aviv)
1:30-2:15
TOPS: Towards optimal petascale simulations (SciDAC Talk)
Esmond Ng (Lawrence Berkeley Lab)
2:15-2:45
Remapping models via hypergraph partitioning
Berkant Barla Cambazoglu (Ohio State)
2:45-3:15
Hypergraphs for run-time reordering
Michelle Strout (Colorado State)
3:15-3:45
Minimal fill elimination ordering
Barry Peyton (Dalton State College)
3:45-4:00
Coffee Break

4:00-5:30
Poster Session

7:00 P.M.
CSC07 Dinner

SUNDAY


February 18, 2007




Session IV: STATISTICAL PHYSICS and AUTOMATIC DIFFERENTIATION
Chair: Bruce Hendrickson (Sandia National Lab)
9:00-10:00
Combinatorial algorithms and statistical physics (Invited Talk)
Phil Duxbury (Michigan State)
10:00-10:30
Sparse Hessians using AD
Assefaw Gebremedhin (Old Dominion)
10:30-11:00
Coffee Break


Session V: AUTOMATIC DIFFERENTIATION and OPTIMIZATION I
Chair: Paul Hovland (Argonne)
11:00-11:30
Jacobian accumulation is NP-complete
Uwe Naumann (RWTH Aachen University)
11:30-12:00
Local Jacobian pre-accumulation
Jean Utke (Argonne)
12:00-1:30
Lunch


Session VI: AUTOMATIC DIFFERENTIATION and OPTIMIZATION II
Chair: Esmond Ng (Lawrence Berkeley Lab)
1:30-2:15
ITAPS: Interoperable technologies for advanced petascale simulations (SciDAC Talk)
Lori Diachin (Livermore National Lab)
2:15-2:45
Pattern graphs for sparse matrices
Shahdat Hossain (University of Lethbridge)
2:45-3:15
Exploiting symmetry for Hessian computation
Sanjukta Bhowmick (Columbia and Argonne)
3:15-4:00
Algorithmic challenges in solving density functional theories for fluids at interfaces (Application Talk)
Laura Frink (Sandia National Lab)
4:00-4:30
Coffee Break

4:30-5:30
Business Meeting
Bruce Hendrickson (Sandia National Lab)
6:00-8:00
CSE Welcome Reception

MONDAY


February 19, 2007



8:30-9:15
CSE Invited Talk
9:15-9:45
Coffee Break


Session VII: FINITE ELEMENTS, PRECONDITIONING, and MULTILEVEL ALGORITHMS
Chair: Daniel Spielman (Yale)
9:45-10:15
Support graph preconditioners for 2-D trusses
Samuel Daitch (Yale)
10:15-10:45
Linear work parallel algorithm for planar Laplacians
Ioannis Koutis (Carnegie Mellon)
10:45-11:15
Combinatorial structure in finite element operators
Robert Kirby (Texas Tech)
11:15-11:45
Multilevel approaches for proteomic networks
Sang-Cheol Seok (Iowa)
11:45-12:00
CSC07 Closing
Erik Boman (Sandia National Lab)

Posters

Title Authors
Combinatorial Optimization of Matrix-Vector Multiplication Wolf
Using Perturbed QR Factorizations to Solve Linear Least-Squares Problems Avron, Ng, & Toledo
Combinatorial Preconditioners for Scalar Finite Elements Avron, Shklarski, & Toledo
Evolution of a Coarse Grid Selection Algorithm Alber & Olson
Hierarchical Coloring Hovland
Exploiting Algebraic Dependences Between Local Partial
Derivatives in Jacobian Accumulation
Lyons
A Discrete Optimization Problem Arising in Finite Element Computation Knepley, Leyffer, & Kirby
Combinatorial Preconditioners for Scalar Finite-Elements Problems Avron, Shklarski, & Toledo
Large-scale Polytope Diameter Experiments using the CBE Processor: Towards a Resolution to Hirsch's Conjecture Koranne & Kulkarni
The CSCAPES Institute The CSCAPES team
Derivative Accumulation on Compressed Row Storage of Extended Jacobians  Varnik & Naumann
An Algorithm to Find Overlapping Subgraphs of a Graph and Applications to Preconditioning Fritzsche,Frommer, & Szyld
Parallel Iterative Solvers for Ill-Conditioned Problems with Reordering Nakajima
Fast Approximation Algorithms for Bipartite Vertex-Weighted Matching Dobrian, Halappanavar, & Pothen