mersenneforum.org New Method for Solving Linear Systems
 Register FAQ Search Today's Posts Mark Forums Read

2012-08-20, 23:13   #1
Dubslow

"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(n3) for a roughly-square 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:
 Originally Posted by Wiedemann THIS ARTICLE presents a random method of solving a nondegenerate linear system in n equations and n unknowns over a finite field in O(nw) field operations, where w is the total number of nonzero coefficients in all the equations.
The reason I'm even asking then, is because of the particular efficiency of the new algorithm in F2, and in particular, AFAICT, the algorithm does not require any multiplications, working mod 2 as NFS does. Additionally, solving for the nullspace makes b = 0, means that checking if a vector satisfies a constraint is trivial. Adding base-2 vectors is also trivial, meaning that the O(n3) is with trivial operations. Perhaps the only non-trivial part is performing the set union, unless you just keep the duplicates anyways.

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?

 2012-08-20, 23:32 #2 Batalov     "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(n2), not O(n), really. In practice, BL time seems to be exactly O(n2) 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 2012-08-21 at 00:57
2012-08-21, 00:27   #3
Dubslow

"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts

Quote:
 Originally Posted by Batalov [tangent] w = ρn for factoring purposes (where ρ is density), so (BL and) BW are O(n2), not O(n), really. There are other applications for very sparse matrices, for them it would be a different story. [/tangent]
You make a fair point... I think it really is w = ρn2, simply because ρ should be a ratio of w/total coeffs, and the later is n^2, so w = w = ρn2. There isn't anything about a NFS relation that would cause the density of non-zeros to increase relative to the area of the matrix for different areas.

Then BL and BW are O(n3), 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 2012-08-21 at 00:33

 2012-08-21, 01:22 #4 c10ck3r     Aug 2010 Kansas 10001000112 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 double-check (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 2012-08-21 at 01:22 Reason: Ps
2012-08-21, 01:33   #5
Dubslow

"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·29·83 Posts

Quote:
 Originally Posted by c10ck3r 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 double-check (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...
Can you do it for a system with 250,000 variables and equations? And that's just a simple C99

 2012-08-21, 01:43 #6 c10ck3r     Aug 2010 Kansas 547 Posts No, but I can factor out 2's and 5's!!
 2012-08-21, 01:45 #7 flashjh     "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]
2012-08-21, 01:48   #8
bsquared

"Ben"
Feb 2007

25×3×5×7 Posts

Quote:
 Originally Posted by flashjh [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]
http://www.ee.ryerson.ca/~elf/abacus/feynman.html

2012-08-21, 01:54   #9
flashjh

"Jerry"
Nov 2011
Vancouver, WA

1,123 Posts

Quote:
 Originally Posted by bsquared http://www.ee.ryerson.ca/~elf/abacus/feynman.html
Nice...

2012-08-21, 02:22   #10
Dubslow

"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

11100001101012 Posts

Quote:
 Originally Posted by flashjh [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]
http://en.wikipedia.org/wiki/Daniel_Tammet

The documentary they mention is how I learned of him; it was broadcast on The Science Channel.

 2012-08-21, 05:19 #11 LaurV Romulan Interpreter     Jun 2011 Thailand 100011101010112 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 bi-yearly 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 2012-08-21 at 05:20

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool carpetpool 2 2017-02-05 20:40 Dome Factoring 14 2015-03-06 17:59 WraithX Math 2 2010-10-23 21:27 drido Math 3 2008-02-08 15:06 Zeta-Flux Math 6 2005-09-22 21:47

All times are UTC. The time now is 06:12.

Sat Jan 16 06:12:55 UTC 2021 up 44 days, 2:24, 0 users, load averages: 3.46, 3.18, 2.88