computation of ranks of many submatrices
- Dominant language
- Macaulay2
- Stars
- 435
- Forks
- 297
- Avg merge
- 4d 20h
- Merged PRs (30d)
- 11
Description
In many situations, one needs to compute ranks of many column-submatrices of a given matrix (e.g. for a matrix with 20 columns there are ~2^20 = ~1 million options), which would be slightly improved if the matrix was put in row echelon form first.
However, a naive `apply(subsets numcols M, cols -> rank M_cols)` approach is still wasteful because of how much time is wasted on computing submatrices!
1. Implement a specialized `rank(Matrix, List)` operation, so we could instead call `apply(subsets numcols M, rank_M)`
2. I'm not an expert in optimized linear algebra operations, but I feel like there is more one could do here. This might be a nice exercise + project for someone to implement a very specialized `ranks(Matrix, List)` (note, rank**s**) which takes all the subsets and partitions them by rank maybe.
Several places where this is useful:
```m2
./NormalToricVarieties/ToricVarieties.m2: all (max X, sigma -> #sigma == rank rayGenMatrix_sigma)
./NormalToricVarieties/ToricVarieties.m2: #sigma === rank rayGenMatrix_sigma and
./NormalToricVarieties/ToricVarieties.m2: if #sigma === rank rayMatrix_sigma then continue;
./NormalToricVarieties/ToricVarieties.m2: if all (coneList', tau -> #tau == rank rayMatrix_sigma) then (
./NormalToricVarieties/ToricVarieties.m2: k := position (coneList, sigma -> #sigma =!= rank rayMatrix_sigma);
./NormalToricVarieties/ToricVarieties.m2: faceTable#t = d - rank R_(positions (s, i -> member (i,t)));
./Polyhedra/core/cone/properties.m2: if (rank raysC_(toList newFace)) + ldim == d-2-i then (
./Points.m2: dupcols := select(L,i->rank(N_{thiscol,i})<2);
./Points.m2: dupcols := select(L,i->rank(N_{thiscol,i})<2);
./SlackIdeals.m2: if rank(S_fl) == d+1 then true else false
./SlackIdeals.m2: if rank(S_fl) == d+1 then true else false
./MultigradedImplicitization.m2: if rank(J_supp) == #supp then(
```
Contributor guide
No contributing guide indexed for this repository
Research direction
Start by examining the existing rank operation and the listed call sites in NormalToricVarieties/ToricVarieties.m2, Polyhedra/core/cone/properties.m2, Points.m2, SlackIdeals.m2, and MultigradedImplicitization.m2. Compare the cost of constructing column-submatrices with the requested rank(Matrix, List) interface. Done means the specialized operation supports the stated subset calls; the optional ranks(Matrix, List) optimization would require a defined algorithm and validation.
Written by the indexing model from the issue text.
Assessment
- Domain
- tooling
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 48/100