Early termination in Ben-Or/Tiwari sparse interpolation and a hybrid of Zippel's algorithm

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Early termination in Ben-Or/Tiwari sparse interpolation and a hybrid of Zippel's algorithm

Full text

Pdf (267 KB)

Source

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

St. Andrews, Scotland

Pages: 192 - 201

Year of Publication: 2000

ISBN:1-58113-218-2

Authors

Erich Kaltofen	Department of Mathematics, North Carolina State University, Raleigh, North Carolina
Wen-shin Lee	Department of Mathematics, North Carolina State University, Raleigh, North Carolina
Austin A. Lobo	Dept. of Mathematics and Computer Science, Washington College, Chestertown, Maryland

Sponsor

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 23, Citation Count: 11

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/345542.345629 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	Michael Ben-Or, A deterministic algorithm for sparse multivariate polynomial interpolation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.301-309, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62241]
	2	W. S. Brown , J. F. Traub, On Euclid's Algorithm and the Theory of Subresultants, Journal of the ACM (JACM), v.18 n.4, p.505-514, Oct. 1971 [doi>10.1145/321662.321665]
	3	R. A. DeMillo and R. J. Lipton. A probabilistic remark on algebraic program testing. Information Process. Letters, 7(4):193-195, 1978.
	4	Angel Díaz , Erich Kaltofen, FOXBOX: a system for manipulating symbolic objects in black box representation, Proceedings of the 1998 international symposium on Symbolic and algebraic computation, p.30-37, August 13-15, 1998, Rostock, Germany [doi>10.1145/281508.281538]
	5	Jean Louis Dornstetter, On the equivalence between Berlekamp's and Euclid's algorithms, IEEE Transactions on Information Theory, v.33 n.3, p.428-431, May 1, 1987 [doi>10.1109/TIT.1987.1057299]
	6	F. R. Gantmacher. The theory of matrices, volume 1. Chelsea publishing company, 1977.
	7	Dima Yu Grigoriev , Marek Karpinski , Michael F. Singer, Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields, SIAM Journal on Computing, v.19 n.6, p.1059-1063, Dec. 1990 [doi>10.1137/0219073]
	8	Dima Yu. Grigoriev , Y. N. Lakshman, Algorithms for computing sparse shifts for multivariate polynomials, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.96-103, July 10-12, 1995, Montreal, Quebec, Canada [doi>10.1145/220346.220359]
	9	G. H. Hardy and E. M. Wright. An Introduction to the Theory of Numbers. Oxford Univ. Press, Oxford, 5 edition, 1979.
	10	E. Kaltofen , Y. N. Lakshman , J.-M. Wiley, Modular rational sparse multivariate polynomial interpolation, Proceedings of the international symposium on Symbolic and algebraic computation, p.135-139, August 20-24, 1990, Tokyo, Japan [doi>10.1145/96877.96912]
	11	Erich Kaltofen , Yagati N. Lakshman, Improved Sparse Multivariate Polynomial Interpolation Algorithms, Proceedings of the International Symposium ISSAC'88 on Symbolic and Algebraic Computation, p.467-474, July 04-08, 1988
	12	E. Kaltofen , A. Lobo, On rank properties of Toeplitz matrices over finite fields, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.241-249, July 24-26, 1996, Zurich, Switzerland [doi>10.1145/236869.237081]
	13	Erich Kaltofen , Barry M. Trager, Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators, Journal of Symbolic Computation, v.9 n.3, p.301-320, March 1990 [doi>10.1016/S0747-7171(08)80015-6]
	14	Y. N. Lakshman , B. David Saunders, Sparse Polynomial Interpolation in Nonstandard Bases, SIAM Journal on Computing, v.24 n.2, p.387-397, April 1995 [doi>10.1137/S0097539792237784]
	15	Lakshman Y. N. and B. D. Saunders. Sparse shifts for univariate polynomials. Applic. Algebra Engin. Commun. Comput., 7(5):351-364, 1996.
	16	J. L. Massey. Shift-register synthesis and BCH decoding. IEEE Trans. Inf. Theory, IT-15:122-127, 1969.
	17	H. Murao and T. Fujise. Modular algorithm for sparse multivariate polynomial interpolation and its parallel implementation. In H. Hong, editor, Proc. First Internat. Syrup. Parallel Symbolic Comput. PASCO '94~, pages 304-315, Singapore, 1994. World Scientific Publishing Co.
	18	J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM (JACM), v.27 n.4, p.701-717, Oct. 1980 [doi>10.1145/322217.322225]
	19	D H Wiedemann, Solving sparse linear equations over finite fields, IEEE Transactions on Information Theory, v.32 n.1, p.54-62, Jan. 1986 [doi>10.1109/TIT.1986.1057137]
	20	Zeljko Zilic , Katarzyna Radecka, On feasible multivariate polynomial interpolations over arbitrary fields, Proceedings of the 1999 international symposium on Symbolic and algebraic computation, p.67-74, July 28-31, 1999, Vancouver, British Columbia, Canada [doi>10.1145/309831.309863]
	21	Richard Zippel, Probabilistic algorithms for sparse polynomials, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.216-226, June 01, 1979
	22	Richard Zippel, Interpolating polynomials from their values, Journal of Symbolic Computation, v.9 n.3, p.375-403, March 1990 [doi>10.1016/S0747-7171(08)80018-1]
	23	R. E. Zippel. Probabilistic algorithms for sparse polynomials. PhD thesis, Massachusetts Inst. of Technology, Cambridge, USA, Sept. 1979.

CITED BY 11

	Erich Kaltofen, An output-sensitive variant of the baby steps/giant steps determinant algorithm, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.138-144, July 07-10, 2002, Lille, France
	Johannes Grabmeier , Erich Kaltofen , Volker Weispfenning, Cited References, Computer algebra handbook, Springer-Verlag New York, Inc., New York, NY, 2003
	Mark Giesbrecht , Erich Kaltofen , Wen-shin Lee, Algorithms for computing the sparsest shifts of polynomials via the Berlekamp/Massey algorithm, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.101-108, July 07-10, 2002, Lille, France
	Wayne Eberly, Early termination over small fields, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.80-87, August 03-06, 2003, Philadelphia, PA, USA
	Mark Giesbrecht , Erich Kaltofen , Wen-shin Lee, Algorithms for computing sparsest shifts of polynomials in power, Chebyshev, and Pochhammer bases, Journal of Symbolic Computation, v.36 n.3-4, p.401-424, September 2003
	Erich Kaltofen , Wen-shin Lee, Early termination in sparse interpolation algorithms, Journal of Symbolic Computation, v.36 n.3-4, p.365-400, September 2003
	Zeljko Zilic , Zvonko G. Vranesic, A Deterministic Multivariate Interpolation Algorithm for Small Finite Fields, IEEE Transactions on Computers, v.51 n.9, p.1100-1105, September 2002
	Erich Kaltofen , Zhengfeng Yang, On exact and approximate interpolation of sparse rational functions, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada
	Annie Cuyt , Wen-shin Lee, A new algorithm for sparse interpolation of multivariate polynomials, Theoretical Computer Science, v.409 n.2, p.180-185, December, 2008
	Wen-shin Lee, From quotient-difference to generalized eigenvalues and sparse polynomial interpolation, Proceedings of the 2007 international workshop on Symbolic-numeric computation, July 25-27, 2007, London, Ontario, Canada
	Annie Cuyt , Wen-shin Lee, Sparse multivariate polynomial interpolation via the quotient-difference algorithm, ACM Communications in Computer Algebra, v.42 n.3, September 2008