Macaulay2 » Documentation
Packages » Macaulay2Doc :: parallelism in engine computations
next | previous | forward | backward | up | index | toc

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 numTBBThreads 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
 -- 2.379s 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)
 -- 2.07761s 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.28074s 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.22268s 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.2102s 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.31791s 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");
 -- 6.04823s 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");
 -- 2.80436s 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);
 -- .702528s 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.02134s elapsed

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

See also