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