The singular value decomposition for polynomial systems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The singular value decomposition for polynomial systems

Full text

Pdf (1.50 MB)

Source

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

Montreal, Quebec, Canada

Pages: 195 - 207

Year of Publication: 1995

ISBN:0-89791-699-9

Authors

Robert M. Corless	IBM T.J. Watson Research Center, Yorktown Heights, NY
Patrizia M. Gianni	IBM T.J. Watson Research Center, Yorktown Heights, NY
Barry M. Trager	IBM T.J. Watson Research Center, Yorktown Heights, NY
Stephen M. Watt	IBM T.J. Watson Research Center, Yorktown Heights, NY

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): 13, Downloads (12 Months): 74, Citation Count: 48

Additional Information:

references cited by index terms collaborative colleagues

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/220346.220371 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	E. Anderson, Z. Bai, C. Bischof, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, S. Ostrouchov, and D. Sorensen, LAPACK User's Guide, 2nd. ed., SIAM, 1995.
	2	W. Auzinger and H. J. Stetter, "An Elimination Algorithm for the Computation of All Zeros of a System of Multivariate Polynomial Equations", in: Conference in Numerical Analysis, ISNM vol 86, Birkhaeuser, 1988, pp. 11-30.
	3	Angelika Bunse-Gerstner , Ralph Byers , Volker Mehrmann, Numerical methods for simultaneous diagonalization, SIAM Journal on Matrix Analysis and Applications, v.14 n.4, p.927-949, Oct. 1993 [doi>10.1137/0614062]
	4	Robert M. Corless, David J. Jeffrey, and M. A. H. Nerenberg, "The Row Echelon Decomposition of a Matrix", manuscript, 1989.
	5	Robert M. Corless , David J. Jeffrey, Well … it isn't quite that simple, ACM SIGSAM Bulletin, v.26 n.3, p.2-6, Aug. 1992 [doi>10.1145/141897.141901]
	6	Keith O. Geddes , Stephen R. Czapor , George Labahn, Algorithms for computer algebra, Kluwer Academic Publishers, Norwell, MA, 1992
	7	P.M. Gianni and B.M. Trager, in preparation.
	8	Gene Golub and Charles Van Loan, Matrix Computations, Wiley-Interscience, 1981.
	9	Roger A. Horn and Charles A. Johnson, Matrix Analysis, Cambridge University Press, 1985.
	10	V. Hribernig , H. J. Stetter, Detection and validation of clusters of polynomial zeros, Journal of Symbolic Computation, v.24 n.6, p.667-681, Dec. 1997 [doi>10.1006/jsco.1997.0160]
	11	N. Karcanias and M. Mitrouli, "A Matrix Pencil Based Numerical Method for the Computation of the GCD of Polynomials", IEEE Trans. Automatic Control, 39, No. 5, May 1994, pp. 977-981.
	12	Daniel Lazard, "Resolution des systemes d'equations algebriques", Theoretical Computer Science 15, (1981) pp. 77-110.
	13	Dinesh Manocha, Computing selected solutions of polynomial equations, Proceedings of the international symposium on Symbolic and algebraic computation, p.1-8, July 20-22, 1994, Oxford, United Kingdom [doi>10.1145/190347.190349]
	14	Dinesh Manocha, Solving Systems of Polynomial Equations, IEEE Computer Graphics and Applications, v.14 n.2, p.46-55, March 1994 [doi>10.1109/38.267470]
	15	Dinesh Manocha and James Demmel, "Algorithms for Intersecting Parametric and Algebraic Curves II: Multiple Intersections", preprint.
	16	H. Michael Möller , Hans J. Stetter, Multivariate polynomial equations with multiple zeros solved by matrix eigenproblems, Numerische Mathematik, v.70 n.3, p.311-329, May 1995 [doi>10.1007/s002110050122]
	17	Matu-Tarow Noda , Tateaki Saaski, Approximate GCD and its application to ill-conditioned algebraic equations, Journal of Computational and Applied Mathematics, v.38 n.1-3, p.335-351, Dec. 23, 1991
	18	A. SchSnhage, "Quasi-GCD Computations", J. Complexity, 1981.
	19	M. SeppSJS. and R. Silhol, private communication.
	20	Hans J. Stetter, "Multivariate Polynomial Equations as Matrix Eigenproblems", WSSIA 2, World Scientific, 1993, pp. 355-371.
	21	H. J. Stetter, "Verification in Computer Algebra Systems", in: Validation Numerics, R. Albrecht, G. Alefeld, H. J. Stetter, eds., Computing Suppl. 9, 1993, pp. 247-263.
	22	G. W. Stewart, "Perturbation theory for the Generalized Eigenvalue Problem," in Recent Advances in Numerical Analysis, ed. C. deBoor and G. H. Golub, Academic Press, New York, 1978.
	23	S. M. Watt, P. A. Broadbery, S. S. Dooley, P. Iglio, S. C. Morrison, J. M. Steinbach and R. S. Sutor, Axiom Library CompiIer User Guide, NAG Ltd, 1994.
	24	Stephen M. Watt , Peter A. Broadbery , Samuel S. Dooley , Pietro Iglio , Scott C. Morrison , Jonathan M. Steinbach , Robert S. Sutor, A first report on the A# compiler, Proceedings of the international symposium on Symbolic and algebraic computation, p.25-31, July 20-22, 1994, Oxford, United Kingdom [doi>10.1145/190347.190356]
	25	J. H. Wilkinson, "The Perfidious Polynomial", in Studies in Numerical Analysis, M.A.A. Studies in Mathematics, 24, Gene H. Golub, ed., pp. 1-28, 1984.
	26	Richard Zippel, Effective Polynomial Computation, Kluwer Academic Publishers, Boston, 1993.

