Macaulay2 / Macaulay2/M2

reduce breaks algorithms

Open
#3,035 11 comments 0 reactions 0 assignees View on GitHub
Core
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.