Add faster, sparse polynomial GCD implementation

[sritchie]

The code for this lives in the simplify package, in

• [ ] sparse-gcd.scm
• [ ] sparse-interpolate.scm

Candidates:

• [ ] "A Fast Parallel Sparse Polynomial GCD Algorithm" http://www.cecm.sfu.ca/CAG/papers/jscgcd2018.pdf
• [ ] Zippel, "Probabilistic Algorithms for Sparse Polynomials" https://rjlipton.files.wordpress.com/2009/11/zippel.pdf

UPDATE: I started working on this a bit as part of the monster sicmutils/sicmutils#341 effort, then backed off. Here's the code I had started sketching to make this work:

:else clause in GCD dispatch...

(def ^:dynamic *euclid-breakpoint-arity* 3)
(def ^:dynamic *gcd-cut-losses* nil)

(or (with-limited-time [1.0 :seconds]
          (fn [] (sparse-gcd u v)))

      (with-limited-time [1.0 :seconds]
          (fn [] (classical-gcd u v)))

      (with-limited-time [100.0 :seconds]
          (fn [] (sparse-gcd u v)))

      (and (< arity *euclid-breakpoint-arity*)
             (with-limited-time [100.0 :seconds]
               (fn [] (classical-gcd u v))))
      (sparse-gcd u v)

      (if *gcd-cut-losses*
          (or (with-limited-time *gcd-cut-losses*
                  (fn [] (classical-gcd u v)))
              1)
          (classical-gcd u v)))

[littleredcomputer]

I have Zippel; it's very hard to implement (as GJS himself notices, having inferred a simpler version of the algorithm in Scmutils that avoids doing the work in Z_p). I had this going on a branch, but the benchmarking I did revealed no meaningful speedup. The CAG paper looks more interesting (and postdates my last deep foray into this area), so it might be worth a try! Thank you for that pointer.

[littleredcomputer]

I found this on Google Scholar and it looks very promising:

Speeding up polynomial GCD, a crucial operation in Maple

[sritchie]

Wow, that does look really good!