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+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.
