<p>A black box polynomial is an object that takes as input a valuefor each variable and evaluates the polynomial at the given input.The process of determining the coefficients and terms of a blackbox polynomial is the problem of black box polynomialinterpolation. Two major approaches have been addressing suchpurpose: the dense algorithms whose computational complexities aresensitive to the degree of the target polynomial, and the sparsealgorithms that take advantage of the situation when the number ofnon-zero terms in a designate basis is small. In this dissertationwe cover power, Chebyshev, and Pochhammer term bases. However, asparse algorithm is less efficient when the target polynomial isdense, and both approaches require as input an upper bound oneither the degree or the number of non-zero terms. By introducingrandomization into existing algorithms, we demonstrate and developa probabilistic approach which we call "early termination." Inparticular we prove that with high probability of correctness theearly termination strategy makes different polynomialinterpolation algorithms "smart" by adapting to the degree or tothe number of non-zero terms during the process when either is notsupplied as an input. Based on the early termination strategy, wedescribe new efficient univariate algorithms that race a denseagainst a sparse interpolation algorithm in order to exploit thesuperiority of one of them. We apply these racing algorithms asthe univariate interpolation procedure needed in Zippel'smultivariate sparse interpolation method. We enhance the earlytermination approach with thresholds, and present insights toother such heuristic improvements. Some potential of the earlytermination strategy is observed for computing a sparse shift,where a polynomial becomes sparse through shifting the variablesby a constant.<P>
| Identifer | oai:union.ndltd.org:NCSU/oai:NCSU:etd-20011106-101821 |
| Date | 04 December 2001 |
| Creators | Lee, Wen-shin |
| Contributors | Erich Kaltofen, Hoon Hong, Carla Savage, Michael Singer |
| Publisher | NCSU |
| Source Sets | North Carolina State University |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://www.lib.ncsu.edu/theses/available/etd-20011106-101821 |
| Rights | unrestricted, I hereby certify that, if appropriate, I have obtained and attached hereto a written permission statement from the owner(s) of each third party copyrighted matter to be included in my thesis, dissertation, or project report, allowing distribution as specified below. I certify that the version I submitted is the same as that approved by my advisory committee. I hereby grant to NC State University or its agents the non-exclusive license to archive and make accessible, under the conditions specified below, my thesis, dissertation, or project report in whole or in part in all forms of media, now or hereafter known. I retain all other ownership rights to the copyright of the thesis, dissertation or project report. I also retain the right to use in future works (such as articles or books) all or part of this thesis, dissertation, or project report. |
Page generated in 0.009 seconds