Monomial bases and polynomial system solving (extended abstract)

ABSTRACT

This paper addresses the problem of efficient construction of monomial bases for the coordinate rings of zero-dimensional varieties.

REFERENCES

• 1: E. Anderson , Z. Bai , C. Bischof , J. Demmel , J. Dongarra , J. Du Croz , A. Greenbaum , S. Hammarling , A. McKenney , S. Ostrouchov , D. Sorensen, LAPACK's user's guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 2: W. Auzinger and H.J. Stett.er. An Elimina.tion Algorithm for the Computation of all Zeros of a. Syst, em of Mult.ivariate Polynomial Equations. In Proc. Intern. Co,f. on Numerzcal Math., Intern. Series of Numerzcal Math., 86, pages 12-30. Birkh/iuser Verlag, Basel, 1988.
• 3: Jörgen Backelin , Ralf Fröberg, How we proved that there are exactly 924 cyclic 7-roots, Proceedings of the 1991 international symposium on Symbolic and algebraic computation, p.103-111, July 15-17, 1991, Bonn, West Germany [doi>10.1145/120694.120708]
• 4: D.N. Bernstein. The Number of Roots of a. System of Equations. Funct. Anal. and Appl., 9(2):183- 185,197.5.
• 5: Göran Björck , Ralf Fröberg, A faster way to count the solutions of inhomogeneous systems of algebraic equations, with applications to cyclic n-roots, Journal of Symbolic Computation, v.12 n.3, p.329-336, Sept. 1991 [doi>10.1016/S0747-7171(08)80153-8]
• 6: G. BjSrck and R. FrSberg. Methods to "Divide out" certain Solutions from Systems of Algebraic Equa.t, ions, Applied to Find a.ll Cyclic 8-Roots. Manuscript, Dept. of Math., Stockholm University, 1994.
• 7: John Canny, Generalised characteristic polynomials, Journal of Symbolic Computation, v.9 n.3, p.241-250, March 1990 [doi>10.1016/S0747-7171(08)80012-0]
• 8: J. Canny, 1993. Personal Communication.
• 9: John F. Canny , Ioannis Z. Emiris, An Efficient Algorithm for the Sparse Mixed Resultant, Proceedings of the 10th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.89-104, May 10-14, 1993
• 10: Ioannis Emiris , John Canny, A practical method for the sparse resultant, Proceedings of the 1993 international symposium on Symbolic and algebraic computation, p.183-192, July 06-08, 1993, Kiev, Ukraine [doi>10.1145/164081.164122]
• 11: O. D. Faugeras , Steve Maybank, Motion from point matches: multiple of solutions, International Journal of Computer Vision, v.4 n.3, p.225-246, Jun. 1990 [doi>10.1007/BF00054997]
• 12: J.-C. Faugbre, 1994. Personal Communication.
• 13: B.K.P. Horn. Relative Orientation Revisited. Opt. Soc. Am., 8(10):1630-1638, October 1991.
• 14: T.W. Hungerford. Algebra. Graduate Texts in Mathematics, 73. Springer-Verlag, New York, 1974.
• 15: N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, v.4 n.4, p.373-395, Dec. 1984 [doi>10.1007/BF02579150]
• 16: D. Lazard. R~solution des syst~mes d'~quations alg@briques. Theor. Comp. Sc~.cncc, 15:77-110, 1981.
• 17: Dinesh Manocha , John F. Canny, Multipolynomial resultants and linear algebra, Papers from the international symposium on Symbolic and algebraic computation, p.158-167, July 27-29, 1992, Berkeley, California, United States [doi>10.1145/143242.143300]
• 18: D. Manocha and J. Canny. Real Time Inverse Kinematics of General 6R Manipulators. In Proc. IEEE Intern. Conf. Robot,cs and Aut.omalion, pages 383- 389, Nice, May 1992.
• 19: H. Michael Möller, Systems of Algebraic Equations Solved by Means of Endomorphisms, Proceedings of the 10th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.43-56, May 10-14, 1993
• 20: B. Mourrain, The 40 “generic” positions of a parallel robot, Proceedings of the 1993 international symposium on Symbolic and algebraic computation, p.173-182, July 06-08, 1993, Kiev, Ukraine [doi>10.1145/164081.164120]
• 21: P. Pedersen and B. Sturmfels. Product Formulas for Resultants and Chow Forms. Math. Ze,~schrifl, 214:377-396, 1993.
• 22: P. Pedersen and B. Sturmfels. Mixed Monomial Bases. In MEGA '9~, April 1994. To Appear.
• 23: James Renegar, On the computational complexity and geometry of the first-order theory of the reals. Par I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals, Journal of Symbolic Computation, v.13 n.3, p.255-299, March 1992
• 24: Bernd Sturmfels, On the Newton Polytope of the Resultant, Journal of Algebraic Combinatorics: An International Journal, v.3 n.2, p.207-236, April 1994 [doi>10.1023/A:1022497624378]
• 25: B. Sturmfels and A. Zelevinsky. Multigraded Resultants of Sylvester Type. J. of Algebra, 163(1):115- 127, 1994.
• 26: B.L. van der Waerden. Modern Algebra. Ungar Publishing Co., New York, 3rd edition, 1950.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices; Computations on polynomials

General Terms:
Algorithms, Theory, Verification