Computing μ-bases of rational curves and surfaces using polynomial matrix factorization

ABSTRACT

The μ-bases of rational curves/surfaces are newly developed tools which play an important role in connecting parametric forms and implicit forms of the rational curves/surfaces. They provide efficient algorithms to implicitize rational curves/surfaces as well as algorithms to compute singular points of rational curves and to reparametrize rational ruled surfaces. In this paper, we present an efficient algorithm to compute the μbasis of a rational curve/surface by using polynomial matrix factorization followed by a technique similar to Gaussian elimination. The algorithm is shown superior than previous algorithms to compute the μ-basis of a rational curve, and it is the only known algorithm that can rigorously compute the μ-basis of a general rational surface. We present some examples to illustrate the algorithm.

REFERENCES

• 1: Falai Chen , Jianmin Zheng , Thomas W. Sederberg, The mu-basis of a rational ruled surface, Computer Aided Geometric Design, v.18 n.1, p.61-72, Feb. 2001 [doi>10.1016/S0167-8396(01)00012-7]
• 2: Falai Chen , Tom Sederberg, A new implicit representation of a planar rational curve with high order singularity, Computer Aided Geometric Design, v.19 n.2, p.151-167, February 2002 [doi>10.1016/S0167-8396(01)00087-5]
• 3: Falai Chen , Wenping Wang, The µ-basis of a planar rational curve: properties and computation, Graphical Models, v.64 n.6, p.368-381, November 2002 [doi>10.1016/S1524-0703(02)00017-5]
• 4: Falai Chen, Reparametrization of a rational ruled surface using the μ-basis, Computer Aided Geometric Design, v.20 n.1, p.11-17, March 2003 [doi>10.1016/S0167-8396(02)00191-7]
• 5: Falai Chen , Wenping Wang, Revisiting the µ-basis of a rational ruled surface, Journal of Symbolic Computation, v.36 n.5, p.699-716, November 2003 [doi>10.1016/S0747-7171(03)00064-6]
• 6: Falai Chen, David Cox, and Yang Liu, The κ-basis of a rational parametric surface, Journal of Symbolic Computation, Vol.39, 2005, 689--706.
• 7: Falai Chen and Wenping Wang, Computing the singular points of a planar rational curve using the κ-basis, preprint, 2004.
• 8: David Cox, John Little, and Donal O'Shea, Using Algebraic Geometry, New York, Springer-Verlag, 1998.
• 9: David A. Cox , Thomas W. Sederberg , Falai Chen, The moving line ideal basis of planar rational curves, Computer Aided Geometric Design, v.15 n.8, p.803-827, Sept. 1998 [doi>10.1016/S0167-8396(98)00014-4]
• 10: F. R. Gantmacher, Theory of Matrices, New York: Chelsea Publishing Co., 1959.
• 11: John P. Guiver and N. K. Bose, Polynomial matrix primitive factorization over arbitrary coefficient filed and related results, IEEE Transactions on Circuits and Systems, Vol.CAS-29, No.10, 1982, 649--657.
• 12: Zhiping Lin, On syzygy modules for polynomial matrices, Linear Algebra and Its Application, Vol.298, 1999, 73--86.
• 13: Martin Morf, Bernard C. Lévy, and Sun-Yuan Kung, New results in 2-D system theory, Part I: 2-D polynomial matrices, factorization, and coprimeness, Proceedings of the IEEE, Vol.65, No.6, 1977, 861--872.
• 14: Thomas W. Sederberg , Falai Chen, Implicitization using moving curves and surfaces, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.301-308, September 1995 [doi>10.1145/218380.218460]
• 15: Thomas W. Sederberg , Takafumi Saito , Dongxu Qi , Krzysztof S. Klimaszewski, Curve implicitization using moving lines, Computer Aided Geometric Design, v.11 n.6, p.687-706, Dec. 1994 [doi>10.1016/0167-8396(94)90059-0]
• 16: D. C. Youla and G. Gnavi, Notes on n dimensional systems, IEEE Transaction on Circuits and System, Vol.26, 1979, 105--111.
• 17: Fangling Zeng and Falai Chen, Degree reduction of rational curves by κ-basis, Computer Mathematics, Proceedings of the Sixth Asian Symposium (ASCM'2003), Lecture Notes Series on Computing, Vol.10, ed. Ziming Li and William Sit, World Scientific, 2003, 265--275.
• 18: Jianmin Zheng , Thomas W. Sederberg, A direct approach to computing the &mgr;-basis of planar rational curves, Journal of Symbolic Computation, v.31 n.5, p.619-629, May 2001 [doi>10.1006/jsco.2001.0437]

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

General Terms:
Algorithms

Keywords:
μ-basis, GCD extraction algorithm, Hermite form, factorization algorithm, implicitization, primitive, syzygy module