20120820, 23:13  #1  
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3·29·83 Posts 
New Method for Solving Linear Systems
only_human pointed us to this, a new method of solving linear systems due to Prasad Raghavendra.
Based on the paper and the comments, it appears to have runtime O(n^{3}) for a roughlysquare m x n matrix. How does this compare to Lanczos and Wiedemann? One of the comments pointed to Wiedemann's original paper, where he suggests that his class of algorithms can solve linear systems in O(n) complexity. Quote:
This all seems too good to be true though, and I'm thinking I've missed something in my thinking, and I'm certainly not an expert by any means... ...so where am I wrong? 

20120820, 23:32  #2 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
9,257 Posts 
[tangent]
w = ρn for factoring purposes (where ρ is density, usually fairly constant), so (BL and) BW are O(n^{2}), not O(n), really. In practice, BL time seems to be exactly O(n^{2}) There are other applications for very sparse matrices, for them it would be a different story. [/tangent] EDIT: I am a practic and too thick (as a brick?) for the theory, but I am trying to parse a few thousand legacy logs; I've done a rough run, but BLanczosTime reported in logs seems to be walltime, so I have to additionally parse all of them for the numbers of threads. Someone will definitely give you a better answer. All eyes on jasonp! EDIT2: cleaned up the data and added another few thousand. In each #threads class the trend is a clear 2.0 Last fiddled with by Batalov on 20120821 at 00:57 
20120821, 00:27  #3  
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3×29×83 Posts 
Quote:
Then BL and BW are O(n^{3}), which puts things on a more competitive basis... still, it seems too good to be true. PS There's some talk in the comments (especially from Terry Tao) about creating a deterministic algorithm, and with less initial starting vectors. Unfortunately, I didn't understand a large part of Tao said (or rather, I can guess what he means, but that's not really good enough). Last fiddled with by Dubslow on 20120821 at 00:33 

20120821, 01:22  #4 
Aug 2010
Kansas
1000100011_{2} Posts 
If y'all are interested in methods of solving linear equations, I guess I can share my method.
The secret is in the simplicity: I stare at the problem until an answer pops into my brain, making no active attempt to solve until I have subconsciously answered it. I then doublecheck (this time actively) to prove my answer correct. I was the fastest in my class, faster than even my Calc teacher (when the aide made the problems). This seems to mimic the phenomenon in which staring at a word search draws one's eyes to a hidden word. P.S. how high of a crank score would this get? Unfortunately, this is my true method... Last fiddled with by c10ck3r on 20120821 at 01:22 Reason: Ps 
20120821, 01:33  #5  
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3·29·83 Posts 
Quote:


20120821, 01:43  #6 
Aug 2010
Kansas
547 Posts 
No, but I can factor out 2's and 5's!!

20120821, 01:45  #7 
"Jerry"
Nov 2011
Vancouver, WA
1,123 Posts 
[digress]
I'm sure he had his limits, but there was a guy in my high school that could solve any square root in his head faster than we could punch it into a calculator. It was amazing because he could give it to as many decimal places as the calculator could display (and he would keep going). I asked him how he did it and he said the numbers just appeared! [/digress] 
20120821, 01:48  #8  
"Ben"
Feb 2007
2^{5}×3×5×7 Posts 
Quote:


20120821, 01:54  #9  
"Jerry"
Nov 2011
Vancouver, WA
1,123 Posts 
Quote:


20120821, 02:22  #10  
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
1110000110101_{2} Posts 
Quote:
The documentary they mention is how I learned of him; it was broadcast on The Science Channel. 

20120821, 05:19  #11 
Romulan Interpreter
Jun 2011
Thailand
10001110101011_{2} Posts 
There are many tricks to do mental math. I am also very fast on it, but not because I am a genius or something, but because I have learned the tricks. I can split big numbers in 2, 3, 5, 6, 9, 11, 15, 17 in seconds, I can multiply any number with 9 or 15 as fast as (or faster then) you can write it down and do it by pencil, using my fingers, and I also can transform numbers with few digits (2, 3, 4, 5, but as the number is bigger is more difficult) from base 10 into base 16 and viceversa. I do this (and also I do multiplication with 15 the same way) in the same style as multiplication with 9, by imagining that I have 16 fingers. You can google for mental math, multiplication with 9, etc, wiki has good articles with links, people have biyearly world championships or so. It was a time when I was always following such events in the news... well, we are all getting older...
Last fiddled with by LaurV on 20120821 at 05:20 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Solving systems of equations modulo n  carpetpool  carpetpool  2  20170205 20:40 
SIQS  problem with solving linear algebra  Dome  Factoring  14  20150306 17:59 
Solving linear systems faster than ever...  WraithX  Math  2  20101023 21:27 
Solving linear systems modulo n  drido  Math  3  20080208 15:06 
Mathematica questionsolving systems  ZetaFlux  Math  6  20050922 21:47 