# Profile-Guided Parallel Task Extraction and Execution for Domain Specific
Heterogeneous SoC
††thanks:  This material is based on research sponsored by Air Force Research
Laboratory (AFRL) and Defense Advanced Research Projects Agency (DARPA) under
agreement number FA8650-18-2-7860. The U.S. Government is authorized to
reproduce and distribute reprints for Governmental purposes notwithstanding
any copyright notation thereon. The views and conclusion contained herein are
those of the authors and should not be interpreted as necessarily representing
the official policies or endorsements, either expressed or implied, of Air
Force Research Laboratory (AFRL) and Defence Advanced Research Projects Agency
(DARPA) or the U.S. Government.

Liangliang Chang  The School of Electrical, Computer and Energy Engineering,
Arizona State University, USA  Joshua Mack  Electrical and Computer
Engineering Department, The University of Arizona, USA  Benjamin Willis  The
School of Electrical, Computer and Energy Engineering, Arizona State
University, USA  Xing Chen  The School of Electrical, Computer and Energy
Engineering, Arizona State University, USA  John Brunhaver  The School of
Electrical, Computer and Energy Engineering, Arizona State University, USA
Ali Akoglu  Electrical and Computer Engineering Department, The University of
Arizona, USA  Chaitali Chakrabarti  The School of Electrical, Computer and
Energy Engineering, Arizona State University, USA

###### Abstract

In this study, we introduce a methodology for automatically transforming user
applications in the radar and communication domain written in C/C++ based on
dynamic profiling to a parallel representation targeted for a heterogeneous
SoC. We present our approach for instrumenting the user application binary
during the compilation process with barrier synchronization primitives that
enable runtime system schedule and execute independent tasks concurrently over
the available compute resources. We demonstrate the capabilities of our
integrated compile time and runtime flow through task-level parallel and
functionally correct execution of real-life applications. We perform
validation of our integrated system by executing four distinct applications
each carrying various degrees of task level parallelism over the Xeon-based
multi-core homogeneous processor. We use the proposed compilation and code
transformation methodology to re-target each application for execution on a
heterogeneous SoC composed of three ARM cores and one FFT accelerator that is
emulated on the Xilinx Zynq UltraScale+ platform. We demonstrate our runtime’s
ability to process application binary, dispatch independent tasks over the
available compute resources of the emulated SoC on the Zynq FPGA based on
three different scheduling heuristics. Finally we demonstrate execution of
each application individually with task level parallelism on the Zynq FPGA and
execution of workload scenarios composed of multiple instances of the same
application as well as mixture of two distinct applications to demonstrate
ability to realize both application and task level parallel execution. Our
integrated approach offers a path forward for application developers to take
full advantage of the target SoC without requiring users to become hardware
and parallel programming experts.

###### Index Terms:

Task-level parallelism, dynamic profiling, heterogeneous SoC and runtime,
parallelism detection

##  I Introduction

SoCs composed of a pool of heterogeneous processing elements offer performance
gains over their homogeneous counterparts as they allow pairing each task or
execution phase of application with a suitable processing element (PE) based
on the state of the system resources. To harness this flexibility, programming
models have been introduced where application developers or domain experts
guide the compilation process by making task to PE mapping decisions based on
offline profiling. For example, in CUDA-based programming, programmers have to
understand the application, partition it into independent tasks, and manually
map them to threads and blocks in GPU. This model of computation results in a
static execution flow and a hand-crafted schedule that is greedily tuned for a
single application. In this study, we introduce an integrated compile time and
runtime environment that automatically detects parallelism in the user
application, transforms the program to parallel representation, and provides
the runtime system with a flexible binary structure. This allows the runtime
system to dynamically schedule and launch these tasks in parallel to
heterogeneous resources based on the system state rather than rely on a hand-
crafted static schedule.

|  Dedicated Framework | Program Analysis | Target Architecture | End-to-End
---|---|---|---|---
Static | Dynamic | Multicore | Hetero. SoC
Tensorflow[1] | ✔ | ✔ |  | ✔ | ✔ | ✔
Halide[2] | ✔ | ✔ |  | ✔ |  | ✔
HPVM[3] | ✔ | ✔ |  | ✔ | ✔ | ✔
Chi et al.[4] | ✔ | ✔ |  |  | ✔ | ✔
Parwiz [5] |  | ✔ | ✔ | ✔ |  |
SD3 [6] |  | ✔ | ✔ | ✔ |  |
Wang et al. [7] |  | ✔ | ✔ | ✔ |  | ✔
Kremlin [8] |  | ✔ | ✔ | ✔ |  | ✔
Ours |  | ✔ | ✔ | ✔ | ✔ | ✔

TABLE I: Related work on program analysis and workload parallelization

Programming models such as OpenMP[9] and Pthread[10] offer interfaces like
pragma labels and thread bindings where users specify the parallelism in their
applications explicitly. Program analysis tools have been introduced to enable
transforming a user application to a parallel representation based on static
[2, 1, 4, 3] or dynamic [6, 8, 7, 5] analysis as listed in Table I. These
tools also vary in terms of their approach to parallelism detection from
instruction level granularity targeted for multi-core architectures to task
level granularity for heterogeneous architectures. Static parallelization
methods require the user to express the application in an explicit data flow
style either using a domain-specific language (DSL) or a dedicated framework.
Among the dynamic methods, our approach is the only one that targets both
homogeneous multi-core architectures and heterogeneous SoCs in an end-to-end
integrated compile and run time flow.

Our approach employs a profile-guided dynamic analysis of memory access
patterns using a combination of memory tuples, loop-access patterns and
function pointers for inferring the required runtime control states that are
necessary for task-level dependence analysis. It offers the ability to
retarget user applications with coarse-grained computation tasks for
heterogeneous architectures through code transformations that enable parallel
task execution in one unified compile time and runtime framework. The key
technical contributions of this study are as follows:

  * •

We introduce a novel profile-guided memory analysis approach to detect the
data dependencies among coarse-grained tasks in a given application and expose
the parallelism among those tasks.

  * •

We present a methodology that partitions the user application into serial and
parallel tasks following a fork-join programming model and compiles into an
application binary representation with embedded parallelism and
instrumentation such that the runtime system can issue and execute all
independent tasks concurrently.

  * •

We integrate the profile-guided parallel program generation tool flow with an
open-source runtime and demonstrate an end-to-end system that is able to
compile and execute real-life applications on off-the-shelf platforms.

We demonstrate the ability to identify task-level parallelism for real life
applications, transform user-application for parallel execution, and
successfully execute those tasks in parallel first using an event-driven
simulation environment DS3[11]. After validating the ability to extract
parallelism, we demonstrate functionally correct task-level parallelism in our
runtime for those parallelized applications on a homogeneous 8-core Xeon
processor. Finally, we demonstrate functionally correct parallel execution on
an emulated heterogeneous SoC composed of 3 ARM CPUs and an FPGA-based
accelerator. This emulation platform illustrates not only our ability to
process single application with parallel execution flow but also our ability
to execute multiple dynamically arriving applications supporting both task-
level and application level parallel execution across heterogeneous set of
resources.

Figure 1: Overall tool flow involves _Pre-processing_ (Section II-D). _Data
DAG Generation_ (Section II-E), followed by _Parallel Code Generation_
(Section II-F).

Figure 2: The state of the user application as it is processed through based
on the tool flow shown in Figure 1. (a) User application with function
pointers, pointers for passing variables and unknown loop iteration count; (b)
Instrumented user application for tracing during pre-processing; (c) Flattened
user application after pre-processing step; (d) Parallelized user application
instrumented with counter based conditional wait.

##  II Profile Guided Parallel Program Generation

###  II-A Overview

The overall flow of the profile guided parallel program generation as
illustrated in Figure 1, involves the Preprocessing (Step-1) and Application
Data DAG Generation (Step-2) followed by Parallel Code Generation (Step-3). In
this design flow, we leverage TraceAtlas [12] for profile-based program
analysis and update Compiler Integrated Extensible DSSoC Runtime (CEDR) [13]
for runtime task scheduling. TraceAtlas[12] offers flexible interfaces to
support dynamic profiling and trace analysis of LLVM IR [14] rapidly with
lower resource requirements compared to other frameworks [15, 16, 17]. We use
TraceAtlas to collect memory address ranges accessed by each basic block in
the IR along with the runtime control states of those blocks. We then use this
information to identify tasks that can be executed in parallel during a task-
level memory analysis of the user application. The CEDR ecosystem allows
integrating compile-time application analysis with a Linux-based runtime
system. We choose CEDR over other runtime frameworks [18, 19, 20, 21, 22, 23,
24] as it enables compilation and development of user applications for
heterogeneous SoCs, evaluating the performance of pre-silicon heterogeneous
hardware configurations based on dynamically arriving workload scenarios
through distinct plug-and-play integration points in a unified workflow.

###  II-B Program Model

Our system partitions the user application into two types of tasks to
represent the execution flow as _Type-1 Task_ and _Type-2 Task_ regions as
described below.

####  II-B1 Type-1 Task

These tasks represent code segments that have low computation complexity,
function as auxiliary, and are suitable for executing on the CPU core in a
single thread.

####  II-B2 Type-2 Task

These tasks represent compute-intensive segments of the execution at the task
level such as FFT and matrix multiplication. We assume that there is
accelerator support for _Type-2 Tasks_ and they can be executed in parallel
using multi-threading on CPU or on the accelerator depending on the state of
the system resources. Users are required to register Type-2 tasks with
C-models and interface functions to invoke the driver of any supported
accelerators. Here the C-model is flexible enough that users can either use
third-party libraries or just manually implement them.

###  II-C Running Example

We utilize a running example that consists of commonly used program structures
with a representative computation task in our problem domain, namely, FFT(Fast
Fourier Transform). Figure 2 presents the workings of our tool flow for the
user application. Figure 2a is crafted in such a way that it includes features
where static analysis is not feasible for detecting data dependence such as
the use of pointers for passing variables (lines 2 and 8), function pointers
for tasks (lines 6 and 11), different function spaces while calling the tasks
(lines 18 and 20), and loop iteration counter that is not known at compile
time (line 19). Pre-processing step refactors the user application through
inlining functions dynamically, redirecting function pointers and flattening
loops that iterate over _Type-2 Tasks_. This prepares the application for data
DAG generation that captures concurrent execution paths over _Type-2 Tasks_
through dynamic memory analysis followed by control and data flow analysis.
Finally refactored code is instrumented with pthread insertion for runtime
system to be able to schedule the detected parallel Type-2 Tasks concurrently.
In the following subsections, we present the details of our approach by
walking through the steps of transforming a user application written in C/C++
into a representation that allows the runtime system to execute tasks without
dependencies in parallel.

