Combining Dimensionality and Rate of Growth Arguments for Establishing Lower Bounds on the Number of Multiplications and Divisions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Combining Dimensionality and Rate of Growth Arguments for Establishing Lower Bounds on the Number of Multiplications and Divisions

Full text

Pdf (1.12 MB)

Source

Journal of the ACM (JACM) archive
Volume 26 , Issue 3 (July 1979) table of contents

Pages: 582 - 601

Year of Publication: 1979

ISSN:0004-5411

Author

Zvi M. Kedem

Programs in Mathematical Sciences, The University of Texas at Dallas, Richardson, TX

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

references 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/322139.322153 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	BELAGA, E C On computing polynomials m one variable with mmal precondmomng of coefficients, Problem~ Kzbernettkt 5 ( 196 !), 7- l 5
	2	BORODIN, A. Horner's rule is umquely optimal in Theory of Machines and Computat:ons, Z Kohavi and A Paz, Eds., Academic Press, New York, 1971, pp 45-58
	3	Roger W. Brockett , David Dobkin, On the optimal evaluation of a set of bilinear forms, Proceedings of the fifth annual ACM symposium on Theory of computing, p.88-95, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804039]
	4	HOPCROFT, J, AND MUSINSKI, J Duality apphed to the complexRy of matrix multtphcatlon and other bdmear forms SIAM J Comptng 2 (Sept 1973), 159-173
	5	KUNG, H T A bound on the multtphcat,on efficiency of iteration Dept of Comptr Scl, Carnegie-Mellon U., Pittsburgh, 1972, pp 1-12
	6	OSTROWSKI, A M On two problems m abstract algebra connected with Homer's rule In Studies m Mathematics and Mechamcs, Presented to Richard yon Mlses by Friends, Colleagues, and Pupds Academic Press, New York, 1954, pp 40--48
	7	PAN, V YA Methods of computing values of polynomials Russian Math Surveys 21 (1966), 105-136.
	8	Mary Shaw , J. F. Traub, On the Number of Multiplications for the Evaluation of a Polynomial and Some of Its Derivatives, Journal of the ACM (JACM), v.21 n.1, p.161-167, Jan. 1974 [doi>10.1145/321796.321810]
	9	STRASSEN, V Evaluation of rational functions In Complexity of Computer Computatlons, R E Miller and J W Thatcher, Eds, Plenum Press, New York, 1972, pp 1-10
	10	STRASSF.N, V. Die Berechnungskomplexitat yon elememarsymmetnschen Funktionen und yon interpolationskoeffizienten Numer Math. 20 (1973), 238-251
	11	WINOGRAD, S On the number of multiplications required to compute certain functions Proc Nat A cad Sct USA. 58 (1967), 1840--1842
	12	WINOGRAD, S On the number of multiphcattons necessary to compute certain functions Comm Pure Appl Math. 23 (1970), 165-179
	13	WINOGRAD, S On the parallel evaluation of certain arithmetic expressions Research Rep RC 4808, IBM Thomas J Watson Research Center, Yorktown Heights, N Y, 1976, pp 1-35