reduce breaks algorithms
- Dominant language
- Macaulay2
- Stars
- 435
- Forks
- 297
- Avg merge
- 4d 20h
- Merged PRs (30d)
- 11
Description
Since #3013 was merged several pieces of code I use have all ground to a halt. Previously, a change I introduced in #2766 caused `submatrix` to call `reduce`, which slowed down submatrix when the target of a matrix needed a gb computation, even if the computation was trivial (see #2898). Here's an example:
```m2
debug needsPackage "FGLM";
I = cyclic(7, MonomialOrder=>Lex)
I = ideal I_*_{0..5} -- keep only the homogeneous part
R = ring I
v = map(module I, R^1, 0)
v_{}
```
This used to be instantaneous in 1.21.
Now, this happens in many more cases, even when there are no relations involved (which was the initial reasoning in #3012). These simple operations should all be O(1), but induce a gb computation:
```m2
v + v
I_{0}
I_{0}+I_{1}
map(image gens I, , {{1}, {0}, {0}, {0}, {0}, {0}, {0}})
```
To see that these are all caused by calls to `reduce`, try running this and repeat the commands above:
```m2
debug Core
addHook(ReduceHooks, Strategy => Trivial, (tar, rawF) -> rawF)
```
I've had to add the lines above to my `init.m2`, otherwise I can't do anything.
---
Tangentially related to this, here's another method that should be trivial, but actually runs an unnecessary Groebner basis on the target:
```m2
debug needsPackage "FGLM";
I = cyclic(7, MonomialOrder=>Lex)
I = ideal I_*_{0..5}
f = inducedMap(module I, , gens I)
```
Contributor guide
No contributing guide indexed for this repository
Research direction
Start by reproducing the listed Macaulay2 examples with `debug Core` and the `ReduceHooks` workaround. Trace which `reduce` calls trigger unnecessary Groebner-basis computations, including the `inducedMap` example. Done means the simple operations remain correct without performing unnecessary computations.
Written by the indexing model from the issue text.
Assessment
- Domain
- performance
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 42/100