Re: [Axiom-developer] exact quotient

[Waldek Hebisch]

Martin Rubey wrote:
> I am currently trying to correct a performance bug of my guessing package, and
> found out that exquo is in general not extremely intelligent.
> 
> In axiom, what exquo really does is to perform division and return "failed" if
> it's not exact.  (I.e., it is in fact slower than quo.quotient)
> 
> What I need is a fast algorithm, that simply assumes that the division is
> exact, and should benefit from that assumption.  (If the assumption is not
> true, the computer may crash, if necessary...) As far as I know, using some
> tricks performance even better than n^2 (n being the size of the input) is
> achievable.
> 
> Most important would be such an implementation for the polynomial rings.
> 
> Anybody interested?
> 

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).

Concerning complexity: for dense univariate polynomials with coefficients
in small finite fields both multiplication and division have complexity
of n times logarithmic terms.  For practical problem sizes logarithmic
terms behave like constants, and you end up comparing your "constants"
with n.  For dense multivariate polynomials one have similar 
results, but complexity grows exponentially with dimension (for
fixed dimension you have some constat coefficent, but it grows
exponentially with dimension).  Unbouded integer coefficents
essentially add one dimension to the problem (so one variable
integer problem have similar complexity like two variable
modular one).  Sparse problems have some similarity to multidimensional
ones.

I was thinking about adding fast operations on dense polynomials
with coefficients in small finite fields -- such operations are
key to many fast algorithms.  Unfortunatly, they fit rather
poorly into existing algebra.  More precisely, to be fast such
operations would have to work directly at Lisp level (or maybe
even at C level).  But that would require building a new set
of domains and adding calls to them from various places in
algebra.  In particular that would change import relations
in the algebra.  Currently (before database bootstrap is
integrated) such changes are likely to cause bootstrap failure...
-- 
                              Waldek Hebisch
address@hidden