Algorithms for computing sparse shifts for multivariate polynomials

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Algorithms for computing sparse shifts for multivariate polynomials

Full text

Pdf (998 KB)

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: 96 - 103

Year of Publication: 1995

ISBN:0-89791-699-9

Authors

Dima Yu. Grigoriev	Department of Computer Science and Department of Mathematics, Pennsylvania State University, State College, PA
Y. N. Lakshman	Department of Mathematics and Computer Science, Drexel University, Philadelphia, PA

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): 0, Downloads (12 Months): 4, Citation Count: 5

Additional Information:

references cited by index terms 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/220346.220359 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	Baur, W., and Strassen, V., (1983), "The complexity of partial derivatives," Theoretical Computer Science, Vol. 22, pp. 317-330.
	2	Thomas Becker , Volker Weispfenning , Heinz Kredel, Gro¨bner bases: a computational approach to commutative algebra, Springer-Verlag, London, 1993
	3	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]
	4	A. Borodin , P. Tiwari, On the decidability of sparse univariate polynomial interpolation, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.535-545, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100292]
	5	Michael Clausen , Andreas Dress , Johannes Grabmeier , Marek Karpinski, On Zero-Testing and Interpolation of $k$-sparse Multivariate Polynomials over Finite Fields, University of Bonn, 1988
	6	J. C. Faugère , P. Gianni , D. Lazard , T. Mora, Efficient computation of zero-dimensional Gro¨bner bases by change of ordering, Journal of Symbolic Computation, v.16 n.4, p.329-344, Oct. 1993 [doi>10.1006/jsco.1993.1051]
	7	Grigoriev, D. Yu. and Karpinski, M. (1987), "The matching problem for bipartite graphs with polynomially bounded permanents is in NC," Proc. 28th IEEE Symp. Foundations Comp. Sci., pp. 166-172.
	8	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]
	9	Dima Yu Grigoriev , Marek Karpinski , Michael F. Singer, The interpolation problem for k-sparse sums of eigenfunctions of operators, Advances in Applied Mathematics, v.12 n.1, p.76-81, March 1991 [doi>10.1016/0196-8858(91)90005-4]
	10	Dima Yu. Grigoriev , Marek Karpinski , Andrew M. Odlyzko, Existence of short proofs for nondivisibility of sparse polynomials under the extended Riemann hypothesis, Papers from the international symposium on Symbolic and algebraic computation, p.117-122, July 27-29, 1992, Berkeley, California, United States [doi>10.1145/143242.143287]
	11	Grigoriev, D., Karpinski, M., and Singer, M. (1993a), "Computational complexity of sparse real algebraic function interpolation," Proc. MEGA '92, Progress in Mathematics, Birkhauser, Vol. 109, pp. 91-104.
	12	Dima Grigoriev , Marek Karpinski, A Zero-Test and an Interpolation Algorithm for the Shifted Sparse Polynominals, Proceedings of the 10th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.162-169, May 10-14, 1993
	13	Dima Grigoriev , Marek Karpinski , Michael F. Singer, Computational Complexity of Sparse Rational Interpolation, SIAM Journal on Computing, v.23 n.1, p.1-12, Feb. 1994 [doi>10.1137/S0097539791194069]
	14	Grigoriev, D., and Lakshman Y. N., (1994), "Algorithms for Computing Sparse Shifts for Multivariate Polynomials," Manuscript.
	15	E. Kaltofen, Single-factor Hensel lifting and its application to the straight-line complexity of certain polynomials, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.443-452, January 1987, New York, New York, United States [doi>10.1145/28395.28443]
	16	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
	17	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]
	18	Kaplanski, I. (1957), "An introduction to differential algebra," Hermann, Paris.
	19	Kapur, D., and Lakshman Y.N., (1992), "Elimination methods: An introduction," in Symbolic and Numerical Computation for Artificial Intelligence, (Ed. Bruce Donald, Deepak Kapur, Joe Mundy), Academic Press, 1992, pp. 45-89.
	20	Lakshman Y.N., (1990) "On the Complexity of Computing CrSbner Bases for Zero Dimensional Polynomial Ideals", Ph.D. Thesis, Rensselaer Polytechnic Institute, Troy, New York, December 1990.
	21	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]
	22	Y. N. Lakshman , B. David Saunders, On computing sparse shifts for univariate polynomials, Proceedings of the international symposium on Symbolic and algebraic computation, p.108-113, July 20-22, 1994, Oxford, United Kingdom [doi>10.1145/190347.190373]
	23	Lazard D., (1989), " Solving Zero~Dimensional Algebraic Systems ", Tech. Report.no.89-48, LITP, Universite Paris VI, June 1989.
	24	Yishay Mansour, Randomized Interpolation and Approximationof Sparse Polynomials, SIAM Journal on Computing, v.24 n.2, p.357-368, April 1995 [doi>10.1137/S0097539792239291]
	25	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]

CITED BY 5

	D. Grigoriev, Testing shift-equivalence of polynomials using quantum machines, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.49-54, July 24-26, 1996, Zurich, Switzerland
	Erich Kaltofen , Wen-shin Lee , Austin A. Lobo, Early termination in Ben-Or/Tiwari sparse interpolation and a hybrid of Zippel's algorithm, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.192-201, July 2000, St. Andrews, Scotland
	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
	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
	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