###  II-D Step 1: Pre-processing

In this step, we implement a profile-guided method to flatten the loops and
inline the functions that interface with _Type-2 Tasks_. The pre-processing
step parses the user application and automatically instruments it with
functions as illustrated in Figure 2b (lines 3, 15, 18 and 20) to be able to
trace each Type-2 Task and loop identifier. The instrumented user application
is compiled and executed to collect profiling data on loop trip count and
function pointer destination. The pre-processing step then parses the
instrumented user application second time, flattens the loop and redirects
Type-2 Task calls. In our running example, assuming that loop trip count is
two the output of the pre-processing step is illustrated in Figure 2c.

###  II-E Step 2:Data DAG Generation

Implementation flow for this step is illustrated in Figure 1b where we start
with compiling the preprocessed application using Clang to generate the LLVM
IR. Recall that a user application is represented with a _Control DAG_ , where
each node represents either _Type-1_ or _Type-2_ tasks and the edges between
the nodes represent the flow of the execution. Here a task can contain
multiple basic blocks. We trace basic block control related flags such as
BasicBlockEnter, BasicBlockExit along with task control related flags such as
TaskEnter and TaskExit using TraceAtlas [12] in _Dynamic Profiling_ stage. We
generate the _Control DAG_ structure of the application based on the above
four control flags. In our running example, the serial flow of program
execution (_ReadData(a0), FFT(a0,b0,.,.), WriteData(b0), ReadData(a1),
FFT(a1,b1,.,.), WriteData(b1)_) illustrated in Figure 2c corresponds to the
_Control DAG_ with six nodes ($0\rightarrow 1\rightarrow 2\rightarrow
3\rightarrow 4\rightarrow 5$) shown in Figure 1b. The entry and exit points
collected at the task level allow for segmenting the program into Type-1 and
Type-2 tasks. Each time TaskEnter or TaskExit is seen, a new node is pushed
into the Control DAG, and the basic blocks that appear between TaskEnter and
TaskExit are recorded as the basic block elements of the node. The traced
memory instructions in TraceAtlas include LoadAddress, StoreAddress, along
with a set of LLVM intrinsic memory instructions such as MemCpy, MemSet, and
MemMove. The addresses of memory instructions, control flags, and _Control
DAG_ are used during _Memory Analysis_ stage to detect data dependencies and
expose parallelism among the tasks.

The _Memory Analysis_ parses the _Control DAG_ and uses the trace information
collected from _TraceAtlas_ to generate the load/store memory tuple sets for
each node. We define a _load memory tuple set_ and a _store memory tuple set_
for each task of the Control DAG to represent the continuously accessed memory
space for read and write activities, respectively. Each tuple for a task is
composed of _start address_ , _end address_ , _number of memory accesses_ ,
_number of bytes accessed_ , and _task label_. The memory tuples are stored in
a red-black tree structure with the start address as the key to reducing the
indexing time.

The visual representation of memory analysis is shown in Figure 3, where the
y-axis shows an index of each node in the _Control DAG_ , x-axis shows the
address range accessed (load or store) by each node through labeled rectangles
in a normalized form. For example, node index one is the first FFT task in the
user application with 2048 samples and 16,384 bytes of memory footprint
starting with the load address range followed by the store address range
corresponding to read and write operations respectively. The read after write
dependence is identified by checking if the load tuple set of the successor
node overlaps with the store tuple set of the predecessor node. A data
dependency between predecessor and successor nodes exists only if the
predecessor node is the last node to write into the load address space of the
successor node. In the running example, referring to the memory analysis
result in Figure 3, Nodes 1 and 3 (_FFT()_ and _ReadData(a1)_) have the same
store address space. Based on the order of execution, the true dependency is
between Nodes 3 and 4 (second FFT task). The second FFT task (Node 4) has a
load address space that does not overlap with the store address space of the
first FFT task (Node 1). Finally, we implement the LastWriterMap data
structure as illustrated in Figure 4 to keep track of the address spaces
modified by each node and utilize this representation to identify Type 2 Tasks
that can be executed in parallel.

The _Data DAG_ stage in this phase detects _Type-2 Tasks_ that can be executed
in parallel and generates the corresponding _Data DAG_. The _Data DAG_ is
built on the _Control DAG_ structure, with each edge representing the data
dependencies between the tasks.

Figure 3:  Memory Dependence Analysis. The address range that a node accesses
when reading and writing are shown with the load and store tuple set. When the
load tuple set of the successor does not overlap with the store tuple set of
the predecessor, they do not have a data dependency.

Figure 4:  Step by step (t1 to t3) _Data DAG_ Generation for _Control DAG_ of
$A\rightarrow B\rightarrow C$ scenario.

Figure 4 shows state of the LastWriterMap and _Data DAG_ generation in three
steps ($t1$ to $t3$) for a simple scenario composed of independent Tasks A and
B feeding their data to Task C with a _Control DAG_ of $A\rightarrow
B\rightarrow C$. Each time a new node is visited in the _Control DAG_ , its
store memory tuple set is written into the LastWriterMap. We overwrite the
existing memory tuples and change the pointed value to the new node’s index if
the store memory tuple set of the new node overlaps with the store memory
tuple set maintained in the current LastWriterMap. At the end of the second
step, the Data DAG with two independent nodes are generated as load address
space of _Task B_ ($B.ld$) is not overlapping with the store address space in
the LastWriterMap. On the other hand, in step 3, edges from _Task A_ and _Task
B_ to _Task C_ are generated due to the load-store overlap between $C.ld$ and
_store memory tuple_ in the LastWriterMap that points to both _Task A_ and
_Task B_.

Figure 5:  Task Reordering for the running example from Figure 2: Nodes 1 and
4 represent two independent FFTs (Type-2 Tasks) with distinct IOs, Nodes 0 and
3 represent reading input data (Type-1 Tasks), and Nodes 2 and 5 represent
writing output data (Type-1 Tasks). The algorithm in Figure 6 generates a
schedule with Control DAG nodes reordered following the fork and join model.

(a) Schedule Generation algorithm flow.

(b) State of the _Schedule_ as Schedule Generation progresses.

Figure 6:  The Schedule Generation algorithm reorders DAG nodes for the
running example from Figure 2.

###  II-F Step3: Parallel Code Generation

We define the group of Type-1 tasks that can be scheduled for execution before
a Type-2 task as the _Type-1 Region_ and the group of Type-2 tasks that can be
scheduled before a Type-1 task as the _Type-2 Region_. After identifying the
Type-2 tasks that can be executed in parallel, we transform the user
application to be represented as a series of code sections composed of Type-1
and Type-2 regions successively in _Task Reordering_ stage. We implement the
_Schedule Generation_ algorithm for this transformation and generate a
_Schedule DAG_ that follows the fork-and-join parallel model as illustrated in
Figure 5 for our running example shown in Figure 2. The _Schedule Generation_
algorithm is realized through seven steps as illustrated in Figure 6 using
_Data DAG_ and _Control DAG_ as its inputs. We define a task as a ready task
if all of its parent tasks in the _Data DAG_ have been scheduled. Steps 1-3
generate _Schedule DAG_ for Type-1 Tasks (Nodes 0 and 3) and mark these nodes
as visited. Steps 4-6 update _Schedule DAG_ with Type-2 Tasks (Nodes 1 and 4)
and mark these nodes as visited. All steps are repeated by visiting Type-1
Tasks followed by visiting Type-2 Tasks that remain in the DAG until all DAG
nodes have been visited. While our running example in Figure 2c involves two
parallel Type-2 Tasks, the _Schedule Generation_ algorithm implements a
generalized solution that is capable of clustering _N_ parallel Type-2 Tasks
into a single region to realize _N-way_ parallelism.

(a) Type-2 tasks execute serially.

(b) Tasks rearranged and merged.

Figure 7:  Code transformation for parallel execution through task merging.

Referring to the user application shown in Figure 2c, during the application
refactoring process of _Pthread Insertion_ , all Type-2 Tasks (FFTs) are
swapped with the enqueue kernel as shown in the tool-generated code with
Figure 2d. This representation is our interface for the Type-2 tasks to be
scheduled by the runtime resource manager. CEDR operates as a background
_Daemon Process_ in the Linux user space and applications are submitted
through inter-process communication (IPC). The CEDR _Management Thread_ parses
the dynamically arriving application binaries and through the enqueue kernel
function places Type-2 Tasks, whose dependencies are resolved, into the ready
queue. The scheduler makes task-to-PE mapping decisions for those tasks that
are in the ready queue. Then CEDR launches a worker thread for each Type-2
Task to execute on the selected PE and monitors the state of execution through
_PE Tracker_.

The trace-based analysis and _Data DAG_ representation enable specifying that
the user application in Figure 2 can be refactored from the original structure
shown in Figure 7(a) into Type-1 and Type-2 regions as illustrated in Figure
7(b). Along with this transformation, the run time environment needs to know
the number of independent Type 2 Tasks grouped together into a single region.
For this, during _Pthread Insertion_ stage, code refactoring also involves
automatically inserting pthread initialization and conditional wait statements
into the transformed application. In this final code representation, two
enqueue kernels are placed one after another without barrier synchronization
but there is a while loop waiting for those two FFT functions to be completed.
At run time, the OS thread initializes the counter value to 0 and waits for
the counter to meet the condition. For our running example, the conditional
wait value is set to two. We updated CEDR to support the execution of parallel
_Type-2 Tasks_ in _Type-2 Region_. Given that the data initializations are
completed by the OS thread, CEDR places both FFTs into the ready queue as
there is no barrier between the two FFTs. The scheduler then picks up both
FFTs from the ready queue and makes the task to PE mapping decisions. For each
FFT, a worker thread is launched and both functions get executed in parallel.
Through the _PE Tracker_ , the CEDR management thread monitors the execution
of each FFT. As soon as an FFT task gets completed, the CEDR worker thread
increments the counter value by one and passes this information back to the OS
thread. When the counter reaches to two, the OS thread resumes its Type-1
region possibly to the next phase that needs outputs of the two FFTs. The
runtime system supports executing _N-way_ parallelism as the counter value is
a parameter that is generated during the _Pthread Insertion_ stage.

