New Method for Solving Linear Systems
 

only_human [URL="http://www.mersenneforum.org/showthread.php?p=308539#post308539"]pointed us[/URL] to [URL="http://rjlipton.wordpress.com/2012/08/09/a-new-way-to-solve-linear-equations/"]this[/URL], 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[sup]3[/sup]) for a roughly-square m x n matrix.

How does this compare to Lanczos and Wiedemann? One of the comments pointed to Wiedemann's [URL="http://www.csd.uwo.ca/~moreno/CS424/Ressources/WIEDEMANN-IEEE-1986.pdf"]original paper[/URL], where he suggests that his class of algorithms can solve linear systems in O(n) complexity.
[quote=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.[/quote]

The reason I'm even asking then, is because of the particular efficiency of the new algorithm in F[sub]2[/sub], 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(n[sup]3[/sup]) 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... :unsure: ...so where am I wrong?

[tangent]
w = ρn for factoring purposes (where ρ is density, usually fairly constant), so (BL and) BW are O(n[SUP]2[/SUP]), not O(n), really.
In practice, BL time seems to be exactly O(n[SUP]2[/SUP])

There are other applications for very sparse matrices, for them it would be a different story.
[/tangent]

[SIZE=1]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![/SIZE]
[SIZE=1][/SIZE]
[SIZE=1]EDIT2: cleaned up the data and added another few thousand. In each #threads class the trend is a clear 2.0[/SIZE]

[QUOTE=Batalov;308708][tangent]

w = ρn for factoring purposes (where [FONT=Calibri][FONT=Calibri][SIZE=3][FONT=Verdana][SIZE=2]ρ[/SIZE][/FONT] is density[/SIZE][/FONT][/FONT]), so (BL and) BW are O(n[SUP]2[/SUP]), not O(n), really.

There are other applications for very sparse matrices, for them it would be a different story.

[/tangent][/QUOTE]

You make a fair point... I think it really is w = ρn[sup]2[/sup], simply because ρ should be a ratio of w/total coeffs, and the later is n^2, so w = w = ρn[sup]2[/sup]. 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(n[sup]3[/sup]), 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).

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...

[QUOTE=c10ck3r;308721]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...[/QUOTE]

Can you do it for a system with 250,000 variables and equations? And that's just a simple C99 :devil:

No, but I can factor out 2's and 5's!!
:bow::dnftt:

[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]

[QUOTE=flashjh;308724][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][/QUOTE]

[url]http://www.ee.ryerson.ca/~elf/abacus/feynman.html[/url]

[QUOTE=bsquared;308725][URL]http://www.ee.ryerson.ca/~elf/abacus/feynman.html[/URL][/QUOTE]
Nice...

[QUOTE=flashjh;308724][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][/QUOTE]

[url]http://en.wikipedia.org/wiki/Daniel_Tammet[/url]

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

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...