Fast Approximate Polynomial Multipoint Evaluation\\ and Applications
Alexander Kobel
It is well known that, using fast algorithms for polynomial multiplication and division, evaluation of a polynomial $F\in\CC[x]$ of degree $n$ at $n$ complex-valued points can be done with $\softOh (n)$ exact field operations in $\CC,$ where $\softOh(\cdot)$ means that we omit polylogarithmic factors. We complement this result by an analysis of approximate multipoint evaluation of $F$ to a precision of $L$ bits after the binary point and prove a bit complexity of $\softOh (n(L + \tau + n\Gamma)),$ where $2^\tau$ and $\cramped{2^{\Gamma}},$ with $\tau,\Gamma\in\NN_{\ge 1},$ are bounds on the magnitude of the coefficients of $F$ and the evaluation points, respectively. In particular, in the important case where the precision demand dominates the other input parameters, the complexity is soft-linear in $n$ and $L.$ Our result on approximate multipoint evaluation has some interesting consequences on the bit complexity of three further approximation algorithms which all use polynomial evaluation as a key subroutine. This comprises an algorithm to approximate the real roots of a polynomial, an algorithm for polynomial interpolation, and a method for computing a Taylor shift of a polynomial. For all of the latter algorithms, we derive near optimal running times. \begin{keywords} approximate arithmetic, fast arithmetic, multipoint evaluation, certified computation, polynomial division, root refinement, Taylor shift, polynomial interpolation \end{keywords}
multipoint-evaluation.tex
\documentclass[11pt]{article}
\pdfoutput=1

\usepackage[utf8]{inputenc}
\usepackage{amsmath,amsthm,amssymb}

%% this is SODA submission format:
% \usepackage[margin=1in,a4paper]{geometry}

%% this is nice to read, and simple:
\usepackage[paper=a4]{typearea}
%% default for DIV=autocalc=10
% \areaset{418.25555pt}{595.80026pt}
\areaset{418pt}{609pt}

