Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

First improvement of fundamental algorithm in 10 years

web.mit.edu

Post reply on HN
Print view View original

31–40 of 42 posts

Re: First improvement of fundamental algorithm in 10 years

#31

Post by CountHackulus »

kenjackson wrote: post #28
jongraehl wrote: post #16

It's an approximate algorithm (nothing wrong with that). I'm confused at how they claim O(m^{4/3}) (m is the number of edges) when even initializing an explicit n by n matrix is O(n^2), unless they assume that the graph isn't sparse (m>=k*n^1.5). Or perhaps the matrix is sparsely represented.

On page 11 of the paper I reference above Spielman makes the following statement: "The most obvious way that sparsification can accelerate the solution of linear equations is by replacing the problem of solving systems in dense matrices by the problem of solving systems in sparse matrices. Recall that the Conjugate Gradient, used as a direct solver, can solve systems in n-dimensional matrices with m non-zero entries…

A 1-approximation is an approximation within a factor of 1. Basically that means that the solution is nearly exact. A 2-approximation would be no more than twice as bad as the optimal solution, and an n-aproximation would be no more than n times as bad as the optimal solution.

This is a common thing to use in randomized or approximate algorithms. For example, solving min-cut by assigning to 2 sets randomly is provably a 2-approximation.

Re: First improvement of fundamental algorithm in 10 years

#32

Post by Confusion »

danger wrote: post #7
superjared wrote: post #3

Earlier quoted context omitted.

Kelner is set to give a talk about it tomorrow[1]. Anyone know if they create videos for these? [1]: http://www.csail.mit.edu/events/eventcalendar/calendar.php?s...

The method sounds very interesting, but the title seems to overstate the work a bit. This is an approximation algorithm, meaning that it's an improvement on an _approximate_variant_of_ a fundamental problem, right?

Is there necessarily a difference? Some fundamental problems, including such simple things as the physical 3-body problem, don't have analytical solutions. That doesn't mean that approximate solutions solve an approximate problem. Algorithms can be designed to give an approximation to the optimal solution of the problem, which is known to be achievable only through ultimately numerical methods.

I don't know whether that is the case here: it is possible that they solve a different problem from the fundamental problem. However, even in that case: if the transformations made to turn the fundamental problem into a more tractable problem are generally applicable, then is there really a difference between solving the fundamental problem and solving the transformed problem?

Re: First improvement of fundamental algorithm in 10 years

#33

Post by Maro »

mds wrote: post #9

Their "represent it as a matrix" approach reminded me of this Richard Feynman story: [...] Richard had completed his analysis of the behavior of the router, and much to our surprise and amusement, he presented his answer in the form of a set of partial differential equations. To a physicist this may seem natural, but to a computer designer, treating a set of boolean circuits as a continuous, differentiable system is…

Great story. I'm a physicist and I've read most of the Feynman stuff, including many of his papers, but I wasn't aware he worked at Thinking Machines Corp.

I submitted it as a stand-along link:

http://news.ycombinator.com/item?id=1732952

Re: First improvement of fundamental algorithm in 10 years

#34

Post by jakozaur »

jedbrown wrote: post #23
Groxx wrote: post #8

Very little info, but I'd argue that the parallel qualities of the new algorithm are at least of similar importance to the improvement in complexity. Old speed: (N + L)^(3/2) New speed: (N + L)^(4/3). (n=nodes, l=links) > For a network like the Internet, which has hundreds of billions of nodes, the new algorithm could solve the max-flow problem hundreds of times faster than its predecessor. Granted, it's massively us…

