Dear all, When looking at trac ticket #7730 (which essentially ends with saying that GCD computations over multivariate polynomial rings are slow), I noticed that the current implementation of multiplication in fraction fields computes the product (a/b) * (c/d) by first computing a*c and b*d, and then dividing out common factors (in the case of exact underlying rings).
I am wondering whether there is a good reason for doing this. Typically, assuming that (or even on the spot enforcing that!) a/b and c/d are in lowest terms, it would be much faster to compute GCD(a,d) and GCD(c,b) and to then divide out appropriately. If all elements involved are of "size" n, say, this way all operations take inputs of size at most n, as opposed to 2n as in the current implementation. To illustrate the usefulness... In the particular example from #7730, this would allow a computation to happen essentially instantly, whereas at the moment it takes close to 5 hours. I am not saying that 5 hours is a reasonable time for Singular to take for the "large" GCD computation or that this shouldn't be improved. However, improving the fraction field implementation to this effect would basically help anyone working with fraction fields whose underlying rings have an expensive GCD (in the sense of "depending on the input size") right away. Unless I am missing an important point for why this approach shouldn't be followed here, I am happy to work on the patch in the next few days, but before writing any code, I'd like to make sure that I understand the idea behind reduction in fraction fields (in the current implementation) properly. Is it just - If the ring is exact, automatically reduce all the time, unless explicitly specified (with reduce=False) otherwise; - If the ring is inexact, never reduce unless the method "reduce" is called explicitly? Kind regards, Sebastian -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
