Macaulay2 / Macaulay2/M2

computation of ranks of many submatrices

Open
#4,182 0 comments 0 reactions 0 assignees View on GitHub
good beginners' project
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.