Re: [math-fun] Raghavendra's algorithm for solving linear systems over finite fields
I can see applications in distributed/parallel implementations. You can do most of the checking & probably a lot of the randomization in parallel. At 09:02 AM 8/15/2012, Warren Smith wrote:
Preliminary draft: http://www.eecs.berkeley.edu/~prasad/linsystems.pdf
--I don't understand why anybody would want to use this algorithm for any purpose. It's slower than everything else I can think of and also randomized i.e. can fail.
However... perhaps it might be useful if changed to be about finite RINGS not fields. In rings, you cannot divide, hence gaussian elimination is not usable. Hence this algorithm then has less competition. (Even then I'm dubious, but then it'd have at least a hope.)
Maybe the algorithm might be useful in sparse systems? Ordinary Gaussian elimination [we should fix the name -- who really discovered this?] generates fill-in, so special methods are already needed for large sparse systems. For larger primes than 2, maybe the sum of P+1 vectors could be replaced with an average of a few vectors. This might also work for non-finite fields, where the chance that a random vector will satisfy a random linear equation is zero: Instead of averaging a few vectors that satisfy the first K-1 equations, choose a random linear combination that also satisfies the Kth equation. More interesting problem: Can this be made to work for non-linear systems? We'd need a way to combine vectors, similar to summing or averaging, that preserves the "solves equations 1...K-1" property. Rich PS: <Crabbing about mathematical notation for supposed clarity.> I read the algorithm from the paper first, and was confused. I found Lipton's description much better. Do subscripts and summation signs really help anything? ---------- Quoting Henry Baker <hbaker1@pipeline.com>:
I can see applications in distributed/parallel implementations. You can do most of the checking & probably a lot of the randomization in parallel.
At 09:02 AM 8/15/2012, Warren Smith wrote:
Preliminary draft: http://www.eecs.berkeley.edu/~prasad/linsystems.pdf
--I don't understand why anybody would want to use this algorithm for any purpose. It's slower than everything else I can think of and also randomized i.e. can fail.
However... perhaps it might be useful if changed to be about finite RINGS not fields. In rings, you cannot divide, hence gaussian elimination is not usable. Hence this algorithm then has less competition. (Even then I'm dubious, but then it'd have at least a hope.)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Just noticed this problem, with one solution given, in an obscure article: << Find a finite subset of the plane such that for any two of its points the perpendicular bisector of the segment connecting them passes through exactly two points of the set.
--Dan
Presumably the finite subset is required to have at least two points; otherwise the condition is vacuously satisfied. (Well, SOMEONE had to say it...) Jim On Thu, Aug 16, 2012 at 2:42 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Just noticed this problem, with one solution given, in an obscure article:
<< Find a finite subset of the plane such that for any two of its points the perpendicular bisector of the segment connecting them passes through exactly two points of the set.
--Dan _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Let H denote the Hilbert space of all square-summable sequences of real numbers. (With the usual inner product <x,y> = Sum_{k=1...oo} x_k y_k, and corresponding norm ||x|| = <x,x>^(½) and metric d(x,y) = ||x-y||.) H is a vector space endowed with the topology determined by its metric. Now define L := {x in H | all but finitely many coordinates x_k are 0, and Sum_{k=1...oo} x_k = 0}. L is clearly a vector subspace of H. PUZZLE: Describe explicitly the closure Cl(L) of L. --Dan
On Thursday 06 September 2012 19:05:53 Dan Asimov wrote:
Let H denote the Hilbert space of all square-summable sequences of real numbers. ... L := {x in H | all but finitely many coordinates x_k are 0, and Sum_{k=1...oo} x_k = 0}. ... PUZZLE: Describe explicitly the closure Cl(L) of L.
... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... It's all of H. Let x be any element of h and for each k define x[k] to agree with x for its first k coordinates, and have the next k coordinates equal, their value chosen to make the sum of the coordinates 0. The remaining (infinity-2k) coordinates are zero. Obviously x[k] is in L. Writing y\k for the result of zeroing the first k coordinates of y, ||x-x[k]|| = ||x\k-x[k]\k|| <= ||x\k|| + ||x[k]\k|| where the first summand obviously -> 0 as k->oo because otherwise x isn't square-summable and the second also -> 0 because it's at most ||x||/sqrt(k). -- g
OK --- here comes Fred sticking his neck out again. I claim Cl(L) = {sequences with sum absolutely convergent to zero} union {square-summable sequences with sum divergent, or only conditionally convergent}. The complement in H of Cl(L) comprises sequences with sum absolutely convergent to some nonzero real. WFL
Dan Asimov wrote:
Find a finite subset of the plane such that for any two of its points the perpendicular bisector of the segment connecting them passes through exactly two points of the set.
To avoid spoilers (and for brevity), I'll give my points as the roots of a polynomial over the complex numbers: z^8 + (6 + 4 Sqrt[3]) z^4 - (7 + 4 Sqrt[3]) = 0. Dan, is this the original solution? Sincerely, Adam P. Goucher http://cp4space.wordpress.com/
Yes, Adam, this is exactly the unique solution (up to similarity) known to date, according to what I read. --Dan On 2012-09-05, at 7:07 AM, Adam P. Goucher wrote:
Dan Asimov wrote:
Find a finite subset of the plane such that for any two of its points the perpendicular bisector of the segment connecting them passes through exactly two points of the set.
To avoid spoilers (and for brevity), I'll give my points as the roots of a polynomial over the complex numbers:
z^8 + (6 + 4 Sqrt[3]) z^4 - (7 + 4 Sqrt[3]) = 0.
Dan, is this the original solution?
On 2012-09-06 01:21, Dan Asimov wrote:
Yes, Adam, this is exactly the unique solution (up to similarity) known to date, according to what I read.
--Dan
On 2012-09-05, at 7:07 AM, Adam P. Goucher wrote:
Dan Asimov wrote:
Find a finite subset of the plane such that for any two of its points the perpendicular bisector of the segment connecting them passes through exactly two points of the set.
To avoid spoilers (and for brevity), I'll give my points as the roots of a polynomial over the complex numbers:
z^8 + (6 + 4 Sqrt[3]) z^4 - (7 + 4 Sqrt[3]) = 0.
Dan, is this the original solution?
A tidy similarity being -7 + 4 Sqrt[3] + (6 - 4 Sqrt[3]) x^4 + x^8 = 0. Dan, how about revealing your "obscure source"? --rwg
participants (8)
-
Adam P. Goucher -
Dan Asimov -
Fred lunnon -
Gareth McCaughan -
Henry Baker -
James Propp -
rcs＠xmission.com -
rwg