next | previous | forward | backward | up | top | index | toc | Macaulay2 website
EigenSolver :: EigenSolver

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.581877 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:

Authors

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
  • 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.