In October 2010, this paper was presented by the authors.
Approaching optimality for solving SDD systems by Ioannis Koutis, Gary L. Miller, and Richard Peng.
Public reports on that paper can be found at: A Breakthrough in Algorithm Design in the September 2011 issue of CACM and PC Pro in: Algorithm sees massive jump in complex number crunching.
The claim is that the new approach will be a billion times faster than traditional techniques.
In February of 2011, the authors have posted a new and improved version of their algorithm in:
A nearly-mlogn time solver for SDD linear systems.
Koutis has written a MATLAB implementation at: CMG: Combinatorial Multigrid
For further background, see: Combinatorial Preconditioning, sparsification, local clustering, low-stretch trees, etc. by Spielman, one of the principal researchers in this area.
The most obvious application in topic maps would be recommender systems that bring possible merges to a topic map author’s attention or even perform merging on specified conditions. (If the application doesn’t seem obvious, read the post I refer to in: Text Feature Extraction (tf-idf) – Part 1 , again. Will also give you some ideas about scaleable merging tests as well.)
Years ago Lars Marius told me that topic maps needed to scale on laptops to be successful. It looks like algorithms are catching up to meet his requirement.
[…] a follow up to my posting about SDD systems yesterday, I wanted to uncover some more material on the […]
Pingback by SDD Contest! « Another Word For It — September 19, 2011 @ 7:54 pm