FastMinors -- faster linear algebra, especially for computation of minors

Description

FastMinors is a package for computing relevant minors (determinants of submatrices) of matrices of polynomial functions quickly

This package provides functionality for doing certain linear algebra operations over rings quickly. There is also some multithreaded capability which is disabled by default. Note this package was previously called FastLinAlg.

Tutorials:
There are tutorials on how to use various strategies and options in FastMinorsStrategyTutorial and RegularInCodimensionTutorial which we recommend the user explore if they are interested in the more advanced features of the package.

Useful functions:

chooseGoodMinors Tries to find interesting minors of a matrix.
isRankAtLeast Tries to show that a matrix has rank at least a given number by looking at submatrices
regularInCodimension checks whether a ring is regular in codimension n, but doesn't return false.
projDim checks the projective dimension of a module and may give better answers than pdim in the case that R is not homogeneous
recursiveMinors provides a different strategy for computing minors of a matrix. It is a cofactor strategy where the determinants of smaller minors are stored.
isCodimAtLeast provides a way for finding lower bounds for the codimension of an ideal, without actually computing the codimension.

Many of these functions have extensive options for finetuning their behavior, for instance by controlling how submatrices are chosen. See the documentation for StrategyDefault

Acknowledgements:

The authors would like to thank the anonymous referee, David Eisenbud, Eloisa Grifo, and Srikanth Iyengar for useful conversations and comments on the development of this package.

Boyana Martinova received funding from the University of Utah Mathematics Department REU program and from the ACCESS program at the University of Utah, while developing this package.
Marcus Robinson received funding from the NSF RTG grant 1246989 while developing this package.
Karl Schwede received funding from NSF grant 1801849 and a fellowship from the Simons Foundation while developing this package.
Yuhui (Wei) Yao received funding from the University of Utah Mathematics Department REU program, while developing this package

Authors

Certification

Version 1.2.6 of this package was accepted for publication in volume 13 of Journal of Software for Algebra and Geometry on 2023-05-08, in the article FastMinors package for Macaulay2. That version can be obtained from the journal or from the Macaulay2 source code repository.

Version

This documentation describes version 1.2.6 of FastMinors.

Source code

The source code from which this documentation is derived is in the file FastMinors.m2.

Exports

