5 ms·
...over finite fields (http://en.wikipedia.org/wiki/Finite_field_arithmetic http://en.wikipedia.org/wiki/Finite_field_arithmetic) which is cool for many things
by andrewcooke 14y ago
...over finite fields (http://en.wikipedia.org/wiki/Finite_field_arithmetic http://en.wikipedia.org/wiki/Finite_field_arithmetic)
which is cool for many things, but it's probably not what you expected from the title.
tl;dr: filter a collection of random guesses one equation at a time. new trick is expanding the set of guesses as you work through, so you don't need to start with 2^n (if modulo 2) for example.
- ColinWright 14y agoI've edited the title - thanks.
- jps359 14y agoAs I understand it, the conjugate gradient method works over the reals.
- stephencanon 14y agoConjugate Gradient works over the reals if the matrix is symmetric positive definite.
- jmount 14y agoWhich can be arranged. Instead of solving for x in A x = b solve for x in t(A) A x = t(A) b (t() being transpose, and you may not need to explicitly form t(A) A).
- stephencanon 14y ago... which works, but the condition number of AtA is the square of the condition number of A, so convergence may be very slow, or the results may be numerically unusable. You can often work around that with a carefully chosen pre-conditioner, but you're rapidly going down a rabbit hole that takes you away from the extreme simplicity of conjugate-gradient.
- jmount 14y agoTrue. But this is all a rabbit hole. I think the upper comment was trying to point out that real linear algebra already has work from a trial vector methods of solution. So there is some precedent for non-factorization based solutions. But even that detracts that this really does seem to be a new method for finite fields.
- deleted 14y ago[deleted]