Sylvester-Habicht sequences and fast Cauchy index computation. (English) Zbl 0976.65043
Summary: The authors improve the classical sub-resultant theorem by proving a new exact divisibility result for Sylvester-Habicht polynomials. Then, they adapt the quotient boot method to the Sylvester-Habicht transition matrices, obtaining new algorithms for computing the Cauchy index of rational function, and the signature of a non-singular Hankel matrix, in a fast and also storage efficient way. Another elegant new result is proved: the size of coefficients in the ordinary remainder sequence is quadrature in \(d\), \(d\) being the bound of degrees of integer polynomials used in the algorithms.
Reviewer: Jacek Gilewicz (Marseille)
MSC:
| 65F30 | Other matrix algorithms (MSC2010) |
| 12Y05 | Computational aspects of field theory and polynomials (MSC2010) |
| 68W30 | Symbolic computation and algebraic computation |
Keywords:
sub-resultant theorem; Sylvester-Habicht polynomials; algorithms; Cauchy index; rational function; signature; Hankel matrixReferences:
| [1] | Brent, R. P.; Gustavson, F. G.; Yun, D. Y.Y., Fast solution of toeplitz systems of equations and computation of Padé approximants, J. Algorithms, 1, 259-295 (1980) · Zbl 0475.65018 |
| [2] | Brown, W. S., On Euclid’s algorithm and the computation of polynomial greatest common divisor, J. A. C. M., 18, 476-504 (1971) · Zbl 0226.65040 |
| [3] | Brown, W. S.; Traub, J. F., On Euclid’s algorithm and the theory of sub-resultants, J. A. C. M., 18, 505-524 (1971) · Zbl 0226.65041 |
| [4] | Collins, G. E., Subresultants and reduced polynomial remainder sequence, J. A. C. M., 14, 128-142 (1967) · Zbl 0152.35403 |
| [5] | Ducos, L., Algorithme de Bareiss, algorithmes des sous-résultants, Informatique théorique et applications, 30, 319-347 (1996) · Zbl 0868.65026 |
| [6] | Frobenius, F. G., Über das Trägheitsgesetz der quadratischen Formen (1884), p. 241-256 |
| [7] | Gantmacher, F. R., Théorie des matrices, tome I (1966), Dunod 1966 and New York, Springer-Verlag 1986 · Zbl 0136.00410 |
| [8] | Gemigniani, L., Computing the inertia of Bézout and Hankel matrices, Calcolo, 28, 267-274 (1991) · Zbl 0766.65035 |
| [9] | Gemigniani, L., Solving Hankel systems over the integers, J. Symb. Comput., 18, 573-584 (1994) · Zbl 0830.15015 |
| [10] | Gonzalez, L.; Lombardi, H.; Recio, T.; Roy, M.-F., Spécialisation de la suite de Sturm et sous-résultants I, Informatique théorique et applications, 24, 561-588 (1990) · Zbl 0732.68059 |
| [11] | Gonzalez, L.; Lombardi, H.; Recio, T.; Roy, M.-F., Spécialisation de la suite Sturm, Informatique théorique et applications, 28, 1-24 (1994) · Zbl 0999.12502 |
| [12] | Gonzalez, L.; Lombardi, H.; Recio, T.; Roy, M.-F., Sturm-Habicht sequence, determinants and real roots of univariate polynomials, (Caviness, B.; Johnson, J., Quantifier Elimination and Cylindrical Algebraic Decomposition (1998), Springer-Verlag: Springer-Verlag New York) · Zbl 0900.12002 |
| [13] | Habicht, W., Eine Verallgemeinerung des Sturmschen Wurzelzählverfahrens, Comm. Math. Helvetici, 21, 99-116 (1948) · Zbl 0029.24402 |
| [14] | Henrici, P., Upper bounds for the abscissa of stability of a stable polynomial, SIAM J. Num. Anal., 7, 538-544 (1970) · Zbl 0247.30001 |
| [15] | Henrici, P., Applied and Computational Complex Analysis (1974), J. Wiley: J. Wiley New York · Zbl 0313.30001 |
| [16] | Ho, C.-H.; Yap, C. K., Pseudo-subresultants, J. Symb. Comput., 21, 1-14 (1996) · Zbl 0849.68069 |
| [17] | Knebusch, M.; Scheiderer, C., Einführung in die reelle Algebra (1989), Aufbaukurs Mathematik: Aufbaukurs Mathematik Vieweg · Zbl 0732.12001 |
| [18] | Krein, M. G.; Naimark, M. A., The method of symmetric and hermitian forms in the theory of separation of roots of algebraic equation. Kharkov 1936 (in Russian). English translation, Linear and Multi-linear Algebra (1981), 10, 265-308 (1936) · Zbl 0584.12018 |
| [19] | Kung, H. T., On computing reciprocals of power series, Numer. Math., 22, 341-348 (1974) · Zbl 0274.65009 |
| [20] | D. Lazard; D. Lazard |
| [21] | Lickteig, T.; Roy, M.-F., Cauchy index computation, Calcolo, 33, 337-351 (1996) · Zbl 0904.65024 |
| [22] | Loos, R., Generalized polynomial remainder sequences, Computer Algebra, Symbolic and Algebraic Computation (1982), Springer-Verlag: Springer-Verlag Berlin · Zbl 0577.13001 |
| [23] | Moenck, R. T., Fast computation of GCDs, Proceedings STOC ‘73, 142-151 (1973) · Zbl 0306.68027 |
| [24] | C. Quitté; C. Quitté |
| [25] | D. Reischert, 1997, ACM Press, 233, 240; D. Reischert, 1997, ACM Press, 233, 240 |
| [26] | Roy, M.-F., Basic algorithms in real algebraic geometry and their complexity: from Sturm’s theorem to the existential theory of reals, Lectures on Real Geometry in Memoriam of Mario Raimondo (1996) · Zbl 0894.14028 |
| [27] | Schönhage, A., Schnelle Berechnung von Kettenbruchentwicklungen, Acta Informatica, 1, 139-144 (1971) · Zbl 0223.68008 |
| [28] | A. Schönhage, Proceedings, EUROCAM ‘82, 1982, Marseille; A. Schönhage, Proceedings, EUROCAM ‘82, 1982, Marseille |
| [29] | Schönhage, A.; Strassen, V., Schnelle Multiplikation großer Zahlen, Computing, 7, 281-292 (1971) · Zbl 0223.68007 |
| [30] | Sieveking, M., An algorithm for division of power series, Computing, 10, 153-156 (1972) · Zbl 0251.68023 |
| [31] | Strassen, V., The computational complexity of continued fractions, SIAM J. Comp., 12/1, 1-27 (1983) · Zbl 0543.68026 |
| [32] | Sturm, C., Mémoire sur la résolution des équations numériques, Inst. France Sc. Math. Phys., 6 (1835) |
| [33] | Sylvester, J. J., On a theory of syzygetic relations of two rational integral functions, comprising an application to the theory of Sturm’s function, Trans. Roy. Soc. London (1835) |
| [34] | K. Thull, C. K. Yap; K. Thull, C. K. Yap |
| [35] | Yap, C. K., Fundamental Problems in Algorithmic Algebra (1999), Oxford University Press: Oxford University Press Oxford |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
