#4000: [with patch, needs work] Implement QQ['x'] via Flint ZZ['x'] +
denominator
------------------------------+---------------------------------------------
Reporter: malb | Owner: somebody
Type: enhancement | Status: new
Priority: major | Milestone: sage-wishlist
Component: basic arithmetic | Keywords:
Reviewer: | Author: Martin Albrecht
Merged: |
------------------------------+---------------------------------------------
Comment(by malb):
Replying to [comment:11 spancratz]:
> Actually, I am not quite sure about this. When working with a random
polynomial of degree 2000, which will have lots of non-zero entries all of
type fmpz_t, it shouldn't really matter whether we manually initialise a
few more for the denominators.
We shouldn't forget about small polynomials, they should be fast too. Two
instead of one system call sounds rather expensive to me for basic
arithmetic.
> I've tried implementing the denominator with the convention that it is
either ``NULL`` (which should be interpreted as one) or initialised to a
positive integer. But this didn't really change the performance.
Did you try small examples? Also, how much does the realloc trick you
implemented give you?
> Another idea, which will sometimes help to keep numbers small, is to
instead represented the polynomial over the rationals as ``(num / dem)
prim`` where ``num / dem`` is a rational number in reduced form and
``prim`` is a primitive integer polynomial with positive leading
coefficient. Obviously, this change vastly improved the performance of
negation (which then only operates on the rational number and leaves the
integer polynomial part alone). But it didn't change much apart from
that. Anyway, given we need to compute the content of the numerator
anyway to ensure that it is coprime to the denominator, we might as well
store it separately. I'll implement this throughout the patch and upload
a new version later today.
>
> This still leaves the problem: How can we speed up addition?
Did you try the LCM idea? Rationale:
{{{
#!python
sage: P.<x> = QQ[]
sage: f = P.random_element(3000)
sage: g = P.random_element(3000)
sage: fD = f.denominator()
sage: gD = g.denominator()
sage: (fD*gD).nbits()
320
sage: (fD.lcm(gD)).nbits()
228
}}}
> At the moment, I don't have any further ideas. In fact, I think it
might perhaps be the case that we simply can't, since in this kind of
implementation we have to at least do a few polynomial scalar
multiplications (and perhaps polynomial scalar divisions as well as
integer gcd computations to maintain the form of the representation) plus
all the coefficient additions. In contrast to this, implementing
polynomials as an array of coefficients one only has to do the (rational!)
coefficient additions.
Well, this other implementation would have to do quite a few rational
additions where it would have to deal with denominators quite a bit. I am
not convinced yet it has to be this slow. You could also ask on [sage-
devel] I am sure, e.g. Bill Hart (main author of FLINT) would have some
cool ideas.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/4000#comment:12>
Sage <http://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 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-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