Figure 8: The tool generated _Data DAG_ of the test applications.

##  III Experimental Setup

Application | Type-2 task | Phases | Parallelism/Phase
---|---|---|---
4-Pulse Doppler | FFT(256pt) | 3 | 8, 4, 4
256-Pulse Doppler | FFT(256pt) | 3 | 512, 256, 256
WiFi-TX | FFT(128pt) | 1 | 10
Radar Correlator | FFT(512pt) | 2 | 2, 1
Temporal Mitigation | GeMM(4x64) | 2 | 2, 1
TABLE II: Benchmark applications with _Type-2 task_ , the number of _Type-2
task_ phases, and the maximum number of parallel _Type-2 tasks_ for each
phase.

###  III-A Applications

For our analysis, we use Pulse Doppler, WiFi-TX, Radar Correlator and Temporal
Mitigation as real-world applications from the domain of software defined
radio. These applications have varying levels of parallelization and help
illustrate the generalizability of our approach.
Pulse Doppler determines both the distance of an object and its velocity based
on a series of short radar pulses emitted, and the user application observes
the shift in the frequencies of the return pulses with respect to the input
pulse.
WiFi TX implements a WiFi transmit chain, generating a single packet with 64
bits of input data and scrambling, encoding, modulating, followed by forward
error correction.
Radar Correlator models the use of a radar pulse to determine distance to an
object by looking at the time delay in the received pulse compared to the
input pulse.
Temporal Interference Mitigation receives a signal consisting of low-energy
radar signals combined with high-energy communications data and applies a
technique known as successive interference cancellation to cancel out the
communications data and extract the radar signals for further processing.

Figure 8 shows the execution phases as a data flow graph (DFG) for each
application generated by our tool chain, where a phase is defined as a
distinct _Type-2 Region_. For the sake of simplicity, we show DFG for the
4-Pulse Doppler version which has three execution phases, but in our
evaluations, we also use the full scale implementation with 256-Pulses. In
Table II we summarize the type of task, the number of execution phases, and
the degree of task-level parallelism observed during each execution phase.

###  III-B Evaluation Platforms

For our evaluations, we utilize three diverse platforms, namely, DS3 [11], an
event-driven simulator, a homogeneous architecture based on Intel(R) Xeon(R)
CPU E5-2650 v3 multicore processor, and Xilinx Zynq Ultrascale+ ZCU102 MPSoC
development board.

DS3 simulates the execution of an application represented as a DAG over a user
specified heterogeneous SoC configuration where the task to processing element
mapping decisions are handled through its built-in Earliest Finish Time (EFT)
scheduler. This environment serves as a suitable platform to estimate
performance gains of the task-level parallelism extracted through our tool
chain.

On the Xeon(R) CPU, each application is processed through our compiler tool
chain and then executed through the CEDR environment over 8-cores. This setup
allows us to validate the end-to-end integrated compiler and runtime flow over
a homogeneous architecture and evaluate the performance gain with respect to
serial execution.

The Xilinx Zynq Ultrascale+ ZCU102 MPSoC development board is used to emulate
a heterogeneous SoC with 3 ARM CPU cores and 1 FFT accelerator. This setup
serves three purposes. First, it allows validating our ability to compile a
user application for execution on a heterogeneous SoC. Second, we demonstrate
our ability to execute parallel FFT tasks in a single application across a
pool of heterogeneous resources concurrently. Third, we demonstrate our
ability to manage workload scenarios where multiple independent user
applications arrive dynamically and parallel execution at both application and
task levels are realized through our integrated compile and runtime flow. To
facilitate data transfer to and from accelerators, we use direct memory access
(DMA) blocks to move data between the host ARM core and the FFT accelerator
via the AXI4-Stream protocol. On the host side, we utilize udmabuf to enable
contiguous userspace-accessible buffers for transferring data to and from the
hardware accelerators. A user application communicates with the accelerators
by writing the data into a udmabuf buffer and a DMA engine is then configured
to move data from this buffer into an accelerator for processing. This setup,
while allowing experimentation on a heterogeneous hardware configuration, does
not offer a realistic SoC representation since we are not emulating a
dedicated NoC. Therefore we strictly use it for functional verification
purpose rather than conducting realistic performance evaluations.

For the FPGA evaluation we use the Radar Correlator and WiFi-TX. We process
them through our compiler tool chain and submit them as single or 100 instance
jobs where the CEDR management thread parses application binary, monitors
system resources, schedules tasks based on Minimum Execution Time (MET), Round
Robin (RR) and Earliest Finish Time (EFT) schedulers. We measure application
execution time as the difference between the end of the last task and the
start of the first task of an application, including the overhead of all
scheduling decisions and data transfers to and from the accelerator in
between.

##  IV Results and Analysis

(a) 4-Pulse Doppler on SoC with 4 FFTs.

(b) 4-Pulse Doppler on SoC with 8 FFTs.

(c) 256-Pulse Doppler on SoC with 8 FFTs.

Figure 9:  Execution flow for Pulse Doppler on DS3-simulated SoCs with varying
numbers of FFT accelerators: (a) 8 parallel FFTs in the first stage are
executed over 4 FFT accelerators in two rounds, followed by single round
execution in second and third stages. (b) 8 parallel FFTs in the first stage
are executed over 8 FFT accelerators in one round, followed by single round
execution in the following two stages. (c) Full scale Pulse Doppler on an SoC
with 8 FFTs where 256 FFTs in the first stage are evenly distributed as 64 FFT
rounds over 8 cores followed by 32 FFT rounds in the subsequent two stages.
Figure 10:  The execution flow of 256-Pulse Doppler in three stages over the
8-core Xeon processor managed by CEDR with 8 FFT accelerators matches the
execution obtained from DS3 illustrated in Figure 9(c).

(a) Minimum Execution Time - MET

(b) RoundRobin - RR

(c) Earliest Finish Time - EFT

Figure 11: 100 instances of auto-parallelized Radar Correlator application
running on ZCU102 FPGA using three types of schedulers. Coloring encodes the
application instance number modulo 10.

(a) Two instances of parallel Radar Correlator running with EFT scheduler.

(b) Single instances of auto-parallelized Radar Correlator with serial WiFi
TX.

Figure 12:  Demonstration of inter and intra-application parallelism via
simultaneous execution on ZCU102 FPGA

###  IV-A Functional Verification and Performance Analysis

Pulse Doppler shows higher degree of parallelism relative to the other
applications we use in this study. Therefore, we start with functional
verification based on the Pulse Doppler execution through DS3 based simulation
over an SoC with 4 and 8 FFT accelerators as shown in Figure 9(a) and Figure
9(b), respectively. Since the 4-pulse version has 8 FFTs during the first
stage (Figure 9(a)), an SoC with 4 FFT accelerators takes two rounds to
complete the first stage, whereas on the 8 FFT configuration it takes one
round. These two figures together illustrate ability to launch FFT tasks in
parallel. Figure 9(c) shows the 256-Pulse Doppler execution over the 8 FFT SoC
configuration where first stage of the execution takes 64 rounds to complete
and subsequent two phases take 32 rounds each. Overall, the plots in Figure 9
show that our tool flow is able to extract parallelism in each stage of the
execution and distribute the parallel tasks over the available compute
resources.

We demonstrate the execution of the real 256-Pulse Doppler implementation that
is compiled for execution over the 8-core Xeon processor configuration using
Figure 10, where execution of the parallelized application is managed by the
CEDR. This plot shows same flow as Figure 9(c) with three stage execution
where first stage takes 64 rounds and subsequent two stages take 32 rounds
each. This plot validates the runtime’s ability to distribute FFT tasks as
expected. Here we note that the DS3 based execution shows faster execution
time than the Xeon processor based execution. There are two key factors to
this observation. First the DS3 uses a model based execution where the FFT
compute time is based on its actual execution over the Xilinx FFT IP Core
synthesized for the ZCU102 FPGA. The compute time for the FFT accelerator is
128 ns whereas the execution time for the FFT task on the Xeon processor is
25,000 ns. Furthermore, overhead associated with the CEDR environment in terms
of parsing application binary and dispatching task to the compute resources
contribute to the increased overall execution time. Such runtime overhead is
not modeled in DS3.

Application | Whole Application | Only Tasks
---|---|---
Xeon CPU | DS3 | Xeon CPU | DS3
Radar Correlator | 9.6 | 14.8 | 30.5 | 91.6
Pulse Doppler | 59.0 | 67.3 | 73.5 | 84.0
Temporal Mitigation | 3.9 | 15.5 | 48.8 | 97.5
WiFi-TX | 17.0 | 21.2 | 23.4 | 29.4
Average | 22.4 | 29.7 | 44.1 | 75.6
TABLE III:  Execution time reduction (%) with respect to the serial single
Xeon core-based execution covering the end-to-end execution of the whole
application and the time spent only over the FFT or GEMM tasks.

Finally, Table III shows reduction in execution time with respect to the
serial execution for each application through CEDR on Xeon processor and DS3
in terms of time taken by the whole application and time spent only for the
Type-1 and Type-2 tasks excluding data loads/stores from/to the disk.
Consistent with the observations on the Pulse Doppler plots (Figure 9(c) and
Figure 10), as shown in Table III, for the computation tasks, we see an
average of 44% and 75.6% reduction in execution time with respect to the
serial execution on the x86-based multi-core processor and DS3-based
simulation respectively. For the whole application, the average reduction in
execution time drops to 22.4% and 29.7% respectively, because of the reading
from the disk and writing to the disk that contribute to the prolonged
execution time. Note that WiFi-TX has less time saving compared to other
applications. The reason is that WiFi-TX time spent on FFT is relatively less
as this application involves other compute phases such as Scrambler,
Interleaver, and Pilot-Insertion.

###  IV-B FPGA-based Emulation and Analysis