Functions and commands
- chooseGoodMinors -- returns an ideal generated by interesting minors in a matrix
- chooseRandomSubmatrix -- returns coordinates for a random submatrix
- chooseSubmatrixLargestDegree -- returns coordinates for higher degree submatrix of a matrix
- chooseSubmatrixSmallestDegree -- returns coordinates for low degree submatrix of a matrix
- getSubmatrixOfRank -- tries to find a submatrix of the given rank
- isCodimAtLeast -- returns true if we can quickly see whether the codim is at least a given number
- isDimAtMost -- returns true if we can quickly see whether the dim is at most a given number
- isRankAtLeast -- determines if the matrix has rank at least a number
- projDim -- finds an upper bound for the projective dimension of a module
- recursiveMinors -- uses a recursive cofactor algorithm to compute the ideal of minors of a matrix
- regularInCodimension -- attempts to show that the ring is regular in codimension n
- reorderPolynomialRing -- produces an isomorphic polynomial ring with a different, randomized, monomial order
Methods
- chooseGoodMinors(ZZ,ZZ,Matrix) -- see chooseGoodMinors -- returns an ideal generated by interesting minors in a matrix
- chooseGoodMinors(ZZ,ZZ,Matrix,Ideal) -- see chooseGoodMinors -- returns an ideal generated by interesting minors in a matrix
- chooseRandomSubmatrix(ZZ,Matrix) -- see chooseRandomSubmatrix -- returns coordinates for a random submatrix
- chooseSubmatrixLargestDegree(ZZ,Matrix) -- see chooseSubmatrixLargestDegree -- returns coordinates for higher degree submatrix of a matrix
- chooseSubmatrixSmallestDegree(ZZ,Matrix) -- see chooseSubmatrixSmallestDegree -- returns coordinates for low degree submatrix of a matrix
- getSubmatrixOfRank(ZZ,Matrix) -- see getSubmatrixOfRank -- tries to find a submatrix of the given rank
- isCodimAtLeast(ZZ,Ideal) -- see isCodimAtLeast -- returns true if we can quickly see whether the codim is at least a given number
- isDimAtMost(ZZ,Ideal) -- see isDimAtMost -- returns true if we can quickly see whether the dim is at most a given number
- isRankAtLeast(ZZ,Matrix) -- see isRankAtLeast -- determines if the matrix has rank at least a number
- projDim(Module) -- see projDim -- finds an upper bound for the projective dimension of a module
- recursiveMinors(ZZ,Matrix) -- see recursiveMinors -- uses a recursive cofactor algorithm to compute the ideal of minors of a matrix
- regularInCodimension(ZZ,Ring) -- see regularInCodimension -- attempts to show that the ring is regular in codimension n
- reorderPolynomialRing(Symbol,Ring) -- see reorderPolynomialRing -- produces an isomorphic polynomial ring with a different, randomized, monomial order
Symbols
- PeriodicCheckFunction -- see chooseGoodMinors -- returns an ideal generated by interesting minors in a matrix
- DetStrategy -- DetStrategy is a strategy for allowing the user to choose how determinants (or rank), is computed
- Rank -- see DetStrategy -- DetStrategy is a strategy for allowing the user to choose how determinants (or rank), is computed
- Recursive -- see DetStrategy -- DetStrategy is a strategy for allowing the user to choose how determinants (or rank), is computed
- FastMinorsStrategyTutorial -- How to use and construct strategies for selecting submatrices in various functions
- SPairsFunction -- see isCodimAtLeast -- returns true if we can quickly see whether the codim is at least a given number
- MaxMinors -- an option to control depth of search
- MinDimension -- an option for projDim
- Modulus -- an option for regularInCodimension
- PointOptions -- options to pass to functions in the package RandomPoints
- MinorsCache -- see recursiveMinors -- uses a recursive cofactor algorithm to compute the ideal of minors of a matrix
- CodimCheckFunction -- see regularInCodimension -- attempts to show that the ring is regular in codimension n
- MinMinorsFunction -- see regularInCodimension -- attempts to show that the ring is regular in codimension n
- UseOnlyFastCodim -- see regularInCodimension -- attempts to show that the ring is regular in codimension n
- RegularInCodimensionTutorial -- A tutorial for how to use the advanced options of the regularInCodimension function
- GRevLexLargest -- see StrategyDefault -- strategies for choosing submatrices
- GRevLexSmallest -- see StrategyDefault -- strategies for choosing submatrices
- GRevLexSmallestTerm -- see StrategyDefault -- strategies for choosing submatrices
- LexLargest -- see StrategyDefault -- strategies for choosing submatrices
- LexSmallest -- see StrategyDefault -- strategies for choosing submatrices
- LexSmallestTerm -- see StrategyDefault -- strategies for choosing submatrices
- Points -- see StrategyDefault -- strategies for choosing submatrices
- Random -- see StrategyDefault -- strategies for choosing submatrices
- RandomNonzero -- see StrategyDefault -- strategies for choosing submatrices
- Threads -- an option for various functions
Other things
- StrategyCurrent -- strategies for choosing submatrices
- StrategyDefault -- strategies for choosing submatrices
- StrategyDefaultNonRandom -- strategies for choosing submatrices
- StrategyDefaultWithPoints -- strategies for choosing submatrices
- StrategyGRevLexSmallest -- strategies for choosing submatrices
- StrategyLexSmallest -- strategies for choosing submatrices
- StrategyPoints -- strategies for choosing submatrices
- StrategyRandom -- strategies for choosing submatrices

For the programmer

The object FastMinors is a package.