mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2012-08-20, 23:13   #1
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·2,399 Posts
Default 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?
Dubslow is offline   Reply With Quote
Old 2012-08-20, 23:32   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100011101010002 Posts
Default

[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
Batalov is offline   Reply With Quote
Old 2012-08-21, 00:27   #3
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·2,399 Posts
Default

Quote:
Originally Posted by Batalov View Post
[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
Dubslow is offline   Reply With Quote
Old 2012-08-21, 01:22   #4
c10ck3r
 
c10ck3r's Avatar
 
Aug 2010
Kansas

547 Posts
Default

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
c10ck3r is offline   Reply With Quote
Old 2012-08-21, 01:33   #5
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×2,399 Posts
Default

Quote:
Originally Posted by c10ck3r View Post
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
Dubslow is offline   Reply With Quote
Old 2012-08-21, 01:43   #6
c10ck3r
 
c10ck3r's Avatar
 
Aug 2010
Kansas

547 Posts
Default

No, but I can factor out 2's and 5's!!
c10ck3r is offline   Reply With Quote
Old 2012-08-21, 01:45   #7
flashjh
 
flashjh's Avatar
 
"Jerry"
Nov 2011
Vancouver, WA

1,123 Posts
Default

[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]
flashjh is offline   Reply With Quote
Old 2012-08-21, 01:48   #8
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2×17×97 Posts
Default

Quote:
Originally Posted by flashjh View Post
[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
bsquared is offline   Reply With Quote
Old 2012-08-21, 01:54   #9
flashjh
 
flashjh's Avatar
 
"Jerry"
Nov 2011
Vancouver, WA

1,123 Posts
Default

Quote:
Originally Posted by bsquared View Post
Nice...
flashjh is offline   Reply With Quote
Old 2012-08-21, 02:22   #10
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

719710 Posts
Default

Quote:
Originally Posted by flashjh View Post
[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.
Dubslow is offline   Reply With Quote
Old 2012-08-21, 05:19   #11
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

100010101011002 Posts
Default

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

All times are UTC. The time now is 02:30.

Fri Oct 30 02:30:58 UTC 2020 up 49 days, 23:41, 1 user, load averages: 2.46, 2.45, 2.35

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.