In Figure 11, we show timing analysis for the Radar Correlator that is
refactored into parallel execution form through our compiler tool chain. The
three plots illustrate the makespan for completing a workload composed of 100
instances of Radar Correlator executed based on the MET, RR, and EFT
schedulers. This experiment shows that making a greedy choice favoring the
accelerator (common in hand-crafted code) only results in FFT tasks starving
for the accelerator to become available. MET enforces serial execution on the
accelerator and also serves as a baseline for total execution time. The RR and
EFT schedulers allow for utilizing the parallelism embedded into the
application binary, and each one completes the workload in 41.61ms (1.48x
faster) and 40.66ms (1.51x faster), respectively.

Figure 12 illustrates the runtime system’s ability to execute FFT tasks from
two applications as well as the independent FFTs within an application
concurrently. In Figure 12(a), we show execution for two instances of Radar
Correlator arriving concurrently where a total of four FFT tasks are
dispatched to all PEs concurrently. Finally in Figure 12(b), we show the PE
utilization based on the concurrent execution of WiFi TX and Radar Correlator
applications. The EFT in this case favors the FFT accelerator to be used by
the WiFi TX as it has higher latency than the Radar Correlator. It splits the
use of ARM cores among the two applications and assigns Cores 2 and 3 to WiFi
TX after the completion of the Radar Correlator.

##  V Conclusions

In order to make heterogeneous SoCs accessible, there is the need for
integrating the application development, compilation and runtime processes
vertically towards a unified ecosystem that enables productive application
deployment without requiring users to become hardware experts in the process.
Towards this goal, in this study, we present an integrated flow where we
expose parallelism in a user application through dynamic profiling and memory
analysis, and design a flexible binary structure where an application task can
be invoked on any of its supported processing elements in the target SoC. We
pass the parallelized binary to the runtime system that handles parsing
dynamically arriving applications, scheduling tasks, and completing the
workloads. We validate our approach through real-life radar applications
executed on a diverse set of platforms. We believe that our integrated end-to-
end system allows hardware-agnostic application development, enables exposing
parallelism automatically in the user application and successful deployment on
both multi-core homogeneous and heterogeneous architectures. The proposed
dynamic analysis based method is sensitive to the nature of the inputs that
may trigger different control flow for the same application. Future works will
focus on addressing this open problem by merging the _Control DAG_ for
different inputs and setting up a back-up control flow to recover the program
execution and resolve unpredictable application behavior.

## References

  * [1] M. Abadi, P. Barham, J. Chen, Z. Chen, A. Davis, J. Dean, M. Devin, S. Ghemawat, G. Irving, M. Isard _et al._ , “Tensorflow: A system for large scale machine learning,” in _12th USENIX symposium on operating systems design and implementation (OSDI 16)_ , 2016, pp. 265–283.
  * [2] J. Ragan-Kelley, C. Barnes, A. Adams, S. Paris, F. Durand, and S. Amarasinghe, “Halide: a language and compiler for optimizing parallelism, locality, and recomputation in image processing pipelines,” _Acm Sigplan Notices_ , vol. 48, no. 6, pp. 519–530, 2013.
  * [3] M. Kotsifakou, P. Srivastava, M. D. Sinclair, R. Komuravelli, V. Adve, and S. Adve, “Hpvm: Heterogeneous parallel virtual machine,” in _Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming_ , 2018, pp. 68–80.
  * [4] Y. Chi, L. Guo, J. Lau, Y.-k. Choi, J. Wang, and J. Cong, “Extending high-level synthesis for task-parallel programs,” in _2021 IEEE 29th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM)_. IEEE, 2021, pp. 204–213.
  * [5] A. Ketterlin and P. Clauss, “Profiling data-dependence to assist parallelization: Framework, scope, and optimization,” in _2012 45th Annual IEEE/ACM International Symposium on Microarchitecture_. IEEE, 2012, pp. 437–448.
  * [6] M. Kim, H. Kim, and C.-K. Luk, “Sd3: A scalable approach to dynamic data-dependence profiling,” in _2010 43rd IEEE/ACM International Symposium on Microarchitecture_. IEEE, 2010, pp. 535–546.
  * [7] Z. Wang, G. Tournavitis, B. Franke, and M. F. O’boyle, “Integrating profile-driven parallelism detection and machine-learning-based mapping,” _ACM Transactions on Architecture and Code Optimization (TACO)_ , vol. 11, no. 1, pp. 1–26, 2014.
  * [8] S. Garcia, D. Jeon, C. M. Louie, and M. B. Taylor, “Kremlin: Rethinking and rebooting gprof for the multicore age,” _ACM SIGPLAN Notices_ , vol. 46, no. 6, pp. 458–469, 2011.
  * [9] L. Dagum and R. Menon, “Openmp: an industry standard api for shared-memory programming,” _IEEE computational science and engineering_ , vol. 5, no. 1, pp. 46–55, 1998.
  * [10] D. R. Butenhof, _Programming with POSIX threads_. Addison-Wesley Professional, 1997.
  * [11] S. E. Arda, A. Krishnakumar, A. A. Goksoy, N. Kumbhare, J. Mack, A. L. Sartor, A. Akoglu, R. Marculescu, and U. Y. Ogras, “Ds3: A system-level domain-specific system-on-chip simulation framework,” _IEEE Transactions on Computers_ , vol. 69, no. 8, pp. 1248–1262, 2020.
  * [12] R. Uhrie, C. Chakrabarti, and J. Brunhaver, “Automated parallel kernel extraction from dynamic application traces,” _arXiv preprint arXiv:2001.09995_ , 2020.
  * [13] J. Mack, , S. Hassan, N. Kumbhare, M. Gonzales, and A. Akoglu, “CEDR - A Compiler-integrated, Extensible DSSoC Runtime,” _ACM Transactions on Embedded Computing Systems_ , Apr. 2022. [Online]. Available: https://doi.org/10.1145/3529257
  * [14] C. Lattner and V. Adve, “Llvm: A compilation framework for lifelong program analysis & transformation,” in _International Symposium on Code Generation and Optimization,_. IEEE, 2004, pp. 75–86.
  * [15] Y. S. Shao, B. Reagen, G.-Y. Wei, and D. Brooks, “Aladdin: A pre-rtl, power-performance accelerator simulator enabling large design space exploration of customized architectures,” in _Proceeding of the 41st Annual International Symposium on Computer Architecuture_ , ser. ISCA ’14. IEEE Press, 2014, p. 97–108.
  * [16] D. Lehmann and M. Pradel, “Wasabi: A framework for dynamically analyzing webassembly,” in _Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems_ , ser. ASPLOS ’19. New York, NY, USA: Association for Computing Machinery, 2019, p. 1045–1058.
  * [17] C.-K. Luk, R. Cohn, R. Muth, H. Patil, A. Klauser, G. Lowney, S. Wallace, V. J. Reddi, and K. Hazelwood, “Pin: building customized program analysis tools with dynamic instrumentation,” _Acm sigplan notices_ , vol. 40, no. 6, pp. 190–200, 2005.
  * [18] C. Augonnet, S. Thibault, R. Namyst, and P.-A. Wacrenier, “StarPU: a unified platform for task scheduling on heterogeneous multicore architectures,” _Concurrency and Computation: Practice and Experience_ , vol. 23, no. 2, pp. 187–198, 2011.
  * [19] B. Donyanavard, T. Mück, S. Sarma, and N. Dutt, “Sparta: Runtime task allocation for energy efficient heterogeneous manycores,” in _2016 International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS)_ , 2016, pp. 1–10.
  * [20] B. Donyanavard, T. Mück, A. M. Rahmani, N. Dutt, A. Sadighi, F. Maurer, and A. Herkersdorf, “Sosa: Self-optimizing learning with self-adaptive control for hierarchical system-on-chip management,” in _Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture_ , ser. MICRO ’52. New York, NY, USA: Association for Computing Machinery, 2019, p. 685–698.
  * [21] B. Maity, B. Donyanavard, A. Surhonne, A. Rahmani, A. Herkersdorf, and N. Dutt, “SEAMS: Self-Optimizing Runtime Manager for Approximate Memory Hierarchies,” _ACM Transactions on Embedded Computing Systems_ , vol. 20, no. 5, pp. 48:1–48:26, Jul. 2021.
  * [22] A. L. del Mestre Martins, A. H. L. da Silva, A. M. Rahmani, N. Dutt, and F. G. Moraes, “Hierarchical adaptive multi-objective resource management for many-core systems,” _Journal of Systems Architecture_ , vol. 97, pp. 416–427, 2019.
  * [23] X. Tan, J. Bosch, C. Álvarez, D. Jiménez-González, E. Ayguadé, and M. Valero, “A hardware runtime for task-based programming models,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 30, no. 9, pp. 1932–1946, 2019.
  * [24] K. Moazzemi, B. Maity, S. Yi, A. M. Rahmani, and N. Dutt, “HESSLE-FREE: Heterogeneous systems leveraging fuzzy control for runtime resource management,” _ACM Transactions on Embedded Computing Systems_ , vol. 18, no. 5s, pp. 74:1–74:19, Oct. 2019.


#
On the BCSS Proof of the Fundamental Theorem of Algebra

J. Maurice Rojas1

###### Abstract

Section 10.4 of the 1998 Springer-Verlag book Complexity and Real Computation,
by Blum, Cucker, Shub, and Smale, contains a particularly elegant proof of the
Fundamental Theorem of Algebra: The central idea of the proof naturally leads
to a homotopy continuation algorithm for finding the roots of univariate
polynomials, and extends naturally to a proof of Bézout’s Theorem (on the
number of roots of systems of $n$ equations in $n$ unknowns). We present a
more detailed version of the BCSS Proof which is hopefully useful for students
and researchers not familiar with algebraic geometry. So while there are no
new results in this paper, the exposition is arguably more elementary. Any
errors here are solely the responsibility of the current author.

11footnotetext:  Department of Mathematics, Texas A&M University TAMU 3368,
College Station, Texas 77843-3368, USA. e-mail<EMAIL_ADDRESS>, Web
Page: www.math.tamu.edu/~rojas . Partially supported by NSF grants DMS-1460766
and CCF-1409020, and a von Neumann visiting professorship.

##  1 Preliminaries

The main theorem we prove is the following:

###### The Fundamental Theorem of Algebra.

