Success Stories

Sparse Matrices & Large Graphs

Results: Enables Analysis of TERAbyte-sized Graphs

The Challenge

Large-scale computation on graphs are fundamental to the representation, manipulation, exploration, analysis, and visualization of data and interrelationships in many parts of information retrieval, computational biology, web search, information analytics, and knowledge discovery. Sparse matrix computations allow structured representation of irregular data structures and decompositions, and irregular access patterns in parallel applications.

graph Sparse matrices frequently have dimensions that are in the millions or more, and so many non-zeros that they cannot fit on one workstation. Furthermore, even when the sparse matrices are themselves not too large, the fill-in caused by intermediate operations (e.g., LU factorization) makes it necessary to distribute the factors over several processors.

Star-P Solution

Star-P provides a simple way to express graphs as sparse matrices and provides the infrastructure to manipulate large graphs in the same way as in MATLAB®. Graph algorithm users can use Star-P to explore their graphs, e.g., looking at partitionings or connected components. Analysts can prototype algorithms in Star-P and/or plug in their existing MPI, OpenMP, or UPC libraries into Star-P as a test-bed for creating test cases, exploring the output and comparing with other algorithms. Star-P provides an interactive problem-solving environment for rapid development of graph-theoretic applications, and executes those applications with scalable performance on very large (multi-terabyte) memory systems.

graph
Enlarge Image

Summary & Metrics

  • Explore large graphs using familiar MATLAB® environment
  • Work interactively and explore patterns and connections within enormous data sets
  • Scale to hundreds of processors and multi-terabyte data sets