Recursive Polynomial Remainder Sequence and the Nested Subresultants

  • Akira Terui
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3718)


We give two new expressions of subresultants, nested subresultant and reduced nested subresultant, for the recursive polynomial remainder sequence (PRS) which has been introduced by the author. The reduced nested subresultant reduces the size of the subresultant matrix drastically compared with the recursive subresultant proposed by the authors before, hence it is much more useful for investigation of the recursive PRS. Finally, we discuss usage of the reduced nested subresultant in approximate algebraic computation, which motivates the present work.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Knuth, D.: The Art of Computer Programming, 3rd edn. Seminumerical Algorithms, vol. 2. Addison-Wesley, Reading (1998)Google Scholar
  2. 2.
    Collins, G.E.: Subresultants and Reduced Polynomial Remainder Sequences. J. ACM 14, 128–142 (1967)zbMATHCrossRefGoogle Scholar
  3. 3.
    Brown, W.S., Traub, J.F.: On Euclid’s Algorithm and the Theory of Subresultants. J. ACM 18, 505–514 (1971)zbMATHCrossRefMathSciNetGoogle Scholar
  4. 4.
    Loos, R.: Generalized polynomial remainder sequences. In: Buchberger, B., Collins, G.E., Loos, R. (eds.) Computer Algebra: Symbolic and Algebraic Computation, 2nd edn., pp. 115–137. Springer, Heidelberg (1983)Google Scholar
  5. 5.
    Terui, A.: Subresultants in recursive polynomial remainder sequence. In: Ganzha, V., Mayr, E., Vorozhtsov, E. (eds.) Proc. The Sixth Computer Algebra in Scientific Computing: CASC 2003, München, pp. 363–375. Institute für Informatik, Technische Universität München (2003)Google Scholar
  6. 6.
    Terui, A.: Recursive polynomial remainder sequence and calculation of the number of real zeros of univariate polynomial (in Japanese). In: Noro, M. (ed.) Computer algebra—algorithms, implementations and applications (Kyoto, 2003), Research Institute for Mathematical Sciences, Kyoto Univ., Kyoto. RIMS Collection of Research Reports, vol. 1395, pp. 97–103 (2004)Google Scholar
  7. 7.
    von zur Gathen, J., Lücking, T.: Subresultants revisited. Theoret. Comput. Sci. 297, 199–239 (2003); Latin American theoretical informatics (Punta del Este, 2000)zbMATHCrossRefMathSciNetGoogle Scholar
  8. 8.
    Bareiss, E.H.: Sylvester’s identity and multistep integer-preserving Gaussian elimination. Math. Comp. 22, 565–578 (1968)zbMATHCrossRefMathSciNetGoogle Scholar
  9. 9.
    Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. The Johns Hopkins University Press, Baltimore (1996)zbMATHGoogle Scholar
  10. 10.
    Ducos, L.: Optimizations of the subresultant algorithm. J. Pure Appl. Algebra 145, 149–163 (2000)zbMATHCrossRefMathSciNetGoogle Scholar
  11. 11.
    Lombardi, H., Roy, M.F., El Din, M.S.: New structure theorem for subresultants. J. Symbolic Comput. 29, 663–689 (2000)zbMATHCrossRefMathSciNetGoogle Scholar
  12. 12.
    Corless, R.M., Gianni, P.M., Trager, B.M., Watt, S.M.: The singular value decomposition for polynomial systems. In: Proc. ISSAC 1995, pp. 195–207. ACM, New York (1995)CrossRefGoogle Scholar
  13. 13.
    Emiris, I.Z., Galligo, A., Lombardi, H.: Certified approximate univariate GCDs. J. Pure Appl. Algebra 117/118, 229–251 (1997); Algorithms for algebra (Eindhoven, 1996) CrossRefMathSciNetGoogle Scholar
  14. 14.
    Diaz-Toca, G.M., Gonzalez-Vega, L.: Barnett’s theorems about the greatest common divisor of several univariate polynomials through Bezout-like matrices. J. Symbolic Comput. 34, 59–81 (2002)zbMATHCrossRefMathSciNetGoogle Scholar
  15. 15.
    Rupprecht, D.: An algorithm for computing certified approximate GCD of n univariate polynomials. J. Pure and Applied Algebra 139, 255–284 (1999)zbMATHCrossRefMathSciNetGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Akira Terui
    • 1
  1. 1.Graduate School of Pure and Applied SciencesUniversity of TsukubaTsukubaJapan

Personalised recommendations