On May 27, 7:28 pm, David Harvey <[EMAIL PROTECTED]> wrote:
> What happens if I add a/(bc) to d/(be)? Does the implementation attempt
> to recognise that there is a common factor in the denominators? (i.e.
> assuming the system does not already know about the factor of b.)
The implementation does not attempt to recognize factors on its own.
I think that would be much too expensive. But typically factored
numbers
come for prior operations and in that case of course they are
recognized.
The problem is not to speed up a single addition of fractions but the
case where you evaluate for example a polynomial (or rational
function) with a large number of terms
on fractions.
>
> And I assume if you have a fraction a/b, where the system has
> remembered some factorisation information about b, then if you compute
> 1/(a/b) it throws that information away?
>
No it does not throw that information away. Internally elements of the
ring
are stored in "factored" form r_1^{e_1}...r_n^{e_n} (with a lazily
evaluated
cached product). This
information is preserved under "mulltiplicative" operations.
(multiplication, division, (mock)gcd, (mock)lcm). It is destroyed
under additive operations.
Michel
>
>
>
> > Hi,
>
> > The current implementation of fraction fields is slow. This is very
> > apparent for rings with a slow gcd algorithm. But even if this is not
> > the
> > case then constantly taking gcd's eventually becomes a major
> > bottleneck.
> > See the example below which uses the new libSingular.
>
> > It was pointed out on this list that not taking gcd's at every step
> > quickly leads to combinatorial explosion when evaluating polynomials
> > with
> > a large number of terms.
>
> > I think I have found a solution for this last problem. The trick is to
> > cache partial partial factorizations of denominators. I.e. for example
> > if we performa an addition a/b+c/d=(ad+cb)/ad then we remember that
> > the denominator
> > ad is really a*d. If next time we have to add (ad+cb)/ad+(c/d)^2 we
> > can
> > take as new denominator ad^2 instead of ad^3.
>
> > I have created a new FractionField_cache implementation which uses
> > this idea.
> > See
> >http://emis.uhasselt.be/sage_patches/fraction_field_cache.
> > The specific patch is here
> >http://emis.uhasselt.be/sage_patches/fraction_field_cache/
> > factor_cacheing.patch
> > It depends on the one_element patch by William. It creates three new
> > files
>
> > factor_cache.pyx
> > fraction_field_cache.py
> > fraction_field_element_cache.py
>
> > and modifies setup.py (to build the extension factor_cache). To use
> > the
> > new implementation do
>
> > from sage.rings.fraction_field_cache import FractionField_cache
>
> > Example (using the new libSingular)
>
> > sage: from sage.rings.fraction_field_cache import FractionField_cache
> > sage: R.<x,y,z>=QQ[]
> > sage: Q=FractionField_cache(R,auto_reduce=False)
> > sage: def t():((x+y+z)**20)(Q(1,x+y),y,y**100).reduce()
> > ....
> > sage: time t()
> > CPU times: user 2.11 s, sys: 0.02 s, total: 2.13 s
> > Wall time: 2.27 <== compare this
>
> > sage: from sage.rings.fraction_field import FractionField_generic
> > sage: Q=FractionField_generic(R)
> > sage: def t():((x+y+z)**20)(Q(1,x+y),y,y**100)
> > ...
> > sage: time t()
> > CPU times: user 12.49 s, sys: 0.06 s, total: 12.54 s
> > Wall time: 14.36 <== to this
>
> > For more benchmarks see
> >http://emis.uhasselt.be/sage_patches/fraction_field_cache/summary.log
> >http://emis.uhasselt.be/sage_patches/fraction_field_cache/benchmark.log
>
> > Yet more benchmarks can be created with the following program
> >http://emis.uhasselt.be/sage_patches/fraction_field_cache/benchmark.py
>
> > Notes:
> > (1) When testing, please be careful to use the constructor
> > Q(num,denom) to create
> > fractions. A FractionField_cache constructed using __init__ is of
> > course not globally unique. So fractions of the form num/denom will
> > live in a FractionField_generic and not in Q.
> > (2) I did not look at coercions although if there are problems they
> > should
> > be trivial to fix.
> > (3) The actual cacheing of partial factorizations of denominators
> > is done in the extension "factor_cache". Please read the docstring
> > there
> > for the implementation.
> > (4) I hope to write an implementation of the subresultant algorithm
> > for
> > poly_dicts (if someone else does not do it). Then every polynomial
> > ring will have a fallback gcd algorithm (if the base ring has one).
> > Although I think I can optimize it quite a bit this algorithm will
> > of course be slower than more specialized ones. For this I would
> > like the FractionField implementation to be more optimized.
>
> > Question: What should I do now? I think the implementation of
> > FractionField_cache
> > improves upon the implementation of FractionField_generic. Please
> > give some feedback.
>
> > Michel
>
> > PS. I has been discussed to perform the final reduce only for example
> > if a fraction
> > is printed. I have not done this yet since it makes benchmarking
> > somewhat more
> > tricky. But I can do this if people think this is a better solution.
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/
-~----------~----~----~----~------~----~------~--~---