A (univariate) polynomial $f\\!\in\\!\mathbb{C}[x]$ of degree $d\\!\geq\\!1$
has exactly $d$ roots in $\mathbb{C}$, counting multiplicities.

The Fundamental Theorem of Algebra (FTA) is arguably more a statement from
complex analysis than from algebra. The first statement of the FTA dates back
to work of Girard in 1629 and the first correct approach to its proof dates
back to work of D’Alembert in 1746. Perhaps the first proof which would be
considered rigorous by today’s standards is due to Motzkin and Ostrowski, from
1933. See [RS02, Sec. 1.8, Pg. 61] for valuable historical notes on the FTA.

While one can certainly prove the FTA in one line via Liouville’s Theorem from
complex analysis, the proof we present below (from [BCSS98, Sec. 10.4]) will
have two important advantages: (1) It leads naturally to a homotopy
continuation algorithm for finding the roots of univariate polynomials, and
(2) the proof extends naturally to a proof Bézout’s Theorem, on the number of
roots of $n$ polynomials in $n$ variables.

It will be useful to recall two equivalent definitions of multiplicity before
we eventually introduce a third, equivalent definition:

###### Proposition 1.1

Suppose $f\\!\in\\!\mathbb{C}[x]$ is a univariate polynomial of degree
$d\\!\geq\\!1$ and $m\\!\in\\!\mathbb{N}$. Then the following two conditions
on a root $\zeta\\!\in\\!\mathbb{C}$ of $f$ are equivalent, and are referred
to as $f$ having a root of multiplicity $m$:
(a) $f(x)\\!=\\!(x-\zeta)^{m}g(x)$ identically, for some
$g\\!\in\\!\mathbb{C}[x]$ not divisible by $x-\zeta$.
(b)
$f(\zeta)\\!=\\!f^{\prime}(\zeta)\\!=\cdots=f^{(m-1)}(\zeta)\\!=\\!0\\!\neq\\!f^{(m)}(\zeta)$.
We also call roots of multiplicity $1$ non-degenerate, and roots of
multiplicity $\geq\\!2$ degenerate. $\blacksquare$

The proof of Proposition 1.1 is straightforward (at least over the complex
numbers) via Taylor series. It is worth noting that Definition (a) extends
naturally to any field, while Definition (b) extends naturally to any analytic
function on $\mathbb{C}$.

Let us now fix some notation: If $f(x)\\!=\\!a_{0}+\cdots+a_{d}x^{d}$ and
$g(x)\\!=\\!b_{0}+\cdots+b_{e}x^{e}$ are polynomials in $\mathbb{C}[x]$ then
we define the Sylvester matrix of $(f,g)$ (of format $(d,e)$) to be:
$\mathrm{Syl}_{d,e}(f,g):=\begin{bmatrix}a_{0}&\cdots&a_{d-1}&a_{d}&0&\cdots&\cdots&0\\\
&&&\ddots&&&\ddots&\\\ 0&\cdots&\cdots&0&a_{0}&\cdots&a_{d-1}&a_{d}\\\
b_{0}&\cdots&b_{e}&0&0&\cdots&\cdots&0\\\ &&&\ddots&&&\ddots&\\\
0&\cdots&&\cdots&0&b_{0}&\cdots&b_{e}\end{bmatrix}\begin{matrix}\\\
\left.\rule{0.0pt}{25.6073pt}\right\\}e\text{ many shifting rows}\\\
\left.\rule{0.0pt}{25.6073pt}\right\\}d\text{ many shifting rows}\\\ \\\
\end{matrix}$
We also define the resultant (of format $(d,e)$) of $(f,g)$ to be the
determinant of $\mathrm{Syl}_{d,e}(f,g)$. Note that the resultant (of format
$(d,d-1)$) of $(f,f^{\prime})$ factors as
$a_{d}\Delta_{d}(a_{0},\ldots,a_{d})$ for some polynomial
$\Delta_{d}\\!\in\\!\mathbb{Z}[a_{0},\ldots,a_{d}]$, thanks to the last column
of the underlying Sylvester matrix. We call $\Delta_{d}$ the degree $d$
(univariate) discriminant polynomial and study it more later. That
$\Delta_{d}$ is in fact not identically zero is a consequence of the following
formula.

###### Proposition 1.2

For all $d\\!\geq\\!1$ we have
$\mathrm{Res}_{d,d-1}(x^{d}-1,dx^{d-1})\\!=\\!(-1)^{d-1}d^{d}$.

Proof: One need only observe that $\mathrm{Syl}_{d,d-1}(x^{d}-1,dx^{d-1})$ is
upper-triangular, with diagonal entries $-1,\ldots,-1$ ($d-1$ times) and
$d,\ldots,d$ ($d$ times). $\blacksquare$

Let us define
$\displaystyle{\Sigma_{d}:=\left\\{\left.(\gamma_{0},\ldots,\gamma_{d})\\!\in\\!\mathbb{C}^{d+1}\;\right|\;\gamma_{d}\Delta_{d}(\gamma_{0},\ldots,\gamma_{d})\\!=\\!0\right\\}}\subset\mathbb{C}^{d+1}$.
The set $\Sigma_{d}$ is a slight variant of the classical discriminant variety
$\nabla_{\\{0,\ldots,d\\}}\subset\mathbb{P}^{d}_{\mathbb{C}}$, which consists
of degree $d$ bivariate homogeneous polynomials having a degenerate root. In
particular, it will be convenient to identify the polynomial
$\gamma_{0}+\cdots+\gamma_{d}x^{d}\\!\in\\!\mathbb{C}[x]$ with the point
$(\gamma_{0},\ldots,\gamma_{d})\\!\in\\!\mathbb{C}^{d+1}$. In the Appendix, we
will prove the following useful algebraic result:

###### Lemma 1.3

Following the notation above, assume $d,e\\!\geq\\!1$ and
$\mathrm{Res}_{d,e}(f,g)\\!\neq\\!0$. Then the $2\times 1$ system of equations
$f(x)\\!=\\!g(x)\\!=\\!0$ has no complex solutions. In particular,
if$\Delta_{d}(\gamma_{0},\ldots,\gamma_{d})\\!\neq\\!0$, then any complex root
of $\gamma_{0}+\cdots+\gamma_{d}x^{d}$ has multiplicity $1$.

It will also be useful to recall the following basic fact, easily provable via
polynomial division.

###### Proposition 1.4

If $f\\!\in\\!\mathbb{C}[x]$ has degree $d\\!\geq\\!1$ then $f$ has at most
$d$ distinct complex roots. $\blacksquare$

Proposition 1.4 (or rather, the obvious extension where $\mathbb{C}$ is
replaced by an arbitrary field $F$) is sometimes called the Weak Fundamental
Theorem of Algebra.

We will also need some results on building paths avoiding complex
hypersurfaces and bounding roots of polynomials:

###### Proposition 1.5

If $g\\!\in\\!\mathbb{C}[x_{1},\ldots,x_{N}]\setminus\\{0\\}$ has complex zero
set $Z$ then $\mathbb{C}^{N}\setminus Z$ is analytically path-connected: For
any $p,q\\!\in\\!\mathbb{C}^{N}\setminus Z$ there is an analytic
$\phi:[0,1]\longrightarrow\mathbb{C}^{N}\setminus Z$ with $\phi(0)\\!=\\!p$
and $\phi(1)\\!=\\!q$.

Proof: We proceed by induction. Our proof will frequently use the obvious
identification between $\mathbb{R}^{2}$ and $\mathbb{C}$ via real and
imaginary parts.

By an invertible affine transformation
$T:\mathbb{R}^{2}\longrightarrow\mathbb{R}^{2}$, the $N\\!=\\!1$ case can
clearly be reduced to the special case $(p,q)\\!=\\!(0,1)$. So then let
$\mathbb{R}_{+}$ denote the positive ray and consider the family of parabolae
$\\{H_{c}\\}_{c\in\mathbb{R}_{+}}$ defined by
$H_{c}\\!:=\\!\\{(x,y)\\!\in\\!\mathbb{R}^{2}\;|\;y\\!=\\!cx(1-x)\\}$. Note
that each $H_{c}$ intersects $\\{0,1\\}$, and can clearly be parametrized via
$\phi(t)\\!:=\\!(t,ct(1-t))$. The map $\phi$ is clearly analytic and satisfies
$\phi(0)\\!=\\!(0,0)$ and $\phi(1)\\!=\\!(1,0)$ (and the last two points in
$\mathbb{R}^{2}$ can clearly also be viewed as the points $0$ and $1$ in
$\mathbb{C}$).

Clearly, there are only finite many values of $c$ with $H_{c}\cap
Z\\!\neq\\!\emptyset$: If
$Z\\!=\\!\\{(x_{1},y_{1}),\ldots,(x_{\ell},y_{\ell})\\}$ then we simply need
to pick a $c$ satisfying $cx_{i}(1-x_{i})\\!\neq\\!y_{i}$ for all $i$. Picking
$c\\!=\\!\frac{1}{2}\min_{i}\frac{y_{i}}{x_{i}(1-x_{i})}$ clearly suffices. We
thus obtain an $H_{c}$ connecting $0$ and $1$, and the resulting parametrized
path $\phi:[0,1]\longrightarrow\mathbb{R}^{2}$ is clearly analytic, as is also
the composition $T^{-1}(\phi(\cdot))$. So we are done.

To prove the general case we will let $N\\!\geq\\!2$ and reduce to the case
$N\\!=\\!1$ by restricting to a cleverly embedded copy of $\mathbb{C}$ in
$\mathbb{C}^{N}$: Define $L:\mathbb{C}\longrightarrow\mathbb{C}^{N}$ by
$L(t)\\!=\\!(1-t)p+tq$, let $h(t)\\!:=\\!g(L(t))$, and let $W$ denote the zero
set of $h$ in $\mathbb{C}$. Note that $L(0)\\!=\\!p$ and $L(1)\\!=\\!q$ and,
by assumption, $h(0)h(1)\\!=\\!g(p)g(q)\\!\neq\\!0$. So, since $L$ is an
analytic function, it suffices to find an analytic path in
$\mathbb{C}\setminus W$ connecting $0$ and $1$. By the $N\\!=\\!1$ case we
have already proved, we are done. $\blacksquare$

