Slowdown computing resolutions in Complexes

[d-torrance]

Compare the following:

i1 : needsPackage "OldChainComplexes";

i2 : S = ZZ/101[x_1..x_9];

i3 : J = ideal vars S;

o3 : Ideal of S

i4 : T = S/J^5;

i5 : elapsedTime res coker presentation T
 -- 2.99913s elapsed

      1      1287      8580      25740      45045      50050      36036      16380      4290      495
o5 = S  <-- S     <-- S     <-- S      <-- S      <-- S      <-- S      <-- S      <-- S     <-- S    <-- 0
                                                                                                           
     0      1         2         3          4          5          6          7          8         9        10

o5 : ChainComplex

versus:

i1 : needsPackage "Complexes"
 -- warning: symbol "GradedModuleMap" in OldChainComplexes.Dictionary is shadowed by a symbol in Complexes.Dictionary
 --   use the synonym OldChainComplexes$GradedModuleMap
 -- warning: symbol "GradedModule" in OldChainComplexes.Dictionary is shadowed by a symbol in Complexes.Dictionary
 --   use the synonym OldChainComplexes$GradedModule
 -- warning: symbol "res" in OldChainComplexes.Dictionary is shadowed by a symbol in Complexes.Dictionary
 --   use one of the synonyms OldChainComplexes$res, OldChainComplexes$resolution
 -- warning: symbol "resolution" in OldChainComplexes.Dictionary is shadowed by a symbol in Complexes.Dictionary
 --   use one of the synonyms OldChainComplexes$res, OldChainComplexes$resolution

o1 = Complexes

o1 : Package

i2 : S = ZZ/101[x_1..x_9];

i3 : J = ideal vars S;

o3 : Ideal of S

i4 : T = S/J^5;

i5 : elapsedTime res coker presentation T
 -- 10.8809s elapsed

      1      1287      8580      25740      45045      50050      36036      16380      4290      495
o5 = S  <-- S     <-- S     <-- S      <-- S      <-- S      <-- S      <-- S      <-- S     <-- S
                                                                                                  
     0      1         2         3          4          5          6          7          8         9

o5 : Complex

This example is based on check(1, "Depth"), which was running out of memory in the cmake-macos builds for #4171.

[mahrud]

The resolution is computed just as fast in the engine, the slowdown is here:

M2/M2/Macaulay2/packages/Complexes/FreeResolution.m2

Lines 204 to 206 in c6aff10

	maps := hashTable for i from 1 to #modules-1 list (
	i => map(modules#(i-1), modules#i, rawResolutionGetMatrix(RO.RawComputation, i))
	);

Previously this happened on demand, whenever a differential was requested:

M2/M2/Macaulay2/packages/OldChainComplexes/chaincomplexes.m2

Lines 213 to 222 in c6aff10

	ChainComplexMap _ ZZ := Matrix => (f,i) -> if f#?i then f#i else (
	de := if f.?degree then f.degree else 0;
	so := (source f)_i;
	ta := (target f)_(i+de);
	if f.?Resolution then (
	gr := f.Resolution;
	p := map(ta,so,rawResolutionGetMatrix(gr.RawComputation,i));
	if p != 0 then f#i = p;
	p)
	else map(ta,so,0))

Now it's being done prematurely.

I think the previous systems makes much more sense (e.g. if I only care about the betti numbers, no need to fill up memory for no purpose). I'm surprised I hadn't noticed this slowdown before.

[ggsmith]

If one is only interested in the Betti numbers, then why would compute the entire resolution? I would be more inclined to ensure that minimalBetti does not slow down in this way. Assuming this method is faster, we should then highlight its use in the documentation and relevant tests.

[mahrud]

That was just a quick example I gave. Here's another: suppose I need only the top non-zero differential in a resolution, which is often much smaller than the intermediate differentials. There's no reason to precompute every differential in the middle until I get to the last one.

(Tangential: minimalBetti doesn't give multigraded betti numbers, nor does it work over QQ.)