parallelism in engine computations -- parallelism in engine computations

Some computations in the engine can run using multiple cores on your computer. Currently, this includes computation of minimal betti diagrams, non-minimal resolutions, and Groebner bases of 2-sided ideals in associative algebras, all in the graded case, over a finite field. Also included is (one of the algorithms for) the computation of Groebner bases in polynomial rings over finite fields, whether graded or not.

The variable nummTBBThreads controls the number of cores used by Macaulay2. The default value (zero) means the system can choose an appropriate number of cores (often the maximum available). Note that the default behavior is to use multiple cores.

In minimalBetti, and in freeResolution with the Strategy => Nonminimal option, more aggressive parallelism that sometimes uses a lot of memory but can sometimes produce answers in less time can be enabled using the ParallelizeByDegree boolean option.

For examples, we show some simple examples of computation which, for larger size problems, might benefit from using parallelism. Note that in each of these cases, the default is to use all available CPU cores for computation. For these particularly simple examples, the overhead for using multiple cores is non-trivial with respect to the total computation time. Significant speedup is achieved when the time to gauss reduce the requisite matrices is large compared to creating these matrices.

i1 : numTBBThreads

o1 = 0

i2 : I = Grassmannian(1, 6, CoefficientRing => ZZ/101)

o2 = ideal (p   p    - p   p    + p   p   , p   p    - p   p    + p   p   ,
             4,5 3,6    3,5 4,6    3,4 5,6   4,5 2,6    2,5 4,6    2,4 5,6 
     ------------------------------------------------------------------------
     p   p    - p   p    + p   p   , p   p    - p   p    + p   p   , p   p   
      3,5 2,6    2,5 3,6    2,3 5,6   3,4 2,6    2,4 3,6    2,3 4,6   4,5 1,6
     ------------------------------------------------------------------------
     - p   p    + p   p   , p   p    - p   p    + p   p   , p   p    -
        1,5 4,6    1,4 5,6   3,5 1,6    1,5 3,6    1,3 5,6   2,5 1,6  
     ------------------------------------------------------------------------
     p   p    + p   p   , p   p    - p   p    + p   p   , p   p    - p   p   
      1,5 2,6    1,2 5,6   3,4 1,6    1,4 3,6    1,3 4,6   2,4 1,6    1,4 2,6
     ------------------------------------------------------------------------
     + p   p   , p   p    - p   p    + p   p   , p   p    - p   p    +
        1,2 4,6   2,3 1,6    1,3 2,6    1,2 3,6   4,5 0,6    0,5 4,6  
     ------------------------------------------------------------------------
     p   p   , p   p    - p   p    + p   p   , p   p    - p   p    +
      0,4 5,6   3,5 0,6    0,5 3,6    0,3 5,6   2,5 0,6    0,5 2,6  
     ------------------------------------------------------------------------
     p   p   , p   p    - p   p    + p   p   , p   p    - p   p    +
      0,2 5,6   1,5 0,6    0,5 1,6    0,1 5,6   3,4 0,6    0,4 3,6  
     ------------------------------------------------------------------------
     p   p   , p   p    - p   p    + p   p   , p   p    - p   p    +
      0,3 4,6   2,4 0,6    0,4 2,6    0,2 4,6   1,4 0,6    0,4 1,6  
     ------------------------------------------------------------------------
     p   p   , p   p    - p   p    + p   p   , p   p    - p   p    +
      0,1 4,6   2,3 0,6    0,3 2,6    0,2 3,6   1,3 0,6    0,3 1,6  
     ------------------------------------------------------------------------
     p   p   , p   p    - p   p    + p   p   , p   p    - p   p    +
      0,1 3,6   1,2 0,6    0,2 1,6    0,1 2,6   3,4 2,5    2,4 3,5  
     ------------------------------------------------------------------------
     p   p   , p   p    - p   p    + p   p   , p   p    - p   p    +
      2,3 4,5   3,4 1,5    1,4 3,5    1,3 4,5   2,4 1,5    1,4 2,5  
     ------------------------------------------------------------------------
     p   p   , p   p    - p   p    + p   p   , p   p    - p   p    +
      1,2 4,5   2,3 1,5    1,3 2,5    1,2 3,5   3,4 0,5    0,4 3,5  
     ------------------------------------------------------------------------
     p   p   , p   p    - p   p    + p   p   , p   p    - p   p    +
      0,3 4,5   2,4 0,5    0,4 2,5    0,2 4,5   1,4 0,5    0,4 1,5  
     ------------------------------------------------------------------------
     p   p   , p   p    - p   p    + p   p   , p   p    - p   p    +
      0,1 4,5   2,3 0,5    0,3 2,5    0,2 3,5   1,3 0,5    0,3 1,5  
     ------------------------------------------------------------------------
     p   p   , p   p    - p   p    + p   p   , p   p    - p   p    +
      0,1 3,5   1,2 0,5    0,2 1,5    0,1 2,5   2,3 1,4    1,3 2,4  
     ------------------------------------------------------------------------
     p   p   , p   p    - p   p    + p   p   , p   p    - p   p    +
      1,2 3,4   2,3 0,4    0,3 2,4    0,2 3,4   1,3 0,4    0,3 1,4  
     ------------------------------------------------------------------------
     p   p   , p   p    - p   p    + p   p   , p   p    - p   p    +
      0,1 3,4   1,2 0,4    0,2 1,4    0,1 2,4   1,2 0,3    0,2 1,3  
     ------------------------------------------------------------------------
     p   p   )
      0,1 2,3

               ZZ