###### Lemma 1.6

If $f(x)\\!=\\!\gamma_{0}+\cdots+\gamma_{d}x^{d}\\!\in\\!\mathbb{C}[x]$ is a
univariate polynomial of degree $d\\!\geq\\!1$ then all the complex roots of
$f$ lie in the open disk of radius
$2\max\limits_{i\in\\{0,\ldots,d-1\\}}\left|\frac{\gamma_{i}}{\gamma_{d}}\right|^{\frac{1}{d-i}}$
centered at $0$.

Proof: The proof boils down to a judicious use of the Triangle Inequality.
First note that if $\zeta\\!\in\\!\mathbb{C}$ is a root of $f$ then
$|\gamma_{d}\zeta^{d}|\\!=\\!|\gamma_{0}+\cdots+\gamma_{d-1}\zeta^{d-1}|$ and
thus

$\displaystyle|\gamma_{d}||\zeta|^{d}$ $\displaystyle\leq$
$\displaystyle|\gamma_{0}|+|\gamma_{1}||\zeta|+\cdots+|\gamma_{d-1}||\zeta|^{d-1}$
(1)

So let us now consider the special case where $\gamma_{d}\\!=\\!1$ and
$\max\limits_{i\in\\{0,\ldots,d-1\\}}|\gamma_{i}|\\!=\\!1$. In this case,
Inequality (1) implies that
$|\zeta|^{d}\\!\leq\\!1+|\zeta|+\cdots+|\zeta|^{d-1}$. So by geometric series
we obtain $|\zeta|^{d}\\!\leq\\!\frac{|\zeta|^{d}-1}{|\zeta|-1}$. In the event
that $|\zeta|\\!\geq\\!2$ we would then obtain
$|\zeta|^{d}\\!\leq\\!|\zeta|^{d}-1$, which is clearly impossible. So we see
that $|\zeta|\\!<\\!2$ and our lemma is true.

To obtain the general case, let
$C\\!:=\\!\max\limits_{i\in\\{0,\ldots,d-1\\}}\left|\frac{\gamma_{i}}{\gamma_{d}}\right|^{\frac{1}{d-i}}$
and consider the polynomial

$g(x)\\!:=\\!\frac{f(Cx)}{\gamma_{d}C^{d}}.$

(Note that $\gamma_{d}\\!\neq\\!0$ since $f$ is assumed to have degree $d$.)
Clearly, our lemma is proved if we can prove that all the complex roots of $g$
have norm less than $2$. Toward this end, observe that the coefficient of
$x^{i}$ in $g$ (for $i\\!\in\\!\\{0,\ldots,d-1\\}$) is
$\frac{\gamma_{i}C^{i}}{\gamma_{d}C^{d}}\\!=\\!\left(\frac{(\gamma_{i}/\gamma_{d})^{1/(d-i)}}{C}\right)^{d-i}$.
Since $|\gamma_{i}/\gamma_{d}|^{1/(d-i)}\\!\leq\\!C$ by the definition of $C$,
every coefficient of $g$ has norm at most $1$. Furthermore, the coefficient of
$x^{d}$ in $g$ is $1$. So by our early special case, we are done.
$\blacksquare$

Lemma 1.6 is in fact a very special case of more general estimates on complex
roots of univariate polynomials. Such bounds date back to work of Cauchy
around 1829, if not earlier. More recent work relates the norms of complex
roots to Archimedean tropical varieties (e.g., [AKNR18, Thm. 1.7]) and extends
such estimates to polynomials in multiple variables.

Finally, we’ll need the following two analytic results.

###### The Extreme Value Theorem.

(See, e.g., [Mun00].) If $S\\!\subset\\!\mathbb{R}^{N}$ is closed and bounded
and $f:S\longrightarrow\mathbb{R}$ is continuous, then there exist
$a_{1},a_{2}\\!\in\\!S$ with $f(a_{1})\\!=\\!\inf_{x\in S}f(x)$ and
$f(a_{2})\\!=\\!\sup_{x\in S}f(x)$. In particular, $f$ is bounded.
$\blacksquare$

###### The Implicit Function Theorem.

(See, e.g., [Hub15].) If $G:\mathbb{C}^{2}\longrightarrow\mathbb{C}$ is an
analytic function with $G(t_{0},x_{0})\\!=\\!0$ and $\frac{\partial
G}{\partial x}|_{(t_{0},x_{0})}\\!\neq\\!0$ for some
$(t_{0},x_{0})\\!\in\\!\mathbb{C}^{2}$, then there is an open disk
$U\\!\subset\\!\mathbb{C}$ containing $t_{0}$, and an analytic function
$\mathcal{X}:U\longrightarrow\mathbb{C}$ (called a branch of the implicit
function defined by $G(t,x)\\!=\\!0$) with $\mathcal{X}(t_{0})\\!=\\!x_{0}$
and $G(t,\mathcal{X}(t))\\!=\\!0$ for all $t\\!\in\\!U$. $\blacksquare$

The Extreme Value Theorem is covered in most any basic course in real
analysis. We also note that [BCSS98, Sec. 8.2] presents an elegant proof of
the Inverse Function Theorem (via clever infinite series manipulations) that
can be used to derive explicit estimates for the size of the disk in the
Implicit Function Theorem.

##  2 The Proof of the Fundamental Theorem of Algebra

We first observe that the case $d\\!=\\!1$ is trivial:
$\gamma_{0}+\gamma_{1}x$ has only the root $-\gamma_{0}/\gamma_{1}$, which has
multiplicity $1$ since $f^{\prime}(x)$ is identically $\gamma_{1}$, and
$\gamma_{1}\\!\neq\\!0$ since we assumed the degree of $f$ is $d\\!=\\!1$. So
we may assume $d\\!\geq\\!2$ henceforth.

We then separate our proof into two cases: (1) $f\not\in\Sigma_{d}$ and (2)
$f\\!\in\\!\Sigma_{d}$. The first case is harder so we take care of it first.

###  2.1 The Case $f\not\in\Sigma_{d}$

First observe that $x^{d}-1\not\in\Sigma_{d}$ thanks to Proposition 1.2. Since
$\Sigma_{d}$ is the complex zero set of a polynomial, Proposition 1.5 tells us
that there is an analytic function
$\phi\\!=\\!(\phi_{0},\ldots,\phi_{d}):[0,1]\longrightarrow\mathbb{C}^{d+1}\setminus\Sigma_{d}$
with $\phi(0)\\!=\\!x^{d}-1$ and $\phi(1)\\!=\\!f$. (Since we identify
polynomials and points, we could have also said
$\phi(0)\\!=\\!(-1,0,\ldots,0,1)$ and
$\phi(1)\\!=\\!(\gamma_{0},\ldots,\gamma_{d})$.) Let
$G:[0,1]\times\mathbb{C}\longrightarrow\mathbb{C}$ be the analytic function
defined by $G(t,x)\\!:=\\!\phi_{0}(t)+\cdots+\phi_{d}(t)x^{d}$, i.e., $G$
simply evaluates the polynomial $\phi(t)$ on our path at the complex number
$x$.

Our main trick then will be to use our path of polynomials to build $d$ paths
of roots. On one end ($t\\!=\\!0$), the root paths start at the
$d^{\text{\text@underline{th}}}$ roots of unity. We will ultimately prove
that, on the other end ($t\\!=\\!1$), our root paths yield $d$ distinct
complex roots for $f$. Since $f\not\in\Sigma_{d}$ implies that each root of
$f$ has multiplicity $1$, and Proposition 1.4 tells us that $f$ can have no
more than $d$ complex roots, proving that $f$ has $d$ complex roots will
complete our proof.

Letting $D\subseteq[0,1]$ denote the set of $t\\!\in\\![0,1]$ such that
$Z_{t}\\!:=\\!\\{\zeta\\!\in\\!\mathbb{C}\;|\;G(t,\zeta)\\!=\\!0\\}$ has
cardinality $d$, it clearly suffices to prove $D\\!=\\![0,1]$. Toward this
end, we’ll first establish the following facts:
($P_{0}$) $D$ is non-empty. ($P_{1}$) $D$ is open. ($P_{2}$) $D$ is closed.

To prove ($P_{0}$), first note that $x^{d}-1$ has exactly $d$ roots: They are
$e^{2\pi\sqrt{-1}/d},\ldots,e^{2\pi(d-1)\sqrt{-1}/d}$,

thanks to Euler’s 1748 formula for the exponential function. The Implicit
FunctionTheorem applied to each of these roots then implies that there are a
positive $\varepsilon$, and analytic functions
$\mathcal{X}_{1},\ldots,\mathcal{X}_{d}:[0,\varepsilon]\longrightarrow\mathbb{C}$,
with
$\\{\mathcal{X}_{1}(0),\ldots,\mathcal{X}_{d}(0)\\}\\!=\\!\left\\{e^{2\pi\sqrt{-1}/d},\ldots,e^{2\pi(d-1)\sqrt{-1}/d}\right\\}$
and $G(t,\mathcal{X}_{i}(t))\\!=\\!0$ for all $t\\!\in\\![0,\varepsilon)$ and
$i\\!\in\\!\\{1,\ldots,d\\}$. Furthermore, since the $\mathcal{X}_{i}$
arecontinuous and $|\mathcal{X}_{i}(0)-\mathcal{X}_{j}(0)|\\!>\\!0$ for all
$i\\!\neq\\!j$, we can assume further that
$|\mathcal{X}_{i}(t)-\mathcal{X}_{j}(t)|\\!>\\!0$ for all $i\\!\neq\\!j$ and
$t\\!\in\\![0,\varepsilon^{\prime})$, for some positive
$\varepsilon^{\prime}\\!\leq\\!\varepsilon$. Since $Z_{t}$ has cardinality
$\leq\\!d$ for all $t$ (thanks to Proposition 1.4), we thus obtain that
$D\\!\supseteq\\![0,\varepsilon^{\prime})$. So ($P_{0}$) is proved, and we
refer to analytic functions $\mathcal{X}_{i}$ satisfying
$G(t,\mathcal{X}_{i}(t))$ for $t$ in some open interval as root branches. (So
the root paths we are trying to build are connected subsets of the graphs of
the root branches.)

