mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Math (https://www.mersenneforum.org/forumdisplay.php?f=8)
-   -   Solving linear systems faster than ever... (https://www.mersenneforum.org/showthread.php?t=14084)

 WraithX 2010-10-23 03:45

Solving linear systems faster than ever...

I just saw a posting on Slashdot about how some researchers have found a way to speedup solving linear SDD systems. Here's a small excerpt:
[QUOTE]The result is a significant decrease in computer run times. The Gaussian elimination algorithm runs in time proportional to s^3, where s is the size of the SDD system as measured by the number of terms in the system, even when s is not much bigger than the number of variables. The new algorithm, by comparison, has a run time of s*[log(s)]^2. That means, if s = 1 million, that the new algorithm run time would be about a billion times faster than Gaussian elimination.[/QUOTE]
I wasn't sure if this applied to anyone writing matrix solvers for NFS or QS, but thought I'd mention it to see if it could help anyone.

You can find the Slashdot post here:
[url]http://news.slashdot.org/story/10/10/22/1236215/Astonishing-Speedup-In-Solving-Linear-SDD-Systems[/url]

The actual article from Carnegie Mellon University here:
[url]http://www.cmu.edu/news/archive/2010/October/oct21_speedyalgorithm.shtml[/url]

Or a pdf of the paper here:
[url]http://www.cs.cmu.edu/~glmiller/Publications/Papers/KoutisApproaching-2010.pdf[/url]

[QUOTE=WraithX;234171]You can find the Slashdot post here:
[URL]http://news.slashdot.org/story/10/10/22/1236215/Astonishing-Speedup-In-Solving-Linear-SDD-Systems[/URL]
[/QUOTE]Be sure to read through the Slashdot comments, which point out that the comparison to Gaussian elimination speed is misleading because several other asymptotically faster methods already apply to SDD systems. So the speedup, _if the method proves practical_, would be from (much less than s^3) to s*[log(s)]^2.

 Random Poster 2010-10-23 21:27

[QUOTE=WraithX;234171]I wasn't sure if this applied to anyone writing matrix solvers for NFS or QS, but thought I'd mention it to see if it could help anyone.[/QUOTE]
The kind of matrix this new algorithm accepts and the kind of matrix produced by NFS and QS are so completely different that it's very unlikely it will be of any use in factoring.

 All times are UTC. The time now is 22:15.