o2 : Ideal of ---[p   ..p   , p   , p   , p   , p   , p   , p   , p   , p   , p   , p   , p   , p   , p   , p   , p   , p   , p   , p   , p   ]
              101  0,1   0,2   1,2   0,3   1,3   2,3   0,4   1,4   2,4   3,4   0,5   1,5   2,5   3,5   4,5   0,6   1,6   2,6   3,6   4,6   5,6

i3 : S = ring I

o3 = S

o3 : PolynomialRing

i4 : elapsedTime minimalBetti I
 -- 1.95758 seconds elapsed

            0  1   2   3   4    5   6   7   8  9 10
o4 = total: 1 35 140 385 819 1080 819 385 140 35  1
         0: 1  .   .   .   .    .   .   .   .  .  .
         1: . 35 140 189  84    .   .   .   .  .  .
         2: .  .   . 196 735 1080 735 196   .  .  .
         3: .  .   .   .   .    .  84 189 140 35  .
         4: .  .   .   .   .    .   .   .   .  .  1

o4 : BettiTally

i5 : I = ideal I_*;

o5 : Ideal of S

i6 : elapsedTime minimalBetti(I, ParallelizeByDegree => true)
 -- 1.57178 seconds elapsed

            0  1   2   3   4    5   6   7   8  9 10
o6 = total: 1 35 140 385 819 1080 819 385 140 35  1
         0: 1  .   .   .   .    .   .   .   .  .  .
         1: . 35 140 189  84    .   .   .   .  .  .
         2: .  .   . 196 735 1080 735 196   .  .  .
         3: .  .   .   .   .    .  84 189 140 35  .
         4: .  .   .   .   .    .   .   .   .  .  1

o6 : BettiTally

i7 : I = ideal I_*;

o7 : Ideal of S

i8 : numTBBThreads = 1

o8 = 1

i9 : elapsedTime minimalBetti(I)
 -- 2.01108 seconds elapsed

            0  1   2   3   4    5   6   7   8  9 10
o9 = total: 1 35 140 385 819 1080 819 385 140 35  1
         0: 1  .   .   .   .    .   .   .   .  .  .
         1: . 35 140 189  84    .   .   .   .  .  .
         2: .  .   . 196 735 1080 735 196   .  .  .
         3: .  .   .   .   .    .  84 189 140 35  .
         4: .  .   .   .   .    .   .   .   .  .  1

