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.52891 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:
This documentation describes version 0.1 of EigenSolver.
The source code from which this documentation is derived is in the file EigenSolver.m2.
The object EigenSolver is a package.