mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2010-10-23, 03:45   #1
WraithX
 
WraithX's Avatar
 
Mar 2006

23×59 Posts
Default 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.
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:
http://news.slashdot.org/story/10/10...ar-SDD-Systems

The actual article from Carnegie Mellon University here:
http://www.cmu.edu/news/archive/2010...lgorithm.shtml

Or a pdf of the paper here:
http://www.cs.cmu.edu/~glmiller/Publ...ching-2010.pdf
WraithX is offline   Reply With Quote
Old 2010-10-23, 05:27   #2
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·599 Posts
Default

Quote:
Originally Posted by WraithX View Post
You can find the Slashdot post here:
http://news.slashdot.org/story/10/10...ar-SDD-Systems
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.
cheesehead is offline   Reply With Quote
Old 2010-10-23, 21:27   #3
Random Poster
 
Random Poster's Avatar
 
Dec 2008

24×11 Posts
Default

Quote:
Originally Posted by WraithX View Post
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.
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.
Random Poster is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Solving systems of equations modulo n carpetpool carpetpool 2 2017-02-05 20:40
SIQS - problem with solving linear algebra Dome Factoring 14 2015-03-06 17:59
New Method for Solving Linear Systems Dubslow Miscellaneous Math 24 2012-08-24 10:46
Solving linear systems modulo n drido Math 3 2008-02-08 15:06
Mathematica question-solving systems Zeta-Flux Math 6 2005-09-22 21:47

All times are UTC. The time now is 16:23.

Thu Nov 26 16:23:05 UTC 2020 up 77 days, 13:34, 5 users, load averages: 2.16, 1.73, 1.62

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.