On Friday, 4 November 2016 14:19:26 UTC+1, bluescarni wrote: > > For what it's worth I spent some time earlier this year experimenting with > multivariate poly GCD in piranha (e.g., here's the PSR_SR implementation > https://github.com/bluescarni/piranha/blob/master/src/polynomial.hpp#L197). > It's alpha-quality experimental code which I am about to remove for the > time being from the project, but it does produce correct results in all the > tests I have thrown at it (which incidentally helped finding a GCD bug in > sympy, which I was using as a comparison > https://github.com/sympy/sympy/issues/10996). The main motivation in > implementing the functionality was to have some capability of handling > rational functions. > > Overall it was a pretty frustrating experience. For starters, Piranha uses > a sparse multivariate representation based on hash tables, which are of > course unordered and thus not suitable for operations such as division and > GCD. In order to have a real chance of competitive performance, I need to > implement an alternative ordered representation to switch to when > performing these operations (probably the ordered vector representation > with the Pearce heap multiplication algorithm). >
Yeah, you really need some kind of variable-by-variable (i.e. recursive) representation for some of these algorithms. If you use Ben-Or/Tiwari interpolation or Monagan and Javadi or SooGoo, you probably need the sparse distributed representation though. > > Secondly, despite the abundance of literature on the subject, it was very > hard to understand which algorithm it was worth to attempt implementing, > with performance claims all over the place. In the end I settled on the PSR > and the GCDHEU algorithms, mostly because they were the easiest to > implement. PSR tended to work well most of the time, > It's not really any good if the degree gets too large, especially if you are not working over a field. If you get the variable ordering incorrect, for example, the PSR algorithm will not terminate before the universe dies of heat death, if you try to find the GCD of the two polynomials I gave earlier. > GCDHEU was quite effective for small operands. Still, there were cases in > which, for very specific and innocuous-looking polynomials, the runtime > would be atrocious for one algorithm and reasonable for the other, or > vice-versa. I have no idea on how one would pick a good heuristic to choose > the better algorithm before actually performing the computation. It also > didn't help that many books and papers I consulted provided > "implementations" (using the term very loosely) of the algorithms which to > me, as a non-expert on the topic, were either vague, incomplete or > sometimes (I suspect) seemed outright wrong. > There are many completely incorrect published algorithms for GCD, even in the univariate and integer case. Dan Bernstein has a hilarious rant about this somewhere online. It's tempting to completely ignore literature by people who didn't implement their algorithms and test them on known hard cases and real world examples. But just occasionally, really good ideas turn up in papers by people who don't know how to use a computer, so this isn't a winning strategy. Bill. > > Anyway, sorry for the rantish mode, and good luck :) > > Francesco. > > > > > > On 4 November 2016 at 13:39, 'Bill Hart' via sage-devel < > sage-...@googlegroups.com <javascript:>> wrote: > >> >> >> On Thursday, 3 November 2016 23:42:27 UTC+1, Dima Pasechnik wrote: >>> >>> Are there open-source implementations of this available? >>> >> >> Pari might be a good place to look. Otherwise, I doubt it. If Bernard >> Parisse hasn't done it, it probably doesn't exist. >> >> I remember one of the Maple people getting pretty annoyed back in about >> 2010 that no one in the Sage community seemed to be interested in actually >> doing something about hard problems like multivariate GCD (and by >> extension, factorisation). >> >> Much of the stuff in Factory happened since then, but not much else, as >> far as I'm aware (though I am sure the Pari guys have been slowly improving >> their implementation over the years). Factory was a big improvement over >> what Singular was doing before. But it's such a huge area that it didn't >> make much of a dent. For example, the other day I found two polynomials in >> 4 variables with just 30 terms, which Factory takes a minute to find the >> GCD of. Even Magma takes about 3s! >> >> For what it is worth, I'm currently working on multivariate GCD in Julia, >> and eventually Flint, with a view to eventually doing multivariate >> factoring the right way. >> >> I just got a reasonable, but not world beating, univariate factoring >> algorithm going over Z. Multivariate GCD turns out to be an unbelievably >> hard problem; much, much harder than I gave it credit for. >> >> Anyway, there are people here in Kaiserslautern very interested in both >> multivariate GCD and factoring, so if anyone is interested in this and >> would like to contribute, feel free to contact us. >> >> For use in multivariate GCD over Z, I eventually want to implement Soo >> Go's algorithm [1], and over fields, probably a highly optimised Zippel. >> For more generic GCD I can't find anything better than the subresultant >> pseudoremainder algorithm of Collins. If anyone knows of anything better >> that works fairly generically, please let us know. >> >> In some sense, algorithms for factoring are understood fairly well, but >> there's a lot of infrastructure one needs to implement any of them. What >> Nils has suggested above is correct, though it is obviously still an area >> of active research. >> >> Bill. >> >> the only (somewhat) fast library I know is >>> Singular's factory >>> (https://github.com/Singular/Sources/blob/spielwiese/factory/README) >>> used both in Singular and in Macaulay2... >>> >> >>> Also, if you need to output factors, which might exist only over proper >>> extensions, you would have >>> to build these extensions, no? >>> >>> >>> >>> On Thursday, November 3, 2016 at 7:37:58 PM UTC, Nils Bruin wrote: >>>> >>>> On Thursday, November 3, 2016 at 1:37:25 PM UTC-4, Dima Pasechnik wrote: >>>>> >>>>> >>>>> >>>>> On Thursday, November 3, 2016 at 1:06:05 PM UTC, Bill Hart wrote: >>>>>> >>>>>> >>>>>> >>>>>> On Friday, 28 October 2016 18:44:09 UTC+2, Dima Pasechnik wrote: >>>>>>> >>>>>>> 5 variables and degree 100 is really, really huge. Especially over >>>>>>> QQ, the coefficients of >>>>>>> polynomials will just totally blow. >>>>>>> In fact, 5 variables and degree 10 might still be quite hard, in >>>>>>> particular over QQ or other char. 0 fields. >>>>>>> >>>>>> >>>>>> I disagree with all of the above, especially when the polynomials are >>>>>> randomly generated. >>>>>> >>>>> >>>>> Huh? Algebraic geometers are mostly not interested in random data. >>>>> With probability 1, your random data will define something irreducible. >>>>> While if your data is reducible, you might need to build algebraic >>>>> extensions >>>>> of high degree to factor. I don't see how you can handle extensions of >>>>> degrees that might pop >>>>> out of the data of this format... >>>>> >>>> >>>> It should be easy for exactly the same reason why factoring over ZZ[x] >>>> is fast: you reduce to factoring over GF(p)[x] and if you end up with a >>>> square-free factorization, you lift p-adically. There's a (theoretical?) >>>> issue of factor combination that is solved (theoretically as well as >>>> practically) by LLL >>>> >>>> This works for multivariate factorization just as well: you specialize >>>> variables and lift (repeatedly); you don't eliminate variables. No need to >>>> build algebraic extensions. There are still details you need to check for >>>> and you need to show you have a reasonable chance of not making >>>> unfortunate >>>> choices, but polynomial factorization in general show be pretty efficient. >>>> >>>> -- >> You received this message because you are subscribed to the Google Groups >> "sage-devel" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to sage-devel+...@googlegroups.com <javascript:>. >> To post to this group, send email to sage-...@googlegroups.com >> <javascript:>. >> Visit this group at https://groups.google.com/group/sage-devel. >> For more options, visit https://groups.google.com/d/optout. >> > > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
