Tom Coates asked me the following question: > "I need to compute the following. Let f be an element of ZZ[x,y,z]. I need > the sequence
> 1, f, f^2, f^3, ..., f^K > where K is known but large. [Actually I only need certain coefficients of > each power of f, but there doesn't seem to be a way to compute only the > coefficients I care about.] > My first thought was to do this using FLINT, by turning this into a > univariate polynomial problem via encoding > x^a y^b z^c as t^(a+N*b+N^2*c) > for sufficiently large N, and then using univariate polynomial > multiplication. But in practice this turned out to be very slow, perhaps > because FLINT does not make use of the fact that the univariate polynomials > involved here are extremely sparse. > Is there any way to get FLINT to make use of the sparsity here? Or is there > an alternative C library for multivariate (or sparse univariate) polynomial > multiplication that you would recommend?" I'd be interested if anyone has any good answers to these questions. I mentioned libpari and libsingular to Tom. Are there any others? Anyhow, I'm just about to start a new module in flint2 for multivariate polynomial arithmetic. I will only work on multiplication for now, but if anyone is interested in joining me, I'd be pleased to have the help. I'll post any interesting results of this project here. My intention is to use the heap algorithm of Pearce and Monaghan (I have some old code lying around from where I essentially implemented this) and to use the idea, which I'll credit to Richard Fateman for now, of breaking the polynomials up into chunks until they are small enough that all the exponents will fit into a single machine word. This will be a layer on top of the algorithm of Pearce and Monaghan. There is an even higher level which I think is too complicated to handle in FLINT and should probably be done in Sage/Python. It will take a multivariable problem with an arbitrary number of variables and map it to a problem with only the variables that are actually used appearing in the computation. E.g. if you are working in ZZ[u, v, w, x, y, x1, x2, x3, x4, x5, ...., x100] and you want to multiply x1^3 + 3*x1*x2 + x4 by x2 + x1*x4 + x2^3, it won't work in the ring with 105 variables, but will reduce the problem to one with just 4 variables (for which it can call FLINT). I don't know how or if this is handled in Sage currently. Does anyone know the Sage internals for mpoly rings intimately who can shed some light on this? Bill. -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
