Opened 7 years ago

Closed 7 years ago

#749 closed bug (fixed)

map is slow

Reported by: steenpass Owned by: somebody
Priority: minor Milestone: 4-1-0 and higher
Component: dontKnow Version: 4-0-2
Keywords: map, imap, fetch Cc:


Permuting the variables in an ideal with many terms such as

ring R = 0, x(1..10), dp;
ideal I = maxideal(10);

is very slow if it is done via a map:

map phi = R, x(10), x(1..9);
ideal J1 = phi(I);

The fastest way seems to use fetch() and imap() like this:

ring S = 0, (x(10), x(1..9)), dp;
ideal I = fetch(R, I);
ideal J2 = imap(S, I);

This is not surprising since Singular maps are far more general.

But even if the transformation is done on interpreter level, this is already much faster than map:

proc transform(ideal I, ideal phi)
    ideal phi_I;
    intvec exp;
    poly p;
    int i, j, k;
    for (i = ncols(I); i > 0; i--) {
        phi_I[i] = 0;
        for (j = size(I[i]); j > 0; j--) {
            exp = leadexp(I[i][j]);
            p = 1; 
            for (k = size(exp); k > 0; k--) {
                p = p*phi[k]^exp[k];
            phi_I[i] = phi_I[i]+p;

ideal J3 = transform(I, ideal(x(10), x(1..9)));

Note that

  • J1, J2, and J3 are the same,
  • the above procedure has the same functionality as map except that it only works for transformations within the same ring, and
  • the factor by which this procedure is faster than map even increases as the number of terms goes up.

Change History (1)

comment:1 Changed 7 years ago by hannes

Resolution: fixed
Status: newclosed

fixed (see 5f46166c7775b4b01ad9b5572aebcd849a244ef5 and related) maMapIdeal is now the general interface for mapping ideals, which tests for some special cases (permations, substitions of one variable, etc.). This improves the speed of the example above by a factor of 35300. The fastes possiblity is still


which does not need to check for overflow during mapping. As the output does not change, not suitable for a test script.

Note: See TracTickets for help on using tickets.