Home

This wiki documents the current development status of this codebase.

This codebase is an alpha prototype of an implementation of the streaming spectral sparsification algorithm of Kyng et. al. At the moment, the code is developed and documented well enough for research collaborators to use. It is not ready for general release, however.

Current features/progress

Currently, the codebase supports:

• reading in an input graph as a matrix market file, and computing a (non-streaming) spectral sparsifier.

• incomplete correctness testing and performance experiments

Complete functionality

The complete version of the codebase will include:

• full streaming spectral sparsification from a matrix market file (including sublinear memory cost)

• support for more input formats

• complete correctness testing and performance benchmarking suites

• sample uses of spectral sparsification on several large-scale scientific analysis tasks.

Next development tasks

There remain a small number of tasks to complete to finish the implementation. They are as follows:

• diagnose and fix high RAM use during static sparsification.
• switch on "streaming mode" (automatically trigger sparsification whenever edge threshold is reached) and test performance.
• Improve throughput via:
  • Trying GPU-accelerated version of linear solver
  • Further optimizing JL sketch multiplication code