# Presentation: 500033

## Combinatorial Scientific Computing:

**The Role of Discrete Algorithms in**
** ****Computational Science & Engineering**
**Bruce Hendrickson**
**Sandia National Labs**

## CS and CS&E

**Compilers, system software, computer architecture, etc.**

**What’s in the intersection?**

## CS and CS&E

** ****Combinatorial Scientific Computing**

**What’s in the intersection?**

## Combinatorial Scientific Computing

**Development, application and analysis of combinatorial algorithms to enable scientific and engineering computations**

- Theory

- Practice

## World’s Apart

**Computer Science =**
**Graph algorithms, set theory, complexity theory, etc.**
**Computational Science & Engineering =**
**Numerical analysis, PDEs, linear algebra, etc.**
**Differ in many ways**
**Vocabulary, concepts and abstractions**
**Culture – mathematics versus engineering**
**Definition of success **
**Aesthetics**
**Not an easy divide to span!**

**Notes:**
Formal proof versus practical improvement

19th Century giants: Gauss, Hilbert, etc.

False dichotomy.  Fails to serve either community well.

## Sparse Direct Methods

**Reorderings for sparse factorizations**
**Powerfully phrased as graph problems**
**Fill reducing orderings**
**Minimum degree (greedy)**
**Nested dissection (divide & conquer)**
**Bandwidth reducing orderings**
**graph traversals, graph eigenvectors**
**Heavy diagonal to reduce pivoting (matching)**
**Efficient exploitation of sparsity**
**Factorization, triangular solves, etc.**

**Notes:**
Genesis of CSC community

## Graphs and sparse Gaussian elimination  (1961-)

## Matrix Reordering: Strongly Connected Components

**         ****Before                                     After**

## Sparse Direct Methods

**Reorderings for sparse factorizations**
**Powerfully phrased as graph problems**
**Fill reducing orderings**
**Minimum degree (greedy)**
**Nested dissection (divide & conquer)**
**Bandwidth reducing orderings**
**graph traversals, graph eigenvectors**
**Heavy diagonal to reduce pivoting (matching)**
**Efficient exploitation of sparsity**
**Factorization, triangular solves, etc.**

**Notes:**
Genesis of CSC community

## Preconditioning

**Incomplete Factorizations**
**Exploiting sparsity patterns, e.g. level-of-fill**
**Orderings**
**Partitioning for domain decomposition**
**Graph techniques in algebraic multigrid**
**Independent sets, matchings, etc.**
**Support Theory**
**Spanning trees & graph embedding techniques**

## Numerical Optimization

**Sparse Jacobian Evaluation**
**Exploit sparsity to minimize function calls**
**Graph coloring on column intersection graph**
**Sparse basis construction**
**Matroids, graph colorings, spanning trees, etc.**
**Hybrid of combinatorics and numerics**

## ParallelizingScientific Computations

- ParallelizingScientific Computations

**Graph Algorithms**
**Partitioning**
**Coloring**
**Independent sets, etc.**
**Geometric algorithms**
**Space-filling curves & octrees for particles**
**Geometric partitioning**
**Reordering for memory locality**

**Notes:**
Parallelization issues are almost entirely combinatorial

## Parallelization Strategies

**Observation: Parallelization is usually orthogonal to numerics**
**Issues are non-numerical**
**Load balancing**
**Communication minimization**
**Scheduling, etc.**
**Almost invariably combinatorial in spirit**

## Mesh Generation

**Geometric algorithms &**
**     ****data structures**
**Delaunay/Voronoi decompositions**
**Convex hulls**
**Intersection checking, etc.**
**Topology of unstructured meshes**
**graph algorithms**

**Notes:**
Glorious amalgam of mathematical ideas applied to real, and important problem.

## More Mesh Generation

**Rich amalgam of mathematical ideas**
**Differential geometry**
**Harmonic mappings & numerical PDEs**
**Optimization to improve mesh quality**

## Computational Biology

**Genomics**
**Fragment assembly**
**Sequence analysis, etc.**
**Lots of string algorithms**
**Proteomics**
**Structural comparisons**
**NMR and Mass Spec analysis**
**Phylogenics**
**Literature mining**
**Microarray clustering & analysis**
**Etc, etc.**

## Statistical Physics

**Ising spin models and percolation theory**
**Pfaffians, permanents & matching**
**Very rich graph theory**
**Several Nobel prizes awarded**
**Other percolation models**
**External fields, Connectivity, Rigidity, etc. **
**Network flow and other graph algorithms**
**Cellular Automata**

## Graphs in Chemisty

**Categorizing molecules by graph properties**
**Various topological invariants, graph properties**
**Used to screen molecules for desired properties**
**Combinatorics of polymers**
**Geometric and graph properties**
**Statistically correct ensembles**
**Graph enumeration and sampling**

