4 ms·

As I understand it, the conjugate gradient method works over the reals.

• stephencanon 14y ago
  Conjugate Gradient works over the reals if the matrix is symmetric positive definite.
  • jmount 14y ago
    Which 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 ago
        True. 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]