Border bases of positive dimensional polynomial ideals

ABSTRACT

The border bases were generalized to general polynomial ideals (zero and positive dimensional ideals). A new algorithm to compute a border basis for a given polynomial system w.r.t. a specified term order was presented. This algorithm computes a border basis, as well as a reduced Gröbner basis for the polynomial system. A particular eigenvector method to find some components of positive dimensional polynomial systems was sketched too.

REFERENCES

• 1: Hans J. Stetter, Numerical Polynomial Algebra, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2004
• 2: W. Auzinger, H. J. Stetter. An Elimination Algorithm for the Computation of all Zeros of a System of Multivariate Polynomial Equations. In: Conf. in Numerical Analysis, ISNM80, Birkhäuser, Basel, 1988, 11--30.
• 3: H. Michael Möller , Ralf Tenberg, Multivariate polynomial system solving using intersections of Eigenspaces, Journal of Symbolic Computation, v.32 n.5, p.513-531, November 2001 [doi>10.1006/jsco.2001.0476]
• 4: Bernard Mourrain, A New Criterion for Normal Form Algorithms, Proceedings of the 13th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.430-443, November 15-19, 1999
• 5: H. J. Stetter. Proposal for the Algorithmic Use of the BKK-Number in the Algebraic Reduction of a 0-dimensional Polynomial System. Symbolic-Numeric Computation (D. M. Wang and L. H. Zhi eds), Birkhäuser, Basel Boston, 2007.
• 6: Bernard Mourrain , Philippe Trebuchet, Generalized normal forms and polynomial system solving, Proceedings of the 2005 international symposium on Symbolic and algebraic computation, p.253-260, July 24-27, 2005, Beijing, China [doi>10.1145/1073884.1073920]
• 7: A. Kehrein, M. Kreuzer. Characterization of Border Basis. Journal of Pure and Applied Algebra, 2005, 196: 251--270.
• 8: A. Kehrein, M. Kreuzer, L. Robbiano. An Algebraist's View on Border Basis. In: Solving Polynomial Equations. Foundation, Algorithms, and Applications (A. Dickenstein and I. Z. Emiris eds), Springer, 2005, 169--202.
• 9: Y. F. Chen, X. S. Gao. Involutive Directions and New Involutive Directions. Computers and Mathematics with Application, 2001, 41 (7-8): 945--956.
• 10: A. Kehrein, M. Kreuzer. Computing Border Basis. Journal of Pure and Applied Algebra, 2006, 205: 279--295.
• 11: Y. Z. Huang, W. D. Wu. A Modified Version of An Algorithm for Solving Polynomial Systems. Academia Sinica MM Research Preprint, 1990, 5: 23--29.
• 12: K. Huang, Y. Z. Huang, W. D. Wu. Matrix Eigenproblem Approach for a Class of Positive Dimensional Multivariate Polynomial System Solving. Academia Sinica MM Research Preprint, 1998, 16: 59--66.
• 13: J. Faugère. A New Efficient Algorithm for Computing Gröbner Bases (F4). Journal of Pure and Applied Algebra, 1999, 139: 61--88.
• 14: Jean Charles Faugère, A new efficient algorithm for computing Gröbner bases without reduction to zero (F₅), Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.75-83, July 07-10, 2002, Lille, France [doi>10.1145/780506.780516]
• 15: B. Buchberger. Gröbner Bases: An Algorithmic Nethod in Polynomial Ideal Theory, In: (Bose, N.K. ed.) Progress. Directions and Open Problems in Multidimensional Systems Theory. Dordrecht: Reidel Publ. Comp, 1985, 184--232.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Systems of equations

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms

Keywords:
algorithm, border basis, polynomial ideal