At the moment, to get to K = 100, you are only using about 388 bits.
So the size here is not all that large, only a few limbs.
In general arithmetic modulo primes that will fit in a limbs is
generally faster than multiple precision arithmetic. But this is
mainly due to there being less overhead. S
It turns out that for my problem it suffices to compute the
polynomials
1, f, f^2, ..., f^K
modulo N for some large but known number N, so I suspect that it may
be faster to work modulo p for various primes p and then use the
Chinese Remainder Theorem.
How large, roughly speaking, can I take my
On 16 May, 02:41, Roman Pearce wrote:
> On May 15, 6:21 pm, Bill Hart wrote:
>
> > I have the right number of terms, but not quite the right coefficient,
> > as of yet. This is a good test to help me dig out the bug. :-)
>
> Do you have a division routine? I divided f^100 by f to check the
> r
OK, it's working now. I was adding a coefficient where I should have
been setting it.
Times didn't really change though.
Bill.
On 16 May, 02:21, Bill Hart wrote:
> I have the right number of terms, but not quite the right coefficient,
> as of yet. This is a good test to help me dig out the bug.
On May 15, 6:21 pm, Bill Hart wrote:
> I have the right number of terms, but not quite the right coefficient,
> as of yet. This is a good test to help me dig out the bug. :-)
Do you have a division routine? I divided f^100 by f to check the
result. This is one way I test sdmp. You can also plu
I have the right number of terms, but not quite the right coefficient,
as of yet. This is a good test to help me dig out the bug. :-)
Thanks.
By the way, is your computation running on more than one core?
Bill.
On 16 May, 02:12, Roman Pearce wrote:
> I get that f^100 is a polynomial with 37219
I get that f^100 is a polynomial with 3721951 terms. The largest
coefficient belongs to x^44*y^181*z^131 and is
540685566063956356849231312581525435336487979299724512007837438591842230283354998840425635151449237483722428755963200
--
To post to this group, send an email to sage-devel@googlegroups
As a check for my implementation, how many bits does the largest
coefficient have?
Bill.
On 16 May, 01:28, Roman Pearce wrote:
> Maple 14 on iMac Core i5 2.66 GHz 8GB (64-bit):
>
> f := x*y^3*z^2 + x^2*y^2*z + x*y^3*z + x*y^2*z^2 + y^3*z^2 + y^3*z +
> 2*y^2*z^2 + 2*x*y*z + y^2*z + y*z^2 + y^2 +
Hmm, actually, on my machine Magma is much slower, and that is the
latest Magma. Though perhaps we don't have the right Magma for our
machine or something.
Bill.
On 16 May, 01:22, Bill Hart wrote:
> The times I get with the new code are 28s to K = 70 and 135s to K =
> 100. This is on an Opteron
Maple 14 on iMac Core i5 2.66 GHz 8GB (64-bit):
f := x*y^3*z^2 + x^2*y^2*z + x*y^3*z + x*y^2*z^2 + y^3*z^2 + y^3*z +
2*y^2*z^2 + 2*x*y*z + y^2*z + y*z^2 + y^2 + 2*y*z + z;
curr := 1:
TIMER := time[real]():
for i from 1 to 100 do
curr := expand(curr*f):
lprint(i=time[real]()-TIMER):
end do:
K=
The times I get with the new code are 28s to K = 70 and 135s to K =
100. This is on an Opteron K102 though, which probably does the
coefficient arithmetic a little faster than the core2. In fact much of
the time is probably coefficient arithmetic in this problem I would
guess. The coefficients must
On May 15, 9:03 pm, William Stein wrote:
> 1. On what hardware?
This was on 64 bit GNU/Linux (Fedora release 12) running on a dual
processor machine with two Intel Core 2 CPUs (each 2.4GHz, 4Gb
cache). I have included the contents of /proc/cpuinfo at the bottom
of this reply.
> 2. Can you po
On Sat, May 15, 2010 at 12:55 PM, Tom Coates wrote:
>
> Thank you (everyone!) for the many extremely helpful comments and
> links.
>
> Recall that I need to compute
>
> 1, f, f^2, ..., f^K
>
> for f in ZZ[x,y,z] and K known but large. (In fact I only need
> certain coefficients of the f^i, but th
Thank you (everyone!) for the many extremely helpful comments and
links.
Recall that I need to compute
1, f, f^2, ..., f^K
for f in ZZ[x,y,z] and K known but large. (In fact I only need
certain coefficients of the f^i, but this does not seem to help very
much.)
I have implemented the most naiv
I did lots of experimenting. If I really go crazy with optimisation I
can get it down to about 1.93s. About another 0.05s is just taken up
figuring out which case we are in (e.g. everything fits in one limb,
or two limbs, or whatever). I could duplicate the code multiple times
for the different cas
Oh, sorry. I did get confused. I didn't see you had "SDMP-Core2"
written in your benchmark table. I hadn't realised you were quoting
sdmp times.
Bill.
On 14 May, 21:19, Francesco Biscani wrote:
> Hi Bill,
>
> On Fri, May 14, 2010 at 3:28 PM, Bill Hart
> wrote:
> > If I make a couple of simplif
Actually I wasn't allocating them in slabs. I had my threadsafe
version of the flint integer format turned on. The other version
allocates mpz's in slabs, but was broken. So.
having now fixed that. I do get the time down to about 2.1s on
sage.math. However, that's not noticeably faster th
Hi Bill,
On Fri, May 14, 2010 at 3:28 PM, Bill Hart wrote:
> If I make a couple of simplifications, namely assume that the output
> fits into two limbs, and that none of the polynomials has length >
> 2^32 - 1, etc, I get pretty good times, certainly better than reported
> in Francesco's paper. I
On May 14, 9:54 am, Bill Hart wrote:
> On the other hand, I am unable to replicate the very sparse benchmark
> unless I assume the result will fit in 2 limbs and allocate all the
> output mpz's in advance, etc. Then I can basically replicate it. If I
> use my generic no assumptions code it takes a
On the other hand, I am unable to replicate the very sparse benchmark
unless I assume the result will fit in 2 limbs and allocate all the
output mpz's in advance, etc. Then I can basically replicate it. If I
use my generic no assumptions code it takes about 3s. I don't think I
can improve that much
With a bit of fiddling I can get the Fateman benchmark down to 53.5s
on sage.math (2.66 GHz Core2/penryn) making no assumptions about the
size of the output coefficients. I've checked that at least the output
poly has the right length and coeffs of the right size.
Adjusting for the clock speed, th
Thanks all for the very interesting comments and links to publications
and CAS's.
I've implemented the algorithm using flint2's fmpz (multiprecision)
integer type for coefficients and at this stage for 62 bit integers
for exponents, only. (However it should be trivial to lift this
restriction.)
I
On 13 mai, 19:03, Roman Pearce wrote:
> On May 13, 2:45 am, parisse wrote:
>
> > In my own experience, coding with an univariate polynomial is not
> > efficient especially if the polynomial is sparse.
>
> There must be some kind of inefficiency. If you use word
> operations
> for all monomial
Since this is turning into an all purpose post, I'm going to crosspost
to sci.math.symbolic. I want to start by saying that the heap
method
should be called "Johnson's algorithm". See
http://portal.acm.org/citation.cfm?id=1086847
We've made contributions to improve it, but our actual work has
be
On May 13, 2:45 am, parisse wrote:
> In my own experience, coding with an univariate polynomial is not
> efficient especially if the polynomial is sparse.
There must be some kind of inefficiency. If you use word
operations
for all monomial operations then it should be fast. See
http://portal.ac
Hi Bill,
in my own experience Kronecker substitution can be effective in a
number of situations. It would also automatically handle the case you
mention about working only on a subset of variables (i.e., the ones
involved in the multiplication).
I have the description of my implementation and som
In my own experience, coding with an univariate polynomial is not
efficient especially if the polynomial is sparse. I'm using heapmult
or Lagrange interpolation in giac for polynomials represented as
sparse distributed polynomials, with monomials coded as integers if
they fit. I also experienced th
1. almost regardless of f, f^K for sufficiently large K is likely to
be fairly dense.
2. You could encode f more tightly as a univariate polynomial by using
different N, depending on the degree
of x,y,z, etc.
3. (most plausible) you could use a recursive representation for f,
which could, I thi
28 matches
Mail list logo
