\relax 
\citation{AHU74}
\citation{F72}
\citation{K73}
\citation{BM75}
\citation{PSLT93}
\citation{R88}
\citation{PRT92}
\citation{ASU75}
\@writefile{toc}{\contentsline {section}{\numberline {1}Introduction}{4}}
\newlabel{sec-intro}{{1}{4}}
\@writefile{toc}{\contentsline {subsection}{\numberline {1.1}Machine Model.}{4}}
\newlabel{subsec-assump}{{1.1}{4}}
\@writefile{toc}{\contentsline {subsection}{\numberline {1.2}Multipoint Polynomial Evaluation and Interpolation.}{4}}
\newlabel{subsec-poly eval def}{{1.2}{4}}
\citation{MB72}
\citation{BM71}
\citation{H72}
\citation{F72}
\citation{K73}
\citation{BM75}
\citation{N79}
\citation{PSLT93}
\@writefile{toc}{\contentsline {subsection}{\numberline {1.3}Multipoint Polynomial Evaluation at a Small Number of Points.}{5}}
\newlabel{subsec-Small Number of Points}{{1.3}{5}}
\newlabel{prop-eval small points}{{1.1}{5}}
\citation{MB72}
\citation{F72}
\citation{K73}
\citation{BM75}
\citation{CT65}
\citation{CLW67}
\citation{RK24}
\citation{DL42}
\citation{G58}
\citation{GS66}
\citation{RR72}
\newlabel{prop-gen eval small points}{{1.2}{6}}
\@writefile{toc}{\contentsline {subsection}{\numberline {1.4}The DFT and Generalizations.}{6}}
\newlabel{subsec-gen}{{1.4}{6}}
\citation{ASU75}
\citation{DR95}
\citation{DGR96}
\citation{ASU75}
\newlabel{prop-gen FFT}{{1.3}{7}}
\newlabel{prop-gen FFT eval small points}{{1.4}{7}}
\@writefile{toc}{\contentsline {subsection}{\numberline {1.5}Organization of this paper.}{7}}
\newlabel{subsec-org}{{1.5}{7}}
\citation{GR88}
\citation{EB96}
\citation{G88}
\citation{G88}
\citation{GGS87}
\citation{GR87}
\citation{CGR88}
\citation{CK95}
\citation{CK95}
\citation{PRT92}
\citation{RT96b}
\citation{GR88}
\citation{PRT92}
\citation{RT96a}
\@writefile{toc}{\contentsline {section}{\numberline {2}Approximate Complex Polynomial Evaluation via the Multipole Methods}{9}}
\newlabel{sec-multipole}{{2}{9}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.1}Trummer's Problem.}{9}}
\newlabel{subsec-Trummer}{{2.1}{9}}
\newlabel{prop-trummer}{{2.1}{9}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.2}Multipole Methods.}{9}}
\newlabel{subsec-Multipole}{{2.2}{9}}
\citation{PRT92}
\citation{RT96a}
\citation{PRT92}
\citation{RT96a}
\newlabel{prop-multipole}{{2.1}{10}}
\citation{PRT92}
\citation{RT96a}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.3} Reduction to Trummer's Problem.}{11}}
\newlabel{subsec-Re-evaluation}{{2.3}{11}}
\newlabel{prop-coef}{{2.2}{11}}
\newlabel{prop-reeval errors}{{2.3}{11}}
\citation{AHU74}
\newlabel{prop-aux errors}{{2.4}{13}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.4}Approximate Complex Polynomial Evaluation via DFT and Multipole Algorithms.}{14}}
\newlabel{subsec-approx poly eval}{{2.4}{14}}
\newlabel{prop-unit circle reeval}{{2.2}{14}}
\citation{PRT92}
\citation{RT96a}
\citation{PRT92}
\citation{RT96a}
\citation{GR88}
\citation{EB96}
\citation{PRT92}
\citation{RT96a}
\newlabel{the-reeval}{{2.1}{15}}
\citation{AHU74}
\citation{CK95}
\citation{PRT92}
\citation{RT96a}
\citation{PRT92}
\citation{RT96b}
\citation{PRT92}
\citation{RT96a}
\citation{PRT92}
\citation{RT96b}
\newlabel{the-reeval not fixed}{{2.2}{18}}
\citation{P89}
\citation{G88}
\citation{DB74}
\citation{H84}
\@writefile{toc}{\contentsline {section}{\numberline {3} Chebychev Points and Approximate Real Polynomial Evaluation}{19}}
\newlabel{sec-real eval}{{3}{19}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.1}The Chebychev Point Evaluation Problem.}{19}}
\newlabel{subsec-cheby def}{{3.1}{19}}
\newlabel{lem-exact Chebychev point eval}{{3.1}{19}}
\citation{DB74}
\citation{R88}
\citation{PRT92}
\citation{F72}
\citation{K73}
\citation{BM75}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.2}Approximate Real Evaluation via Interpolation at the Chebychev Points.}{20}}
\newlabel{subsec-real fn eval}{{3.2}{20}}
\newlabel{prop-Chebychev interpol}{{3.1}{20}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.3}Approximate Real Polynomial Evaluation via Interpolation at the Chebychev Points.}{20}}
\newlabel{subsec-real eval}{{3.3}{20}}
\citation{PRT92}
\citation{BP94}
\newlabel{prop-approx real point eval}{{3.2}{21}}
\newlabel{prop-approx complex coef real point eval}{{3.3}{21}}
\newlabel{lem-approx Chebychev point eval}{{3.4}{22}}
\@writefile{toc}{\contentsline {section}{\numberline {4}Approximate Evaluation on a Circle}{22}}
\newlabel{sec-circle}{{4}{22}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.1}Approximate Polynomial Evaluation on a Circle via Interpolation at the Chebychev Angles.}{22}}
\newlabel{subsec-Chebychev Angles}{{4.1}{22}}
\citation{F72}
\citation{K73}
\citation{BM75}
\newlabel{thm-circle appox}{{4.1}{23}}
\newlabel{prop-bound dz dx for theta}{{4.1}{23}}
\newlabel{lem-approx circle interval theta}{{4.2}{25}}
\newlabel{cor-DFT aprox}{{4.1}{26}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.2}An Alternative Approach to Approximate Evaluation on a Circle via Approximate Real Polynomial Evaluation.}{26}}
\newlabel{subsec-alt real eval}{{4.2}{26}}
\citation{DR95}
\citation{DR95}
\newlabel{thm-approx circle interval}{{4.2}{27}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.3}Dutt and Rokhlin's Approximation of a Polynomial on the Unit Circle.}{27}}
\@writefile{toc}{\contentsline {section}{\numberline {5}Approximation Everywhere on the Unit Circle is Not Possible.}{28}}
\newlabel{sec-circle lower bounds}{{5}{28}}
\newlabel{theorem-no approx DFT multiple intervals}{{5.1}{28}}
\newlabel{prop-full circle}{{5.1}{28}}
\newlabel{lem-inner product}{{5.1}{29}}
\newlabel{prop-error q}{{5.2}{29}}
\newlabel{prop-rep q}{{5.3}{30}}
\newlabel{lem-approx matrix product}{{5.2}{32}}
\newlabel{prop-no small rank approx}{{5.4}{32}}
\newlabel{subsec-ack}{{5}{33}}
\bibcite{AHU74}{AHU 74}
\bibcite{ASU75}{ASU 75}
\bibcite{BP94}{BP 94}
\bibcite{BM71}{BM 71}
\bibcite{BM75}{BM 75}
\bibcite{CK95}{CK 95}
\bibcite{CGR88}{CGR 88}
\bibcite{CdB80}{CdB 80}
\bibcite{CLW67}{CLW 67}
\bibcite{CT65}{CT 65}
\bibcite{DB74}{DB 74}
\bibcite{DL42}{DL 42}
\bibcite{DK88}{DK 88}
\bibcite{DGR96}{DGR 96}
\bibcite{D93}{D 93}
\bibcite{DR95}{DR 95}
\bibcite{EMT97}{EMT 97}
\bibcite{EB96}{EB 96}
\bibcite{F72}{F 72}
\bibcite{GS66}{GS 66}
\bibcite{G88}{G 88}
\bibcite{GGS87}{GGS 87}
\bibcite{G58}{G 58}
\bibcite{GR87}{GR 87}
\bibcite{GR88}{GR88}
\bibcite{H86}{H 86}
\bibcite{H84}{H 84}
\bibcite{H72}{H 72}
\bibcite{K73}{K 73}
\bibcite{MR89}{MR 89}
\bibcite{MB72}{MB 72}
\bibcite{N79}{N 79}
\bibcite{P89}{P89}
\bibcite{PRT92}{PRT 92}
\bibcite{PSLT93}{PSLT93}
\bibcite{RR72}{RR 72}
\bibcite{R97}{R 97}
\bibcite{RT96b}{RT 96a}
\bibcite{RT96a}{RT 96b}
\bibcite{R88}{R 88}
\bibcite{RK24}{RK 24}
\citation{BP94}
\@writefile{toc}{\contentsline {section}{\numberline {6}Appendix: Proof of an Alternative Approximate Evaluation on a Circle}{37}}
\newlabel{sec-append alt}{{6}{37}}
\newlabel{prop-bound dz dx}{{6.1}{38}}
\citation{P89}
\@writefile{toc}{\contentsline {section}{\numberline {7}Appendix: Exact Chebychev Point Evaluation in $O(n\mathop {\mathgroup \symoperators log}\nolimits n)$ Work}{43}}
\newlabel{sec-Chebychev Eval}{{7}{43}}
\newlabel{prop-rec chev def}{{7.1}{43}}
\newlabel{prop-rec chev}{{7.2}{44}}
\citation{F72}
\citation{K73}
\citation{BM75}
\citation{AHU74}