Computing the topology of a real algebraic plane curve whose equation is not directly available

ABSTRACT

We present a collection of methods and tools for computing the topology of real algebraic plane curves de .ned by bivariate polynomial equations that are known at certain values or easy to evaluate, but whose explicit description is not available.The principal techniques used are the reduction of the computation of the real roots of the discriminant to a sparse generalized eigenvalue problem,the use of the structure of the nullspace of the classical Bezoutian, and its description in terms of the Lagrange Basis.

REFERENCES

• 1: Amirhossein Amiraslani, New algorithms for matrices, polynomials and matrix polynomials, University of Western Ontario, Ont., Canada, 2006
• 2: A. Amiraslani, D. A. Aruliah and R. M. Corless. The Rayleigh quotient iteration for generalized companion matrix pencils. Submitted, 2006.
• 3: A. Amiraslani, R. M. Corless and P. Lancaster. Linearization of matrix polynomials expressed in polynomial bases. Submitted, 2006.
• 4: D. A. Aruliah, R. M. Corless, L. Gonzalez-Vega and A. Shakoori. Geometric Applications of the Bezout Matrix in the Bivariate Tensor-Product Lagrange basis. In these proceedings, 2007.
• 5: D. A. Aruliah, R. M. Corless, L. Gonzalez-Vega and A. Shakoori. Companion Matrix Pencils and Bezout Matrices for Hermite Interpolants. In these proceedings, 2007.
• 6: A. Amiraslani. Dividing polynomials when you only know their values. In Proceedings EACA, Laureano Gonzalez-Vega and Tomas Recio editors, pages 5--10, June 2004.
• 7: Dennis S. Arnon , Scott McCallum, A polynomical-time algorithm for the topological type of a real algebraic curve, Journal of Symbolic Computation, v.5 n.1-2, p.213-236, February/April 1988 [doi>10.1016/S0747-7171(88)80013-0]
• 8: C. L. Bajaj , C. M. Hoffman , R. E. Lynch , J. E. H. Hopcroft, Tracing surface intersections, Computer Aided Geometric Design, v.5 n.4, p.285-307, Nov. 1988 [doi>10.1016/0167-8396(88)90010-6]
• 9: Dario Bini , Victor Y. Pan, Polynomial and matrix computations (vol. 1): fundamental algorithms, Birkhauser Verlag, Basel, Switzerland, 1994
• 10: L. Bus, H. Khalil and B. Mourrain. Resultant-Based Method for Plane Curves Intersection Problems. Lecture Notes in Computer Science 3718, 75--92, 2005.
• 11: Paola Cellini , Patrizia M. Gianni , Carlo Traverso, Algorithms for the Shape of Semialgebraic Sets. A New Approach, Proceedings of the 9th International Symposium, on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.1-18, October 07-11, 1991
• 12: R. M. Corless. Generalized companion matrices in the Lagrange basis. In Proceedings EACA, L. Gonzalez-Vega and T. Recio editors, pages 317--322, June 2004.
• 13: R. M. Corless, N. Rezvani and A. Amiraslani. Pseudospectra of matrix polynomials that are expressed in alternative bases. Mathematics and Computer Science, (in press)2007.
• 14: F. Cucker, L. Gonzalez-Vega and F. Rosello. On algorithms for real algebraic plane curves. In Effective Methods in Algebraic Geometry, Progress in Mathematics 94, 63--88, Birkhausser, 1991.
• 15: James W. Demmel, Applied numerical linear algebra, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997
• 16: I. G. Gohberg, P. Lancaster, and L. Rodman. Matrix polynomials. Academic Press, 1982.
• 17: Ronald L. Graham , Donald E. Knuth , Oren Patashnik, Concrete Math, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 18: Arno Eigenwillig , Michael Kerber , Nicola Wolpert, Fast and exact geometric analysis of real algebraic plane curves, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada [doi>10.1145/1277548.1277570]
• 19: H. Feng. Decomposition and computation of the topology of plane real algebraic curves . PhDthesis, The Royal Institute of Technology, Stockholm, Sweden, 1992.
• 20: M. Fioravanti and L. Gonzalez-Vega. On the geometric extraneous components appearing when using implicitization. In Mathematical Methods for Curves and Surfaces, pages 157--168. Nashboro Press, 2005.
• 21: P. Gianni and C. Traverso. Shape determination of real curves and surfaces. Ann. Univ. Ferrara Sez VII Sec. Math., vol. XXIX, 87--109, 1983.
• 22: Laureano Gonzalez-Vega , Ioana Necula, Efficient topology determination of implicitly defined algebraic plane curves, Computer Aided Geometric Design, v.19 n.9, p.719-743, December 2002 [doi>10.1016/S0167-8396(02)00167-X]
• 23: Laureano Gonzalez-Vega, Implicitization of parametric curves and surfaces by using multidimensional Newton formulae, Journal of Symbolic Computation, v.23 n.2-3, p.137-151, Feb./March 1997 [doi>10.1006/jsco.1996.0080]
• 24: Laureano González-Vega , M'Hammed El Kahoui, An improved upper complexity bound for the topology computation of a real algebraic plane curve, Journal of Complexity, v.12 n.4, p.527-544, Dec. 1996 [doi>10.1006/jcom.1996.0032]
• 25: G. Heinig and K. Rost. Algebraic methods for Toeplitz-like matrices and operators. OperatorTheory: Advances and Applications, 13, Birkhaüser, 1984.
• 26: U. Helmke and P. A. Fuhrmann. Bezoutians. Linear Algebra and Its Applications 122/123/124, 1039--1097, 1989.
• 27: Hoon Hong, An efficient method for analyzing the topology of plane real algebraic curves, Mathematics and Computers in Simulation, v.42 n.4-6, p.571-582, Nov. 1996
• 28: J. Keyser, T. Culver, D. Manocha and S. Krishnan. Efficient and Exact Manipulation of Algebraic Points and Curves. Computer Aided Design 32, 649--662, 2000.
• 29: Dinesh Manocha , James Demmel, Algorithms for intersecting parametric and algebraic curves I: simple intersections, ACM Transactions on Graphics (TOG), v.13 n.1, p.73-100, Jan. 1994 [doi>10.1145/174462.174617]
• 30: Dinesh Manocha , James Demmel, Algorithms for intersecting parametric and algebraic curves II: multiple intersections, Graphical Models and Image Processing, v.57 n.2, p.81-100, March 1995 [doi>10.1006/gmip.1995.1010]
• 31: M.-F. Roy. Basic algorithms in real algebraic geometry and their complexity:from Sturm's theorem to the existential theory of reals. In Lectures in real geometry, 1--67, de Gruyter Exp. Math., 23, de Gruyter, 1996.
• 32: M.-F. Roy and A. Szpirglas. Complexity of the computation of cylindrical decomposition and topology of real algebraic curves using Thom's Lemma. Lecture Notes in Mathematics 1420, 223--236, Springer-Verlag, 1990.
• 33: T. Sakkalis. The topological configuration of a real algebraic curve. Bulletin of the Australian Mathematical Society 43, 37--50, 1991.
• 34: Raimund Seidel , Nicola Wolpert, On the exact computation of the topology of real algebraic curves, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064111]
• 35: A. Shakoori. The Bezout matrix in the Lagrange basis. In Proceedings EACA, Laureano Gonzalez-Vega and Tomas Recio editors, 295--299, June 2004.
• 36: Françoise Tisseur , Nicholas J. Higham, Structured Pseudospectra for Polynomial Eigenvalue Problems, with Applications, SIAM Journal on Matrix Analysis and Applications, v.23 n.1, p.187-208, 2001 [doi>10.1137/S0895479800371451]

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.4 Applications

General Terms:
Algorithms, Experimentation