New Method for Solving Linear Systems

Dubslow · 2012-08-20, 23:13

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³) 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 F₂, 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³) 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?

Batalov · 2012-08-20, 23:32

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

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

Dubslow · 2012-08-21, 00:27

Quote:

Originally Posted by Batalov

[tangent]

w = ρn for factoring purposes (where ρ is density), so (BL and) BW are O(n²), 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 = ρn², simply because ρ should be a ratio of w/total coeffs, and the later is n^2, so w = w = ρn². 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³), 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).

c10ck3r · 2012-08-21, 01:22

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

Dubslow · 2012-08-21, 01:33

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

c10ck3r · 2012-08-21, 01:43

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

flashjh · 2012-08-21, 01:45

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

bsquared · 2012-08-21, 01:48

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

flashjh · 2012-08-21, 01:54

Quote:

Originally Posted by bsquared

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

Nice...

Dubslow · 2012-08-21, 02:22

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.

LaurV · 2012-08-21, 05:19

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

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(n²), not O(n), really. In practice, BL time seems to be exactly O(n²) 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, 01:22	#4
c10ck3r Aug 2010 Kansas 1000100011₂ 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, 05:19	#11
LaurV Romulan Interpreter Jun 2011 Thailand 10001110101011₂ 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
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
Solving linear systems faster than ever...	WraithX	Math	2	2010-10-23 21:27
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

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]