Re: sparse polynomial arithmetic

On Apr 3, 6:08 pm, Bill Hart <goodwillh...@xxxxxxxxxxxxxx> wrote:
On Apr 4, 1:27 am, rjf <fate...@xxxxxxxxx> wrote:



What is lisp? Does it multiply polynomials?

Lisp is a programming language. There is an ANSI standard for "Common
Lisp".
Does it multiply polynomials? Well, you can easily write programs to
do so in Lisp.
There are a number of computer algebra systems written in lisp:
Macsyma/Maxima, Axiom, Reduce, Jacal (Scheme dialect), Mathlab, plus
many experiments.

there are lots of examples
that would run slowly if all arithmetic were replaced by calls to the
very efficient libraries available (like GMP) for arbitrary precision
arithmetic. The run-of-the-mill arithmetic should be (and generally
is) compilable to machine integer or float arithmetic, which, for what
it does, is much much faster than calls to GMP.

FLINT doesn't use either of the strategies you have in mind, for small
polynomials.

If FLINT neither uses machine integer/float arithmetic, nor calls to
libraries, what does it do?




A mixed approach that tries to estimate what is going on beforehand
may be smart: e.g.
are these inputs and outputs sparse/dense?
are the coefficients [in the answer] going to be large/small (e.g.
in finite field, floats?)?
How much memory is available if we have to spread out in memory?
What kind of blocking makes sense given cache sizes etc.

I once read a paper by someone who suggested that for polynomials of
length 128000 blocking worked, but for small polynomials (length 1000
to 32000) cache blocking doesn't work.

Can you identify this paper? (and what is meant by "length"?)


I'm not sure what size you consider to be a small polynomial, but
using machine words or doubles would not be faster for polynomials
more than length about 20 at most, less probably on some
architectures. But now you are talking about saving time on a
computation which takes a tenth of a microsecond.

You have a need to multiply a few billion polynomials efficiently?

Generally computer algebra systems multiply (mostly small) polynomials
quite often.
If you ran one for a few days, it might very well multiply a few
billion polynomials.

RJF
.

Relevant Pages

  • Re: Axiom or Maxima?
    ... expressions, matrices, probably polynomials), ... Initial work on SPAD predated the refinement of the common lisp object system design. ... which might be a suitable framework. ... There has been at least one attempt to do the "right thing" more specifically in CLOS, ...
    (comp.lang.lisp)
  • Re: Development in C# - Class to represent a multivariate polynomial expression
    ... I think your best bet is to find a Lisp or Scheme implementation in C# ... it is easy to write code for polynomials or other algebraic operations. ... This approach also makes it much easier to cope with feature creep, ...
    (sci.math.symbolic)
  • Re: whats it worth to write a short program for polynomial multiplication?
    ... Obviously, in an appropriate programming language, this ... matrices, elements in a finite field, strings, etc. ... information which describes the polynomials (sparse, univariate, ... There are 58 * operators in Axiom, many of which can by automatically ...
    (sci.math.symbolic)
  • =?ISO-8859-1?Q?Vector_23=2C_N=B04?=
    ... — About polynomials. ... Gianluigi Quario discovers new ways to handle ... Borror’s new tutorial for the q programming language. ...
    (comp.lang.apl)
  • Re: Public Key, Symbolic Calculation
    ... this long thread about the C programming language just has ... roots of polynomials over Q in polynomial time. ... need to do a literature search on your own. ...
    (sci.crypt)