axiom-developer
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Axiom-developer] exact quotient


From: Martin Rubey
Subject: Re: [Axiom-developer] exact quotient
Date: 20 Jun 2007 23:08:49 +0200
User-agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.4

Waldek Hebisch <address@hidden> writes:

> I am interested in Axiom performance.  But do you have reasons to supect
> exquo?  I mean, did you look at profile of some problematic run?  While I
> agree that perfroming division and checking that remainder is zero is not
> very smart, it should not matter much for polynomials (at least for
> polynomials in single variable, for multivariate polynomials division is not
> defined, so you must do something smarter anyway).

Well, I'm not so sure - I just don't know.  To fix things: I am really only
(for the moment) interested in the case where we are dealing with multivariate
polynomials.

As far as I can see, the poor performance is due to poor multiplication and
exquo, but I cannot be sure.  I find it a bit hard to measure.

[one day later...]

OK, the situation is worse than I would have thought.  I did the following
rather simple test, which is, however, very realistic for my application: (Note
that in my application, for certain reasons, I also have to use the POLY
constructor.)

-------------------------------------------------------------------------------
-- define a bivariate polynomial of "size" (= number of coefficients) n+1
mon(n,k) == (random k * x + random k * y)^n

l(kappa, m) == [mon(kappa, 10000) for i in 1..m]

-- test performance of multiplication
test(kappa, m, n) ==
    ls1 := l(kappa, m)
    ls2 := l(kappa, m)
    res: List List Integer := []
    for trial in 1..n repeat
        GBC(t)$Lisp
        tim1 := integer GET_-UNIVERSAL_-TIME()$Lisp
        for i in ls1 for j in ls2 repeat i*j;
        tim2 := integer GET_-UNIVERSAL_-TIME()$Lisp
        res := cons([kappa, tim2-tim1], res)
    output res
    res

reduce(append, [test(kappa, 500, 5) for kappa in 10..100 by 10])
-------------------------------------------------------------------------------

On my machine, I get the following output

   [[10,1],[10,0],[10,1],[10,1],[10,1]]
   [[20,2],[20,2],[20,3],[20,2],[20,2]]
   [[30,6],[30,6],[30,5],[30,6],[30,6]]
   [[40,11],[40,12],[40,12],[40,12],[40,12]]
   [[50,19],[50,20],[50,19],[50,20],[50,20]]
   [[60,32],[60,32],[60,35],[60,35],[60,35]]
   [[70,52],[70,52],[70,52],[70,55],[70,51]]
   [[80,77],[80,77],[80,76],[80,76],[80,76]]
   [[90,102],[90,102],[90,108],[90,103],[90,103]]

This really looks like complexity between O(k^2.5) and O(k^3.0) for me, where k
is the number of monomials of the input.  I expected something like O(k^2)
though:

(a1*x1 + a2*x2+...+ak*xk)*(b1*x1 + b2*x2+...+bk*xk)
= (a1*x1 + a2*x2+...+ak*xk)*B
= a1*B*x1 + a2*B*x2...+ak*B*xk

which makes k^2 coefficient multiplications.  The cost of multiplying variables
should really be negligible, I believe.

Reducing this and exquo to O(k^2) would be a *huge* speedup for my guessing
package.  For example, it would reduce the time needed for a certain example in
my article from 5 hours down to 45 minutes.

Unfortunately, I have no idea how to go about this.

Martin





reply via email to

[Prev in Thread] Current Thread [Next in Thread]