#16812: use FLINT to speed up Chebyshev T polynomial creation
-------------------------------------+-------------------------------------
Reporter: rws | Owner:
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-6.4
Component: symbolics | Resolution:
Keywords: flint, speedup | Merged in:
Authors: Ralf Stephan | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/maldun/use_flint_to_speed_up_chebyshev_t_polynomial_creation|
59d04f5fd05174cc0197424363db69c420e3e8f1
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by rws):
Replying to [comment:32 maldun]:
> Typing
>
> {{{
> chebyshev_T(1000000,x)
> }}}
> in the old version gives a proper result in 7.52
> The exact same input gives me full memory (8GB on my machine) and about
1GB swap + a frozen system in the new version.
That result may be proper for a symbolic `x` but the times are completely
different for ring elements because expansion, which is avoided with
symbolic `x`, happens automatically. This speed difference for polynomial
ring elements actually is the reason for this ticket (see description).
> Higher input gives a an error of flint (Memory allocation error)
>
> Some switch would be nice. I guess the best measure would be the break
even point on memory consumption.
>
> Edit: I think a good point would be about order 5000-10000: It is
reasonable from view of speed/memory and an explicit representation would
be too cluttered anyway
I don't think Sage has to anticipate user memory size, I can go happily to
150.000 with 8GB:
{{{
sage: R.<x> = ZZ[]
sage: timeit('chebyshev_T(10^5,x)')
5 loops, best of 3: 454 ms per loop
sage: timeit('chebyshev_T(150000,x)')
5 loops, best of 3: 1.01 s per loop
}}}
Who knows what will be in ten years? Note also that noone displays such
results, and that's good because the output process takes near all memory
and CPU, not FLINT.
Now, it might have been a bad idea by me to use FLINT on symbolic input
but I thought users might appreciate unconvoluted polynomials as output.
OTOH, they might get another motivation from this to use rings if they
want straight output of polys. So I'll roll back the symbolic involvement,
no limit is needed, and Bob's your uncle.
--
Ticket URL: <http://trac.sagemath.org/ticket/16812#comment:35>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
