Algorithms for sparse rational interpolation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Algorithms for sparse rational interpolation

Full text

Pdf (451 KB)

Source

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

Bonn, West Germany

Pages: 7 - 13

Year of Publication: 1991

ISBN:0-89791-437-6

Authors

Dima Yu. Grigoriev	Dept. of Computer Science, University of Bonn and Steklov Institute of Mathematics, Soviet Academy of Sciences, Leningrad
Marek Karpinski	Dept. of Computer Science, University of Bonn 5300 Bonn 1 and International Computer Science Institute, Berkeley, California

Sponsors

GMD : German Natl Research Ctr for Information Tech. - Gesellschft
German Comp Soc : GI - Gesellshaft for Informatik
SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 12, Citation Count: 2

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/120694.120696 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.

	BS 83	Baur, W., Strassen, V., The Complexity of Partial Derivatives, Theor. Comput. Sci., 1983, 22, pp. 317-330.
	BC 86	Paul W Beame , Stephen A Cook , H James Hoover, Log depth circuits for division and related problems, SIAM Journal on Computing, v.15 n.4, p.994-1003, Nov. 1986 [doi>10.1137/0215070]
	BT 88	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]
	CG 82	Chistov, A. L., Grigoriev, D. Yu., Polynomial-Time Factoring Multivariable Polynomials Over a Global Field, Preprint LOMI, E-5-82, Leningrad, 1982.
	C 85	Stephen A. Cook, A taxonomy of problems with fast parallel algorithms, Information and Control, v.64 n.1-3, p.2-22, Jan./Feb./March 1985 [doi>10.1016/S0019-9958(85)80041-3]
	DG 91	Andreas Dress , Johannes Grabmeier, The interpolation problem for k-sparse polynomials and character sums, Advances in Applied Mathematics, v.12 n.1, p.57-75, March 1991 [doi>10.1016/0196-8858(91)90004-3]
	GK 87	Grigoriev, D. Yu., Karpinski, M., The Matching Problem for Bipartite Graphs wi~h Polynomially Bounded Permanents is in NC, Proc. 28th IEEE FOCS (1987), pp. 166-172.
	GKS 90	Grigoriev, D. Yu., Karpinski, M., Singer, M., Interpolation of Sparse Rational Functions Without Knowing Bounds on Exponents, Proc. 31~t IEEE FOCS 1990, pp. 840- 846.
	GKS 91	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]
	KT 88	Kaltofen E., Trager, B., Computing with Polynomials Given by Black Boxes for Their Evaluations: Greatesl Common Divisors, Factorization, Separation of Numerators and Denominators, Proc. 29th IEEE FOCS 1988, pp. 296-305.
	KR 90	Richard M. Karp , Vijaya Ramachandran, Parallel algorithms for shared-memory machines, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	K 89	Marek Karpinski, Boolean Complexity of Algebraic Interpolation Problems, Proceedings of the 2nd Workshop on Computer Science Logic, p.138-147, October 03-07, 1988
	L 82	Loos, R., Generalized Polynomial Remainder Sequences, in: "Computer Algebra", Springer, 1982, pp. 115-137.
	MS 81	Mac Williams, F. J., Sloan, N. J. A., The Theory of Error Correcting Codes, North- Holland, 1981.
	M 86	K Mulmuley, A fast parallel algorithm to compute the rank of a matrix over an arbitrary field, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.338-339, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12164]
	P 77a	Plaisted, D., Sparse Complex Polynomials and Polynomial Reducibility, J. Comput. System Sci. 14 (1977), pp. 210-221
	P 77b	Plalsted, D., New N.P-Hard and NP- Complete Polynomial and Integer Divisibility Problems, Proc. 18th IEEE FOCS (1977), pp. 241-253.

CITED BY 2

	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
	Gudmund S. Frandsen , Igor E. Shparlinski, On reducing a system of equations to a single equation, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.163-166, July 04-07, 2004, Santander, Spain