EigenSolver -- polynomial system solver via eigen-computations

Description

This package implements a solver for zero-dimensional polynomial systems based on eigenvalue/eigenvector computations. The theoretical basis for this is Stickelberger's Theorem (cf. [1, Theorem 2.6], also [2]), which states that if I is a zero-dimensional ideal in a polynomial ring $R$ over an algebraically closed field $k$, then the points of V(I) can be obtained as eigenvalues of multiplication matrices corresponding to variables, on the finite-dimensional $k$-vector space $R/I$.

Since the main solving is done via linear algebra, this solver can be significantly quicker than other solvers performing nonlinear computations. However, a Grobner basis of the ideal I is still needed, e.g. in order to obtain the sizes of the multiplication matrices.

i1 : needsPackage "ExampleSystems"

o1 = ExampleSystems

o1 : Package

i2 : I = ideal cyclic(6, QQ)

o2 = ideal (a + b + c + d + e + f, a*b + b*c + c*d + d*e + a*f + e*f, a*b*c +
     ------------------------------------------------------------------------
     b*c*d + c*d*e + a*b*f + a*e*f + d*e*f, a*b*c*d + b*c*d*e + a*b*c*f +
     ------------------------------------------------------------------------
     a*b*e*f + a*d*e*f + c*d*e*f, a*b*c*d*e + a*b*c*d*f + a*b*c*e*f +
     ------------------------------------------------------------------------
     a*b*d*e*f + a*c*d*e*f + b*c*d*e*f, a*b*c*d*e*f - 1)

o2 : Ideal of QQ[a..f]

i3 : elapsedTime sols = zeroDimSolve I;
 -- 0.222511 seconds elapsed

i4 : #sols -- 156 solutions

o4 = 156

The authors would like to acknowledge the June 2020 Macaulay2 workshop held virtually at Warwick, where this package was first developed.

References:

[1] Sturmfels, Bernd. Solving systems of polynomial equations. No. 97. American Mathematical Soc., 2002
[2] Cox, David A. Stickelberger and the Eigenvalue Theorem. https://arxiv.org/abs/2007.12573

Authors

Laurent Busé <[email protected]>
Justin Chen <[email protected]>
Kisun Lee <[email protected]>
Anton Leykin <[email protected]>
Tomas Pajdla <[email protected]>
Erika Pirnes <[email protected]>

Version

This documentation describes version 0.1 of EigenSolver.

Source code

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

Exports

Functions and commands
- zeroDimSolve -- zero-dimensional polynomial system solver
Methods
- zeroDimSolve(Ideal) -- see zeroDimSolve -- zero-dimensional polynomial system solver
Symbols
- Basis -- see zeroDimSolve -- zero-dimensional polynomial system solver
- Multiplier -- see zeroDimSolve -- zero-dimensional polynomial system solver

For the programmer

The object EigenSolver is a package.