\usepackage{biblatex}
\bibliography{longtitles,multipoint-evaluation}
\DeclareFieldFormat{eprint:citeseerx}{%
  CiteSeerX\addcolon\space
  \ifhyperref
  {\href{http://citeseerx.ist.psu.edu/viewdoc/summary?doi=#1}{\nolinkurl{#1}}}
  {\nolinkurl{#1}}}
\DeclareFieldFormat{eprint:hal}{%
  \textsc{oai}\addcolon\space
  \ifhyperref
  {\href{http://hal.inria.fr/#1}{\nolinkurl{hal.inria.fr:#1}}}
  {\nolinkurl{hal.inria.fr:#1}}}

% \usepackage{fnpct}
\usepackage[bottom]{footmisc}
% \usepackage{footnotebackref}

\usepackage{color}
\definecolor{citecolor}{rgb}{0.8,0,0}
\definecolor{linkcolor}{rgb}{0,0,0.8}
\definecolor{urlcolor}{rgb}{0,0,0.8}
\usepackage[colorlinks=true,linktocpage=true,hyperfootnotes=false]{hyperref}
\usepackage[capitalise]{cleveref}
\hypersetup{%
  citecolor=citecolor,
  linkcolor=linkcolor,
  urlcolor=urlcolor
}
\setcounter{tocdepth}{2}
\usepackage{microtype}
\usepackage[mathic]{mathtools}

%% from http://tex.stackexchange.com/questions/43966/how-to-make-the-optional-title-of-a-theorem-bold-with-amsthm
\makeatletter
\def\th@plain{%
  \thm@notefont{}% same as heading font
  \itshape % body font
}
\def\th@definition{%
  \thm@notefont{}% same as heading font
  \normalfont % body font
}
\makeatother

\newtheorem{theorem}{Theorem}
% \crefname{theorem}{Thm.}{Thms.}
\Crefname{theorem}{Theorem}{Theorems}

\newtheorem{corollary}[theorem]{Corollary}
% \crefname{corollary}{Cor.}{Cors.}
\Crefname{corollary}{Corollary}{Corollaries}

\newtheorem{lemma}[theorem]{Lemma}
\Crefname{lemma}{Lemma}{Lemmata}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
% \crefname{definition}{Def.}{Defs.}
\Crefname{definition}{Definition}{Definitions}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
% \crefname{remark}{Rem.}{Rems.}
\Crefname{remark}{Remark}{Remarks}

\theoremstyle{definition}
\newtheorem{algorithm}[theorem]{Algorithm}
% \spnewtheorem{algorithm}[theorem]{Algorithm}{\bfseries}{}
% \crefname{algorithm}{Alg.}{Algs.}
\Crefname{algorithm}{Algorithm}{Algorithms}

\Crefname{proof}{Proof}{Proofs}

\crefformat{equation}{#2(#1)#3}
\Crefformat{equation}{Equation #2(#1)#3}
\crefrangeformat{equation}{#3(#1)#4--#5(#2)#6}
\Crefrangeformat{equation}{Equations #3(#1)#4 to #5(#2)#6}

% \crefname{section}{Sec.}{Secs.}
\Crefname{section}{Section}{Sections}

\newtheorem*{keywords}{Keywords}

\newcommand{\NN}{\ensuremath{\mathbb{N}}}
\newcommand{\ZZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\RR}{\ensuremath{\mathbb{R}}}
\newcommand{\CC}{\ensuremath{\mathbb{C}}}
\newcommand{\Oh}{\ensuremath{O}}
% \newcommand{\sOh}{\ensuremath{{O^\sim}}}
\newcommand{\sOh}{\ensuremath{{\tilde{O}}}}
\newcommand{\softOh}{\sOh}
\DeclareMathOperator{\bdiv}{div}
\newcommand{\ii}{\ensuremath{\mathrm{i}}}
\DeclareMathOperator{\trunc}{trunc}

\newcommand{\tf}{\ensuremath{\tilde{f}}}
\newcommand{\tF}{\ensuremath{\tilde{F}}}
\newcommand{\tg}{\ensuremath{\tilde{g}}}
\newcommand{\tG}{\ensuremath{\tilde{G}}}
\renewcommand{\th}{\ensuremath{\tilde{h}}}
\newcommand{\tH}{\ensuremath{\tilde{H}}}
\newcommand{\tQ}{\ensuremath{\tilde{Q}}}
\newcommand{\tr}{\ensuremath{\tilde{r}}}
\newcommand{\tR}{\ensuremath{\tilde{R}}}
\newcommand{\trho}{\ensuremath{\tilde{\rho}}}
\newcommand{\tvarrho}{\ensuremath{\tilde{\varrho}}}

\newcommand{\hF}{\ensuremath{\hat{F}}}
\newcommand{\hG}{\ensuremath{\hat{G}}}
\newcommand{\hH}{\ensuremath{\hat{H}}}
\newcommand{\hQ}{\ensuremath{\hat{Q}}}
\newcommand{\hR}{\ensuremath{\hat{R}}}
\newcommand{\hrho}{\ensuremath{\hat{\rho}}}
\newcommand{\hx}{\ensuremath{\hat{x}}}

%% the nice epsilon
\newcommand{\eps}{\ensuremath{\varepsilon}}

\newcommand{\mul}{\ensuremath{\mu}}
\newcommand{\sGamma}{\ensuremath{{\Gamma^\ast}}}
\newcommand{\stau}{\ensuremath{{\tau^\ast}}}

\DeclarePairedDelimiter\abs{\lvert}{\rvert}
\DeclarePairedDelimiter\norm{\lVert}{\rVert}
\DeclarePairedDelimiter\sumnorm{\lVert}{\rVert_1}
\DeclarePairedDelimiter\infnorm{\lVert}{\rVert_\infty}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}

\title{Fast Approximate Polynomial Multipoint Evaluation\\
  and Applications}

\usepackage[noblocks]{authblk}
\renewcommand\Authand{\hspace{4em}}
\renewcommand\Affilfont{\small}
\author[1--3]{Alexander Kobel}
\author[1]{Michael Sagraloff}
\affil[1]{Max-Planck-Institut f\"ur Informatik}
\affil[2]{International Max Planck Research School for Computer Science}
\affil[3]{Universit\"at des Saarlandes\vspace{1ex}\authorcr
  Saarbr\"ucken, Germany\vspace{1ex}\authorcr
  \texttt{\{akobel,msagralo\}@mpi-inf.mpg.de}}

\date{}

\begin{document}

\maketitle

\begin{abstract}
  It is well known that, using fast algorithms for polynomial multiplication and division, evaluation of a polynomial $F\in\CC[x]$ of degree $n$ at $n$ complex-valued points
  can be done with $\softOh (n)$ exact field operations in $\CC,$ where $\softOh(\cdot)$ means that we omit polylogarithmic factors.
  We complement this result by an analysis of \emph{approximate multipoint evaluation} of $F$ to a precision of $L$ bits after the binary point and prove a bit complexity of $\softOh (n(L + \tau + n\Gamma)),$
  where $2^\tau$ and $\cramped{2^{\Gamma}},$ with $\tau,\Gamma\in\NN_{\ge 1},$  are bounds on the magnitude of the coefficients of $F$ and the evaluation points, respectively.
  In particular, in the important case where the precision demand dominates the other input parameters, the complexity is soft-linear in $n$ and $L.$

  Our result on approximate multipoint evaluation has some interesting consequences on the bit complexity of three further approximation algorithms which all use polynomial evaluation as a key subroutine.
  This comprises an algorithm to approximate the real roots of a polynomial, an algorithm for polynomial interpolation, and a method for computing a Taylor shift of a polynomial.
  For all of the latter algorithms, we derive near optimal running times.

  \begin{keywords}
    approximate arithmetic, fast arithmetic, multipoint evaluation, certified computation, polynomial division, root refinement, Taylor shift, polynomial interpolation
  \end{keywords}
\end{abstract}
\thispagestyle{empty}
\addtocounter{page}{-1}

\clearpage
\section{Introduction}

We study the problem of approximately evaluating a polynomial $F\in\CC[x]$ of degree $n$ at $n$ points $x_{1},\ldots,x_{n}\in\CC.$
More precisely, we assume the existence of an oracle which provides arbitrarily good approximations of the polynomial's coefficients as well as of the points $x_{i}$ for free;
that is, querying the oracle is as expensive as reading the approximation.
Under this assumption, we aim to compute approximations $\tilde{y}_{i}$ of $y_{i}\coloneqq F(x_{i})$ such that $\abs{y_{i}-\tilde{y}_{i}}\le 2^{-L}$ for all $i=1,\ldots,n$, where $L\in\NN$ is a given non-negative integer.
In what follows, let $2^{\tau}$ and $2^{\Gamma}$ with $\tau,\Gamma\in \NN_{\ge 1}$ be upper bounds for the absolute values of the coefficients of $F$ and the points $x_{i},$ respectively.
\medskip

When considering a sequential approach, where each $\tilde{y}_{i}\approx F(x_{i})$ is computed independently by using Horner's Scheme and approximate but certified interval arithmetic \cite{Aqir},
we need $O(n)$ arithmetic operations with a precision of $O(L+\tau+n\Gamma)$ for each of the points $x_{i}$.
Thus, the total cost for all evaluations is bounded by $\sOh(n^{2}(L+\tau+n\Gamma))$ bit operations.\footnote{$\sOh$ means that polylogarithmic factors are ignored.}

In this paper, we show that using an approximate variant of the classical fast multipoint evaluation scheme \cite{moenckborodin72,vzGG03},
we can improve upon the latter bound by a factor of $n$ to achieve $\sOh(n(L+\tau+n\Gamma))$ bit operations.
The classical fast multipoint evaluation algorithm reduces polynomial evaluation at $n$ points to successive polynomial multiplications and divisions which are all balanced with respect to degree.
It is a well known fact that, for exactly computing all values $y_{i},$ it uses only $O(n\log^{2}n)$ \emph{exact field operations} in $\CC$ compared to $O(n^{2})$ field operations if all evaluations are carried out independently;
see \cref{sec:multipointevaluation} for a short review.
This method has mostly been studied for low precisions, in particular for its performance with machine floating point numbers; see, e.g., \cite[Section 2]{BF00} or the extensive discussion in \cite{KZ08}.
It is widely considered to be numerically unstable, mainly due to the need of polynomial divisions, and the precision demand for the sequential evaluations based on Horner's scheme does not directly carry over.

In previous work (e.g., \cite{DBLP:journals/adcm/Pan95,DBLP:journals/siamcomp/Reif99}), more involved algorithms for fast approximate multipoint evaluation have been introduced
that allow to decrease the total number of (infinite precision) arithmetic operations from $O(n\log^{2} n)$ to $O(n\log n)$ (if $n$ dominates all other input parameters).
The authors mainly focus on the \emph{arithmetic complexity} of their algorithms, and thus no bound on the \emph{bit complexity} is given.
For the special case where the points $x_{i}$ are the roots of unity, the problem can be solved with $\sOh(n(\tau+L))$ bit operations by carrying out the fast Fourier transform with approximate arithmetic~\cite[Theorem~8.3]{schonhage:fundamental}.
However, for general points, we are not aware of any bit complexity result which considerably improves upon the bound $\sOh(n^{2}(L+\tau+n\Gamma))$ that one directly obtains from carrying out all evaluations independently.
\medskip


The main contribution of this paper is to show that the previously claimed issue of numerical instability within the classical fast multipoint evaluation scheme can be resolved.
The crux of our approach is best described as follows:
First, we exploit the fact that all divisors in the considered polynomial divisions are monic polynomials $g_{i,j}(x) = (x - x_{(j-1)\cdot 2^i + 1}) \cdots (x - x_{j\cdot 2^i}),$ with $i$ from $1$ to $\log n-1$ and $j$ from $1$ to $n / 2^i,$
which allow a numerical stable division, at least if the precision $L$ dominates the values $n$ and $\Gamma$; see \cref{cor:div-compl-monic} for a precise statement.
Second, we consider a numerical division algorithm from Sch\"onhage \cite{Schoenhage82} which yields an output precision of $L$ bits after the binary point if the algorithm runs with an \emph{internal} precision of $2L.$
However, we aim to stress the fact (as proven in \cref{subsec:division}) that, for the input of the division algorithm, it suffices to consider an approximation of only $L$ bits after the binary point.
This turns out to be crucial in the multipoint evaluation algorithm where we have to consider a number of $\log n$ successive divisions, and thus the propagated error stays within $\approx 2^{-L}$ compared to $\approx 2^{-L/n}.$
\medskip

Our result has an interesting consequence on the bit complexity of other approximation algorithms which all use polynomial evaluation as a key subroutine.
Most algorithms for computing approximations of the real roots of a square-free polynomial $F\in\RR[x],$ with $n\coloneqq \deg F,$
consider polynomial evaluation of $F$ at a constant number of points in some isolating interval $I$ (e.g., at its endpoints) that contains exactly one root of $F.$
In \cref{sec:refinement}, we combine our fast method for approximate multipoint evaluation with a recently introduced algorithm for real root approximation, called \textsc{Aqir} \cite{Aqir},
to show that the bit complexity for computing $L$-bit approximations of all real roots of $F$ improves by a factor of $n$ from $\sOh(n^{2}L)$ to $\sOh(nL)$ if $L$ dominates parameters that only depend on $F$
(e.g., the separation of its roots).
The latter result mainly stems from the fact that, instead of considering the refinements of each of the isolating intervals independently, we may carry out all evaluations of $F$ in parallel.\footnote{Very recent work~\cite{pantsi:ISSAC13} introduces an alternative method for real root refinement which, for the task of refining a single isolating interval, achieves comparable running times as \textsc{Aqir}. In a preliminary version of their conference paper (which has been sent by the authors to M.~Sagraloff in April 2013), the authors claim that using approximate multipoint evaluation also yields an improvement by a factor $n$ for their method. Given the results from this paper, this seems to be correct, however, their version of the paper did not contain a rigorous argument to bound the precision demand for the fast multipoint evaluation.}

Another important application of multipoint evaluation is polynomial interpolation.
For given points $x_{1},\ldots,x_{n}\in\CC$ and corresponding interpolation values $v_{1},\ldots,v_{n},$ there exists a unique polynomial $F\in\CC[x]$ of degree less than $n$ such that $F(x_{i})=v_{i}$ for all $i.$
Based on our approach for fast multipoint evaluation, we prove that computing an $L$-bit approximation $\tilde{F}$ of $F$ (i.e., $\sumnorm{\tilde{F}-F} \le 2^{-L}$) uses only $\sOh(nL)$ bit operations
(for $L$ dominating $n$ and the bitsizes of the $x_i$'s and $v_i$'s).
Our more general complexity bound as stated in \cref{sec:interpolation} also involves the absolute values of the points $x_{i}$ and the values $v_{i}$ as well as the geometric location of the $x_{i}$'s.

Finally, we combine fast approximate multipoint evaluation and approximate interpolation in order to derive an alternative method to \cite[Theorem~8.4]{Schoenhage82}
for computing an $L$-bit approximation of a Taylor shift of a polynomial $F$ (i.e., the polynomial $F_{m}(x)\coloneqq F(m+x)$ for some $m\in\CC$) with $\sOh(nL)$ bit operations (again, for $L$ dominating).
The details are given in \cref{sec:taylor}.
\clearpage

\section{Approximate Polynomial Multipoint Evaluation}\label{sec:multipointevaluation}

Given a polynomial $F(x) = \sum_{i=0}^n f_i x^i \in \CC[x]$ of degree $n,$ complex points $x_1, \dots, x_n \in \CC,$ and a non-negative integer $L\in\NN,$
our goal is to compute approximations $\tilde{y}_j$ for $y_j \coloneqq F(x_j)$ such that $\abs{\tilde{y}_j - y_j} \le 2^{-L}$ for all $j=1,\ldots,n.$
Furthermore, let $2^{\tau}$ and $2^{\Gamma},$ with $\tau,\Gamma\in\NN_{\ge 1},$ denote bounds on the absolute values of the coefficients of $F$ and the points $x_{j},$ respectively.

For the sake of simplicity, assume that $n = 2^k$ is a power of two; otherwise, pad $f$ with zeros.
We require that arbitrary good approximations of the coefficients $f_{i}$ and the points $x_j$ are provided by an oracle for the cost of reading the approximations.
That is, asking for an approximation of $F$ and the points $x_{j}$ to a precision of $\ell$ bits after the binary point takes $\Oh(n(\tau+\Gamma+\ell))$ bit operations.

\begin{algorithm}[Multipoint evaluation]
  We will follow the classical divide-and-conquer method for fast polynomial multipoint evaluation:
  \label{alg:exact-mp-eval}%
  \begin{enumerate}%
  \item\label{alg:exact-mp-eval:subproducts}%
    Starting with the linear factors $g_{0,j}(x) \coloneqq x - x_j,$ we recursively compute the subproduct tree
    \begin{align}\label{def:gij}
      g_{i,j}(x) &\coloneqq (x - x_{(j-1) 2^i + 1}) \cdots (x - x_{j 2^i})
      = g_{i-1,2j-1}(x) \cdot g_{i-1,2j}(x)
    \end{align}
    for $i$ from 1 to $k-1$ and $j$ from $1$ to $n / 2^i=2^{k-i},$ that is, going up from the leaves.
    Notice that $\deg g_{i,j} = 2^i.$
  \item\label{alg:exact-mp-eval:remainders}%
    Starting with $r_{k,1}(x) \coloneqq F(x),$ we recursively compute the remainder tree
    \begin{align*}
      r_{i,j}(x) &\coloneqq F(x) \bmod g_{i,j}(x)
      = r_{i+1,\ceil{j/2}}(x) \bmod g_{i,j}(x)
    \end{align*}
    for $i$ from $k-1$ to $0$ and $j$ from $1$ to $n / 2^i=2^{k-i},$ that is, going down from the root.
    Notice that $\deg r_{i,j} < 2^i.$
  \item\label{alg:exact-mp-eval:results}%
    Observe that the value at point $x_j$ is exactly the remainder
    \begin{align*}
      r_{0,j} = F(x) \bmod g_{0,j}(x) = F(x) \bmod (x - x_j) = F(x_j) \in \CC.
    \end{align*}
  \end{enumerate}
\end{algorithm}

It is well known that this scheme requires a total number of $\Oh(\mul(n)\log n)$ arithmetic operations in $\CC$
(e.g., see \cite[Chapter~1, Section~4]{BP94} or \cite[Corollary~10.8]{vzGG03}), where $\mul(n)$ denotes the arithmetic complexity of multiplying two polynomials of degree $n$ or, equivalently,
the bit complexity of multiplying two $n$-bit integers. Hence, using an asymptotically fast multiplication method with soft-linear bit complexity such as the algorithms by De et al. \cite{DKSS08} or F\"urer \cite{Furer09} yields a soft-linear arithmetic complexity for polynomial multipoint evaluation.
However, we are mainly interested in the bit complexity of the above algorithm if the multiplications and divisions are carried out with approximate but certified arithmetic
such that an output precision of $L$ bits after the binary point can be guaranteed.
Fast polynomial division is widely considered to be numerically instable which explains why a result on the bit complexity of approximate polynomial evaluation is still missing.
We will close this gap by using a method from Sch\"onhage for numerical polynomial division based on  a direct application of discrete Fourier transforms to minimize the number of numerically unstable operations; see \cref{subsec:division}.

\subsection{Fast Approximate Polynomial Multiplication}\label{subsec:fastmultiplication}

\begin{definition}[Polynomial approximation]
  Let $\norm{\cdot}$ be a norm on the set of complex polynomials considered as a vector space over $\CC.$
  For a polynomial $f=\sum_{i=0}^{n} a_{i}x^{i} \in \CC[x]$ and an integer $\ell,$  a polynomial $\tf \in \CC[x]$ is called an \emph{(absolute) $\ell$-bit approximation of $f$ w.r.t.\ $\norm{\cdot}$} if $\norm{\tf - f} \le 2^{-\ell}.$
  Alternatively, if $\tf = f + \Delta f,$ this is equivalent to $\norm{\Delta f} \le 2^{-\ell}.$

  When not mentioned explicitly, we assume the norm to be the $1$- or sum-norm $\sumnorm{\cdot}$ with $\sumnorm{f} = \sum_{i=0}^{n} \abs{a_i }.$
\end{definition}
The definition of an (absolute) polynomial approximation does not take into account the degree.
Typically, degree loss arises when approximating a polynomial with very small leading coefficients which may be truncated to zero.
However, the definition also allows for a higher (but finite) degree of the approximation.

We further remark that any $\ell$-bit $\sumnorm{\cdot}$-approximation of a polynomial implies an $\ell$-bit approximation of each coefficient or,
in other words, an $\ell$-bit approximation w.r.t. the $\infty$- or maximum-norm $\infnorm{f} = \max_i\abs{a_i}.$
Conversely, any coefficient-wise approximation $\tf$ on $f$ to $\ell + \log(\tilde{n}+1)$ bits, with $\tilde{n} = \deg \tf,$ constitutes an $\ell$-bit $\sumnorm{\cdot}$-approximation of $f.$

The reason why we favor the sum-norm is its sub-multiplicativity property, that is, for $f,$ $g \in \CC[x],$ we have
\begin{align}\label{submulti}
  \sumnorm{f\cdot g}
  \le \sumnorm{f}\cdot \sumnorm{g}.
\end{align}

In practice, we also require the precision of the coefficients to be not too high in order to avoid costly arithmetic with superfluous accuracy.
In the light of the preceding comment, we can assume that the coefficients are represented by dyadic values with less than $\ell + \log(n+1) + c$ bits after the binary point for some small constant $c.$

\begin{definition}[Integer truncation]
  For a complex number $z = a + \ii\,b \in \CC,$ a Gaussian integer $\tilde{z} = \tilde{a} + \ii\,\tilde{b} \in \ZZ[\ii]$ is called an \emph{integer truncation of $z$} if $\abs{z - \tilde{z}} \le 1.$
  An integer truncation $\tilde{f} \in \ZZ[\ii][x]$ of a polynomial $f \in \CC[x]$ is defined coefficient-wise.
\end{definition}
In what follows, we ignore the fact that there are several truncations for a complex number and, for the sake of simplicity, pretend that we can compute ``the'' truncation of $f$ and denote it by $\trunc(f).$
This is reasonable since, for any $\ell\ge 1,$ coefficient-wise rounding of any $\ell$-bit $\infnorm{\cdot}$-approximation of $f$ yields a unique truncation (although not necessarily the same for different $\ell$).

\begin{theorem}[Numerical multiplication of polynomials]
  \label{thm:mul-compl}
  Let $f\in\CC[x]$ and $g\in\CC[x]$ be polynomials of degree less than or equal to $n$ and with coefficients of modulus less than $2^b$ for some integer $b\ge 1.$
  Then, computing an $\ell$-bit $\sumnorm{\cdot}$-approximation $\th$ for the product $h \coloneqq f\cdot g$ is possible in
  \begin{align*}
    \Oh (\mul (n (\ell + b + 2\log n))) \quad&\text{or}\quad \sOh (n(\ell + b))\\
    \shortintertext{bit operations and with a precision demand of at most}
    \ell + b + 2\ceil{\log(n+1)} + 3 \quad&\text{or}\quad \ell + \Oh (b + \log n)
  \end{align*}
  bits on each the coefficients of $f$ and $g.$
\end{theorem}
\begin{proof}
  Let $s \coloneqq \ell + b+2\ceil{\log(n+1)}+2.$
  Define $F \coloneqq  2^s f$ and $G \coloneqq  2^s g,$ and notice that $H \coloneqq F\,G = 2^{2s}h.$
  We consider polynomials $\tF \coloneqq \trunc(F)$ and $\tG \coloneqq \trunc(G) \in \ZZ[\ii][x]$ and write $\Delta F \coloneqq \tF - F$ and $\Delta G \coloneqq \tG - G.$
  Since $\sumnorm{\Delta F},$ $\sumnorm{\Delta G}\le n+1,$
  \begin{align*}
    \sumnorm{ \tF \, \tG - F\,G } &\le \sumnorm{\Delta F\cdot G} + \sumnorm{F\cdot \Delta G}+\sumnorm{\Delta F \cdot \Delta G}\\
    &\le \sumnorm{\Delta F}\cdot \sumnorm{G}+\sumnorm{F}\cdot \sumnorm{\Delta G}+\sumnorm{\Delta F}\cdot \sumnorm{\Delta G}\\
    &\le (n+1)^{2} 2^{s+b}+(n+1)^{2} 2^{s+b}+(n+1)^{2}\\
    &\le (n+1)^{2}\cdot 2^{s+b+2}
  \end{align*}
  holds.
  For $\th \coloneqq 2^{-2s} \tF\,\tG,$ it follows that
  \begin{align*}
    \sumnorm{\th - h} \le 2^{-2s} (n+1)^{2} \cdot 2^{s+b+2}  \le 2^{b+2\log(n+1)+2 - s} \le 2^{-\ell},
  \end{align*}
  hence an $\ell$-bit-approximation as required can be recovered from the exact product of $\tF$ and $\tG$ by mere bitshifts. Since $\infnorm{\tF},$ $\infnorm{\tG} \le 2^{s+b},$ multiplication of $\tF$ and $\tG$ can be carried out exactly in $\Oh (\mul((s+b) n))$ bit operations. This proves the complexity result.
  For the precision requirement, notice that $\infnorm{F},$ $\infnorm{G} \le 2^{s+b},$ and thus we need $(s + b + \lceil\log (n+1)\rceil+3)$-bit $\infnorm{\cdot}$-approximations of $f$ and $g$ to compute $\tF$ and $\tG.$
\end{proof}


\subsection{Fast Approximate Polynomial Division}\label{subsec:division}

\begin{definition}[Numerical division of polynomials]
  Given a dividend $f\in\CC[x],$ a divisor $g \in \CC[x],$ and an integer $\ell\ge 1,$ the task of \emph{numerical division of polynomials} is to compute polynomials $\tQ\in\CC[x]$ and $\tR\in\CC[x]$ satisfying
  \begin{align*}
    \sumnorm{f - (\tQ \cdot g + \tR)} \le 2^{-\ell}
  \end{align*}
  with $\deg \tQ \le \deg f - \deg g$ and $\deg \tR < \deg g.$
\end{definition}

\begin{theorem}({Sch\"onhage \cite[Theorem~4.1]{Schoenhage82}})
  \label{thm:div-compl-org}
  Let $f \in \CC[x]$ be a polynomial of degree $\le 2n$ and with norm $\sumnorm{f} \le 1,$ and let $g \in \CC[x]$ be a polynomial of degree $n$ with norm $1 \le \sumnorm{g} \le 2.$
  Suppose that a bound $2^{\rho},$ with $\rho\in \NN_{\ge 1},$ on the modulus of all roots of $g$ is given.
  Then, numerical division of $f$ by $g$ up to an error of $2^{-\ell}$ needs a number of bit operations bounded by
  \begin{align*}
    \Oh (\mul (n (\ell + n \rho)))=\sOh(n(\ell+n\rho)).
  \end{align*}
\end{theorem}

In his presentation of the division algorithm, Sch\"onhage carefully analyses the required precision for the needed operations in his algorithm as $\mathbf{2}\cdot \ell + 5n \rho + \Oh(n)$ bits;
see \cite[(4.14) and (4.15)]{Schoenhage82}.
Hence, one might conclude that this bound also expresses the precision demand on the input polynomials $f$ and $g.$
However, the factor $\mathbf{2}$ in the above bound is only needed for the precision with which the internal computations have to be performed, whereas it is not necessary for the precision demand of the input polynomials $f$ and $g.$
In particular, for $\ell \ggg n \rho,$ input and output accuracy are asymptotically identical, independently from the algorithm used to carry out the numerical division.
For a proof of the above claim, we need an additional result from Sch\"onhage which provides a worst-case perturbation bound for polynomial zeros under perturbation of its coefficients.

\begin{theorem}(Sch\"onhage \cite[Theorem~2.7]{Schoenhage85})
  \label{thm:root-perturbation}
  Let $f \in \CC[x]$ be a polynomial of degree $n$ with zeros $x_1, \dots, x_n,$ not necessarily distinct, and let $\hat{f}$ be a $\log (\eta\,\sumnorm{f})$-approximation of $f$ for $\eta \le 2^{-7n}.$
  Then, the zeros $\hx_1, \dots, \hx_n$ of $\hat{f}$ can be numbered such that $\abs{\hx_j - x_j} < 9\sqrt[n]{\eta}$ for $\abs{x_j} \le 1$ and $\abs{1/\hx_j - 1/x_j} < 9\sqrt[n]{\eta}$ for $\abs{x_j} \ge 1.$%
  \footnote{Sch\"onhage points out that the theorem also holds for zeros at infinity, that is, in the case where $\deg f \ne \deg \hat{f}.$
    However, in our applications, the degrees will always be the same.}
\end{theorem}

We can now give a stronger version of \cref{thm:div-compl-org} which comprises the claimed bound on the needed input precision. In addition, we show that, within a comparable time bound as given in~\cref{thm:div-compl-org}, we can guarantee that the computed polynomials $\tilde{Q}$ and $\tilde{R}$ are $\ell$-bit approximations of their exact counterparts.

\begin{theorem}
  \label{lem:div-prec-req}
  Let $f,$ $g$ and $\rho$ as in \cref{thm:div-compl-org}, and $Q \coloneqq f \bdiv g$ and $R \coloneqq f \bmod g$ be the exact quotient and remainder in the polynomial division of $f$ by $g.$

  Then, the cost for computing $\ell$-bit approximations $\tQ$ and $\tR$ of $Q$ and $R$ satisfying $\sumnorm{f-(\tQ\cdot g+\tR))}\le 2^{-\ell}$ is bounded by $\sOh(n(\ell+n\rho))$ bit operations.
  For this computation, we need $(\ell+32n\rho)$-bit approximations of the polynomials $f$ and $g.$
\end{theorem}

\begin{proof}
  Let $\hat{f} = f + \Delta f$ and $\hat{g} = g + \Delta g$ be arbitrary $\ell_f$- and $\ell_g$-bit approximations for $f = \sum_{i=0}^{2n} f_i x^i$ and $g = \sum_{i=0}^{n} g_ix^i,$
  where $\deg \hat{f} \le 2n,$ $\deg \hat{g} \le \deg g,$ and $\ell_f$ and $\ell_g$ are integers to be specified later.

  \medskip
  First, we note that $\deg g$ and $\deg \hat{g}$ actually coincide for any $\ell_g \ge n(\rho+2)+1.$
  Namely, there exists at least one coefficient $g_{i}$ of $g$ with $\abs{g_{i}}\ge 1/(n+1)\ge 2^{-n}$ since $\sumnorm{g}\ge 1,$ and thus $\abs{g_{n}}\ge \abs{g_{i}}\cdot 2^{-n-n\rho}\ge 2^{-n(\rho+2)},$
  where the second to last inequality follows from the fact that $\abs{g_{i}}\le \abs{g_{n}}\cdot 2^{n}\prod_{z:g(z)=0}\max(1,\abs{z})\le \abs{g_{n}}\cdot 2^{n+n\rho}.$
  Hence, in particular, we have
  \begin{align*}
    \abs{g_{n}},\abs{\hat{g}_{n}}\ge 2^{-n(\rho+2)-1}\ge 2^{-4n\rho}\text{ for all }\ell_g \ge n(\rho+2)+1.
  \end{align*}

  \medskip
  Next, we derive a necessary condition on the precision $\ell_g$ such that $2^{2\rho}$ is a root bound for $\hat{g}.$
  Suppose that $\ell_g \ge \max(n(\rho+2)+1,7n+1),$ then we may apply \cref{thm:root-perturbation} to the polynomials $g$ and $\hat{g}$ which have the same degrees as shown above.
  For $x$ and $\hx$ an arbitrary corresponding pair of roots of the polynomials $g$ and $\hat{g},$ we distinguish two cases:
    \begin{enumerate}
  \item If $\abs{x} \le 1,$ it immediately follows $\abs{\hx} < \abs{x} + 9\sqrt[n]{2^{-\ell_g}}$ and, hence, $\abs{\hx} < 2^{\rho} + 1< 2^{2\rho}.$
  \item For $x$ outside the unit circle, we have $\abs{x} / \abs{\hx} > 1 - 9\sqrt[n]{2^{-\ell_g}} \abs{x}.$
    Thus, we aim for $9\sqrt[n]{2^{-\ell_g}} 2^{\rho} \le 1/2$ which is fulfilled if $\ell_g \ge n(\rho+5)>n\log 18 + n \rho.$
  \end{enumerate}
  In what follows, we assume that $\ell_g \ge \max(7n+1,n(\rho+5)).$
  This ensures that the degrees of $g$ and $\hat{g}$ coincide and $2^{\hat{\rho}},$ with $\hrho\coloneqq 2\rho,$ constitutes an upper bound on the absolute value of all roots of $g$ as well as for all roots of $\hat{g}.$

  \medskip
  Suppose that $f= Q \cdot g + R$ and $\hat{f} = \hQ \cdot \hat{g} + \hR$ are the \emph{exact} representations of $f$ and $\hat{f}$ after division with remainder,
  then we aim to show that the pair $(\hQ,\hR)$ is actually a good approximation of $(Q,R)$ (i.e., $\approx \min(\ell_{f},\ell_{g})$-bit approximations) if $\ell_{f}$ and $\ell_{g}$ are both large enough.
  Write $\Delta Q \coloneqq \hQ - Q$ and $\Delta R \coloneqq \hR - R.$
  The coefficients $Q_{k}$ of $Q$ appear as leading coefficients in the Laurent series of the function
  \begin{align*}
    \frac{f(x)/x^n}{g(x)} = \frac{f_{2n} + f_{2n-1}/x + f_{2n-2}/x^2 + \cdots}{g_n + g_{n-1}/x + g_{n-2}/x^2 + \cdots}
    = Q_n + \frac{Q_{n-1}}{x} + \frac{Q_{n-2}}{x^2} + \cdots
  \end{align*}
  and can be represented, using Cauchy's integral formula, as
  \begin{align}
    \label{eq:cauchy-integral}
    Q_k = \frac{1}{2\pi \ii} \int_{\abs{x}=\varrho} \frac{f(x)/x^n}{g(x)} x^{k-1} \; dx
  \end{align}
  for any $\varrho > 2^{\rho}$; see \cite[(4.7)--(4.9)]{Schoenhage82}.
  Using the corresponding representation of the coefficients $\hQ_k$ of $\hat{Q},$ we can estimate (here, for any $\varrho > 2^{\hat{\rho}}$)
  \begin{align}
    \abs{\hQ_k - Q_k}
    \label{eq:cauchy-integral-delta}
    &= \frac{1}{2\pi} \; \abs[\Big]{ \int_{\abs{x}=\varrho} \frac{\Delta f(x) \cdot g(x) - f(x) \cdot \Delta g(x)}{g(x) \, \hat{g}(x)} x^{k-n-1} \; dx }.
  \end{align}
  Throughout the following considerations, we fix $\varrho: = 2^{\hrho}+1=2^{2\rho}+1<2^{3\rho}.$
  The absolute value of the numerator of the integrand is bounded by
  \begin{align*}
    &\hphantom{{}={}}
    (\abs{\Delta f(x) \cdot g(x)} + \abs{f(x) \cdot \Delta g(x)}) \cdot \abs{x}^{k-n-1}\\
    &\le (\sumnorm{\Delta f} \,\varrho^{2n} \cdot \sumnorm{g} \,\varrho^n + \sumnorm{f} \,\varrho^{2n} \cdot \sumnorm{\Delta g} \,\varrho^n) \cdot \varrho^{k-n-1}\\
    &\le (2^{-\ell_f+1} + 2^{-\ell_g+1}) \,\varrho^{2n+k-1}\le (2^{-\ell_f+1} + 2^{-\ell_g+1}) \,\varrho^{2n+k}
  \end{align*}
  and, for the denominator, we have
  \begin{align*}
    \abs{g(x)\,\hat{g}(x)} &\ge \abs{g_n} (\varrho-2^{\rho})^n \!\cdot \abs{\hat{g}_n} (\varrho-2^{\hrho})^n \ge \abs{g_{n}}\cdot \abs{\hat{g}_{n}}\ge 2^{-8n\rho}.
  \end{align*}
  Now, using the latter two estimates in \cref{eq:cauchy-integral-delta} yields
  \begin{align*}
    \abs{\Delta Q_k} = \abs{\hQ_k - Q_k}
    &\le
    (2^{1-\ell_g} + 2^{-\ell_g})\cdot 2^{8n\rho}\cdot \varrho^{2n+k}.
  \end{align*}
  Summing over all $k = 0, \dots, n$ gives
  \begin{align*}
    \sumnorm{\Delta Q} = \sumnorm{\hQ - Q} &\le (2^{-\ell_f+1} + 2^{-\ell_g+1}) \cdot 2^{8n\rho}\cdot\varrho^{2n} \frac{\varrho^{n+1}-1}{\varrho-1}\\
    &\le (2^{-\ell_f+1} + 2^{-\ell_g+1}) \cdot 2^{8n\rho}\cdot\varrho^{3n+1}\\
    &< (2^{-\ell_f+1} + 2^{-\ell_g+1}) \cdot 2^{20n\rho}<2^{-\min(\ell_{f},\ell_{g})+20n\rho+2},
  \end{align*}
  where we used that $\varrho=2^{2\rho}+1<2^{2\rho+1}$ and thus $\varrho^{3n+1}< 2^{12n\rho}.$
  Hence, for
  \begin{align}
    \label{constraintsell}
    \ell_f,\, \ell_g \ge \ell+20n\rho+4,
  \end{align}
  the polynomial $\hQ$ is an $(\ell+2)$-bit approximation of $Q.$
  An analogous computation as above based on the formula \cref{eq:cauchy-integral} further shows that
  \begin{align}
    \label{eq:bound-norm-Q}
    \sumnorm{Q} \le 2^{4n\rho}\cdot \varrho^{2n+1}\le 2^{13n\rho}.
  \end{align}
  Hence, under the above constraints from \eqref{constraintsell} for $\ell_{f}$ and $\ell_{g},$ we conclude that
  \begin{align*}
    \sumnorm{\hR - R}
    &= \sumnorm{ (\hat{f} - \hQ\,\hat{g}) - (f - Q\,g) }\\
    &\le \sumnorm{\Delta f} + \sumnorm{Q}\sumnorm{\Delta g} + \sumnorm{\Delta Q}\sumnorm{g} + \sumnorm{\Delta Q}\sumnorm{\Delta g}\\
    &\le 2^{-\ell_f} + 2^{13n\rho} \cdot 2^{-\ell_g} + 2^{-\ell-2}\cdot 2 + 2^{-\ell-2}\cdot 2^{-\ell_g}\\
    &< 2^{-\ell-3} + 2^{-\ell-3} + 2^{-\ell-1} + 2^{-\ell-3}\le 2^{-\ell},
  \end{align*}
  thus $\hR$ constitutes an $\ell$-bit approximation of $R.$

  \medskip
  We are now in the position to put the pieces together and prove the main statements of the theorem.
  For $\tilde{\ell}\coloneqq \ell+32n\rho> (\ell+3)+20n\rho+4,$\footnote{In fact, it suffices to choose $\tilde{\ell}\coloneqq \ell+27n\rho$, however, we aimed for ``nice numbers.''} we first choose $\tilde{\ell}$-bit approximations $\tilde{f}$ and $\tilde{g}$ of $f$ and $g,$ respectively,
  such that $\sumnorm{\tilde{f}}\le 1$ and $1\le \sumnorm{\tilde{g}}\le 2.$%
  \footnote{Notice that this can always be achieved since we can always choose approximations of $f$ and $g$ which decrease or increase the corresponding $1$-norms by less than $\cramped{2^{-\tilde{\ell}}}<1/2.$}
  We can now apply \cref{thm:div-compl-org} to compute polynomials $\tilde{Q}$ and $\tilde{R}$ such that $\sumnorm{\tilde{f}-(\tilde{Q}\cdot \tilde{g}+\tilde{R})}\le 2^{-\tilde{\ell}}.$
  For this step, we need $\sOh(n(\ell+n\rho))$ bit operations.
  We define $\hat{f}\coloneqq \tilde{Q}\cdot\hat{g}+\tilde{R}$ and $\hat{g}\coloneqq \tilde{g},$ where the latter two polynomials are $\tilde{\ell}$-bit approximations of $f$ and $g,$ respectively.
  Thus, the above consideration shows that $\tilde{Q}$ and $\tilde{R}$ are $(\ell+3)$-bit approximations of the exact solutions $Q$ and $R,$ respectively.
  It follows that
  \begin{align*}
    \sumnorm{f-(\tilde{Q} g+\tilde{R})}&\le \sumnorm{(Q-\tilde{Q})\cdot g}+\sumnorm{R-\tilde{R}}\\
    &\le \sumnorm{Q-\tilde{Q}}\cdot \sumnorm{g}+2^{-\ell-3}\le 2^{-\ell}
  \end{align*}
  holds, completing the proof.
\end{proof}

Notice that the above result shows that the precision demand for the input polynomials is of the same size as the desired output precision plus a term which only depends on fixed parameters, that is, $n$ and $\rho$.
This will turn out to be crucial when considering numerical division within the multipoint evaluation algorithm.
Namely, since we have to perform $\log n$ successive divisions, a precision demand of $\mathbf{2}\cdot \ell$ (as needed for the internal computations in Sch\"onhage's algorithm) for the input in each iteration
would eventually propagate to a precision demand of $n\ell,$ which is undesirable.
However, from the above theorem, we conclude that, for an output precision of $\ell$, an input precision of $\ell+O((\log n)\cdot n\rho)$ is sufficient because, in each of the $\log n$ successive divisions, we loose a precision of $O(n\rho).$
In order to give more precise results (and rigorous arguments), we first have to make \cref{lem:div-prec-req} applicable to polynomials with higher norm as they appear in the multipoint evaluation scheme.
With this task in mind, we concentrate on the case of \emph{monic} divisors $g.$

\begin{corollary}
  \label{cor:div-compl-monic}
  Let $f \in \CC[x]$ be a complex polynomial of degree $\le 2n$ with $\sumnorm{f} \le 2^{b}$ for some integer $b \ge 1,$ and let $g$ be a \emph{monic} polynomial of degree $n$ with a given root bound $2^{\rho},$
  where $\rho\in\NN_{\ge 1}.$
  Let $Q \coloneqq f \bdiv g$ and $R \coloneqq f \bmod g$ denote the exact quotient and remainder in the polynomial division of $f$ by $g.$

  Then, the cost for computing $\ell$-bit approximations $\tQ$ and $\tR$ of $Q$ and $R$, respectively, with $\sumnorm{f-(\tQ\cdot g+\tR))}\le 2^{-\ell}$ is bounded by
  \begin{align*}
    \sOh(n(\ell+b+n\rho))
  \end{align*}
  bit operations.
  For this computation, we need $(\ell+b+n(2\rho+2\ceil{\log 2n}+32))$-bit approximations of the polynomials $f$ and $g.$
  The approximate remainder $\tR$ fulfills
  \begin{align}
    \label{eq:bound-norm-remainder}
    \sumnorm{\tR}
    \le 2^{16n+2n\rho+2n\log\ceil{2n}+b}  = 2^{b + 2n\rho + \Oh (n\log n)}.
  \end{align}
\end{corollary}
\begin{proof}
  Let $s \coloneqq \rho+\ceil{\log 2n}$ and $\ell^\ast \coloneqq \ell + b + ns.$
  We define
  \begin{align*}
    f^\ast(x) \coloneqq 2^{-b-2ns}f(2^{s}x) \quad\text{and}\quad g^\ast(x) \coloneqq 2^{-ns} g(2^{s}x).
  \end{align*}
  It follows that $\sumnorm{f^\ast} \le 1$ and $1 \le \sumnorm{g^\ast}$ since $g^\ast$ is again monic.
  In addition, the scaling of $g$ by $2^{s}$ yields that all roots of $g^{*}$ have absolute values less than or equal to $1/(2n).$
  Thus, the $i$-th coefficient of $g^{*}$ is bounded by $\binom{n}{i}\frac{1}{(2n)^{i}}$ which shows that $\sumnorm{g^\ast}\le (1 + \frac{1}{2n})^n < e^{1/2} < 2.$
  We now apply \cref{lem:div-prec-req} to the polynomials $f^{*}$ and $g^{*},$ and to some desired output precision $\ell^{*}$ which will be specified later:
  Suppose that $Q^{*} \coloneqq f^{*} \bdiv g^{*}$ and $R^{*} \coloneqq f^{*} \bmod g^{*},$ it takes $\sOh(n(\ell^{*}+n))$ bit operations to compute $\ell^{*}$-bit operations $\tilde{Q}^{*}$ and $\tilde{R}^{*}$ of $Q^{*}$ and $R^{*},$
  respectively, such that $\sumnorm{f^{*}-(\tilde{Q}^{*}g+\tilde{R}^{*})}<2^{-\ell^{\mathrlap{*}}}.$
  For this, we need $(\ell^{*}+32n)$-bit operations of the polynomials $f^{*}$ and $g^{*}.$
  Notice that we used the fact that $2^{1}$ constitutes a root bound for $g^{*}.$
  We further remark that,  in order to compute the approximations for $f^{*}$ and $g^{*},$ it suffices to consider $(\ell^{*}+32n)$-bit approximations of the polynomials $f$ and $g.$
  In order to recover approximations for the polynomials $Q$ and $R,$ we consider an inverse scaling, that is,
  \begin{align*}
    \tQ(x) \coloneqq 2^{b+ns}\tQ^\ast(2^{-s} x)
    \quad\text{and}\quad
    \tR(x) \coloneqq 2^{2ns+b}\tR^\ast(2^{-s} x).
  \end{align*}
  Since $f(x)=Q(x)\cdot g(x)+R(x),$ we have
  \begin{align*}
    \underbrace{2^{-2ns-b}f(2^{s}x)}_{f^{*}}=\underbrace{2^{-b-ns}Q(2^{s}x)}_{Q^{*}}\cdot \underbrace{2^{-ns}g(2^{s}x)}_{g^{*}}+\underbrace{2^{-2ns-b}R(2^{s}x)}_{R^{*}},
  \end{align*}
  and, thus, for any $\ell^{*}\ge b+2ns,$ the polynomials $\tQ(x)$ and $\tR(x)$ are $(\ell^{*}-b-2ns)$-approximations of $Q$ and $R,$ respectively.
  In addition, $\sumnorm{f-(\tQ g+\tR)}\le 2^{-\ell^{*}+b+2ns}.$
  Hence, for $\ell^{*}\coloneqq \ell+b+2ns,$ the bound on the bit complexity of the numerical division as well as the bound on the precision demand follows.

  For the estimate on $\sumnorm{\tR},$ we recall that \cref{eq:bound-norm-Q} yields $\sumnorm{Q^\ast} \le 2^{13n}$
  which implies that $\sumnorm{R^{*}}\le \sumnorm{f^{*}}+\sumnorm{Q^{*}}\cdot \sumnorm{g^{*}}\le 1+2\cdot 2^{13n}<2^{16n}.$
  Thus, we have
  \begin{align*}
    \sumnorm{R}\le 2^{2ns+b}\sumnorm{R^{*}}<2^{16n+2ns+b}<2^{16n+2n\rho+2n\log\ceil{2n}+b}=2^{b+2n\rho +O(n\log n)},
  \end{align*}
  and the same bound also applies to $\tilde{R}$ since it is an $\ell$-bit approximation of $R.$
\end{proof}


\subsection{Fast Approximate Multipoint Evaluation: Complexity Analysis}

We can now apply the results of the previous two sections to the recursive divide-and-conquer multipoint evaluation scheme as described on page \pageref{alg:exact-mp-eval}.
Using approximate multiplications and divisions, our goal is to compute approximations $\tilde{r}_{0,j}$ of the final remainders $r_{0,j}= F \bmod (x-x_j)=F(x_{j})$ such that $\abs{\tilde{r}_{0,j} - F(x_j)} \le 2^{-L}$ for all $j=1,\ldots,n.$
In other words, we aim to compute $L$-bit approximations of the remainders $r_{0,j}.$
For this purpose, we will do a bottom-up backwards analysis of the required precisions for dividend and divisor in every layer of the remainder tree which will yield the according requirements on the accuracy of the subproduct tree.

\begin{theorem}\label{thm:main}
  Let $F \in \CC[x]$ be a polynomial of degree $n$ with $\sumnorm{F} \le 2^\tau,$ with $\tau \ge 1,$ and let $x_1, \dots, x_n \in \CC$ be complex points with absolute values bounded by $2^{\Gamma},$ where $\Gamma\ge 1.$
  Then, approximate multipoint evaluation up to a precision of $2^{-L}$ for some integer $L \ge 0,$ that is, computing $\tilde{y}_j$ such that $\abs{\tilde{y}_j - F(x_j)} \le 2^{-L}$ for all $j,$ is possible with
  \begin{align*}
    \sOh (n (L + \tau + n\Gamma)).
  \end{align*}
  bit operations.
  Moreover, the precision demand on $F$ and the points $x_j$ is bounded by $L + \Oh (\tau + n\Gamma + n \log n)$ bits.
\end{theorem}
\begin{proof}
  Define $g_{i,j}$ and $r_{i,j}$ as in \cref{alg:exact-mp-eval}.
  We analyse a run of the algorithm using approximate multiplication and division, with a precision of $\ell^{\bdiv}_i$ for the approximate divisors $\tg_{i,\ast}$ and remainders $\tr_{i,\ast}$
  in the $i$-th layer of the subproduct and the remainder tree.
  We recall that $\deg \tg_{i,\ast} = \deg g_{i,\ast} = 2^i.$

  According to \cref{cor:div-compl-monic}, for the recursive divisions to yield an output precision $\ell_i \ge 0,$
  it suffices to have approximations $\tr_{i+1, \ast}$ and $\tg_{i,\ast}$ of the exact polynomials $f\coloneqq r_{i+1,\ast}$ and $g\coloneqq g_{i,\ast}$ to a precision of
  \begin{align}
    \label{eq:prec-l_i}
    \ell^{\bdiv}_{i+1} &\coloneqq \ell^{\bdiv}_i + \log \sumnorm{r_{i+1,\ast}} +2^{i+1}\Gamma+ \Oh (i\cdot 2^i)
  \end{align}
  bits, since the roots of each $g_{i,\ast}$ are contained in the set $\{x_{1},\ldots,x_{n}\}$ and, thus, their absolute values are also bounded by $2^{\Gamma}.$
  In addition, it holds that $\sumnorm{r_{\log n,0}}=\sumnorm{F}\le 2^{\tau}.$
  In order to bound the absolute values of the remainders $r_{i,\ast}$ for $i<\log n,$ we can use our remainder bound from \cref{eq:bound-norm-remainder} in an iterative manner to show that
  \begin{align}
    \label{eq:bound-r_i}
    \log \sumnorm{r_{i,\ast}} &= \log \sumnorm{r_{i+1,\ast}} +2^{i+1}\Gamma+  \Oh (i\cdot 2^{i})
    = \tau +2n\Gamma +O(n\log n).
  \end{align}

  Combining \cref{eq:prec-l_i} and \cref{eq:bound-r_i} then yields
  \begin{align*}
    \ell^{\bdiv} \coloneqq \max_{i>0} \ell^{\bdiv}_i = \ell^{\bdiv}_0 + \tau +2n\Gamma+ \Oh(n\log n).
  \end{align*}
  Hence, choosing $\ell^{\bdiv}_0\coloneqq L,$ we eventually achieve evaluation up to an error of $2^{-L}$ if all numerical divisions are carried out with precision $\ell^{\bdiv}.$
  The bit complexity to carry out a single numerical division at the $i$-th layer of the tree is then bounded by $\sOh(2^{i}(\ell^{\bdiv}+\tau+2^{i}\Gamma))=\sOh(2^{i}(L+n\Gamma+\tau)).$
  Since there are $n/2^{i}$ divisions, the total cost at the $i$-th layer is bounded by $\sOh(n(L+n\Gamma+\tau)).$
  The depth of the tree equals $\log n,$ and thus the overall bit complexity is $\sOh(n(L+n\Gamma+\tau)).$

  It remains to bound the precision demand and, hence, the cost for computing $(L+\tau+2n\Gamma+\Oh(n\log n))$-bit approximations of the polynomials $g_{i,\ast}.$
  According to \cref{thm:mul-compl}, in order to compute the polynomials $g_{i,\ast}$ to a precision of $\ell^{\operatorname{mul}}_i,$ we have to consider $\ell^{\operatorname{mul}}_{i-1}$-bit approximations of $g_{i-1,\ast},$  where
  \begin{align*}
    \ell^{\operatorname{mul}}_i \coloneqq \ell^{\operatorname{mul}}_{i-1}+2\log \sumnorm{g_{i-1,\ast}}+O(i)=\ell^{\operatorname{mul}}_{i-1}+2i\Gamma+O(i)=\ell^{\operatorname{mul}}_{0}+O(\log n\cdot \Gamma).
  \end{align*}
  Hence, it suffices to run all multiplications in the product tree with a precision of $\ell^{\operatorname{mul}}=L+\tau+\Oh(n\Gamma+n\log n).$
  The bit complexity for all multiplications is bounded by $\sOh(n\ell^{\operatorname{mul}})=\sOh(n(L+\tau+n\Gamma)),$
  and the precision demand for the points $x_{i}$ is bounded by $\ell^{\operatorname{mul}}+O(\Gamma+\log n)=L+\tau+\Oh(n\Gamma+n\log n).$
\end{proof}


\section{Applications}


\subsection{Quadratic Interval Refinement for Roots of a Polynomial}
\label{sec:refinement}

Polynomial evaluation is the key operation in many algorithms to approximate the real roots of a square-free polynomial $F(x)\in\ZZ[x]$:
Given an isolating interval $I=(a,b)$ for a real root $\xi$ of $F$ (i.e., $I$ contains $\xi$ and $\bar{I}=[a,b]$ contains no other root of $F$) and an arbitrary positive integer $L,$
we aim to compute an approximation of $\xi$ to $L$ bits after the binary point (or, in other words, an $L$-bit approximation of $\xi$) by means of refining $I$ to a width of $2^{-L}$ or less.

A very simple method to achieve this goal is to perform a binary search for the root $\xi.$
That is, in the $j$-th iteration (starting with $I_{0}\coloneqq (a_{0},b_{0})=(a,b)$ in the $0$-th iteration),
we split the interval $I_{j}=(a_{j},b_{j})$ at its midpoint $m(I_{j})$ into two equally sized intervals $I_{j}'=(a_{j},m(I_{j}))$ and $I_{j}''=(m(I_{j}),b_{j}).$
We then check which of the latter two intervals yields a sign change of $F$ at its endpoints,\footnote{%
  Here, it is important that $f$ is considered to be square-free.
  Thus, $\xi$ must be a simple root, and any isolating interval $I=(a,b)$ for $\xi$ yields $F(a)\cdot F(b)<0.$}
and define $I_{j+1}$ to be the unique such interval.
If $F(m(I_{j}))=0,$ we can stop because, in this special case, we have exactly computed the root $\xi.$
The main drawback of this simple approach is that only linear convergence can be achieved.

In \cite{abbott-quadratic}, Abbott introduced a method, denoted quadratic interval refinement (\textsc{Qir}), to overcome this issue.
It is a trial and error approach which combines the bisection method and the secant method.
More precisely, in each iteration, an additional integer $N_{j}$ is stored (starting with $N_{0}=4$) and (only conceptually) the interval $I_{j}$ is subdivided into $N_{j}$ equally sized subintervals $I_{j,1},\ldots,I_{j,N_{j}}.$
The graph of $f$ restricted to $I_{j}$ is approximated by the secant $S$ passing through the points $(a_{j},F(a_{j}))$ and $(b_{j},F(b_{j})).$
The idea is that, for $I_{j}$ small enough, the intersection point $x_{S}$ of $S$ and the real axis is a considerably good approximation of the root $\xi,$
and thus the root $\xi$ is likely to be located in the same of the $N_{j}$ subintervals as $x_{S}.$
Hence, we compute $x_{S}$ and consider the unique subinterval $I_{j,\ell},$ with $\ell\in\{1,\ldots,N_{j}\},$ which contains $x_{S}.$
If $I_{j,\ell}$ yields a sign change of $F$ at its endpoints, we know that it contains $\xi$ and, thus, proceed with $I_{j+1}\coloneqq I_{j,\ell}.$
In addition, we set $N_{j+1}\coloneqq N_{j}^{2}.$
This is called a \emph{successful} \textsc{Qir} step.
If we are not successful (i.e., there is no sign change of $F$ at the endpoints of $I_{j,\ell}$), we perform a bisection step as above and set $N_{j+1}\coloneqq \min(4,\sqrt{N_{j}}).$
It has been shown \cite{DBLP:conf/casc/Kerber09} that the \textsc{Qir} method eventually achieves quadratic convergence; in particular, all steps are eventually successful.
As a consequence, the bit complexity for computing an $L$-bit approximation of $\xi$ drops from $\sOh(n^{3}L)$ (using the bisection approach) to $\sOh(n^{2}L)$ (for the \textsc{Qir} method) if $L$ is dominating.
Namely, the number of refinement steps reduces from $O(L)$ to $O(\log L),$ and the bit complexity in each step is bounded by $\sOh(n^{2}L)$ for both methods (exact polynomial evaluation at a rational number of bitsize $L$).

In \cite{Aqir,DBLP:journals/corr/abs-1104-1362}, a variant of the \textsc{Qir} method, denoted \textsc{Aqir}, has been proposed.
It is almost identical to the original \textsc{Qir} method;
however, for the sign evaluations and the computation of $x_{S},$ exact polynomial arithmetic over the rationals has been replaced by approximate but certified interval arithmetic.
\textsc{Aqir} improves upon \textsc{Qir} with regard to two main aspects:
First, it works for arbitrary real polynomials whose coefficients can only be approximated.
Second, it allows to run the computations with an almost optimal precision in each step which is due to an adaptive precision management and the fact that the evaluation points are chosen ``away from'' the roots of $p$;
see \cite{Aqir,DBLP:journals/corr/abs-1104-1362} for details.
In particular, the precision requirement in the worst case drops from $O(nL)$ to $O(L)$ in each step, thus resulting in an overall improvement from $\sOh(n^{2}L)$ to $\sOh(nL)$ with respect to bit complexity.
Now, if isolating intervals for \emph{all} real roots of $p$ are given, then computing $L$-bit approximations of all real roots uses $\sOh(n^{2}L)$ bit operations
since we have to consider the cost for the refinement of each of the isolating intervals as many times as the number of real roots (which is at most $n$).
\emph{This is the point, where approximate multipoint evaluation comes into play.}
Namely, instead of considering the evaluations of $f$ for each interval independently, we can perform $n$ many of these evaluations in parallel without paying more than a polylogarithmic factor compared to only one evaluation.
This yields a total bit complexity of $\sOh(nL)$ for computing $L$-bit approximations of all real roots.
We remark that the latter bound is optimal up to logarithmic factors because reading the output already needs $\Theta(nL)$ bit operations.
For the special case, where $p$ has integer coefficients, we fix the following result:

\begin{theorem}
  Let $F\in\ZZ[x]$ be a square-free polynomial of degree $n$ with integer coefficients bounded by $2^{\tau},$ and let $L$ be an arbitrary given positive integer.
  Then, computing isolating intervals for all real roots of $F$ of width $2^{-L}$ or less uses $\sOh(n^{3}\tau+nL)$ bit operations.
\end{theorem}
\begin{proof}
  Let $\xi_{1},\ldots,\xi_{m}$ denote the real roots of $F.$
  We proceed in three steps:

  In the first step, we compute isolating intervals $I_{\xi_{1}},\ldots,I_{\xi_{m}}$ for all real roots.

  In the second step, the intervals are refined such that
  \begin{align}
    w(I_{\xi_{k}})<w_{\xi_{k}}\coloneqq \frac{\abs{F'(\xi_{k})}}{32\,e\,d^{3}2^{\tau}\max\{1, \abs{\xi_{k}}\}^{d-1}}\quad\text{for all }k=1,\ldots,m
    \label{sizewI},
  \end{align}
  where $e\approx 2.71\ldots$ denotes the Eulerian number.
  For the latter two steps, we use an asymptotically fast real root isolation algorithm, called \textsc{NewDsc}, which has been introduced in \cite{NewDsc}.
  The proof of \cite[Theorem~10]{NewDsc} shows that we need $\sOh(n^{3}\tau)$ bit operations to carry out all necessary computations.

  Finally, we use \textsc{Aqir} to refine the intervals $I_{\xi_{k}}$ to a size of $2^{-L}$ or less.
  Since the intervals $I_{\xi_{k}}$ fulfill the inequality \eqref{sizewI}, \cite[Corollary~14]{Aqir} yields that each \textsc{Aqir}-step will be \emph{successful} if we start with $I_{0}\coloneqq I_{\xi_{k}}$ and $N_{0}\coloneqq 4.$
  That is, in each of the subsequent refinement steps, $I_{j}$ will be replaced by an interval $I_{j+1}$ of width $w(I_{j})/N_{j},$ and we have $N_{j+1}=N_{j}^{2}.$
  In other words, we have quadratic convergence right from the beginning and never fall back to bisection.
  According to \cite[Lemma~21]{DBLP:journals/corr/abs-1104-1362} and the preceding discussion, the needed precision for each polynomial evaluation in the refinement steps is bounded by $\sOh(L+n\Gamma_{F}+\Sigma_{F}),$
  where $2^{\Gamma_{F}}$ denotes a bound on the modulus of all complex roots $z_{1},\ldots,z_{n}$ of $F,$
  $\Sigma_{F}\coloneqq \sum_{i=1}^{n}\log \sigma(z_{i})^{-1},$ and $\sigma(z_{i})\coloneqq \min_{j\neq i}\abs{z_{i}-z_{j}}$ the separation of $z_{i}.$
  For a polynomial $F$ with integer coefficients of absolute value $2^{\tau}$ or less, we may consider $\Gamma_{F}=2^{\tau+1}$ according to Cauchy's root bound, and, in addition, it holds that $\Sigma_{F}=\sOh(n\tau)$;
  see \cite{DBLP:journals/corr/abs-1104-1362} and the references therein for details.
  Thus, the bound on the needed precision simplifies to $\sOh(L+n\tau).$
  In each iteration of the refinement of a single interval $I_{\xi_{k}},$ we have to perform a constant number of polynomial evaluations,\footnote{%
    In fact, there are up to $9$ evaluations in each step. See \cite[Algorithm~3]{Aqir} for details.}
  hence there are $O(n)$ many evaluations for all intervals.
  All of the involved evaluation points are located in the union of the intervals $I_{\xi_{k}},$ and thus they have absolute value bounded by $2^{\tau}.$
  In addition, $p$ has coefficients of absolute value bounded by $2^{\tau}.$
  Hence, in each iteration, we need $\sOh(n^{2}\tau+nL)$ bit operations for all evaluations according to \cref{thm:main}.
  Since we have quadratic convergence for all intervals, there are only $O(\log L)$ iterations for each interval, hence the claimed bound follows.
\end{proof}

\subsection{Polynomial Interpolation}\label{sec:interpolation}

Fast polynomial interpolation can be considered as a direct application of polynomial multipoint evaluation.
Given $n$ (w.l.o.g.\ we again assume that $n=2^{k}$ is a power of two) pairwise distinct interpolation points $x_{1},\ldots,x_{n}\in\CC$ and corresponding values $v_{1},\ldots,v_{n},$
we aim to compute the unique polynomial $F\in\CC[x]$ of degree less than $n$ such that $F(x_{i})=v_{i}$ for all $i=1,\ldots,n.$
Using Lagrange interpolation, we have
\begin{align*}
  F(x)
  = \sum_{i=1}^{n} v_{i} \cdot \!\!\!\!\prod_{{j=1;\,j\neq i}}^{n}\frac{x-x_{j}}{x_{i}-x_{j}}
  = \sum_{i=1}^{n} v_{i} \lambda_{i}^{-1} \cdot \prod_{\mathclap{j=1;\,j\neq i}}^{n} (x-x_{j})
  = \sum_{i=1}^{n}\mu_{i} \cdot \prod_{\mathclap{j=1;\,j\neq i}}^{n} (x-x_{j}),
\end{align*}
where $\lambda_{i}\coloneqq \prod_{j=1;\,j\neq i}^{n}(x_{i}-x_{j})$ and $\mu_{i}\coloneqq v_{i}\cdot \lambda_{i}^{-1}.$
Now, in order to compute $F(x),$ we proceed in two steps:
In the first step, we compute the values $\lambda_{i}.$
Let $g(x)\coloneqq \prod_{j=1}^{n}(x-x_{j})$ (notice that $g(x)$ coincides with the polynomial $g_{k,1}(x)$ from \eqref{def:gij}), then $\lambda_{i}=g'(x_{i}),$
and thus the values $\lambda_{i}$ can be obtained by a fast multipoint evaluation of the derivative $g'(x)$ of the polynomial $g(x)$ at the points $x_{i}.$
We can compute $g$ and $g'$ with $\sOh(n)$ arithmetic operations in $\CC,$ and, using fast multipoint evaluation, the same bound also applies to the number of arithmetic operations to compute all values $\lambda_{i}.$
Hence, computing the values $\mu_{i}$ takes $\sOh(n)$ arithmetic operations in $\CC.$
Now, in order to compute $F_{k,1}(x)\coloneqq F(x)=\sum_{i=1}^{n}\mu_{i} \cdot \prod_{j=1;j\neq i}^{n} (x-x_{j}),$ we write
\begin{align}
  \label{iteration:interpolation}
  F_{k,1}(x)
  = g_{k-1,1}(x) \cdot \underbrace{\sum_{i=1}^{n/2}\mu_{i} \cdot \prod_{\substack{j=1\mathrlap{;}\\j\neq i}}^{n/2} (x-x_{j})}_{\eqqcolon F_{k-1,1}(x)}
  + g_{k-1,2}(x) \cdot \underbrace{\sum_{\mathclap{i=n/2+1}}^{n}\mu_{i} \;\cdot\; \prod_{\mathclap{\substack{j=n/2+1\mathrlap{;}\\j\neq i}}}^{n} (x-x_{j})}_{\eqqcolon F_{k-1,2}(x)}.
\end{align}
Following a divide-and-conquer approach, we can recursively compute $F(x)$ from the values $\mu_{i}$ and the polynomials $g_{i,j}$ as defined in \cref{def:gij}.
It is then straight forward to show that $\sOh(n)$ arithmetic operations in $\CC$ are sufficient to carry out the necessary computations.

In contrast to the exact computation of $F(x)$ as outlined above, we now focus on the problem of computing an $L$-bit approximation $\tilde{F}$ of $F.$
We assume that arbitrarily good approximations of the points $x_{i}$ and the corresponding values $v_{i}$ are provided.
We introduce the following definitions:
\begin{gather}
  \nonumber
  \Gamma \coloneqq \max_{i=1}^{n}\log\max(2,\abs{x_{i}})\ge 1,
  \quad V\coloneqq \max_{i=1}^{n}\log\max(2,\abs{v_{i}})\ge 1, \quad\text{and}\\
  \Lambda \coloneqq \max_{i=1}^{n}\log\max(1,\abs{\lambda_{i}}^{-1})=\max_{i=1}^{n}\log\max(1,\;\prod_{\mathclap{j=1;\,j\neq i}}^{n}\;\abs{x_{i}-x_{j}}^{-1}).\label{def:GammaLambdaV}
\end{gather}
In \cref{subsec:fastmultiplication}, we have already shown that computing $\ell$-bit approximations of all polynomials $g_{i,j}$ needs $\sOh(n^{2}\Gamma+n\ell)$ bit operations.
Furthermore, we need approximations of the points $x_{i}$ to $\sOh(n\Gamma+\ell)$ bits after the binary point.
Applying \cref{thm:main} to the derivative $g'(x)\coloneqq g_{1,k}'(x)$ of $g_{1,k}(x)$ and the points $x_{1},\ldots,x_{n}$ then shows that computing $\ell$-bit approximations $\tilde{\lambda}_{i}$ of the values $\lambda_{i}$
uses $\sOh(n^{2}\Gamma+n\ell)$ bit operations since the modulus of the points $x_{i}$ is bounded by $2^{\Gamma}$ and the coefficients of $g'$ have absolute value of size $2^{O(n\Gamma)}.$
The precision demand on $g'$ and the points $x_{i}$ is bounded by $\sOh(n\Gamma+\ell)$ bits after the binary point.
Now, in order to compute an $\ell$-bit approximation $\tilde{\mu}_{i}$ of $\mu_{i}=v_{i}\lambda^{-1}_{i},$ we have to approximate $v_{i}$ and $\lambda_{i}$ to $O(\ell+\Lambda+V)$ bits after the binary point.
Hence, computing such approximations $\tilde{\mu}_{i}$ for all $i$ needs
\begin{align*}
  \sOh(n(\ell+n\Gamma+\Lambda+V))
\end{align*}
bit operations, and the precision demand for the points $x_{i}$ and the values $v_{i}$ is bounded by $\sOh(\ell+n\Gamma+\Lambda+V)$ bits after the binary point.
For computing $\tilde{F},$ we now apply the recursion from \cref{iteration:interpolation}. Starting with $\ell$-bit approximations of $\mu_{i}$ and $g_{i,j},$ the so-obtained polynomial $\tilde{F}$ differs from $F$ by at most $\ell-O(n\Gamma+\Lambda+V)$-bits after the binary point
since the coefficients of all occurring polynomials in the intermediate computations have modulus bounded by $2^{O(n\Gamma+\Lambda+V)}.$
Hence, we conclude the following theorem:

\begin{theorem}
  \label{thm:interpolation}
  Let $x_{1},\ldots,x_{n}\in\CC$ be arbitrary, but distinct, given interpolation points and $v_{1},\ldots,v_{n}\in\CC$ be arbitrary corresponding interpolation values.
  Furthermore, let $F\in\CC[x]$ be the unique polynomial of degree less than $n$ such that $F(x_{i})=v_{i}$ for all $i.$
  Then, for any given integer $L,$ we can compute an $L$-bit approximation $\tilde{F}$ of $F$ with
  \begin{align}
    \label{eq:interpolation}
    \sOh(n(n\Gamma+V+\Lambda+L))
  \end{align}
  bit operations, where $\Gamma,$ $V,$ and $\Lambda$ are defined as in \cref{def:GammaLambdaV}.
  The points $x_{i}$ and the values $v_{i}$ have to approximated to $\sOh(n\Gamma+V+\Lambda+L)$ bits after the binary point.
\end{theorem}

\begin{remark}
  In the special case, where $x_{i}=e^{i\cdot \frac{2\pi \mathbf{i}}{n}}$ are the $n$-th roots of unity, we have $\Gamma=1$ and $\Lambda=\log n$ because
  $\prod_{j=1;\,j\neq i}^{n}\abs{x_{i}-x_{j}}=\abs[\big]{\frac{d(x^{n}-1)}{dx}(x_{i})}=\abs{n\cdot x_{i}^{n-1}}=n.$
  The bound in \cref{eq:interpolation} then simplifies to $\sOh(n(n+L+V))$ which is comparable to the complexity bound that one gets from considering an inverse FFT to the vector $(v_{1},\ldots,v_{n})$ using approximate arithmetic
  \cite[Theorem~8.3]{schonhage:fundamental}, regardless of the fact that the latter approach is certainly much more reasonable and efficient in practice.
\end{remark}

\subsection{Asymptotically Fast Approximate Taylor Shifts}
\label{sec:taylor}

Our last application concerns the problem of computing the Taylor shift of a polynomial $F\in\CC[x]$ by a given $m\in\CC.$
More precisely, given oracles for arbitrarily good approximations of $F$ and $m$ and a positive integer $L,$ we aim to compute an $L$-bit approximation of $F_{m}(x)\coloneqq F(m+x).$
Computing the shifted polynomial $F_{m}$ is crucial in many subdivision algorithms to compute the roots of a polynomial.
Asymptotically fast methods have already been studied in \cite{schonhage:fundamental} and \cite{vzgathen-gerhard:taylor:97}, where the computation of the coefficients of $F_{m}$ is reduced to a multiplication of two polynomials.
We follow a slightly different approach based on multipoint evaluation, where the problem is reduced to an evaluation-\hspace{0pt}interpolation problem.
More specifically, we first evaluate $F$ at the $n$ points $x_{i}\coloneqq m+e^{i\cdot \frac{2\pi \mathbf{i}}{n}},$ where $n\coloneqq \deg F+1.$
We then compute $F_{m}$ as the unique polynomial of degree less than $n$ which takes the values $v_{i}\coloneqq p(x_{i})$ at the roots of unity $\omega_{i}\coloneqq e^{i\cdot \frac{2\pi \mathbf{i}}{n}}.$
In the preceding sections, we have shown how to carry out the latter two computations with an output precision of $\ell$ bits after the binary point.
\Cref{thm:interpolation} and the subsequent remark shows that, in order to compute an $L$-bit approximation of $F_{m},$ it suffices to run the final interpolation with an input precision of $\sOh(n+L+V)$ bits after the binary point,
where $V=\max_{i=1}^{n}\log\max(2,\abs{F(x_{i})})=\log n2^{\tau}(2\max(1,\abs{m}))^{n} = O(n+\tau+n\log\max(1,\abs{m}))$ and $\infnorm{F}<2^{\tau}.$
The cost for the interpolation is bounded by
\begin{align*}
  \sOh(n(n+L+V))=\sOh(n(n+L+\tau+n\log\max(1,\abs{m}))).
\end{align*}
It remains to bound the cost for the evaluation of $F$ at the points $x_{i}.$
Since we need approximations of $F(x_{i})$ to $\sOh(L+n+\tau+n\log\max(1,\abs{m}))$ bits after the binary point and $\abs{x_{i}}<2\max(1,\abs{m})$ for all $i,$ \cref{thm:main} yields the bound
\begin{align*}
  \sOh(n(n+n\log\max(1,\abs{m})+\tau+L))
\end{align*}
for the number of bit operations to run the approximate multipoint evaluation.
The polynomial $F$ and the points $x_{i}$ have to be approximated to $\sOh(n+n\log\max(1,\abs{m})+\tau+L)$ bits after the binary point.
We fix the following result which provides a complexity bound comparable to \cite[Theorem~8.4]{schonhage:fundamental}:

\begin{theorem}\label{thm:taylor}
  Let $F\in\CC[x]$ be a polynomial of degree less than $n$ with coefficients of modulus less than $2^{\tau},$ and let $m\in\CC$ be an arbitrary complex number.
  Then, for any given positive integer $L,$ we can compute an $L$-bit approximation $\tilde{F}_{m}$ of $F_{m}(x)=F(m+x)$ with
  \begin{align*}
    \sOh(n(n+n\log\max(1,\abs{m})+\tau+L))
  \end{align*}
  bit operations.
  For this computation, the coefficients of the polynomial $F$ as well as the point $m$ have to be approximated to $\sOh(n+n\log\max(1,\abs{m})+\tau+L)$ bits after the binary point.
\end{theorem}

\clearpage
\printbibliography

\end{document}

multipoint-evaluation.bbl
% $ biblatex auxiliary file $
% $ biblatex version 1.7 $
% Do not modify the above lines!
%
% This is an auxiliary file used by the 'biblatex' package.
% This file may safely be deleted. It will be recreated as
% required.
%
\begingroup
\makeatletter
\@ifundefined{ver@biblatex.sty}
  {\@latex@error
     {Missing 'biblatex' package}
     {The bibliography requires the 'biblatex' package.}
      \aftergroup\endinput}
  {}
\endgroup

\preamble{%
\newcommand{\longtitle}[1]{#1}
}

\entry{abbott-quadratic}{article}{}
  \name{author}{1}{}{%
    {{}%
     {Abbott}{A.}%
     {John}{J.}%
     {}{}%
     {}{}}%
  }
  \strng{namehash}{AJ1}
  \strng{fullhash}{AJ1}
  \field{sortinit}{A}
  \verb{eprint}
  \verb 1203.1227
  \endverb
  \field{title}{{Quadratic Interval Refinement for Real Roots}}
  \field{journaltitle}{Computing Research Repository}
  \field{eprinttype}{arxiv}
  \field{year}{2012; originally presented as a poster at \longtitle{the
  }International Symposium on Symbolic and Algebraic Computation 2006}
\endentry

\entry{BF00}{article}{}
  \name{author}{2}{}{%
    {{}%
     {Bini}{B.}%
     {Dario~A.}{D.~A.}%
     {}{}%
     {}{}}%
    {{}%
     {Fiorentino}{F.}%
     {Giuseppe}{G.}%
     {}{}%
     {}{}}%
  }
  \list{publisher}{1}{%
    {Kluwer Academic Publishers}%
  }
  \keyw{polynomial roots; simultaneous iterations; clustered roots; inclusion
  theorems; root neighborhoods; adaptive algorithms; mathematical software;
  26C10; 65H05; 30C15}
  \strng{namehash}{BDAFG1}
  \strng{fullhash}{BDAFG1}
  \field{sortinit}{B}
  \verb{doi}
  \verb 10.1023/A:1019199917103
  \endverb
  \field{issn}{1017-1398}
  \field{number}{2--3}
  \field{pages}{127\bibrangedash 173}
  \field{title}{Design, analysis, and implementation of a multiprecision
  polynomial rootfinder}
  \field{volume}{23}
  \field{journaltitle}{Numerical Algorithms}
  \field{year}{2000}
\endentry

\entry{BP94}{book}{}
  \name{author}{2}{}{%
    {{}%
     {Bini}{B.}%
     {Dario~A.}{D.~A.}%
     {}{}%
     {}{}}%
    {{}%
     {Pan}{P.}%
     {Victor~Y.}{V.~Y.}%
     {}{}%
     {}{}}%
  }
  \list{publisher}{1}{%
    {Birkh\"auser}%
  }
  \keyw{ca}
  \strng{namehash}{BDAPVY1}
  \strng{fullhash}{BDAPVY1}
  \field{gender}{pm}
  \field{sortinit}{B}
  \field{isbn}{0-817-63786-9}
  \field{title}{Polynomial and Matrix Computations}
  \field{volume}{1: Fundamental Algorithms}
  \list{location}{1}{%
    {Boston}%
  }
  \field{year}{1994}
\endentry

\entry{DKSS08}{inproceedings}{}
  \name{author}{4}{}{%
    {{}%
     {De}{D.}%
     {Anindya}{A.}%
     {}{}%
     {}{}}%
    {{}%
     {Kurur}{K.}%
     {Piyush~P.}{P.~P.}%
     {}{}%
     {}{}}%
    {{}%
     {Saha}{S.}%
     {Chandan}{C.}%
     {}{}%
     {}{}}%
    {{}%
     {Saptharishi}{S.}%
     {Ramprasad}{R.}%
     {}{}%
     {}{}}%
  }
  \list{publisher}{1}{%
    {Association for Computing Machinery}%
  }
  \strng{namehash}{DA+1}
  \strng{fullhash}{DAKPPSCSR1}
  \field{sortinit}{D}
  \field{booktitle}{\longtitle{Proceedings of the 40th }annual Symposium on the
  Theory of Computing}
  \verb{doi}
  \verb 10.1145/1374376.1374447
  \endverb
  \field{pages}{499\bibrangedash 506}
  \field{title}{Fast Integer Multiplication Using Modular Arithmetic}
  \list{location}{1}{%
    {New York, NY, USA}%
  }
  \field{year}{2008}
\endentry

\entry{Furer09}{article}{}
  \name{author}{1}{}{%
    {{}%
     {F{\"u}rer}{F.}%
     {Martin}{M.}%
     {}{}%
     {}{}}%
  }
  \list{publisher}{2}{%
    {Society for Industrial}%
    {Applied Mathematics}%
  }
  \strng{namehash}{FM1}
  \strng{fullhash}{FM1}
  \field{sortinit}{F}
  \verb{doi}
  \verb 10.1137/070711761
  \endverb
  \field{number}{3}
  \field{pages}{979\bibrangedash 1005}
  \field{title}{Faster Integer Multiplication}
  \field{volume}{39}
  \field{journaltitle}{Journal on Computing}
  \field{year}{2009}
\endentry

\entry{vzgathen-gerhard:taylor:97}{inproceedings}{}
  \name{author}{2}{}{%
    {{}%
     {Gathen}{G.}%
     {Joachim}{J.}%
     {von~zur}{v.~z.}%
     {}{}}%
    {{}%
     {Gerhard}{G.}%
     {J\"urgen}{J.}%
     {}{}%
     {}{}}%
  }
  \strng{namehash}{GJvzGJ1}
  \strng{fullhash}{GJvzGJ1}
  \field{sortinit}{G}
  \field{booktitle}{\longtitle{8th }International Symposium on Symbolic and
  Algebraic Computation}
  \verb{doi}
  \verb 10.1145/258726.258745
  \endverb
  \field{pages}{40\bibrangedash 47}
  \field{title}{Fast algorithms for {T}aylor shifts and certain difference
  equations}
  \field{year}{1997}
\endentry

\entry{vzGG03}{book}{}
  \name{author}{2}{}{%
    {{}%
     {Gathen}{G.}%
     {Joachim}{J.}%
     {von~zur}{v.~z.}%
     {}{}}%
    {{}%
     {Gerhard}{G.}%
     {J\"urgen}{J.}%
     {}{}%
     {}{}}%
  }
  \list{publisher}{1}{%
    {Cambridge University Press}%
  }
  \strng{namehash}{GJvzGJ1}
  \strng{fullhash}{GJvzGJ1}
  \field{gender}{pm}
  \field{sortinit}{G}
  \field{edition}{2nd edition}
  \field{isbn}{0-521-82646-2}
  \field{title}{Modern Computer Algebra}
  \list{location}{1}{%
    {Cambridge, UK}%
  }
  \field{year}{2003}
\endentry

\entry{DBLP:conf/casc/Kerber09}{inproceedings}{}
  \name{author}{1}{}{%
    {{}%
     {Kerber}{K.}%
     {Michael}{M.}%
     {}{}%
     {}{}}%
  }
  \list{publisher}{1}{%
    {Springer}%
  }
  \strng{namehash}{KM1}
  \strng{fullhash}{KM1}
  \field{sortinit}{K}
  \field{booktitle}{\longtitle{11th }International Workshop on Computer Algebra
  in Scientific Computing}
  \verb{doi}
  \verb 10.1007/978-3-642-04103-7_15
  \endverb
  \field{pages}{155\bibrangedash 167}
  \field{series}{Lecture Notes in Computer Science}
  \field{title}{On the Complexity of Reliable Root Approximation}
  \field{volume}{5743}
  \field{year}{2009}
\endentry

\entry{Aqir}{inproceedings}{}
  \name{author}{2}{}{%
    {{}%
     {Kerber}{K.}%
     {Michael}{M.}%
     {}{}%
     {}{}}%
    {{}%
     {Sagraloff}{S.}%
     {Michael}{M.}%
     {}{}%
     {}{}}%
  }
  \list{publisher}{1}{%
    {Association for Computing Machinery}%
  }
  \strng{namehash}{KMSM1}
  \strng{fullhash}{KMSM1}
  \field{sortinit}{K}
  \field{booktitle}{\longtitle{Proceedings of the 36th }International Symposium
  on Symbolic and Algebraic Computation}
  \verb{doi}
  \verb 10.1145/1993886.1993920
  \endverb
  \field{pages}{209\bibrangedash 216}
  \field{title}{Efficient Real Root Approximation}
  \field{year}{2011}
\endentry

\entry{DBLP:journals/corr/abs-1104-1362}{article}{}
  \name{author}{2}{}{%
    {{}%
     {Kerber}{K.}%
     {Michael}{M.}%
     {}{}%
     {}{}}%
    {{}%
     {Sagraloff}{S.}%
     {Michael}{M.}%
     {}{}%
     {}{}}%
  }
  \strng{namehash}{KMSM1}
  \strng{fullhash}{KMSM1}
  \field{sortinit}{K}
  \verb{eprint}
  \verb 1104.1362
  \endverb
  \field{title}{Root Refinement for Real Polynomials}
  \field{journaltitle}{Computing Research Repository}
  \field{eprinttype}{arxiv}
  \field{year}{2011}
\endentry

\entry{KZ08}{inproceedings}{}
  \name{author}{2}{}{%
    {{}%
     {K\"ohler}{K.}%
     {Sven}{S.}%
     {}{}%
     {}{}}%
    {{}%
     {Ziegler}{Z.}%
     {Martin}{M.}%
     {}{}%
     {}{}}%
  }
  \strng{namehash}{KSZM1}
  \strng{fullhash}{KSZM1}
  \field{sortinit}{K}
  \field{booktitle}{\longtitle{Proceedings of the 8th }Conference on Real
  Numbers and Computers}
  \verb{eprint}
  \verb 10.1.1.154.7840
  \endverb
  \field{pages}{147\bibrangedash 156}
  \field{title}{On the Stability of Fast Polynomial Arithmetic}
  \list{location}{1}{%
    {Santiago de Compostela, Spain}%
  }
  \field{eprinttype}{citeseerx}
  \field{year}{2008}
\endentry

\entry{moenckborodin72}{inproceedings}{}
  \name{author}{2}{}{%
    {{}%
     {Moenck}{M.}%
     {Robert~T.}{R.~T.}%
     {}{}%
     {}{}}%
    {{}%
     {Borodin}{B.}%
     {Allan}{A.}%
     {}{}%
     {}{}}%
  }
  \list{publisher}{1}{%
    {IEEE Computer Society}%
  }
  \keyw{Algorithm design and analysis;Computer science;Equations;Fast Fourier
  transforms;Helium;Interpolation;Performance evaluation;Polynomials}
  \strng{namehash}{MRTBA1}
  \strng{fullhash}{MRTBA1}
  \field{sortinit}{M}
  \field{booktitle}{13th annual Symposium on Switching and Automata Theory}
  \verb{doi}
  \verb 10.1109/SWAT.1972.5
  \endverb
  \field{issn}{0272-4847}
  \field{pages}{90\bibrangedash 96}
  \field{title}{Fast modular transforms via division}
  \field{year}{1972}
\endentry

\entry{DBLP:journals/adcm/Pan95}{article}{}
  \name{author}{1}{}{%
    {{}%
     {Pan}{P.}%
     {Victor~Y.}{V.~Y.}%
     {}{}%
     {}{}}%
  }
  \list{publisher}{1}{%
    {Springer}%
  }
  \strng{namehash}{PVY1}
  \strng{fullhash}{PVY1}
  \field{sortinit}{P}
  \verb{doi}
  \verb 10.1007/BF02431995
  \endverb
  \field{number}{1}
  \field{pages}{41\bibrangedash 58}
  \field{title}{An algebraic approach to approximate evaluation of a polynomial
  on a set of real points}
  \field{volume}{3}
  \field{journaltitle}{Advances in Computational Mathematics}
  \field{year}{1995}
\endentry

\entry{DBLP:journals/siamcomp/Reif99}{article}{}
  \name{author}{1}{}{%
    {{}%
     {Reif}{R.}%
     {John~H.}{J.~H.}%
     {}{}%
     {}{}}%
  }
  \list{publisher}{2}{%
    {Society for Industrial}%
    {Applied Mathematics}%
  }
  \strng{namehash}{RJH1}
  \strng{fullhash}{RJH1}
  \field{sortinit}{R}
  \verb{doi}
  \verb 10.1137/S0097539797324291
  \endverb
  \field{number}{6}
  \field{pages}{2059\bibrangedash 2089}
  \field{title}{Approximate Complex Polynomial Evaluation in Near Constant Work
  Per Point}
  \field{volume}{28}
  \field{journaltitle}{Journal on Computing}
  \field{year}{1999}
\endentry

\entry{NewDsc}{inproceedings}{}
  \name{author}{1}{}{%
    {{}%
     {Sagraloff}{S.}%
     {Michael}{M.}%
     {}{}%
     {}{}}%
  }
  \list{publisher}{1}{%
    {Association for Computing Machinery}%
  }
  \strng{namehash}{SM1}
  \strng{fullhash}{SM1}
  \field{sortinit}{S}
  \field{booktitle}{\longtitle{Proceedings of the 37th }International Symposium
  on Symbolic and Algebraic Computation}
  \verb{doi}
  \verb 10.1145/2442829.2442872
  \endverb
  \field{pages}{297\bibrangedash 304}
  \field{title}{When {N}ewton meets {D}escartes: A Simple and Fast Algorithm to
  Isolate the Real Roots of a Polynomial}
  \field{year}{2012}
\endentry

\entry{Schoenhage82}{incollection}{}
  \name{author}{1}{}{%
    {{}%
     {Sch\"onhage}{S.}%
     {Arnold}{A.}%
     {}{}%
     {}{}}%
  }
  \name{editor}{1}{}{%
    {{}%
     {Calmet}{C.}%
     {Jacques}{J.}%
     {}{}%
     {}{}}%
  }
  \list{publisher}{1}{%
    {Springer Berlin Heidelberg}%
  }
  \strng{namehash}{SA2}
  \strng{fullhash}{SA2}
  \field{sortinit}{S}
  \field{booktitle}{Computer Algebra}
  \verb{doi}
  \verb 10.1007/3-540-11607-9_1
  \endverb
  \field{isbn}{978-3-540-11607-3}
  \field{pages}{3\bibrangedash 15}
  \field{series}{Lecture Notes in Computer Science}
  \field{title}{Asymptotically Fast Algorithms for the Numerical Multiplication
  and Division of Polynomials with Complex Coefficients}
  \field{volume}{144}
  \field{year}{1982}
\endentry

\entry{Schoenhage85}{article}{}
  \name{author}{1}{}{%
    {{}%
     {Sch\"onhage}{S.}%
     {Arnold}{A.}%
     {}{}%
     {}{}}%
  }
  \list{publisher}{1}{%
    {Elsevier}%
  }
  \strng{namehash}{SA2}
  \strng{fullhash}{SA2}
  \field{sortinit}{S}
  \verb{doi}
  \verb 10.1016/0885-064X(85)90024-X
  \endverb
  \field{issn}{0885-064X}
  \field{number}{1}
  \field{pages}{118\bibrangedash 137}
  \field{title}{Quasi-GCD computations}
  \field{volume}{1}
  \field{journaltitle}{Journal of Complexity}
  \field{year}{1985}
\endentry

\entry{schonhage:fundamental}{misc}{}
  \name{author}{1}{}{%
    {{}%
     {Sch{\"o}nhage}{S.}%
     {Arnold}{A.}%
     {}{}%
     {}{}}%
  }
  \strng{namehash}{SA1}
  \strng{fullhash}{SA1}
  \field{sortinit}{S}
  \field{note}{Manuscript, Department of Mathematics, University of
  T{\"u}bingen.}
  \field{title}{The fundamental theorem of algebra in terms of computational
  complexity}
  \verb{url}
  \verb www.informatik.uni-bonn.de/~schoe/fdthmrep.ps.gz
  \endverb
  \field{year}{1982; updated 2004}
\endentry

\entry{pantsi:ISSAC13}{inproceedings}{}
  \name{author}{2}{}{%
    {{}%
     {Tsigaridas}{T.}%
     {Elias}{E.}%
     {}{}%
     {}{}}%
    {{}%
     {Pan}{P.}%
     {Victor}{V.}%
     {}{}%
     {}{}}%
  }
  \name{editor}{1}{}{%
    {{}%
     {Kauers}{K.}%
     {Manuel}{M.}%
     {}{}%
     {}{}}%
  }
  \list{publisher}{1}{%
    {Association for Computing Machinery}%
  }
  \strng{namehash}{TEPV1}
  \strng{fullhash}{TEPV1}
  \field{sortinit}{T}
  \field{booktitle}{\longtitle{Proceedings of the 38th }International Symposium
  on Symbolic and Algebraic Computation}
  \verb{eprint}
  \verb hal-00816214
  \endverb
  \field{note}{To appear}
  \field{pages}{1\bibrangedash 8}
  \field{title}{On the Boolean complexity of real root refinement}
  \list{location}{1}{%
    {Boston, USA}%
  }
  \field{eprinttype}{hal}
  \field{year}{2013}
\endentry

\lossort
\endlossort

\endinput