o9 : BettiTally

i10 : needsPackage "Complexes"

o10 = Complexes

o10 : Package

i11 : numTBBThreads = 0

o11 = 0

i12 : I = ideal I_*;

o12 : Ideal of S

i13 : elapsedTime freeResolution(I, Strategy => Nonminimal)
 -- 2.62991 seconds elapsed

       1      35      241      841      1781      2464      2294      1432      576      135      14
o13 = S  <-- S   <-- S    <-- S    <-- S     <-- S     <-- S     <-- S     <-- S    <-- S    <-- S
                                                                                                  
      0      1       2        3        4         5         6         7         8        9        10

o13 : Complex

i14 : numTBBThreads = 1

o14 = 1

i15 : I = ideal I_*;

o15 : Ideal of S

i16 : elapsedTime freeResolution(I, Strategy => Nonminimal)
 -- 2.4508 seconds elapsed

       1      35      241      841      1781      2464      2294      1432      576      135      14
o16 = S  <-- S   <-- S    <-- S    <-- S     <-- S     <-- S     <-- S     <-- S    <-- S    <-- S
                                                                                                  
      0      1       2        3        4         5         6         7         8        9        10

o16 : Complex

Groebner bases (based on a linear algebra method, e.g. Faugere's F4 algorithm, are also parallelized. Note: the MGB Strategy of groebnerBasis is not currently parallelized.

i17 : numTBBThreads = 0

o17 = 0

i18 : S = ZZ/101[a..g]

o18 = S

o18 : PolynomialRing

i19 : I = ideal random(S^1, S^{4:-5});

o19 : Ideal of S

i20 : elapsedTime groebnerBasis(I, Strategy => "F4");
 -- 3.58183 seconds elapsed

              1      108
o20 : Matrix S  <-- S

i21 : numTBBThreads = 1

o21 = 1

i22 : I = ideal I_*;

o22 : Ideal of S

i23 : elapsedTime groebnerBasis(I, Strategy => "F4");
 -- 7.55241 seconds elapsed

              1      108
o23 : Matrix S  <-- S

i24 : numTBBThreads = 10

o24 = 10

i25 : I = ideal I_*;

o25 : Ideal of S

i26 : elapsedTime groebnerBasis(I, Strategy => "F4");
 -- 3.38396 seconds elapsed

              1      108
o26 : Matrix S  <-- S

For Groebner basis computation in associative algebras, ParallelizeByDegree is not relevant. In this case, use numTBBThreads to control the amount of parallelism.

i27 : needsPackage "AssociativeAlgebras"

o27 = AssociativeAlgebras

o27 : Package

i28 : numTBBThreads = 0

o28 = 0

i29 : C = threeDimSklyanin(ZZ/101,{2,3,5},{a,b,c})

o29 = C

o29 : FreeAlgebraQuotient

i30 : I = ideal C

               2                         2                         2
o30 = ideal (5a  + 2b*c + 3c*b, 3a*c + 5b  + 2c*a, 2a*b + 3b*a + 5c )

                ZZ
o30 : Ideal of ---<|a, b, c|>
               101

i31 : elapsedTime NCGB(I, 22);
 -- 0.710418 seconds elapsed

               ZZ            1       ZZ            148
o31 : Matrix (---<|a, b, c|>)  <-- (---<|a, b, c|>)
              101                   101

i32 : I = ideal I_*

               2                         2                         2
o32 = ideal (5a  + 2b*c + 3c*b, 3a*c + 5b  + 2c*a, 2a*b + 3b*a + 5c )

                ZZ
o32 : Ideal of ---<|a, b, c|>
               101

i33 : numTBBThreads = 1

o33 = 1

i34 : elapsedTime NCGB(I, 22);
 -- 1.15747 seconds elapsed

               ZZ            1       ZZ            148
o34 : Matrix (---<|a, b, c|>)  <-- (---<|a, b, c|>)
              101                   101

parallelism in engine computations -- parallelism in engine computations

See also