**Notes:**
Cayley coined “graph” in this context.

## CS&E Techniques in Computer Science

**Continuous methods in discrete optimization **
**Using matrix eigenvectors to understand graphs**
**Approximation algorithms via linear or quadratic programming **
**Linear algebra in information analysis **
**Latent semantic indexing (SVD for info retrieval)**
**Google’s page ranking (eigenvector & Perron-Frobenius)**
**Kleinberg’s hubs and authorities (SVD)**
**Multilevel combinatorial algorithms **
**Dominant paradigm for practical graph partitioning **
**Being applied to range of combinatorial problems**
**Origins in algebraic multigrid**

## The Future ...

**“****It’s tough to make predictions,**
**  ****especially about the future” **
**                                         ****Yogi Berra**
**Prediction: All of the aforementioned and more.**

## Info Organization, Analysis & Mining

**Graph algorithms and linear algebra**
**Importance ranking of documents/pages**
**Information retrieval**
**Publication mining is key tool in biology**
**Text analysis & inference**
**Simulation output already overwhelming**
**Learning theory**
**Advanced visualization**

## More Biology

**Gene promotion and inhibition**
**Strings and learning theory**
**Multi-atom interactions**
**Protein complexes**
**Regulatory networks**
**Geometry, topology and graphs**
**Biological systems**
**Whole cell modeling**
**Ecological models**
**Topology and graph analysis**

## Fast Algorithms for Huge Problems

**For computer science theorists, key distinction is between polynomial & exponential time**
**For scientific computing, key is often linear versus quadratic time**

## Examples

**Approximate max-weight matching**
**[Monien, Preis, Diekmann], [Drake, Hougardy]**
**Useful for partitioning**
**Exact algorithm *****O(mn)***** time**
**2-approximation in *****O(m)***** time**

**Extreme Case:**
***“******Can we understand anything interesting about our data when we do not even have time to read all of it?”  ******	******	******	******                     - Ronitt Rubinfeld***

## Sublinear Time Algorithms

**Fast Monte Carlo algorithms for finding ****low-rank approximations to a matrix**
**[Frieze, Kannan, Vempala]**
**Find B****0**** such that:**** ||A – B**0**||**F**  ** ** min****B**** ||A - B||****F**** ****+**** ****ε**** ****||A||****F**
**Run-time independent of size of matrix!**
**Approximating weight of MST in sublinear time **
**[Chazelle, Rubinfeld, Trevisani] **
**Key idea: estimate number of connected components in time independent of size of graph**

## Elsewhere at CSE-03...

**MS23/47 Combinatorial Algorithms in Scientific Computing**
**CP8/32 Discrete Algorithms**
**IP4 Computational Proteomics (Mark Gerstein)**
**MS25 Computational Proteomics**
**CP20 Methods for Particle Simulations**
**CP26 Geometric Algorithms**
**MS81 Locality in Scientific Applications**
**Discrete algorithms play a role in numerous individual talks!**

## Hard Questions

**How will combinatorial methods be used by people who don’t understand them in detail?**
**What are the implications ...**
**for teaching?**
**for software development?**
**for journals?**
**for professional societies?**

**Notes:**
CS students should learn about singular vectors.

CS&E students should learn about max-weight spanning trees.

## Morals

**Things are clearer if you look at them from multiple perspectives**
**Combinatorial algorithms are pervasive in scientific computing and will become more so**
**Lots of exciting opportunities**
**High impact for discrete algorithms work**
**Enabling for scientific computing**

**Notes:**
Combinatorialists can profit from
New problems (often special cases of existing ones) 
Eager customers for advances
New algorithmic insights
Scientific computing folks can profit from 
New tools & techniques
 Novel points of view
For individual researchers
Lots of interesting stuff at boundaries between fields
Opportunities for enormous impact
Dialogue is Necessary!
What problem variants are useful? 
Which application formulations are tractable? 
Computer scientist as tool-maker

Sandia’s success in CS&E is partially due to early tolerance of discrete algorithms.  Look at my department.

## Thanks

**Yogi Berra, Erik Boman, Edmond Chow, Karen Devine, Alan Edelman, Jean-Loup Faulon, John Gilbert, Mike Heath, Pat Knupp, Esmond Ng, Ali P****ı****nar, Steve Plimpton, Cindy Phillips, Alex Pothen, Robert Preis, Padma Raghavan, Jonathan Shewchuk, Dan Spielman, Shang-Hua Teng, Sivan Toledo, etc.**

## For More Information

**www.cs.sandia.gov/~bahendr**
**lists.odu.edu/listinfo/csc**
**Sandia is a multiprogram laboratory operated by Sandia Corporation, a Lockheed-Martin Company, for the US DOE under contract DE-AC-94AL85000**