CITED BY 48

	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
	Paulina Chin , Robert M. Corless , George F. Corliss, Optimization strategies for the approximate GCD problem, Proceedings of the 1998 international symposium on Symbolic and algebraic computation, p.228-235, August 13-15, 1998, Rostock, Germany
	Robert M. Corless , Patrizia M. Gianni , Barry M. Trager, A reordered Schur factorization method for zero-dimensional polynomial systems with multiple roots, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.133-140, July 21-23, 1997, Kihei, Maui, Hawaii, United States
	Victor Y. Pan, Approximate polynomial Gcds, Padé approximation, polynomial zeros and bipartite graphs, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.68-77, January 25-27, 1998, San Francisco, California, United States
	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
	Markus A. Hitz , Erich Kaltofen , Y. N. Lakshman, Efficient algorithms for computing the nearest polynomial with a real root and related problems, Proceedings of the 1999 international symposium on Symbolic and algebraic computation, p.205-212, July 28-31, 1999, Vancouver, British Columbia, Canada
	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
	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
	Zhonggang Zeng, A method computing multiple roots of inexact polynomials, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.266-272, August 03-06, 2003, Philadelphia, PA, USA
	Johannes Grabmeier , Erich Kaltofen , Volker Weispfenning, Cited References, Computer algebra handbook, Springer-Verlag New York, Inc., New York, NY, 2003
	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
	Zhonggang Zeng , Barry H. Dayton, The approximate GCD of inexact polynomials, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.320-327, July 04-07, 2004, Santander, Spain
	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
	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
	Sonia Pérez-Díaz , Juana Sendra , J. Rafael Sendra, Parametrization of approximate algebraic surfaces by lines, Computer Aided Geometric Design, v.22 n.2, p.147-181, February 2005
	D. A. Bini , L. Gemignani, Bernstein-Bezoutian matrices, Theoretical Computer Science, v.315 n.2-3, p.319-333, 6 May 2004
	Sonia Pérez-Díaz , Juana Sendra , J. Rafael Sendra, Parametrization of approximate algebraic curves by lines, Theoretical Computer Science, v.315 n.2-3, p.627-650, 6 May 2004
	Nargol Rezvani , Robert M. Corless, The nearest polynomial with a given zero, revisited, ACM SIGSAM Bulletin, v.39 n.3, September 2005
	Erich Kaltofen , Zhengfeng Yang , Lihong Zhi, Approximate greatest common divisors of several polynomials with linearly constrained coefficients and singular polynomials, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy
	Itnuit Janovitz-Freireich , Lajos Rónyai , Ágnes Szántó, Approximate radical of ideals with clusters of roots, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy
	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
	Robert M. Corless , Stephen M. Watt, Report on the SNAP minisymposium at SIAM '98, ACM SIGSAM Bulletin, v.32 n.2, p.35-37, June 1998
	Sonia Pérez-Díaz , Juana Sendra , J. Rafael Sendra, Distance bounds of ε-points on hypersurfaces, Theoretical Computer Science, v.359 n.1, p.344-368, 14 August 2006
	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
	Masaru Sanuki , Tateaki Sasaki, Computing Approximate GCDs in Ill-conditioned Cases, Proceedings of the 2007 international workshop on Symbolic-numeric computation, July 25-27, 2007, London, Ontario, Canada
	Erich Kaltofen , Zhengfeng Yang , Lihong Zhi, On probabilistic analysis of randomization in hybrid symbolic-numeric algorithms, Proceedings of the 2007 international workshop on Symbolic-numeric computation, July 25-27, 2007, London, Ontario, Canada
	Bingyu Li , Zhuojun Liu , Lihong Zhi, A fast algorithm for solving the Sylvester structured total least squares problem, Signal Processing, v.87 n.10, p.2313-2319, October, 2007
	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
	Hiroshi Kai , Matu-Tarow Noda, Hybrid computation of bivariate rational interpolation, ACM SIGSAM Bulletin, v.34 n.1, p.20-21, March 2000
	Hans J. Stetter, Matrix eigenproblems are at the heart of polynomial system solving, ACM SIGSAM Bulletin, v.30 n.4, p.22-25, Dec. 1996
	Robert M. Corless, Gröbner bases and matrix eigenproblems, ACM SIGSAM Bulletin, v.30 n.4, p.26-32, Dec. 1996
	Joab R. Winkler , John D. Allan, Structured total least norm and approximate GCDs of inexact polynomials, Journal of Computational and Applied Mathematics, v.215 n.1, p.1-13, May, 2008
	Bingyu Li , Zhuojun Liu , Lihong Zhi, A structured rank-revealing method for Sylvester matrix, Journal of Computational and Applied Mathematics, v.213 n.1, p.212-223, March, 2008
	Dario A. Bini , Paola Boito, Structured matrix-based methods for polynomial ∈-gcd: analysis and comparisons, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada
	Hiroshi Kai , Nanami Nakagawa , Matu-Tarow Noda, A hybrid integral for parametrized rational functions, Proceedings of the 2007 international workshop on Symbolic-numeric computation, July 25-27, 2007, London, Ontario, Canada
	Pramook Khungurn , Hiroshi Sekigawa , Kiyoshi Shirayanagi, Minimum converging precision of the QR-factorization algorithm for real polynomial GCD, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada
	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
	Agnes Szanto, Solving over-determined systems by the subresultant method (with an appendix by Marc Chardin), Journal of Symbolic Computation, v.43 n.1, p.46-74, January, 2008
	Greg Reid , Lihong Zhi, Solving polynomial systems via symbolic-numeric reduction to geometric involutive form, Journal of Symbolic Computation, v.44 n.3, p.280-291, March, 2009
	Laurent Busé , Mohamed Elkadi , André Galligo, A computational study of ruled surfaces, Journal of Symbolic Computation, v.44 n.3, p.232-241, March, 2009
	Hiroshi Sekigawa, On real factors of real interval polynomials, Journal of Symbolic Computation, v.44 n.7, p.908-922, July, 2009
	Scott R. Pope , Agnes Szanto, Nearest multivariate system with given root multiplicities, Journal of Symbolic Computation, v.44 n.6, p.606-625, June, 2009
	Mark Giesbrecht , George Labahn , Wen-shin Lee, Symbolic-numeric sparse interpolation of multivariate polynomials, Journal of Symbolic Computation, v.44 n.8, p.943-959, August, 2009
	Robert M. Corless, Pseudospectra for exponential polynomial matrices, Proceedings of the 2009 conference on Symbolic numeric computation, August 03-05, 2009, Kyoto, Japan
	Akira Terui, An iterative method for calculating approximate GCD of univariate polynomials, Proceedings of the 2009 international symposium on Symbolic and algebraic computation, July 28-31, 2009, Seoul, Republic of Korea
	Robert M. Corless , Karin Gatermann , Ilias S. Kotsireas, Using symmetries in the eigenvalue method for polynomial systems, Journal of Symbolic Computation, v.44 n.11, p.1536-1550, November, 2009
	Guillaume Chèze , Jean-Claude Yakoubsohn , André Galligo , Bernard Mourrain, Computing nearest Gcd with certification, Proceedings of the 2009 conference on Symbolic numeric computation, August 03-05, 2009, Kyoto, Japan
	Zhonggang Zeng, The approximate irreducible factorization of a univariate polynomial: revisited, Proceedings of the 2009 international symposium on Symbolic and algebraic computation, July 28-31, 2009, Seoul, Republic of Korea