Efficient algorithms for computing the nearest polynomial with a real root and related problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient algorithms for computing the nearest polynomial with a real root and related problems

Full text

Pdf (761 KB)

Source

International Conference on Symbolic and Algebraic Computation archive
Proceedings of the 1999 international symposium on Symbolic and algebraic computation table of contents

Vancouver, British Columbia, Canada

Pages: 205 - 212

Year of Publication: 1999

ISBN:1-58113-073-2

Authors

Markus A. Hitz	Department of Mathematics and Conquter Science, North Georgia College & State Uuiversity, Dahlonega, GA
Erich Kaltofen	Mathematics Department, North Carolina State University, Raleigh, NC
Y. N. Lakshman	Computing Sciences Research, Bell Labs, Murray Hill, NJ

Sponsors

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation
SIGNUM: ACM Special Interest Group on Numerical Mathematics

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 13, Citation Count: 19

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	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/309831.309937 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	Robert M. Corless , Patrizia M. Gianni , Barry M. Trager , Stephen M. Watt, The singular value decomposition for polynomial systems, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.195-207, July 10-12, 1995, Montreal, Quebec, Canada [doi>10.1145/220346.220371]
	2	J. W. Demmel, On condition numbers and the distance to the nearest III-posted problem, Numerische Mathematik, v.51 n.3, p.251-289, July 1987 [doi>10.1007/BF01400115]
	3	ECKART, C., AN})YOUNG, G. The approximation of one matrix by another of lower rank. Psychometrika 1, 3 (Sept. 1936), 211-218.
	4	André Galligo , Stephen Watt, A numerical absolute primality test for bivariate polynomials, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.217-224, July 21-23, 1997, Kihei, Maui, Hawaii, United States [doi>10.1145/258726.258788]
	5	H{TZ. M. Porting computer algebra algorithms to numerical computing- the difficult case. SIGSAM Bulletin 30, 1 (Mar. 1996), 44-45. ECC.AD'96 abstract.
	6	Markus Alois Hitz , Erich Kaltofen , Joseph E. Flaherty, Efficient algorithms for computing the nearest polynomial with constrained roots, 1998
	7	Markus A. Hitz , Erich Kaltofen, Efficient algorithms for computing the nearest polynomial with constrained roots, Proceedings of the 1998 international symposium on Symbolic and algebraic computation, p.236-243, August 13-15, 1998, Rostock, Germany [doi>10.1145/281508.281624]
	8	David Granville Hough, Explaining and ameliorating the ill condition of zeros of polynomials., 1977
	9	KAHAN, W. NumericM linear algebra.. Canadian Math. Bull. 9 (1966), 757-801.
	10	Erich Kaltofen, Fast parallel absolute irreducibility testing, Journal of Symbolic Computation, v.1 n.1, p.57-68, March 1985 [doi>10.1016/S0747-7171(85)80029-8]
	11	Erich Kaltofen, Polynomial Factorization 1987-1991, Proceedings of the 1st Latin American Symposium on Theoretical Informatics, p.294-313, April 06-10, 1992
	12	N. Karmarkar , Y. N. Lakshman, Approximate polynomial greatest common divisors and nearest singular polynomials, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.35-39, July 24-26, 1996, Zurich, Switzerland [doi>10.1145/236869.236892]
	13	N. K. Karmarkar , Y. N. Lakshman, On approximate GCDs of univariate polynomials, Journal of Symbolic Computation, v.26 n.6, p.653-666, Dec. 1998 [doi>10.1006/jsco.1998.0232 ]
	14	L.IPPERT, R. A., AND Er)F.LMA.X, A. The computation and sensitivity of double eigenvahles. Manuscript; see link at. http-//uwu-math .mit. edu/-ede:l man/, Jan. 1998.
	15	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 ]
	16	POLJAK, S.. AND ~.OHN. J. Checking robust, nonsingula.rity is NP-hard. Math,. Control Signals Systems 6 (1993), 1-9.
	17	STIEFEL, E. /~rber diskrete und linearc Tschebyscheff- Approximationen. Numeri,sche Mathematik 1 (.1959). 1--28.
	18	STIEVEL, E. Note on Jordan elimination, linear programming, and Tsclmbyschcff a,pproximationen. Numerische Math.ematik 2 (1960), 1-17.
	19	VAN DoormEN, P., AND VERMAUT: r. Oll stability radii of generalized eig(:nvalue problems. In Proc. European Conference. on Control (1997).
	20	\~1LKINSON, J. H. The perfidimts polynomial. In Studie.s in Numerical Analysis, G. H. Golub, Ed., vol. 24 of Studies in Mathematics. M.A.A., 198,1, pp. 1-28.

CITED BY 19

	Bin Li , Jiawang Nie , Lihong Zhi, Approximate GCDs of polynomials and SOS relaxation, Proceedings of the 2007 international workshop on Symbolic-numeric computation, July 25-27, 2007, London, Ontario, Canada
	Nargol Rezvani , Robert M. Corless, The nearest polynomial with a given zero, revisited, ACM SIGSAM Bulletin, v.39 n.3, September 2005
	Erich Kaltofen , Bin Li , Kartik Sivaramakrishnan , Zhengfeng Yang , Lihong Zhi, Lower bounds for approximate factorizations via semidefinite programming: (extended abstract), Proceedings of the 2007 international workshop on Symbolic-numeric computation, July 25-27, 2007, London, Ontario, Canada
	Kosaku Nagasaka, Towards certified irreducibility testing of bivariate approximate polynomials, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.192-199, July 07-10, 2002, Lille, France
	Hans J. Stetter, The nearest polynomial with a given zero, and similar problems, ACM SIGSAM Bulletin, v.33 n.4, p.2-4, 12/01/1999
	Stef Graillat, A note on a nearest polynomial with a given root, ACM SIGSAM Bulletin, v.39 n.2, June 2005
	Hiroshi Sekigawa, The nearest polynomial with a zero in a given domain, Proceedings of the 2007 international workshop on Symbolic-numeric computation, July 25-27, 2007, London, Ontario, Canada
	Yuzhen Huang , Wenda Wu , Hans J. Stetter , Lihong Zhi, Pseudofactors of multivariate polynomials, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.161-168, July 2000, St. Andrews, Scotland
	Hiroshi Sekigawa , Kiyoshi Shirayanagi, Locating real multiple zeros of a real interval polynomial, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy
	Hiroshi Sekigawa, On real factors of real interval polynomials, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada
	Erich Kaltofen , John May, On approximate irreducibility of polynomials in several variables, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.161-168, August 03-06, 2003, Philadelphia, PA, USA
	Shuhong Gao , Erich Kaltofen , John May , Zhengfeng Yang , Lihong Zhi, Approximate factorization of multivariate polynomials via differential equations, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.167-174, July 04-07, 2004, Santander, Spain
	Robert M. Corless , Mark W. Giesbrecht , Mark van Hoeij , Ilias S. Kotsireas , Stephen M. Watt, Towards factoring bivariate approximate polynomials, Proceedings of the 2001 international symposium on Symbolic and algebraic computation, p.85-92, July 2001, London, Ontario, Canada
	Hoon Hong , Erich Kaltofen , Michael Singer, East Coast Computer Algebra Day '99 (April 24, 1999): abstracts of invited talks and presented posters, ACM SIGSAM Bulletin, v.33 n.2, p.43-52, June 1999
	Markus A. Hitz, On computing nearest singular hankel matrices, Proceedings of the 2005 international symposium on Symbolic and algebraic computation, p.171-176, July 24-27, 2005, Beijing, China
	J. William Hoffman , James J. Madden , Hong Zhang, Pseudozeros of multivariate polynomials, Mathematics of Computation, v.72 n.242, p.975-1002, 1 April 2003
	Erich Kaltofen , John P. May , Zhengfeng Yang , Lihong Zhi, Approximate factorization of multivariate polynomials using singular value decomposition, Journal of Symbolic Computation, v.43 n.5, p.359-376, May, 2008
	Andre Galligo , Mark van Hoeij, Approximate bivariate factorization: a geometric viewpoint, Proceedings of the 2007 international workshop on Symbolic-numeric computation, July 25-27, 2007, London, Ontario, Canada
	Johannes Grabmeier , Erich Kaltofen , Volker Weispfenning, Cited References, Computer algebra handbook, Springer-Verlag New York, Inc., New York, NY, 2003