I'm kind of late jumping into this thread, but I have some concerns. Unless the factorization is known completely (or gcd's are taken on the unknown part), I still think this can lead to combinatorial explosion fairly quickly. For example,
sage: from sage.rings.fraction_field_cache import FractionField_cache sage: from sage.rings.fraction_field import FractionField_generic sage: R.<x,y,z>=QQ[] sage: T = [ZZ.random_element()*x + ZZ.random_element()*y + ZZ.random_element()*z for _ in range(10)]; sage: S = [prod(random_sublist(T, .2)) for _ in range(50)] sage: Q=FractionField_cache(R,auto_reduce=False) sage: time f = sum([~Q(s) for s in S]) CPU times: user 6.41 s, sys: 0.01 s, total: 6.42 s Wall time: 6.45 sage: len(str(f)) 2011614 sage: time f.reduce() ^C ### Got really tired of waiting after 10 min.... sage: sage: time f(2,3,4) CPU times: user 9.68 s, sys: 0.03 s, total: 9.71 s Wall time: 10.08 244271/26730 sage: sage: Q=FractionField_generic(R) sage: time f = sum([~Q(s) for s in S]) CPU times: user 0.15 s, sys: 0.00 s, total: 0.15 s Wall time: 0.15 sage: len(str(f)) 5430 sage: time f.reduce() # it's already reduced, but it doesn't know that CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s Wall time: 0.00 sage: time f(2,3,4) CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s Wall time: 0.00 244271/26730 That being said, I think it could maybe have its use, as could a general factored element ring (though I too can't think of any uses off the top of my head). - Robert On May 27, 2007, at 10:03 AM, Michel wrote: > 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 sage-devel@googlegroups.com 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/ -~----------~----~----~----~------~----~------~--~---
