Fraction fields (multiplication, in particular)
Sebastian Pancratz
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
John Cremona
instead of setting (a/b) * (c/d) = (a*c//g)/(b*d//g) where
g=gcd(a*c,b*d) you instead use the same formula with
g=gcd(a,d)*gcd(b,c). That seems very sensible to me.
I don't know about the policy regarding reduction on creation of
elements: does anyone? Although my instinct would be do do that, I
can see that there are situations in which it better to wait and
reduce later. This is an issue which must have been considered by a
lot of other CA systems in the past!
At present we cannot rely on the input to + being reduced, since they
might have been created with reduce=False; in which case the value
returned by + (after using your idea) would not be reduced either --
is there any harm in that?
It would be possible for every element to keep a "reduced" boolean
flag which is set to False unless the element has been reduced. then,
when a reduced representative is required, it would save checking (by
doing a gcd computation) when that would be redundant. Surely that
would not be expensive to implement?
Also, we could have each FractionField (i.e. the parent of a
FractionFieldElement) have a "reduction policy" flag which specifies
whether or not elements of that field should be reduced on creation;
this could still be overridden in teh constructor for elements, but
instead of the defaul in FractionFieldElement.__init__() being
reduce=True it could be (say) reduce=None, and then (if None) the
constructor would test the parent's policy and use that.
John
2010/1/5 Sebastian Pancratz <sa...@pancratz.org>:
> --
> To post to this group, send an email to sage-...@googlegroups.com
> To unsubscribe from this group, send an email to sage-devel+...@googlegroups.com
> For more options, visit this group at http://groups.google.com/group/sage-devel
> URL: http://www.sagemath.org
>
Burcin Erocal
On Tue, 5 Jan 2010 04:10:08 -0800 (PST)
Sebastian Pancratz <sa...@pancratz.org> wrote:
> 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.
I believe the reason is that no one implemented anything else.
When I read the paragraph above, I couldn't believe we still used naive
multiplication, especially since I implemented the Henrici
multiplication ages ago. Apparently, I never submitted the patch,
waiting to include other improvements with it indefinitely.
I found my old patch, which had a modification date of "Wed Apr 09
09:24:45 2008", and rebased it to 4.3. The new version is here:
http://sage.math.washington.edu/home/burcin/henrici_mul.patch
It probably needs more work to add more doctests, etc.
Note that you can also do a similar trick for derivatives. It would be
great if you implemented that as well.
Can you handle the rest of the submission & review process? I am very
busy with thesis related work these days.
Thank you.
Cheers,
Burcin
Martin Rubey
> 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.
At least FriCAS does precisely that, so you cannot be completely wrong
:-)
Martin
Sebastian Pancratz
> At present we cannot rely on the input to + being reduced, since they
> might have been created with reduce=False; in which case the value
> returned by + (after using your idea) would not be reduced either --
> is there any harm in that?
Well, as long as the behaviour is clearly documented, I think if a
user chooses to supply a non-reduced element, there shouldn't be any
harm in returning an element which isn't completely reduced. However,
there are two possible problems. Firstly, if GCD computations are
prohibitively expensive, the simple attempt to reduce something as
part of the computation might cause problems. (Note that this is the
case in the current implementation.) Secondly, one might prefer to
return completely non-reduced output in the case of non-reduced
input. Even if GCD computations are feasible, without introducing
flags, we would have to actually compute the GCDs in order to check
whether the input is reduced, introducing unnecessary overhead.
> It would be possible for every element to keep a "reduced" boolean
> flag which is set to False unless the element has been reduced. then,
> when a reduced representative is required, it would save checking (by
> doing a gcd computation) when that would be redundant. Surely that
> would not be expensive to implement?
>
> Also, we could have each FractionField (i.e. the parent of a
> FractionFieldElement) have a "reduction policy" flag which specifies
> whether or not elements of that field should be reduced on creation;
> this could still be overridden in teh constructor for elements, but
> instead of the defaul in FractionFieldElement.__init__() being
> reduce=True it could be (say) reduce=None, and then (if None) the
> constructor would test the parent's policy and use that.
It is at least possible to think of cases where elements cannot
feasibly be reduced at all, that is, when for computing (a/b)*(c/d)
even computing GCD(a,d) and GCD(c,b) instead of GCD(ac,bd) does not
help, however, in such cases the current implementation would be
equally bad.
In this case, having a flag (per element) as you suggest would help.
In fact, I think the two points one should ideally take into account
are the user's choice of reduction and the availability of a GCD
routine. (It wouldn't be enough to work over a Euclidean domain
rather than a principal ideal domain. It's about actually being able
to compute GCDs in reasonable time.) Then, rather than carrying flags
and handling exceptions everywhere, it would be nice to have separate
classes of fraction fields so that this information would all be
available at the time when the fraction field is created. However, if
this is possible in the current framework at all, it sounds like a big
project rather than a small update.
For the purpose of making this a small and easy update, I think it
would be nice to not introduce new flags, provided one can get away
with it. I think the following policy might be OK:
- For exact rings with a GCD implementation, all user-callable
methods other than initialization (and perhaps suitable private helper
methods) should assume that the input is reduced and always return
reduced results. If the input is not reduced, the output should still
be mathematically correct, but might not be in reduced form.
- For exact rings without a GCD implementation, no assumptions are
placed on the input and no reduction takes place.
- For inexact rings, no assumptions are placed on the input and no
reduction takes place.
Does this seem reasonable?
Kind regards,
Sebastian
Sebastian Pancratz
Thank you for the link.
I should have some time in the next couple of days to look at this.
Assuming there are no major unexpected complications --- I wouldn't
want to start an involved process of completely rewriting something
like quotient fields here --- I'll hopefully have enough time to start
& finish this.
Sebastian
On Jan 5, 12:57 pm, Burcin Erocal <bur...@erocal.org> wrote:
> Hi Sebastian,
>
> On Tue, 5 Jan 2010 04:10:08 -0800 (PST)
>
John Cremona
This sounds reasonable to me.
There are lots of related issues we will want to consider at some
point (such as the representation of elements of Q(x) where begin
reduced is not at all the whole story!) but I'm in favour of
implementing the relatively small change you are proposing now an
leaving those for another day.
It seems that Burcin's patch would b a good start for what you are
proposing (and it goes further -- I had never heard of henrici!)
John
Martin Rubey
Sorry, I should have looked closer. FriCAS uses what I just learned to
be called ALgorithm by Brown and Henrici,
Please excuse.
Martin
Sebastian Pancratz
Thank you for the details.
Sebastian
On Jan 5, 4:55 pm, Martin Rubey <martin.ru...@math.uni-hannover.de>
wrote:
> Martin Rubey <martin.ru...@math.uni-hannover.de> writes:
> > Sebastian Pancratz <s...@pancratz.org> writes:
>
> >> 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.
>
> > At least FriCAS does precisely that, so you cannot be completely wrong
> > :-)
>
> Sorry, I should have looked closer. FriCAS uses what I just learned to
> be called ALgorithm by Brown and Henrici,
>
> http://delivery.acm.org/10.1145/810000/804903/p108-horowitz.pdf?key1=...
>
> Please excuse.
>
> Martin
Sebastian Pancratz
I've now attached a patch for this to track ticket #7857. This
includes using the Henrici (or Henrici--Brown) algorithms for the
arithmetic operations +, -, *, and /, as well as for computing the
(univariate) derivative in the case where applicable. If someone
could please review this, that would be great.
Sebastian
On Jan 5, 12:57 pm, Burcin Erocal <bur...@erocal.org> wrote:
> Hi Sebastian,
>
> On Tue, 5 Jan 2010 04:10:08 -0800 (PST)
>
Robert Bradshaw
> For the purpose of making this a small and easy update, I think it
> would be nice to not introduce new flags, provided one can get away
> with it. I think the following policy might be OK:
>
> - For exact rings with a GCD implementation, all user-callable
> methods other than initialization (and perhaps suitable private helper
> methods) should assume that the input is reduced and always return
> reduced results. If the input is not reduced, the output should still
> be mathematically correct, but might not be in reduced form.
> - For exact rings without a GCD implementation, no assumptions are
> placed on the input and no reduction takes place.
> - For inexact rings, no assumptions are placed on the input and no
> reduction takes place.
>
> Does this seem reasonable?
Sounds reasonable to me.
Another ticket that touches a lot of the same code is http://trac.sagemath.org/sage_trac/ticket/7585
I'll try and rebase that on top of what you have in #7857.
As for avoiding reduction, I would either make it a property of the
Parent. Another (not necessarily exclusive) option would be to use
Python contexts, i.e.
F.<x> = Frac(QQ['x'])
with F.reduce(False):
print x/x
Printing x/x.
- Robert