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.12018 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) -- 2.00975 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.36471 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) -- 4.64712 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.77479 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"); -- 5.28697 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"); -- 11.9272 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"); -- 4.95529 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); -- 1.05342 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.51597 seconds elapsed ZZ 1 ZZ 148 o34 : Matrix (---<|a, b, c|>) <-- (---<|a, b, c|>) 101 101