throw the sucker at a video card, and watch it finish thousands of times faster on cheaper hardware This is nonsense even for dense operations. But this matrix is sparse, in which case GPUs are within a modest factor (2-5 or so depending on the matrix, whether you use multiple cores on the CPU, and whether you ask NVidia or Intel). And if the algorithm does not expose a lot of concurrency (as with most multiplicative…

The right answer is in the middle. Of course speed up depends on what are you comparing, but if you benchmark GPU against decent four core CPU the speed up is in order of magnitude.

For dense Matrix currently is about eight times (http://forums.nvidia.com/index.php?showtopic=172176) on CUDA 3.1. That is before the CUDA 3.2 which claim 50-300% performance increase.

For sparse matrix the speed up against multi core CPU is about ten times (http://forums.nvidia.com/index.php?showtopic=83825).

All available as a public libraries (http://developer.nvidia.com/object/cuda_3_2_toolkit_rc.html).

jedbrown, please provide a source of your estimates. Of course I'm interested in some highly optimized libraries like BLAS. Hand written code would be on both systems several times slower.

Re: First improvement of fundamental algorithm in 10 years

#35

Post by jedbrown »

jakozaur wrote: post #34
jedbrown wrote: post #23

Earlier quoted context omitted.

throw the sucker at a video card, and watch it finish thousands of times faster on cheaper hardware This is nonsense even for dense operations. But this matrix is sparse, in which case GPUs are within a modest factor (2-5 or so depending on the matrix, whether you use multiple cores on the CPU, and whether you ask NVidia or Intel). And if the algorithm does not expose a lot of concurrency (as with most multiplicative…

The right answer is in the middle. Of course speed up depends on what are you comparing, but if you benchmark GPU against decent four core CPU the speed up is in order of magnitude. For dense Matrix currently is about eight times ( http://forums.nvidia.com/index.php?showtopic=172176 ) on CUDA 3.1. That is before the CUDA 3.2 which claim 50-300% performance increase. For sparse matrix the speed up against multi core C…

"On the limits of GPU Acceleration" (short summary from Richard Vuduc): http://vuduc.org/pubs/vuduc2010-hotpar-cpu-v-gpu.pdf

"Understanding the design trade-offs among current multicore systems for numerical computations" (somewhat more technical): http://dx.doi.org/10.1109/IPDPS.2009.5161055

"Debunking the 100X GPU vs. CPU myth: an evaluation of throughput computing on CPU and GPU" (from Intel, but using the best published GPU implementations): http://doi.acm.org/10.1145/1815961.1816021

BTW, you may as well cite CUSP (http://code.google.com/p/cusp-library/) for the sparse implementation, it's not part of CUDA despite being developed by Nathan Bell and Michael Garland (NVidia employees).

Re: First improvement of fundamental algorithm in 10 years

#37

Post by adw »

cageface wrote: post #14
T_S_ wrote: post #2

The article refers to the max flow problem. About all this article does is imply that the new method involves the adjacency matrix of the graph and provides little else in the way of details. A better article is needed, not this oversimplified press release.

Adjacency matrices are taught in undergraduate linear algebra classes. This article makes it sound like they invented them.

They're taught in secondary schools in Scotland. (Or at least they were when I did CSYS Maths (Pure), now Advanced Higher...)

Re: First improvement of fundamental algorithm in 10 years

#38

Post by wingo »

jedbrown wrote: post #35
jakozaur wrote: post #34

Earlier quoted context omitted.

The right answer is in the middle. Of course speed up depends on what are you comparing, but if you benchmark GPU against decent four core CPU the speed up is in order of magnitude. For dense Matrix currently is about eight times ( http://forums.nvidia.com/index.php?showtopic=172176 ) on CUDA 3.1. That is before the CUDA 3.2 which claim 50-300% performance increase. For sparse matrix the speed up against multi core C…

"On the limits of GPU Acceleration" (short summary from Richard Vuduc): http://vuduc.org/pubs/vuduc2010-hotpar-cpu-v-gpu.pdf "Understanding the design trade-offs among current multicore systems for numerical computations" (somewhat more technical): http://dx.doi.org/10.1109/IPDPS.2009.5161055 "Debunking the 100X GPU vs. CPU myth: an evaluation of throughput computing on CPU and GPU" (from Intel, but using the best pu…

Really great comment, thank you.

Re: First improvement of fundamental algorithm in 10 years

#40

Post by JosefK »

CountHackulus wrote: post #31
kenjackson wrote: post #28

Earlier quoted context omitted.

On page 11 of the paper I reference above Spielman makes the following statement: "The most obvious way that sparsification can accelerate the solution of linear equations is by replacing the problem of solving systems in dense matrices by the problem of solving systems in sparse matrices. Recall that the Conjugate Gradient, used as a direct solver, can solve systems in n-dimensional matrices with m non-zero entries…

A 1-approximation is an approximation within a factor of 1. Basically that means that the solution is nearly exact. A 2-approximation would be no more than twice as bad as the optimal solution, and an n-aproximation would be no more than n times as bad as the optimal solution. This is a common thing to use in randomized or approximate algorithms. For example, solving min-cut by assigning to 2 sets randomly is provabl…

I believe you mean Max-Cut can be 2 approximated with the trivial random algorithm. Min cut can be solved exactly, and that algorithm would give an expected n^2 approx factor (for min cut).
Post reply on HN