The proof of Statement ($P_{1}$) follows the proof of Statement ($P_{0}$)
almost identically: If $Z_{t}$ has cardinality $d$ for some $t\\!\in\\![0,1]$,
then the Implicit Function Theorem applied to each of the
$\zeta\\!\in\\!Z_{t}$ yields $d$ root branches defined in an open neighborhood
$U\\!\ni\\!t$. By continuity again, we obtain that there is a non-empty open
set $U^{\prime}\\!\subseteq\\!U$, with $U^{\prime}\\!\ni\\!t$ as well, such
that the root paths do not intersect at any $t\\!\in\\!U^{\prime}$. So then
$U^{\prime}\\!\subseteq\\!D$ and ($P_{1}$) is proved.

To prove Statement ($P_{2}$) we first need to observe that
$|\phi_{0}|,\ldots,|\phi_{d}|$ are continuousfunctions on the compact set
$[0,1]$. So by the Extreme Value Theorem, there is apositive $M$ with
$|\phi_{0}(t)|,\ldots,|\phi_{d-1}(t)|\\!\leq\\!M$ for all $t\\!\in\\![0,1]$.
Furthermore, $\phi_{d}$ is nonzero on all of $[0,1]$ (by the definition of
$\Sigma_{d}$) and thus $|\phi_{d}|$ is a positive on $[0,1]$. So by the
Extreme Value Theorem once again, $|\phi_{d}|$ has a positive minimum $m$ on
$[0,1]$, and thus $\left|\frac{\phi_{i}(t)}{\phi_{d}(t)}\right|\\!\leq\\!M/m$
for all $i\\!\in\\!\\{0,\ldots,d-1\\}$ and $t\\!\in\\![0,1]$. By Lemma 1.6 we
thus obtain that
$\mathcal{I}:=\\{(t,\zeta)\\!\in\\![0,1]\times\mathbb{C}\;|\;G(t,\zeta)\\!=\\!0\\}$
is a bounded set. $\mathcal{I}$ is also closed since it is the intersection of
a closed (and bounded) rectangle with the zero set of a continuous function.

Suppose now that $t^{\prime}\\!\in\\![0,1]\setminus D$ is a limit point of
$D$. Then there are sequences
$\zeta^{(1)}_{1},\zeta^{(1)}_{2},\ldots\in\mathbb{C}$,
$\vdots$
$\zeta^{(d)}_{1},\zeta^{(d)}_{2},\ldots\in\mathbb{C}$,
and $t_{1},t_{2},t_{3},\ldots\in D$, such that
$\left\\{\zeta^{(1)}_{i},\ldots,\zeta^{(d)}_{i}\right\\}$ has cardinality $d$
for all $i\\!\in\\!\mathbb{N}$,
$G\\!\left(t_{i},\zeta^{(j)}_{i}\right)\\!=\\!0$ for all
$(i,j)\\!\in\\!\mathbb{N}\times\\{1,\ldots,d\\}$, and
$\lim\limits_{i\rightarrow\infty}t_{i}\\!=\\!t^{\prime}$.

We claim that the sequences of roots
$\left(\zeta^{(1)}_{i}\right)_{i\in\mathbb{N}},\ldots,\left(\zeta^{(d)}_{i}\right)_{i\in\mathbb{N}}$
always remain at a positive distance from each other. More precisely, we claim
that there is a $\delta$ with
$\left|\zeta^{(j)}_{i}-\zeta^{(j^{\prime})}_{i}\right|\\!\geq\\!\delta\\!>\\!0$
for all $j\\!\neq\\!j^{\prime}$ and $i\\!\in\\!\mathbb{N}$. For if not, then
there is a pair $(j,j^{\prime})$ with $j\\!\neq\\!j^{\prime}$ and a
subsequence $i_{1},i_{2},\ldots$ with
$\lim_{n\rightarrow\infty}\left|\zeta^{(j)}_{i_{n}}-\zeta^{(j^{\prime})}_{i_{n}}\right|\\!=\\!0$,
i.e., both $\zeta^{(j)}_{i_{n}}$ and $\zeta^{(j^{\prime})}_{i_{n}}$ tend to a
common limit $\zeta$. Since $G$ and $\frac{\partial G}{\partial x}$ are
continuous, we would then obtain $G(t^{\prime},\zeta)\\!=\\!0$ and

$\left.\frac{dG}{dx}\right|_{(t^{\prime},\zeta)}=\lim_{n\rightarrow\infty}\frac{G\left(t_{i_{n}},\zeta^{(j)}_{i_{n}}\right)-G\left(t_{i_{n}},\zeta^{(j^{\prime})}_{i_{n}}\right)}{\zeta^{(j)}_{i_{n}}-\zeta^{(j^{\prime})}_{i_{n}}}=\lim_{n\rightarrow\infty}\frac{0-0}{\zeta^{(j)}_{i_{n}}-\zeta^{(j^{\prime})}_{i_{n}}}=0.$

But then, this contradicts the fact that $\phi([0,1])$ avoids $\Sigma_{d}$. So
the sequences
$\left(\zeta^{(1)}_{i}\right)_{i\in\mathbb{N}},\ldots,$$\left(\zeta^{(d)}_{i}\right)_{i\in\mathbb{N}}$
are indeed separated by some positive $\delta$.

By this separation, and from the fact that $\mathcal{I}$ is closed and
bounded, we then obtain that each sequence
$\left(\zeta^{(j)}_{i}\right)_{i\in\mathbb{N}}$ has a limit point
$\zeta^{(j)}$, and these limit points are all separated by a distance at least
$\delta$ from each other. In particular, again using the continuity of $G$, we
obtain $G\\!\left(t^{\prime},\zeta^{(j)}\right)\\!=\\!0$ for all
$j\\!\in\\!\\{1,\ldots,d\\}$. So $Z_{t^{\prime}}$ has cardinality $\geq\\!d$
and thus, by Proposition 1.4 again, $t^{\prime}\\!\in\\!D$. So we at last have
Statement ($P_{2}$).

To conclude, note that we must have $D\\!=\\![0,1]$ since $[0,1]$ is
connected, and $D$ being non-empty, open, and closed implies that $D$ must be
a connected component of $[0,1]$. $\blacksquare$

###  2.2 The Case $f\in\Sigma_{d}$

First note that we may assume $\gamma_{d}\\!\neq\\!0$, for otherwise we could
simply decrease $d$ and reduce to a lower degree case.

Now let $L(t,x)\\!:=\\!(1-t)(\gamma_{d}x^{d}-\gamma_{d})+tf(x)$ and observe
that the coefficient of $x^{d}$ in $L(t,x)$ is exactly $\gamma_{d}\\!\neq\\!0$
for all $t\\!\in\\!\mathbb{C}$. So the roots of $L(0,x)$ are the roots of
unity, $L(1,x)\\!=\\!f(x)$, and $L(t,x)$ has degree $d$ in $x$ for all
$t\\!\in\\![0,1]$. Furthermore, since $x^{d}-1\not\in\Sigma_{d}$ (as already
observed in our last case), $\Delta_{d}(L(t,x))$ is a polynomial of positive
degree $\leq\\!2d-1$ in $t$. So, by restricting $L(t,\cdot)$ to
$[\varepsilon,1]$ for some suitable $\varepsilon\\!\geq\\!0$ and rescaling
$t$, we can build an analytic path
$\psi\\!=\\!(\psi_{0},\ldots,\psi_{d}):[0,1]\longrightarrow\mathbb{C}^{d+1}$
with $\psi(0)\\!=\\!g$ for some
$g\\!\in\\!\mathbb{C}^{d+1}\setminus\Sigma_{d}$ and only intersecting
$\Sigma_{d}$ at $\psi(1)\\!=\\!f$. We will use $\psi$ to build root paths that
prove that $f$ has at least one root in $\mathbb{C}$ and then conclude by long
division.

More precisely, similar to our last case, let
$H(t,x)\\!:=\\!\psi_{0}(t)+\cdots+\psi_{d}(t)\zeta^{d}$
$W_{t}\\!:=\\!\\{\zeta\\!\in\\!\mathbb{C}\;|\;H(t,\zeta)\\!=\\!0\\}$
$\mathcal{J}:=\\{(t,\zeta)\\!\in\\![0,1]\times\mathbb{C}\;|\;H(t,\zeta)\\!=\\!0\\}$.
Thanks to the framework of the $f\not\in\Sigma_{d}$ case (which we’ve already
proved), it is clear that $H$ is analytic,
$\mathcal{J}\setminus(\\{1\\}\times\mathbb{C})$ is a disjoint union of $d$
real analytic curves, and $\mathcal{J}$ is closed and bounded. In particular,
these curves induce (possibly overlapping) limit points
$(1,\rho_{1}),\ldots,(1,\rho_{d})$. Furthermore, since $H$ is continuous, $f$
must vanish at each $\rho_{i}$. So $f$ has at least one root
$\rho\\!\in\\!\mathbb{C}$ and, letting $\mu$ ($\geq\\!1$) denote the
multiplicity of $\rho$, it suffices to prove that
$\frac{f(x)}{(x-\rho)^{\mu}}$ has exactly $d-\mu$ roots in $\mathbb{C}$
counting multiplicities. So by induction, we are done. $\blacksquare$

##  3 Consequences for Intersection Multiplicity and
Resultants

We first point out that the preceding proof yields a geometric definition of
intersection multiplicity: For a degenerate root $\rho\\!\in\\!\mathbb{C}$ of
$f$, following the notation of the last section, we can define the
intersection multiplicity of a root $\rho$ to be the number of paths of
$\mathcal{J}$ ending at $(1,\rho)$, i.e., the number of $\rho_{i}$ equal to
$\rho$. With just a little more work (see, e.g., [BCSS98, Ch. 10]), we can
show that this definition makes sense, i.e., our definition is independent of
how we build a path of polynomials in $\mathbb{C}^{d+1}\setminus\Sigma_{d}$
tending to $f$. It turns out that this definition of intersection multiplicity
generalizes easily to higher-dimensions, e.g., Bézout’s Theorem (see [BCSS98,
Sec. 10.5] for the details).

A useful consequence of the Fundamental Theorem of Algebra is the following
inverse of the implication from Lemma 1.3:

###### Lemma 3.1

