Solving projective complete intersection faster

ABSTRACT

In this paper, we present a new method for solving square polynomial systems with no zero at infinity. We analyze its complexity, which indicates substantial improvements, compared with the previously known methods for solving such systems. We describe a framework for symbolic and numeric computations, developed in C++, in which we have implemented this algorithm. We mention the techniques that are involved in order to build efficient codes and compare with existing softwares. We end by some applications of this method, considering in particular an autocalibration problem in Computer Vision and an identification problem in Signal Processing, and report on the results of our first implementation.

REFERENCES

• 1: Anderson , Bai , Bischof , Demmel , Dongarra , DuCroz , Greenbaum , Hammarling , McKenney , Sorenson, LAPACK Working Note 20: A Portable Linear Algebra Library For High-Performance Computers, University of Tennessee, Knoxville, TN, 1990
• 2: Philippe Aubry , Daniel Lazard , Marc Moreno Maza, On the theories of triangular sets, Journal of Symbolic Computation, v.28 n.1-2, p.105-124, July/Aug. 1999 [doi>10.1006/jsco.1999.0269]
• 3: Auzinger, W., and Stetter, H. An elimination algorithm for the computation of all zeros of a system of multivariate polynomial equations. In Prec. Intern. Conf. on Numerical Math. (1988), vol. 86 of Int. Series of Numerical Math, Birkh~user Verlag, pp. 12-30.
• 4: Thomas Becker , Volker Weispfenning , Heinz Kredel, Gro¨bner bases: a computational approach to commutative algebra, Springer-Verlag, London, 1993
• 5: Laurent Bernardin , Bruce Char , Erich Kaltofen, Symbolic computation in Java: an appraisement, Proceedings of the 1999 international symposium on Symbolic and algebraic computation, p.237-244, July 28-31, 1999, Vancouver, British Columbia, Canada [doi>10.1145/309831.309946]
• 6: Didier Bondyfalat , Bernard Mourrain , Victor Y. Pan, Controlled iterative methods for solving polynomial systems, Proceedings of the 1998 international symposium on Symbolic and algebraic computation, p.252-259, August 13-15, 1998, Rostock, Germany [doi>10.1145/281508.281629]
• 7: 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
• 8: Comon, P., Grellier, O., and Mourrain, B. Blind channel identification with MSK inputs. In Asilemar Conference (Pacific Grove, California, November 1-4 1998). Invited session.
• 9: Cox, D., Little, J., and O'Shea, D. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Undergraduate Texts in Mathematics. Springer Verlag, New York, 1992.
• 10: James W. Demmel , John R. Gilbert , Xiaoye S. Li, An Asynchronous Parallel Supernodal Algorithm for Sparse Gaussian Elimination, SIAM Journal on Matrix Analysis and Applications, v.20 n.4, p.915-952, Oct. 1999 [doi>10.1137/S0895479897317685]
• 11: Angel Díaz , Erich Kaltofen, FOXBOX: a system for manipulating symbolic objects in black box representation, Proceedings of the 1998 international symposium on Symbolic and algebraic computation, p.30-37, August 13-15, 1998, Rostock, Germany [doi>10.1145/281508.281538]
• 12: Ioannis Z. Emiris , Bernard Mourrain, Matrices in elimination theory, Journal of Symbolic Computation, v.28 n.1-2, p.3-44, July/Aug. 1999 [doi>10.1006/jsco.1998.0266]
• 13: Olivier Faugeras, Three-dimensional computer vision: a geometric viewpoint, MIT Press, Cambridge, MA, 1993
• 14: Faug~re J.C. A new efficient algorithm for computing GrSbner Basis (F4). J. of Pure and Applied Algebra 139 (1999), 61-88.
• 15: Gelfand, I., Kapranov, M., and Zelevinsky, A. Discriminants, Resultants and Multidimensional Determinants. Boston, BirkhSuser, 1994.
• 16: Marc Giusti , Grégoire Lecerf , Bruno Salvy, A Gröbner free alternative for polynomial system solving, Journal of Complexity, v.17 n.1, p.154-211, March 1, 2001 [doi>10.1006/jcom.2000.0571]
• 17: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 18: Deepak Kapur , Tushar Saxena, Comparison of various multivariate resultant formulations, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.187-194, July 10-12, 1995, Montreal, Quebec, Canada [doi>10.1145/220346.220370]
• 19: Kruppa, E. Zur Ermittlung eines Objektes aus zwei Perspektiven mit innere Orientierung. Sitz.-Ber. Akad. Wiss., Wien, Math.-Naturw. K1. Abt. IIa, 122 (1913), 1939-1948.
• 20: Macaulay, F. Some formulae in elimination. Proc. London Math. Soc. 1, 33 (1902), 3-27.
• 21: 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
• 22: B. Mourrain, Computing the isolated roots by matrix methods, Journal of Symbolic Computation, v.26 n.6, p.715-738, Dec. 1998 [doi>10.1006/jsco.1998.0236]
• 23: 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
• 24: Bernard Mourrain , Victor Y. Pan, Multivariate polynomials, duality, and structured matrices, Journal of Complexity, v.16 n.1, p.110-180, March 2000 [doi>10.1006/jcom.1999.0530]
• 25: David R. Musser , Atul Saini, The STL Tutorial and Reference Guide: C++ Programming with the Standard Template Library, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1995
• 26: Pozo, R. Tnt, templates for numerical toolkit, 1997. http://math, nist. gov/tnt/.
• 27: Rouillier, F. Solving zero-dimensional polynomial systems throuhg Rational Univariate Representation. App. Alg. in Eng. Com. Comp. 9, 5 (1999), 433-461.
• 28: Siek, J, G. A Modern Framework for Portable High Performance Numerical Linear Algebra. PhD thesis, Univ. Notre Dame, Indiana, 1999.
• 29: Veldhuizen, T. Blitz++, 1999. http://monet, uwaterloo, ca/blitz/.
• 30: Veldhuizen~ T.~ and Cannon~ D. Active Libaries: Rethinking the roles of compilers and libraries. In SIAM Workshop on Object Oriented Methods for Inter-Operable Scientific and Engineering Computing (1998).

INDEX TERMS

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

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

General Terms:
Algorithms, Performance