# 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.709548 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

• Laurent Busé
• Justin Chen
• Kisun Lee
• Anton Leykin
• Tomas Pajdla
• Erika Pirnes

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