Following the notation of Lemma 1.3, assume instead that
$\mathrm{Res}_{d,e}(f,g)\\!=\\!0$ and $a_{d}b_{e}\\!\neq\\!0$. Then there is a
$\zeta\\!\in\\!\mathbb{C}$ with $f(\zeta)\\!=\\!g(\zeta)\\!=\\!0$.

We prove Lemma 3.1 in the Appendix.

##  4 A Root Approximation Algorithm from our Proof

Given any $f\\!\in\\!\mathbb{C}[x]$, consider the function
$H(t,x)\\!:=\\!(1-t)(x^{d}-1)+tf(x)$. Let $N$ be a large integer to be
specified later, and consider the following iteration: Define
$z^{(1)}_{0},\ldots,z^{(d)}_{0}$ to be the $d^{\text{\text@underline{th}}}$
roots of unity, and then set

$z^{(j)}_{n+1}:=z^{(j)}_{n}-\left(\left.\frac{\partial H}{\partial
x}\right|_{\left(\frac{n+1}{N},z^{(j)}_{n}\right)}\right)^{-1}H\\!\left(\frac{n+1}{N},z^{(j)}_{n}\right)$

for all $j\\!\in\\!\\{1,\ldots,d\\}$ and $n\\!\in\\!\\{0,\ldots,N-1\\}$. This
is the most basic homotopy continuation method for approximating the roots of
$f$: Under certain reasonably enforceable conditions,
$z^{(1)}_{N},\ldots,z^{(d)}_{N}$ are high-precision approximations to all the
roots of $f$.

The key trick behind this method is that the sequences
$\left(H\\!\left(\frac{n}{N},x\right),z^{(1)}_{n}\right)_{n\in\mathbb{N}},\ldots,\left(H\\!\left(\frac{n}{N},x\right),z^{(d)}_{n}\right)_{n\in\mathbb{N}}$
respectively yield discrete approximations to pieces of the incidence variety
$\mathcal{J}\\!:=\\!\left\\{(c_{0},\ldots,c_{d},\zeta)\\!\in\\!\mathbb{C}^{d+1}\times\mathbb{C}\;|\;c_{0}+\cdots+c_{d}\zeta^{d}\\!=\\!0\right\\}$.
In particular, the incidence variety consists of all pairs consisting of a
polynomial and its roots, and we are trying to recover a point on
$\mathcal{J}$ from its projection onto the first factor: the coefficient space
$\mathbb{C}^{d+1}$. The preceding iteration takes $d$ (easily obtainable)
points on $\mathcal{J}$ and then applies Newton’s method (to deformations of
$f$) to follow the $d$ curves leading to the (hard to find) pairs
$(f,\zeta_{1}),\ldots,(f,\zeta_{d})$ where
$\left\\{\zeta^{(1)},\ldots,\zeta^{(d)}\right\\}$ is the multi-set of roots of
$f$ (appearing with appropriate multiplicity).

If by luck we have that the line segment
$\mathcal{L}:=\left\\{(1-t)(x^{d}-1)+tf(x)\right\\}_{t\in[0,1]}$ does not
intersect $\Sigma_{d}$, and $N$ is sufficiently large, then one can in fact
guarantee that the underlying Newton iterations are all well-defined and that
the points $z^{(1)}_{N},\ldots,z^{(d)}_{N}$ are approximate roots of $f$ in
the sense of Smale. One should of course not rely on luck. However, the
assumption that $\mathcal{L}$ does not intersect $\Sigma_{d}$ actually holds
with probability $1$ for many natural probability measures on the space of
coefficients $\mathbb{C}^{d+1}$. And, in the event that $\mathcal{L}$
intersects $\Sigma_{d}$, there are well-known strategies to modify the
underlying path and iteration.

As for the size of the paramter $N$, there is a rigorous notion of approximate
root (due to Smale [Sma81]) that gives a practical sufficient condition for an
approximation $z^{(j)}_{N}$ to be efficiently refinable (to arbitrarily small
distance from a true root) via Newton’s method applied directly to
$\left(f,z^{(j)}_{N}\right)$. Four seminal references on analyzing how large
$N$ should be are [SS94, BCSS98, BP09, Lai17].

This approach to numerical solving has a transparent generalization to systems
of multivariate polynomial equations (see, e.g., [SW05]), and has already been
implemented and proven quite valuable. An excellent example is the package
Bertini, which is freely downloadable after a simple google search. Homotopy
methods thus possess a certain conceptual beauty, and making them faster and
fully reliable leads to many active research problems in (numerical) algebraic
geometry.

## Appendix: Proving the Equivalence of Vanishing
Discriminants and the Presence of Degenerate Roots

Collecting powers of $x$, it is easy to prove the following proposition, which
we’ll use below:

###### Proposition 4.1

For any $d,e\\!\geq\\!1$, and complex constants $\alpha_{i}$, $\beta_{i}$,
$\gamma_{i}$, and $u_{i}$, we have that the matrix product identity
$[\alpha_{0},\ldots,\alpha_{e-1},\beta_{0},\ldots,\beta_{d-1}]\mathrm{Syl}_{d,e}(f,g)\\!=\\![u_{0},\ldots,u_{d+e-1}]$
holds if and only if the polynomial identity
$(\alpha_{0}+\cdots+\alpha_{e-1}x^{e-1})f+(\beta_{0}+\cdots+\beta_{d-1}x^{d-1})g(x)=u_{0}+\cdots+u_{d+e-1}x^{d+e-1}$
holds. $\blacksquare$

### The Proof of Lemma 1.3

If $d\\!=\\!e\\!=\\!1$ then the resultant not vanishing is equivalent to the
vectors $[a_{0},a_{1}]$ and $[b_{0},b_{1}]$ being linearly independent. So it
is clear that $f\\!=\\!g\\!=\\!0$ can have no complex solutions. So let us
assume, swapping $f$ and $g$ if necessary, that $d\\!\geq\\!2$.

Then $\mathrm{Res}_{d,e}(f,g)\\!\neq\\!0$ implies that
$\det\mathrm{Syl}_{d,e}(f,g)\\!\neq\\!0$, and thus the linear system
$[r_{0},\ldots,r_{e-1},s_{0},\ldots,s_{d-1}]\mathrm{Syl}_{d,e}(f,g)\\!=\\![1,0,\ldots,0]$
has a unique solution.

By Proposition 4.1 we then have that
$(r_{0}+\cdots+r_{e-1}x^{e-1})f(x)+(s_{0}+\cdots+s_{d-1}x^{d-1})g(x)\\!=\\!1$
identically. This implies, in particular, that $f$ and $g$ can have no complex
roots in common: Evaluating our last polynomial linear combination at such a
root would imply that $0\\!=\\!1$ — a contradiction. So we obtain the main
assertion.

The consequence for $\Delta_{d}$ follows immediately upon setting
$g\\!=\\!f^{\prime}$ and observing that any root $\zeta\\!\in\\!\mathbb{C}$ of
$f$ with $f^{\prime}(\zeta)\\!\neq\\!0$ is a root of multiplicity $1$, thanks
to Proposition 1.1. $\blacksquare$

### The Proof of Lemma 3.1

Under the stated hypotheses, $\det\mathrm{Res}_{d,e}(f,g)\\!=\\!0$. So
Proposition 4.1 implies that there must be polynomials
$r,s\\!\in\\!\mathbb{C}[x]$, at least one of which is not identically $0$,
with degrees respectively bounded from above by $e-1$ and $d-1$, satisfying
$rf+sg\\!=\\!0$ identically. In particular, the factorizations of $rf$ and
$-sg$ must be identical. Note also that if $s$ is identically $0$ then $f$
must be identically $0$, and we trivially have that $f$ vanishes at all the
roots of $g$. (And $g$ has at least $1$ complex root, thanks to the
Fundamental Theorem of Algebra.) So we may assume that both $r$ and $s$ are
not identically $0$.

By the Fundamental Theorem of Algebra, $f$ has exactly $d$ degree $1$ factors
(counting multiplicity) since $a_{d}\\!\neq\\!0$. Since $s$ has no more than
$d-1$ linear factors, $f$ and $g$ must have a degree $1$ factor in common. So
we are done. $\blacksquare$

## References

  * [AKNR18] Martín Avendaño; Roman Kogan; Mounir Nisse; and J. Maurice Rojas, “Metric Estimates and Membership Complexity for Archimedean Amoebae and Tropical Hypersurfaces,” presented at MEGA 2013. Published in Journal of Complexity, Vol. 46, June 2018, pp. 45–65.
  * [BP09] Carlos Beltrán and Luis Miguel Pardo, “Smale’s 17th problem: average polynomial time to compute affine and projective solutions,” J. Amer. Math. Soc. 22 (2009), no. 2, pp. 363–385.
  * [BCSS98] Lenore Blum; Felipe Cucker; Mike Shub; and Steve Smale, Complexity and Real Computation, Springer-Verlag, 1998.
  * [Fuj16] M. Fujiwara, “Über die obere Schranke des absoluten Betrags der Wurzeln einer algebraischen Gleichung,” Tôhoku Mathematical Journal, 10, pp. 167–171, 1916.
  * [Hub15] John Hubbard and Barbara Burke Hubbard, Vector Calculus, Linear Algebra, and Differential Forms: A Unified Approach, Matrix Editions, 2015.
  * [Lai17] Pierre Lairez, “A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time,” Found. Comput. Math. 17 (2017), no. 5, pp. 1265–1292.
  * [Mun00] James R. Munkres, Topology, 2nd edition, Pearson, 2000.
  * [RS02] Q. I. Rahman and G. Schmeisser, Analytic Theory of Polynomials, London Mathematical Society Monographs 26, Oxford Science Publications, 2002.
  * [SS94] Mike Shub and Steve Smale, “Complexity of Bezout’s theorem V – Polynomial time,” Theoretical Computer Science, vol. 133, no. 1, pp. 141–164, 1994.
  * [SW05] Andrew J. Sommese and Charles W. Wampler, “The Numerical Solution to Systems of Polynomials Arising in Engineering and Science,” World Scientific, Singapore, 2005.
  * [Sma81] Steve Smale, “The fundamental theorem of algebra and complexity theory,” Bull. Amer. Math. Soc. (N.S.) Volume 4, Number 1 (1981), pp. 1–36.