Quantifier elimination and the sign variation method for real root isolation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Quantifier elimination and the sign variation method for real root isolation

Full text

Pdf (795 KB)

Source

International Conference on Symbolic and Algebraic Computation archive
Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation table of contents

Portland, Oregon, United States

Pages: 264 - 271

Year of Publication: 1989

ISBN:0-89791-325-6

Authors

G. E. Collins	Ohio State Univ., Columbus
J. R. Johnson	Ohio State Univ., Columbus

Sponsor

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 16, Citation Count: 5

Additional Information:

references cited by index terms review collaborative colleagues peer to peer

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/74540.74574 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	George E. Collins , Alkiviadis G. Akritas, Polynomial real root isolation using Descarte's rule of signs, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.272-275, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806346]
	2	Dennis Soule Arnon, Algorithms for the geometry of semi-algebraic sets, 1981
	3	Dennis S. Arnon, A cluster-based cylindrical algebraic decomposition algorithm, Journal of Symbolic Computation, v.5 n.1-2, p.189-212, February/April 1988 [doi>10.1016/S0747-7171(88)80012-9]
	4	Dennis S. Arnon , George E. Collins , Scott McCallum, Cylindrical algebraic decomposition I: the basic algorithm, SIAM Journal on Computing, v.13 n.4, p.865-877, Nov. 1984 [doi>10.1137/0213054]
	5	Dennis S. Arnon , Maurice Mignotte, On mechanical quantifier elimination for elementary algebra and geometry, Journal of Symbolic Computation, v.5 n.1-2, p.237-259, February/April 1988 [doi>10.1016/S0747-7171(88)80014-2]
	6	George E. Collins , Rudiger Loos, Real zeroes of polynomials, Computer algebra: symbolic and algebraic computation (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1983
	7	George E. Collins. Quantifier elimination for the elementarv theory of real closed fields by cylindrical algebraic decomposition. In Lecture Notes In Computer Science, pages 134-183. Springer-\'erlag, Berlin, {975. \'%1.33.
	8	~I. Vincent. Sur la resolution des equations numeriques. Jour. des 3{athematique Pures et Appliques, 1:3'41-372, 1836.

CITED BY 5

	Robert M. Corless, Sufficiency analysis for the calculus of variations, Proceedings of the international symposium on Symbolic and algebraic computation, p.197-204, July 20-22, 1994, Oxford, United Kingdom
	J. R. Johnson, Real algebraic number computation using interval arithmetic, Papers from the international symposium on Symbolic and algebraic computation, p.195-205, July 27-29, 1992, Berkeley, California, United States
	Arno Eigenwillig , Vikram Sharma , Chee K. Yap, Almost tight recursion tree bounds for the Descartes method, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy
	Fabrice Rouillier , Paul Zimmermann, Efficient isolation of polynomial's real roots, Journal of Computational and Applied Mathematics, v.162 n.1, p.33-50, 1 January 2004
	Hoon Hong, Simple solution formula construction in cylindrical algebraic decomposition based quantifier elimination, Papers from the international symposium on Symbolic and algebraic computation, p.177-188, July 27-29, 1992, Berkeley, California, United States

INDEX TERMS

Primary Classification:
J. Computer Applications

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

General Terms:
Algorithms, Design, Theory

REVIEW

"George W. Zobrist : Reviewer"

Root isolation involves finding disjoint intervals, each containing a single root, for all the real roots of a polynomial. This paper studies the properties of the sign variation method for root isolation. The sign variation rule is based on D more...

Collaborative Colleagues:

G. E. Collins: colleagues

J. R. Johnson: colleagues

Peer to Peer - Readers of this Article have also read:

Data structures for quadtree approximation and compression Communications of the ACM 28, 9
Hanan Samet
A hierarchical single-key-lock access control using the Chinese remainder theorem Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing
Kim S. Lee , Huizhu Lu , D. D. Fisher
An intelligent component database for behavioral synthesis Proceedings of the 27th ACM/IEEE Design Automation Conference on
Gwo-Dong Chen , Daniel D. Gajski
The GemStone object database management system Communications of the ACM 34, 10
Paul Butterworth , Allen Otis , Jacob Stein
Putting innovation to work: adoption strategies for multimedia communication systems Communications of the ACM 34, 12
Ellen Francik , Susan Ehrlich Rudman , Donna Cooper , Stephen Levine

Adobe Acrobat

QuickTime

Windows Media Player

Real Player