Fractions with factored denominators
Nicolas M. Thiery
I am manipulating univariate fractions in A[t] where A is a ring (say
QQ[x1,...,xn]), and all the denominators factor nicely in many small
terms like (1-x1 t) * (1 - 2*x2*t - (x3*x4) t^4) * ... I need to do
ring operations (products, sums, ...), and to have the result reduced
to the form A/B (if possible with A prime to B)
So far, I am working in FractionField(A[t]). However, the expansion of
the denominators give many many terms, and is a computation killer.
Is there currently a way in Sage to define a close variant of
FractionField(QQ[x]), where the numerators would be expanded, but the
denominators would be kept into factored form?
Thanks!
Cheers,
Nicolas
--
Nicolas M. Thiéry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/
Michel
A long time ago I made a FractionFIeld implementation which would
cache factorizations of denominators. instead of taking gcd's all the
time
http://markmail.org/message/7hxox5cbz5knxjse#query:new%20implementation%20of%20fraction%20field+page:1+mid:5bf3l37bsim34m4g+state:results
It is usually much faster than the naive implementation but it is
possible
to make examples where it is slower (see the above thread). That's
why it was rejected.
Regards,
Michek
On Mar 9, 6:05 am, "Nicolas M. Thiery" <Nicolas.Thi...@u-psud.fr>
wrote:
Martin Rubey
> Hi Nicolas,
>
> A long time ago I made a FractionFIeld implementation which would
> cache factorizations of denominators. instead of taking gcd's all the
> time
>
> http://markmail.org/message/7hxox5cbz5knxjse#query:new%20implementation%20of%20fraction%20field+page:1+mid:5bf3l37bsim34m4g+state:results
>
> It is usually much faster than the naive implementation but it is
> possible to make examples where it is slower (see the above
> thread). That's why it was rejected.
Maybe there is a way to make Sage do it as in FriCAS: (please excuse
the ASCII art)
(1) -> a: FRAC FR INT
(2) -> a := 12/25
2
2 3
(2) ---
2
5
Type: Fraction(Factored(Integer))
(3) -> a * 5
2
2 3
(3) ---
5
Type: Fraction(Factored(Integer))
In words:
Fraction is a domain constructor that takes any integral domain and
returns it's field of fractions.
Factored is a domain constructor that takes an integral domain, and
tries to keep its elements in factored form as long as possible.
(and I hurry to add that I'd rather have something like:
Factored is a domain constructor that takes a unique
factorisation domain, and keeps its elements in factored form)
On Mar 9, 6:05 am, "Nicolas M. Thiery" <Nicolas.Thi...@u-psud.fr>
wrote:
> I am manipulating univariate fractions in A[t] where A is a ring (say
> QQ[x1,...,xn]), and all the denominators factor nicely in many small
> terms like (1-x1 t) * (1 - 2*x2*t - (x3*x4) t^4) * ... I need to do
> ring operations (products, sums, ...), and to have the result reduced
> to the form A/B (if possible with A prime to B)
>
> So far, I am working in FractionField(A[t]). However, the expansion of
> the denominators give many many terms, and is a computation killer.
There is also a domain LocalAlgebra, that allows fraction as Nicolas
wants them, but it would need (a tiny little bit of) work, because it
requires that the numerators form an algebra over the denominators,
and it is nowhere stated that Integer has Algebra Factored Integer.
The code is in fricas/src/algebra/fraction.spad.pamphlet, in case it
helps.
I admit that I still do not understand the Sage model of types...
Martin
Nicolas M. Thiery
On Mon, Mar 09, 2009 at 12:03:34AM -0700, Michel wrote:
> A long time ago I made a FractionFIeld implementation which would
> cache factorizations of denominators. instead of taking gcd's all the
> time
>
> http://markmail.org/message/7hxox5cbz5knxjse#query:new%20implementation%20of%20fraction%20field+page:1+mid:5bf3l37bsim34m4g+state:results
>
> It is usually much faster than the naive implementation but it is
> possible
> to make examples where it is slower (see the above thread). That's
> why it was rejected.
Cool, thanks so much for your pointer and your patch!
In combinatorics, when playing with rational generating series, we
have *lots* of fractions with denominators that factor well. So this
gives quite a few applications to your code.
Let me dream a bit. I very much like the idea of Factored(Ring), where
elements are kept in factored form as long as possible, as is done in
FriCas (thanks Martin for the pointer). I would like to have several
variants to choose from:
- PartiallyFactored(Ring)
The factors are not guaranteed to be relatively prime
- RelativelyPrimeFactored(Ring)
The factors are guaranteed to be relatively prime, but not necessarily
prime themselves
- FullyFactored(Ring)
The factors are all guaranteed to be prime
In each case, the gcd function would do its best to exploit the
structure (e.g. remember which factors are readily relatively prime).
As readily pointed out, this is very modular, and leaves the user with
the choice of the appropriate implementation of fraction field for his
particular application (as the discussion pointed out there won't be
one perfect implementation optimal in all cases). For example for my
application, I ideally would use Ring /
GcdFreePartiallyFactored(Ring). As a starter, I could do with
FractionField(PartiallyFactored(Ring)).
How much work would it be to adapt your patch in this direction? I
definitely volunteer for testing and reviewing it! In fact, your
patch would be very welcome on the Sage-combinat patch server so that
we can easily start playing with it (even though it's not only about
combinatorics).
Best regards,
Nicolas
--
Nicolas M. Thiéry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/
Martin Rubey
> Let me dream a bit. I very much like the idea of Factored(Ring), where
> elements are kept in factored form as long as possible, as is done in
> FriCas (thanks Martin for the pointer). I would like to have several
> variants to choose from:
>
> - PartiallyFactored(Ring)
> The factors are not guaranteed to be relatively prime
> - RelativelyPrimeFactored(Ring)
> The factors are guaranteed to be relatively prime, but not necessarily
> prime themselves
> - FullyFactored(Ring)
> The factors are all guaranteed to be prime
actually, this would be my dream, too! (I think I proposed something
like this on fricas-devel already, but I don't remember well.)
But perhaps you should make sure that your Ring is a UFD -- it won't
make much sense otherwise, would it?
Martin
Nicolas M. Thiery
>
> "Nicolas M. Thiery" <Nicolas...@u-psud.fr> writes:
>
> > Let me dream a bit. I very much like the idea of Factored(Ring), where
> > elements are kept in factored form as long as possible, as is done in
> > FriCas (thanks Martin for the pointer). I would like to have several
> > variants to choose from:
> >
> > - PartiallyFactored(Ring)
> > The factors are not guaranteed to be relatively prime
> > - RelativelyPrimeFactored(Ring)
> > The factors are guaranteed to be relatively prime, but not necessarily
> > prime themselves
> > - FullyFactored(Ring)
> > The factors are all guaranteed to be prime
>
> actually, this would be my dream, too! (I think I proposed something
> like this on fricas-devel already, but I don't remember well.)
:-) Please provide a pointer if you find back your e-mail.
> But perhaps you should make sure that your Ring is a UFD -- it won't
> make much sense otherwise, would it?
Probably. At least, this covers all my current applications!
For the record, my ring is currently S[t], where S is the ring of
symmetric functions in the e basis. You probably are not that
surprised about that :-)
Cheers,
Martin Rubey
> > actually, this would be my dream, too! (I think I proposed something
> > like this on fricas-devel already, but I don't remember well.)
>
> :-) Please provide a pointer if you find back your e-mail.
sorry, very unlikely :-(
> > But perhaps you should make sure that your Ring is a UFD -- it
> > won't make much sense otherwise, would it?
>
> Probably. At least, this covers all my current applications!
>
> For the record, my ring is currently S[t], where S is the ring of
> symmetric functions in the e basis. You probably are not that
> surprised about that :-)
Is it easy to factor such polynomials? How do you do it?
Martin
Martin Rubey
> "Nicolas M. Thiery" <Nicolas...@u-psud.fr> writes:
>
> > > actually, this would be my dream, too! (I think I proposed something
> > > like this on fricas-devel already, but I don't remember well.)
> >
> > :-) Please provide a pointer if you find back your e-mail.
>
> sorry, very unlikely :-(
I should elaborate: I really wanted to say that I think that your
dream is probably a good dream, because it's a dream dreamed
independently by at least two people, and I believe that this
increases the likelihood of "good" :-)
It is however unlikely that I find the e-mail, because
1) I post a lot
2) I frequently find hat I posted some idea only while dreaming,
without actually typing it :-)
> > > But perhaps you should make sure that your Ring is a UFD -- it
> > > won't make much sense otherwise, would it?
> >
> > Probably. At least, this covers all my current applications!
> >
> > For the record, my ring is currently S[t], where S is the ring of
> > symmetric functions in the e basis. You probably are not that
> > surprised about that :-)
>
> Is it easy to factor such polynomials? How do you do it?
Oh, I realize that this is a very stupid question. They are
algebraically independent, so you can simply use multivariate
polynomial factorization, right?
Martin
Nicolas M. Thiery
> > symmetric functions in the e basis. You probably are not that
> > surprised about that :-)
>
> Is it easy to factor such polynomials? How do you do it?
Well, it's a free algebra, so you could always coerce to
QQ['e1,e2,...,], factor, and back (or better, the factorization
implementation should be generic to apply on any free algebra). But in
the short run, I actually don't care about factoring the small
denominators I start with.
Michel
I have no time at the moment to look at this patch. I used it to do
some
computations which were completely undoable with the standard
implementation of FractionField, and which became extremely fast
using this implementation.
So the lukewarm (to say the least) reaction by some very much
discouraged me.
Anyway here is a working link
http://emis.uhasselt.be/~vdbergh/sage_patches/fraction_field_cache/
The beef is contained in a cython file
factor_cache.pyx
which acts as a wrapper around RingElement but which caches
information
about factorizations (to take mock gcd's and lcm's).
FractionField_cache is an implementation of FractionField which uses
factor_cache to cache factorizations of the denominator. You can turn
this behaviour on and off using "auto_reduce".
It is quite likely that the files need to be adapted to work with the
current version of
Sage.
Regards,
Michel
On Mar 9, 7:53 pm, "Nicolas M. Thiery" <Nicolas.Thi...@u-psud.fr>
wrote:
>
> On Mon, Mar 09, 2009 at 12:03:34AM -0700, Michel wrote:
> > A long time ago I made a FractionFIeld implementation which would
> > cache factorizations of denominators. instead of taking gcd's all the
> > time
>
David Kohel
First, I think (at least last time I tried) there is a lot of room to
speed
up arithmetic in function fields, which would be my first priority.
Second, as a mathematical construction, I think that the
localizations
A_S where A is a ring (e.g. UFD or PID) and S = {p_1,...,p_n} is a
set
of primes/irreducibles, would be a useful class to have.
If one knows the primes inverted this would give the "correct"
structure
in which to carry out these calculations.
Regards,
David
Alex Ghitza
Hi,
First, I think (at least last time I tried) there is a lot of room to
speed
up arithmetic in function fields, which would be my first priority.
Second, as a mathematical construction, I think that the
localizations
A_S where A is a ring (e.g. UFD or PID) and S = {p_1,...,p_n} is a
set
of primes/irreducibles, would be a useful class to have.
definite +1. In fact, this is (unsurprisingly) one of the features that the audience at Sage Days 14 asked for in yesterday's "what do you want from Sage" session.
--
Alex Ghitza -- Lecturer in Mathematics -- The University of Melbourne -- Australia -- http://www.ms.unimelb.edu.au/~aghitza/
Nicolas M. Thiery
On Thu, Mar 12, 2009 at 10:03:53AM -0700, David Kohel wrote:
> First, I think (at least last time I tried) there is a lot of room
> to speed up arithmetic in function fields, which would be my first
> priority.
> Second, as a mathematical construction, I think that the
> localizations A_S where A is a ring (e.g. UFD or PID) and S =
> {p_1,...,p_n} is a set of primes/irreducibles, would be a useful
> class to have.
In practice, it may occur that we don't really know in advance who are
the primes (because we are going to add later on news fraction with
some new "primes" in the denominator).
Well, that's just to point out a use case, in case someone gets some
clear idea how to handle this in a mathematically proper way, if at
all possible.
> If one knows the primes inverted this would give the "correct"
> structure in which to carry out these calculations.
Could you please post an appropriate ticket on the subject, with a
link to Michel's work? I am way too much of an amateur in this area
to give any good description of what should be done.
Thanks!
Nicolas
--
Nicolas M. Thiéry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/
Nicolas M. Thiery
> some computations which were completely undoable with the standard
> implementation of FractionField, and which became extremely fast
> using this implementation.
> So the lukewarm (to say the least) reaction by some very much
> discouraged me.
>
> Anyway here is a working link
>
> http://emis.uhasselt.be/~vdbergh/sage_patches/fraction_field_cache/
>
> The beef is contained in a cython file
>
> factor_cache.pyx
>
> which acts as a wrapper around RingElement but which caches
> information
> about factorizations (to take mock gcd's and lcm's).
>
> FractionField_cache is an implementation of FractionField which uses
> factor_cache to cache factorizations of the denominator. You can turn
> this behaviour on and off using "auto_reduce".
>
> It is quite likely that the files need to be adapted to work with the
> current version of Sage.
Thanks for the pointer!
Well, I am pretty much already overloaded myself, so I can will just
vote +2 on this feature request for the moment.
Best,
Nicolas
--
Nicolas M. Thiéry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/