Show simple item record

dc.contributor.authorHorowitz, Ellisen_US
dc.date.accessioned2007-04-19T19:02:54Z
dc.date.available2007-04-19T19:02:54Z
dc.date.issued1973-01en_US
dc.identifier.citationhttp://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR73-160en_US
dc.identifier.urihttps://hdl.handle.net/1813/6009
dc.description.abstractThe problem of devising efficient algorithms for computing $Q(x_{1},\ldots,x_{r-1},P(x_{1},\ldots,x_{r-1}))$ where $P$ and $Q$ are multivariate polynomials is considered. It is shown that for polynomials which are completely dense an algorithm based upon evaluation and interpolation is more efficient than Horner's method. Then various characterizations for sparse polynomials are made and the subsequent methods are re-analyzed. In conclusion, a test is devised which takes only linear time to compute and by which a decision can automatically be made concerning whether to use a substitution algorithm which exploits sparsity or one which assumes relatively dense inputs. This choice yields the method which takes the fewest arithmetic operations.en_US
dc.format.extent1263494 bytes
dc.format.extent420554 bytes
dc.format.mimetypeapplication/pdf
dc.format.mimetypeapplication/postscript
dc.language.isoen_USen_US
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleOn the Substitution of Polynomial Formsen_US
dc.typetechnical reporten_US


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record

Statistics