# RapidLayout: Fast Hard Block Placement
of FPGA-optimized Systolic Arrays
using Evolutionary Algorithms

Niansong Zhang  Sun Yat-sen University
Guangzhou, China
<EMAIL_ADDRESS>Xiang Chen  Sun Yat-sen University
Guangzhou, China
<EMAIL_ADDRESS>Nachiket Kapre  University of Waterloo
Ontario, Canada
<EMAIL_ADDRESS>
###### Abstract

Evolutionary algorithms can outperform conventional placement algorithms such
as simulated annealing, analytical placement as well as manual placement on
metrics such as runtime, wirelength, pipelining cost, and clock frequency when
mapping FPGA hard block intensive designs such as systolic arrays on Xilinx
UltraScale+ FPGAs. For certain hard-block intensive, systolic array
accelerator designs, the commercial-grade Xilinx Vivado CAD tool is unable to
provide a legal routing solution without tedious manual placement constraints.
Instead, we formulate an automatic FPGA placement algorithm for these hard
blocks as a multi-objective optimization problem that targets wirelength
squared and maximum bounding box size metrics. We build an end-to-end
placement and routing flow called RapidLayout using the Xilinx RapidWright
framework. RapidLayout runs 5–6$\times$ faster than Vivado with manual
constraints and eliminates the weeks-long effort to generate placement
constraints manually for the hard blocks. We also perform automated post-
placement pipelining of the long wires inside each convolution block to target
650 MHz URAM-limited operation. RapidLayout outperforms (1) the simulated
annealer in VPR by 33% in runtime, 1.9–2.4$\times$ in wirelength, and
3–4$\times$ in bounding box size, while also (2) beating the analytical placer
UTPlaceF by 9.3$\times$ in runtime, 1.8–2.2$\times$ in wirelength, and
2–2.7$\times$ in bounding box size. We employ transfer learning from a base
FPGA device to speed-up placement optimization for similar FPGA devices in the
UltraScale+ family by 11–14$\times$ than learning the placements from scratch.

##  I Introduction

Modern high-end FPGAs provide high compute density with a heterogeneous
mixture of millions of classic lookup tables and programmable routing network
along with tens of thousands of DSP and RAM hard blocks. These hard blocks
offer ASIC-like density and performance for signal processing functions and
on-chip SRAM access. For example, Xilinx UltraScale+ VU11P is equipped with
960 UltraRAM blocks, 4032 Block RAM slices, and 9216 DSP48 blocks capable of
operating at 650–891 MHz frequencies which are typically unheard of with LUT-
only designs. Furthermore, these hard blocks provide specialized nearest-
neighbour interconnect for high-bandwidth, low-latency cascade data movement.
These features make it particularly attractive for building systolic neural
network accelerators such as CLP [29, 28], Cascades [27], and Xilinx SuperTile
[35, 34].

Exploiting the full capacity of FPGA resources including hard blocks at high
clock frequency is challenging. The CLP designs presented in [29, 28] only
operate at 100–170 MHz on Virtex-7 FPGAs but leave DSPs unused. The Xilinx
SuperTile [35, 34] designs run at 720 MHz, but leave half of the DSPs unused,
and also waste URAM bandwidth by limiting access. The chip-spanning 650 MHz
1920$\times$9 systolic array design for the VU11P FPGA [27] requires 95% or
more of the hard block resources but fails to route in commercial-grade Xilinx
Vivado run with high effort due to congestion. Manual placement constraints
are necessary to enable successful bitstream generation, but this requires
weeks of painful trial-and-error effort and visual cues in the Vivado
floorplanner for the correct setup. This effort is needed largely due to
irregularity and asymmetry of the columnar DSP and RAM fabric and the complex
cascade constraints that must be obeyed for the systolic data movement
architecture. Once the constraints are configured, Vivado still needs 5–6
hours of compilation time, making design iteration long and inefficient.
Furthermore, to ensure high-frequency operation, it becomes necessary to
pipeline long wires in the design. Since timing analysis must be done post-
implementation, we end up either suffering the long CAD iteration cycles or
overprovisioning unnecessary pipelining registers to avoid the long design
times.

Given this state of affairs with the existing tools, we develop RapidLayout:
an alternative, automated, fast placement approach for hard block designs. It
is important that such a toolflow addresses the shortcomings of the manual
approach by (1) discovering correct placements quickly without the manual
trial-and-error loop through slow Vivado invocations, (2) encoding the complex
placement restrictions of the data movement within the systolic architecture
in the automated algorithm, (3) providing fast wirelength estimation to permit
rapid objective function evaluation of candidate solutions, and (4) exploiting
design symmetry and overcoming irregularity of the columnar FPGA hard block
architecture. Given this wish list, we used the Xilinx RapidWright framework
for our tool.

At its core, the toolflow is organized around the design of a novel
evolutionary algorithm formulation for hard block placement on the FPGA
through multi-objective optimization of wirelength squared and bounding box
metrics. Given the rapid progress in machine learning tools, there is an
opportunity to revisit conventional CAD algorithms [5], including those in
this paper, and attack them with this new toolbox.

The key contributions of this work are listed as follows:

  * $\bullet$

We formulate a novel FPGA placement problem for tens of thousands of hard
blocks as a multi-objective optimization using evolutionary techniques.

  * $\bullet$

We quantify QoR metrics including runtime, wirelength, bounding box size,
clock frequency, and pipelining cost for the evolutionary placement algorithms
NSGA-II and CMA-ES. We compare these metrics against conventional Simulated
Annealing (SA), Genetic Algorithm (GA), Versatile-Place-and-Route (VPR) [22],
and the state-of-art analytical placer UTPlaceF [19].

  * $\bullet$

We build an end-to-end RapidLayout placement-and-routing toolflow using the
open-source Xilinx RapidWright framework.

  * $\bullet$

We develop the transfer learning process for hard block placement to
accelerate placement optimization through migrating existing placement from
base devices to similar devices in the UltraScale+ family (VU3P–VU13P).

##  II Background

We first discuss the hard block intensive systolic array accelerator optimized
for the Xilinx UltraScale+ FPGAs. Next, we discuss the Xilinx RapidWright
framework for programming FPGAs through a non-RTL design flow. Then, we
describe previous research on FPGA placement algorithms. Finally, we review
the classic NSGA-II algorithm and the state-of-art CMA-ES algorithm and
compare them with previous evolutionary placement efforts.

###  II-A FPGA-optimized Systolic Array Accelerator

Figure 1: Convolutional Building Block for FPGA-Optimized Systolic Array in
[27]. Cascade URAM, BRAM, and DSP links are highlighted in bold.

Systolic arrays [14, 16] are tailor-made for convolution and matrix operations
needed for neural network acceleration. They are constructed to support
extensive data reuse through nearest-neighbor wiring between a simple 2D array
of multiply-accumulate blocks. They are particularly amenable to
implementation on the Xilinx UltraScale+ architecture with cascade nearest-
neighbor connections between DSP, BRAM, and URAM hard blocks. We utilize the
systolic convolutional neural network accelerator presented in [27] and
illustrated in Figure 1. The key repeating computational block is a
convolution engine optimized for the commonly-used 3$\times$3 convolution
operation. This is implemented across a chain of 9 DSP48 blocks by cascading
the accumulators. Furthermore, row reuse is supported by cascading three BRAMs
to supply data to a set of three DSP48s each. Finally, the URAMs are cascaded
to exploit all-to-all reuse between the input and output channels in one
neural network layer. Overall, when replicated to span the entire FPGA, this
architecture uses 95–100% of the DSP, BRAM, and URAM resources of the high-end
UltraScale+ VU37P device. When mapped directly using Vivado without any
placement constraints, the router runs out of wiring capacity to fit the
connections between these blocks. Since the convolution block is replicated
multiple times to generate the complete accelerator, it may appear that
placement should be straightforward. However, due to irregular interleaving of
the hard block columns, and the non-uniform distribution of resources, the
placement required to fit the design is quite tedious and takes weeks of
effort.

###  II-B RapidWright

In this paper, we develop our tool based on the Xilinx RapidWright [17] open-
source FPGA framework. It aims to improve FPGA designers’ productivity and
design QoR (quality of result) by composing large FPGA designs through a pre-
implemented and modular methodology. RapidWright provides high-level Java API
access to low-level Xilinx device resources. It supports design generation,
placement, routing, and allows design checkpoint (DCP) integration for
seamless inter-operability with Xilinx Vivado CAD tool to support custom
flows. It also provides access to device geometry information that enables
wirelength calculations crucial for tools that aim to optimize timing.

###  II-C FPGA Placement

FPGA placement maps a clustered logical circuit to an array of fixed physical
components to optimize routing area, critical path, power efficiency, and
other metrics. FPGA placement algorithms can be broadly classified into four
categories: (1) classic min-cut partitioning [31, 23, 24], (2) popular
simulated-annealing-based methods [15, 3, 2, 22], (3) analytical placement
currently used in FPGA CAD tools [1, 9, 19, 8], and (4) esoteric evolutionary
approaches [32, 4, 13]. Min-cut algorithm worked well on small FPGA capacities
by iteratively partitioning the circuit to spread the cells across the device.
Simulated Annealing was the popular choice for placement until recently. It
operates by randomly swapping clusters in an iterative, temperature-controlled
fashion resulting in progressively higher quality results. Analytical placers
are currently industry standard as they solve the placement problem using a
linear algebraic approach that delivers higher quality solutions with less
time than annealing. For example, Vivado uses an analytical placement to
optimize timing, congestion, and wirelength [8].

###  II-D Evolutionary Algorithms

There have been several attempts to deploy evolutionary algorithms for FPGA
placement with limited success. The earliest one by Venkatraman and Patnaik
[32] encodes each two-dimensional block location in a gene and evaluates the
population with a fitness function for critical path and area-efficiency. More
recently, P. Jamieson [11], [12] points out that GAs for FPGA placement are
inferior to annealing mainly due to the crossover operator’s weakness and
proposed a clustering technique called supergenes [13] to improve its
performance.

In this paper, we design a novel combinational gene representation for FPGA
hard block placement and explore two evolutionary algorithms:

  * 1.

NSGA-II: Non-Dominated Sorting Genetic Algorithm (NSGA-II [6]) is a two-
decade-old multi-objective evolutionary algorithm that has grown in popularity
today for Deep Reinforcement Learning [18] and Neural Architecture Search [20]
applications. NSGA-II addresses multi-objective selection with non-dominated
filtering and crowd distance sorting, which allow the algorithm to effectively
explore the solution space and preserve good candidates.

  * 2.

CMA-ES: Covariance Matrix Adaptation Evolutionary Strategy (CMA-ES) is a
continuous domain optimization algorithm for non-linear, ill-conditioned,
black-box problems [10]. CMA-ES models candidate solutions as samplings of an
$n$-dimensional Gaussian variable with mean $\mathbf{\mu}$ and covariance
matrix $\mathbf{C_{\sigma}}$. At each evolutionary iteration, the population
is generated by sampling from $\mathbb{R}^{n}$ with updated mean and
covariance matrix. Here, crossover and mutation become adding Gaussian noise
to the samplings, which overcomes the weakness of GA’s crossover operator. We
use the high-dimensional variant proposed in [26] for fast operation in our
placement challenge.

Hard Block Placement GenotypeDistributionLocationMapping

(a) distribution

(b) location (c) mapping

Figure 2: Our three-tier genotype design for hard block placement. (a)
Distribution defines the amount of hard blocks to be placed in each column.
(b) Location encodes the relative position of the corresponding hard blocks in
its column. (c) Mapping defines the connectivity of hard blocks, i.e., which
hard blocks are mapped to one convolution unit. The selected physical hard-
block groups are numbered, which corresponds to the mapping genotype.

##  III RapidLayout

The challenge for mapping FPGA-optimized systolic arrays to the Xilinx
UltraScale+ device is the placement of hard blocks to their non-uniform,
irregular, columnar locations on the fabric while obeying the cascade data
movement constraints. We first present our problem formulation and then
discuss how to embed it into the evolutionary algorithms.

###  III-A Problem Formulation

To tackle the placement challenge, we formulate the coarse-grained placement
of RAMs and DSP blocks as a constrained multi-objective optimization problem.
The placement for the rest of the logic _i.e._ lookup tables (LUTs) and flip-
flops (FFs) is left to Vivado’s placer. The multi-objective optimization goal
is formalized as follows.

$min\sum_{i,j}((\Delta{x_{i,j}}+\Delta{y_{i,j}})\cdot w_{i,j})^{2}$ (1)

$\min(\max_{k}BBoxSize(C_{k}))$ (2)

subject to:

$0\leq x_{i},y_{i}<XMAX,YMAX$ (3)

${x_{i},y_{i}}\neq{x_{j},y_{j}}$ (4)

$\displaystyle\textrm{if }i\textrm{ is cascaded after }j\textrm{ in the same
column: }x_{i}=x_{j}$ (5) $\displaystyle
y_{i}=\begin{cases}y_{j}+1&i,j\in\\{DSP,URAM\\}\\\
y_{j}+2&i,j\in\\{RAMB\\}\end{cases}$

In the equations above:

  * $\bullet$

$i\in\\{DSP,RAM,URAM\\}$ denotes a physical hard block to which a logic block
is mapped.

  * $\bullet$

$C_{k}$ denotes a convolution unit $k$ that contains 2 URAMs, 18 DSPs, and 8
BRAMs.

  * $\bullet$

$\Delta{x_{i,j}}+\Delta{y_{i,j}}$ is the Manhattan distance between two
physical hard blocks $i$ and $j$.

  * $\bullet$

$w_{i,j}$ is the weight for wirelength estimation. Here we use the number of
connections between hard blocks $i$ and $j$.

  * $\bullet$

$BBoxSize()$ is the bounding box rectangle size (width + height) containing
the hard blocks of a convolution unit $C_{k}$.

  * $\bullet$

$x_{i}$ and $y_{i}$ denote the RPM absolute grid co-ordinates of hard block
$i$ that are needed to compute wirelength and bounding box sizes [36].

Understanding the Objective Function: We approximate routing congestion
performance with squared wirelength (Equation 1) and critical path length with
the maximum bounding box size (Equation 2). These twin objectives try to
reduce pipelining requirements while maximizing clock frequency of operation.
While these optimization targets may seem odd, we have observed cases where
chasing wirelength2 alone has misled the optimizer into generating wide
bounding boxes for a few stray convolution blocks. In contrast, optimizing for
maximum bounding box alone was observed to be extremely unstable and causing
convergence problems. Hence, we choose these two objective functions to
restrict the spread of programmable fabric routing resources and reduce the
length of critical path between hard blocks and associated control logic
fanout.

Understanding Constraints The optimizer only needs to obey three constraints.
The region constraint in Equation 3 restricts the set of legal locations for
the hard blocks to a particular repeatable rectangular region of size
XMAX$\times$YMAX on the FPGA. The exclusivity constraint in Equation 4 forces
the optimizer to prevent multiple hard blocks from being assigned to the same
physical location. The cascade constraint in Equation 5 is the “uphill”
connectivity restriction imposed due to the nature of the Xilinx UltraScale+
DSP, BRAM, and URAM cascades. For DSPs and URAMs, it is sufficient to place
connected blocks next to each other. For BRAMs, the adjacent block of the same
type resides at one block away from the current location. This is because
RAMB180 and RAMB181, which are both RAMB18 blocks, are interleaved in the same
column.

####  III-A1 Genotype Design for Evolutionary Algorithms

We decompose placement into three sub-problems and encode the candidate
solutions with a novel composite genotype design.

  * 1.

Distribution Since the systolic array accelerator does not match the hard
block resource capacity perfectly, we allocate hard blocks across resource
columns according to the distribution genotype.

  * 2.

Location Once we choose the exact number of blocks to place on a given
resource column, we assign each block in the column a location according to a
value between 0 $\rightarrow$ 1.

  * 3.

Mapping Finally, we label selected blocks and allocate them to each
convolution unit according to the mapping genotype. It is a permutation
genotype that optimizes the order of elements without changing their values.

In Figure 2, we visualize the genotype design which consists of the three
parts just discussed earlier. During evolution, each part of the genotype is
updated and decoded independently, but evaluated together.

####  III-A2 Generality of the Evolutionary Formulation

The problem formulation and genotype design are motivated by a convolutional
systolic array. However, the placement formulation is not limited to any
particular hard block design. For example, the computing unit $C_{k}$
(Equation 2) can be any hard block design, as long as the number of hard
blocks, their connections, and cascade information are provided.

####  III-A3 Comparison with Prior Evolutionary Placements

Our genotype design differs from prior works in three aspects: (1) We provide
placement support for heterogeneous hard block types. (2) We encode cascade
constriants into the genotype, which eschews extra legalization steps and
reduces search space. (3) The three-tier gentoype design enables placement
transfer learning across devices (Section IV-D).

###  III-B RapidLayout Design Flow

We now describe the end-to-end RapidLayout design flow:

Convolution Block DCP Netlist Replication [<1s] A Evolutionary Hard Block
Placement [30 s–5 min] B Placement and Site Routing [$\approx$3 min] C Post-
Placement Pipelining [$\approx$10 s] D SLR Placement and Routing [$\approx$55
min] E SLR Replication [$\approx$2 min] F Compute objective Generate
candidates Update RapidWrightVivado Bitstream evolve Figure 3: RapidLayout
Design Flow with runtime details for the Xilinx VU11P FPGA along with tool
usage information. Bulk of the intelligent exploration is done in RapidWright,
and Vivado is only invoked at the end for final placement and routing.

  * $\bullet$

Netlist Replication (<1 s) RapidLayout starts with a synthesized netlist of
the convolution unit with direct instantiations of the FPGA hard blocks. The
unit design is replicated into the entire logical netlist that maps to the
whole Super Logic Region (SLR).

  * $\bullet$

Evolutionary Hard Block Placement (30 s-5min)  RapidLayout uses NSGA-II or
CMA-ES to generate hard block placement for the minimum repeating rectangular
region. Then the rectangular layout is replicated (copy-paste) to produce the
placement solution for the entire SLR.

  * $\bullet$

Placement and Site Routing ($\approx$3 min)  The placement information is
embedded in the DCP netlist by placing the hard blocks on the physical blocks
called “sites”, followed by “site-routing” to connect intra-site pins.

  * $\bullet$

Post-Placement Pipelining ($\approx$10 s)  After finalizing placement, we can
compute the wirelength for each net in the design and determine the amount of
pipelining required for high-frequency operation. This is done post-placement
[33, 7, 30] to ensure the correct nets are pipelined and to the right extent.
The objective of this step is to aim for the 650 MHz URAM-limited operation as
dictated by the architectural constraints of the systolic array [27].

  * $\bullet$

SLR Placement and Routing ($\approx$55 min)  Once the hard blocks are placed
and pipelined, we call Vivado to complete LUT/FF placement and routing for the
SLR.

  * $\bullet$

SLR Replication (1-5 min)  The routed design on the SLR is copied across the
entire device using RapidWright APIs to complete the overall implementation.

For VU11P device, RapidLayout accelerates the end-to-end implementation by
$\approx$5–6$\times$ when measuring CAD runtime alone ($\approx$one hour vs.
Vivado’s 5–6 hours). This does not include the weeks of manual tuning effort
that is avoided by automatically discovering the best placement for the
design.

###  III-C Example Walkthrough

To illustrate how the different steps help produce the full-chip layout, we
walk you through the intermediate stages of the flow. We will inspect three
stages of placement, going from a single block layout to a repeating rectangle
layout, and then onto a full-chip layout.

Single Block layout: The floorplan of a single convolution block in isolation
is shown in Figure 4, where the hard block columns and chosen resources are
highlighted. We also highlight the extent of routing requirements between the
hard blocks in gray. The locations of the URAM, BRAM, and DSP columns are
irregular, which forces a particular arrangement and selection of resources to
minimize wirelength and bounding box size. It is clear that a simple copy-
paste of a single block is not workable due to this irregularity.

Single Repeating Rectangle Layout: RapidLayout iteratively partitions one SLR
and calculates utilizaiton until the divided section does not fit any unit.
Then, the partition scheme with the highest utilization rate is selected to
determine the repeating rectangular region. In Figure 5, we show the floorplan
for such a region. The resource utilization within the rectangle is 100%
URAMs, 93.7% DSP48s, and 95.2% BRAMs, which holds for the entire chip after
replication. Our optimizer minimizes overlapping and thus reducing routing
congestions to permit high-frequency operation.

Full-Chip Layout: The entire chip layout is generated in two steps: (1) First,
the rectangular region’s placement is replicated to fill up one SLR (SLR0).
The SLR is then pipelined and fully routed. (2) Second, the placement and
routing from SLR0’s implementation are replicated across the two other SLRs to
fill up the FPGA.

Figure 4: Floorplan layout visualization of a single convolution block
implementation supporting dual 3$\times$3 kernels to match URAM bandwidth.
This is the design shown in Figure 1 earlier. The bounding polygon that
encloses all hard blocks and the routing connections is shown in gray. Figure
5: Floorplan layout visualization of a single repeating rectangular region
layout with 80 convolution blocks. The bounding polygon from Figure 4 is also
shown here for scale. SLR0Repeating Rect. (Fig 5)SLR1SLR2Copy Placements +
Vivado P+RCopy Placement + Routingin RapidWrightFCDE Figure 6: Full-chip
layout for the systolic array accelerator generated from a repeating rectangle
of size two clock regions high and the full chip wide. After one replication
we span one SLR region. We place and route this with Vivado, export DCP,
reimport into RapidWright to clone across SLRs.

(a) Wirelength, Bounding Box vs. Runtime Comparison

(b) Effect of Convergence on Wirelength, Bounding Box

Figure 7: Performance, Wirelength, and Bounding Box Comparison: SA, NSGA-II,
NSGA-II (Red), and CMA-ES  TABLE I: Runtime(avg), Wirelength(avg), Max
BBox(avg), Pipelining Registers(min), and Frequency(avg) for all methods.
NSGA-II shows reduced genotype as well. Speeups and QoR improvements wins by
Evolutionary algorithms also reported in red$\rightarrow$NSGA-II and
green$\rightarrow$CMA-ES for each competitor algorithm (SA, GA, UTPlaceF, VPR,
Manual).

Method NSGA-II CMA-ES SA GA VPR UTPlaceF Manual Runtime (secs) 586 (323) 51
1577 (2.7$\times$, 30.8$\times$) 850 (1.5$\times$, 16.7$\times$) 76
(0.13$\times$, 1.5$\times$) 473 (0.8$\times$, 9.3$\times$) 1–2 wks Wirelength
3.5K (3.5K) 4.4K 3.1K (0.9$\times$, 0.7$\times$) 9.2K (2.6$\times$,
2.1$\times$) 8.5K (2.4$\times$, 1.9$\times$) 7.8K (2.2$\times$, 1.8$\times$)
8.1K (2.3$\times$, 1.8$\times$) BBox 1183 (1543) 1606 1387 (1.2$\times$,
0.9$\times$) 1908 (1.6$\times$, 1.2$\times$) 4941 (4.1$\times$, 3.1$\times$)
3218 (2.7$\times$, 2.0$\times$) 1785 (1.5$\times$, 1.1$\times$) Pipeline Reg.
256K (273K) 273K 273K (1.1$\times$, 1$\times$) 323K (1.3$\times$, 1.2$\times$)
- - 306K (1.2$\times$, 1.1$\times$) Frequency (MHz) 733 (688) 708 711
(1.03$\times$, 0.99$\times$) 585 (1.3$\times$, 1.2$\times$) - - 693
(1.1$\times$, 1.02$\times$)

##  IV Results

RapidLayout is implemented in Java to enable seamless integration with
RapidWright Java APIs. We use the Java library Opt4J [21] as the optimization
framework for NSGA-II, SA, and GA. CMA-ES is implemented with Apache Commons
Math Optimization Library [25] 3.4 API. We use VPR 7.0 official release [22]
and UTPlaceF TCAD version [19] binary for QoR comparison. All placed designs
are routed and timed with Vivado Design Suite 2018.3. We run our experiments
on an Ubuntu 16.04 LTS machine with Intel Xeon Gold 5115 CPU (10 cores, 20
threads) and 128 GB DDR4 RAM.

###  IV-A Performance and QoR Comparison

We compare the performance and QoR of evolutionary algorithms against (1)
conventional simulated annealing (SA), (2) academic placement tool VPR 7.0,
(3) state-of-art analytical placer UTPlaceF, (4) single-objective genetic
algorithm (GA) [37], and (5) manual placement design. We exclude RapidWright’s
default annealing-based block placer since it does not give feasible placement
solutions. We run each placement algorithm 50 times with seeded random
initialization. Then, we select the top-10 results for each method to route
and report clock frequency. While we include VPR and UTPlaceF in comparison,
they do not support cascade constraints (Equation 5). This limits our
comparison to an approximate check on solution quality and runtime, and we are
unable to translate the resulting placement to the FPGA directly.

In Figure 7a, we plot total runtime and final optimized wirelength2 $\times$
maximum bounding box size for the different placement algorithms along with
Vivado-reported frequency results. We see some clear trends: (1) NSGA-II is
$\approx$2.7$\times$ faster than SA and delivers 1.2$\times$ bounding box
improvement, but has $\approx$12.9% longer wirelength. The average clock
frequency of top-10 results is evidently higher than SA as NSGA-II’s
performance is more stable. (2) CMA-ES is $\approx$30$\times$ faster than SA.
Although the average bounding box size ($\approx$16% larger) and wirelength
($\approx$42% larger) are worse than SA’s results, CMA-ES achieves a slightly
higher average clock frequency at 711 MHz. (4) An alternate NSGA-II method
discussed later in Section IV-B2 with a reduced search space delivers roughly
5 times shorter runtime than SA, with only 2.8% clock frequency degradation,
which is still above the URAM-limited 650 MHz maximum operating frequency.

In Figure 7b, we see the convergence rate of the different algorithms when
observing bounding box sizes and the combined objective. NSGA-II clearly
delivers better QoR after 10 k iterations, while CMA-ES delivers smaller
bounding box sizes within a thousand iterations. Across multiple runs,
bounding box optimization shows a much more noisy behavior with the exception
of CMA-ES. This makes it (1) tricky to rely solely on bounding box
minimization, and (2) suggests a preference for CMA-ES for containing critical
paths within bounding boxes.

Finally, in Table I, we compare average metric values across the 50 runs of
all methods. NSGA-II and CMA-ES deliver superior QoR and runtime against
UTPlaceF and VPR, and speeds up runtime by 3–30$\times$ against annealing with
a minor loss in QoR. Table I also reports the number of registers needed for
the 650 MHz operations. NSGA-II delivers this with 17k ($\approx$6%) less
registers against annealing and 50k ($\approx$16%) less registers against
manual placement. NSGA-II results in Table I are run in 20 threads. Although
CMA-ES runs in serial, the runtime is $\approx$10$\times$ faster than NSGA-II
with a QoR gap.

###  IV-B Parameter Tuning for Annealing and NSGA-II

In this section, we discuss cooling schedule selection for annealing and
optimizations to NSGA-II to explore quality, runtime tradeoffs.

####  IV-B1 Parameter Tuning for SA

The cooling schedule determines the final placement quality, but it is highly
problem-specific. We plot the cooling schedule tuning process in Figure 8 and
choose the hyperbolic cooling schedule for placement experiments presented in
Table I to achieve the best result quality.

Figure 8: SA Parameter Tuning. Each cooling schedule is experimented with 10
sets of parameters. Annealing placement experiments presented in Table I use
hyperbolic cooling schedule for the best QoR performance.

####  IV-B2 NSGA-II Reduced Genotype

As per the genotype design, distribution and location genotypes take up a
large portion of the composite genotype, and they demand quantization and
legalization steps. However, for high-utilization designs, distribution and
location are less influential since resources are nearly fully utilized.
Therefore, we reduce the genotype to mapping only for NSGA-II, and uniformly
distribute and stack the hard blocks from bottom to top. As a consequence of
this trade-off, we observe a $\approx$1.8$\times$ runtime improvement but a
1.3$\times$ larger bounding box size against original NSGA-II. In the
convergence plot of Figure 7b, we discover that reduced genotype does not save
iteration needed, and the bulk of the runtime improvements comes from reduced
genotype decoding and legalization work.

###  IV-C Pipelining

Finally, we explore the effect of pipelining stages on different placement
algorithms. At each pipelining depth, multiple placements from each algorithm
are routed by Vivado to obtain a frequency performance range.

Figure 9: Effect of post-placement pipelining on clock frequency of the
design. NSGA-II delivers 650 MHz without extra pipelining, while CMA-ES,
Annealing, and Manual placement requires at least one stage. NSGA-II and CMA-
ES achieve 750+ MHz with two stages, while SA requires four stages.

In Figure 9, we show the improvement in frequency as a function of the number
of pipeline stages inserted along the long wires by RapidLayout. We note that
NSGA-II delivers 650 MHz frequency with no pipelining, while others require at
least one stage. Therefore, NSGA-II saves $\approx$6%–16% registers at
pipelining as shown in Table I. NSGA-II wins over manual design at every
depth, and CMA-ES exhibits the most stable performance. Systolic array
operation at 750+ MHz should be possible with planned future design
refinements. CMA-ES and NSGA-II can deliver 750+ MHz frequency with only two
pipeline stages, while SA requires four stages.

###  IV-D Transfer Learning

TABLE II: Transfer Learning Performance: VU3P, VU11P as Seed Devices

Device Design Size Impl.Runtime Frequency (MHz) Placement Runtime (s) (conv
units) (mins.) Scratch Transfer Scratch Transfer _xcvu3p_ 123 46.4 718.9 -
428.3 - _xcvu5p_ 246 56.9 677.9 660.5 577.9 42.2 (13.7$\times$) _xcvu7p_ 246
55.1 670.2 690.1 578.8 41.9 (13.8$\times$) _xcvu9p_ 369 58.4 684.9 662.3 570.8
42.0 (13.6$\times$) _xcvu11p_ 480 65.2 655.3 - 522.4 - _xcvu13p_ 640 69.4
653.2 701.3 443.7 38.4 (11.6$\times$)

Figure 10: Runtime and QoR comparison between running from scratch and
transfer learning. Transfer learning delivers $\approx$11–14$\times$ faster
runtime, 0.95–1.3$\times$ bbox size improvement, and 1.05–1.17$\times$
wirelength improvement

RapidLayout is capable of delivering high-quality placement results on devices
with different sizes, resource ratio, or column arrangements with transfer
learning ability. Transfer learning uses the genotype of an existing placement
as a starting seed for initializing the placement search on a new device. We
partition Xilinx UltraScale+ family into two groups with a similar number of
hard block columns. We choose VU3P and VU11P as “seed” devices on which
RapidLayout generates placement from scratch with NSGA-II. Thereafter,
placement results on seed devices are migrated to destination devices in the
same group. In Table II and Figure 10, we compare placement runtimes with and
without transfer learning across a range of FPGA device sizes. We observe that
transfer learning accelerates the optimization process by 11–14$\times$ with a
frequency variation from -2% to +7%. If we observe the total implementation
runtime column, we note that SLR replication ensures that the increase in
overall runtime (46 mins.$\rightarrow$69 mins., 1.5$\times$) with device size
is much less than the FPGA capacity increase (123$\rightarrow$640,
5.2$\times$).

##  V Conclusions

We present an end-to-end hard block placement workflow for resource-intensive
systolic array designs on modern heterogeneous FPGAs. We show how to
outperform conventional simulated annealing and state-of-art analytical
placement with evolutionary algorithms on metrics such as runtime, bounding
box size, pipelining cost, and clock period. RapidLayout also employs transfer
learning to quickly generate placements for similar FPGA devices. RapidLayout
is open-source at https://git.uwaterloo.ca/watcag-public/rapidlayout.

##  VI Acknowledgements

This work was conducted as part of MITACS Globalink Research Internship in
2019. This work has been supported in part by NSERC and CMC Microsystems. This
work was also supported by Industry-University Collaborative Education Program
between SYSU and Digilent Technology: Edge AI Oriented Open Source Software
and Hardware Makerspace, and the State’s Key Project of Research and
Development Plan in China under Grants 2017YFE0121300-6. Any opinions,
findings, and conclusions or recommendations expressed in this publication are
those of the authors and do not necessarily reflect the views of the sponsors.

## References

  * [1] Z. Abuowaimer, D. Maarouf, T. Martin, J. Foxcroft, G. Gréwal, S. Areibi, and A. Vannelli.  Gplace3. 0: Routability-driven analytic placer for ultrascale fpga architectures.  ACM Transactions on Design Automation of Electronic Systems (TODAES), 23(5):1–33, 2018.
  * [2] V. Betz and J. Rose.  Vpr: A new packing, placement and routing tool for fpga research.  In International Workshop on Field Programmable Logic and Applications, pages 213–222. Springer, 1997.
  * [3] V. Betz, J. Rose, and A. Marquardt.  Architecture and cad for deep-submicron fpgas, chapter appendix b, 1999\.
  * [4] R. Collier, C. Fobel, L. Richards, and G. Grewal.  A formal and empirical analysis of recombination for genetic algorithm-based approaches to the fpga placement problem.  In 2012 25th IEEE Canadian Conference on Electrical and Computer Engineering (CCECE), pages 1–6. IEEE, 2012.
  * [5] J. Dean.  The deep learning revolution and its implications for computer architecture and chip design.  arXiv preprint arXiv:1911.05289, 2019.
  * [6] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan.  A fast and elitist multiobjective genetic algorithm: Nsga-ii.  IEEE transactions on evolutionary computation, 6(2):182–197, 2002\.
  * [7] K. Eguro and S. Hauck.  Simultaneous retiming and placement for pipelined netlists.  In 2008 16th International Symposium on Field-Programmable Custom Computing Machines, pages 139–148, April 2008.
  * [8] T. Feist.  Xilinx White Paper: Vivado Design Suite (WP416).  Xilinx.
  * [9] M. Gort and J. H. Anderson.  Analytical placement for heterogeneous fpgas.  In 22nd international conference on field programmable logic and applications (FPL), pages 143–150. IEEE, 2012.
  * [10] N. Hansen and A. Ostermeier.  Adapting arbitrary normal mutation distributions in evolution strategies: The covariance matrix adaptation.  In Proceedings of IEEE international conference on evolutionary computation, pages 312–317. IEEE, 1996.
  * [11] P. Jamieson.  Revisiting genetic algorithms for the fpga placement problem.  In GEM, pages 16–22, 2010.
  * [12] P. Jamieson.  Exploring inevitable convergence for a genetic algorithm persistent fpga placer.  In Proceedings of the International Conference on Genetic and Evolutionary Methods (GEM), page 1. The Steering Committee of The World Congress in Computer Science, Computer …, 2011.
  * [13] P. Jamieson, F. Gharibian, and L. Shannon.  Supergenes in a genetic algorithm for heterogeneous fpga placement.  In 2013 IEEE Congress on Evolutionary Computation, pages 253–260. IEEE, 2013.
  * [14] N. P. Jouppi, C. Young, N. Patil, D. Patterson, G. Agrawal, R. Bajwa, S. Bates, S. Bhatia, N. Boden, A. Borchers, R. Boyle, P. Cantin, C. Chao, C. Clark, J. Coriell, M. Daley, M. Dau, J. Dean, B. Gelb, T. V. Ghaemmaghami, R. Gottipati, W. Gulland, R. Hagmann, C. R. Ho, D. Hogberg, J. Hu, R. Hundt, D. Hurt, J. Ibarz, A. Jaffey, A. Jaworski, A. Kaplan, H. Khaitan, D. Killebrew, A. Koch, N. Kumar, S. Lacy, J. Laudon, J. Law, D. Le, C. Leary, Z. Liu, K. Lucke, A. Lundin, G. MacKean, A. Maggiore, M. Mahony, K. Miller, R. Nagarajan, R. Narayanaswami, R. Ni, K. Nix, T. Norrie, M. Omernick, N. Penukonda, A. Phelps, J. Ross, M. Ross, A. Salek, E. Samadiani, C. Severn, G. Sizikov, M. Snelham, J. Souter, D. Steinberg, A. Swing, M. Tan, G. Thorson, B. Tian, H. Toma, E. Tuttle, V. Vasudevan, R. Walter, W. Wang, E. Wilcox, and D. H. Yoon.  In-datacenter performance analysis of a tensor processing unit.  In 2017 ACM/IEEE 44th Annual International Symposium on Computer Architecture (ISCA), pages 1–12, June 2017.
  * [15] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi.  Optimization by simulated annealing.  science, 220(4598):671–680, 1983.
  * [16] Kung.  Why systolic architectures?  Computer, 15(1):37–46, Jan 1982.
  * [17] C. Lavin and A. Kaviani.  Rapidwright: Enabling custom crafted implementations for fpgas.  In 2018 IEEE 26th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM), pages 133–140. IEEE, 2018\.
  * [18] K. Li, T. Zhang, and R. Wang.  Deep reinforcement learning for multi-objective optimization.  arXiv preprint arXiv:1906.02386, 2019.
  * [19] W. Li, S. Dhar, and D. Z. Pan.  Utplacef: A routability-driven fpga placer with physical and congestion aware packing.  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 37(4):869–882, 2017.
  * [20] Z. Lu, I. Whalen, V. Boddeti, Y. Dhebar, K. Deb, E. Goodman, and W. Banzhaf.  Nsga-net: neural architecture search using multi-objective genetic algorithm.  In Proceedings of the Genetic and Evolutionary Computation Conference, pages 419–427. ACM, 2019.
  * [21] M. Lukasiewycz, M. Glaß, F. Reimann, and J. Teich.  Opt4J - A Modular Framework for Meta-heuristic Optimization.  In Proceedings of the Genetic and Evolutionary Computing Conference (GECCO 2011), pages 1723–1730, Dublin, Ireland, 2011.
  * [22] J. Luu, J. Goeders, M. Wainberg, A. Somerville, T. Yu, K. Nasartschuk, M. Nasr, S. Wang, T. Liu, N. Ahmed, K. B. Kent, J. Anderson, J. Rose, and V. Betz.  Vtr 7.0: Next generation architecture and cad system for fpgas.  ACM Trans. Reconfigurable Technol. Syst., 7(2):6:1–6:30, June 2014\.
  * [23] P. Maidee, C. Ababei, and K. Bazargan.  Fast timing-driven partitioning-based placement for island style fpgas.  In Proceedings of the 40th annual design automation conference, pages 598–603, 2003.
  * [24] P. Maidee, C. Ababei, and K. Bazargan.  Timing-driven partitioning-based placement for island style fpgas.  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 24(3):395–406, 2005.
  * [25] A. C. Math.  Commons math: The apache commons mathematics library, 2013.
  * [26] R. Ros and N. Hansen.  A simple modification in cma-es achieving linear time and space complexity.  In International Conference on Parallel Problem Solving from Nature, pages 296–305. Springer, 2008.
  * [27] A. Samajdar, T. Garg, T. Krishna, and N. Kapre.  Scaling the cascades: Interconnect-aware fpga implementation of machine learning problems.  In 2019 29th International Conference on Field Programmable Logic and Applications (FPL), pages 1–8, Sep. 2019.
  * [28] Y. Shen, M. Ferdman, and P. Milder.  Overcoming resource underutilization in spatial cnn accelerators.  In 2016 26th International Conference on Field Programmable Logic and Applications (FPL), pages 1–4, Aug 2016.
  * [29] Y. Shen, M. Ferdman, and P. Milder.  Maximizing cnn accelerator efficiency through resource partitioning.  In Proceedings of the 44th Annual International Symposium on Computer Architecture, ISCA ’17, pages 535–547, New York, NY, USA, 2017. ACM.
  * [30] D. P. Singh and S. D. Brown.  Integrated retiming and placement for field programmable gate arrays.  In Proceedings of the 2002 ACM/SIGDA Tenth International Symposium on Field-Programmable Gate Arrays, FPGA ’02, page 67–76, New York, NY, USA, 2002. Association for Computing Machinery.
  * [31] S. Trimberger and M.-R. Chene.  Placement-based partitioning for lookup-table-based fpgas.  In Proceedings 1992 IEEE International Conference on Computer Design: VLSI in Computers & Processors, pages 91–94. IEEE, 1992.
  * [32] R. Venkatraman and L. M. Patnaik.  An evolutionary approach to timing driven fpga placement.  In Proceedings of the 10th Great Lakes symposium on VLSI, pages 81–85, 2000.
  * [33] N. Weaver, Y. Markovskiy, Y. Patel, and J. Wawrzynek.  Post-placement c-slow retiming for the xilinx virtex fpga.  In Proceedings of the 2003 ACM/SIGDA Eleventh International Symposium on Field Programmable Gate Arrays, FPGA ’03, page 185–194, New York, NY, USA, 2003. Association for Computing Machinery.
  * [34] E. Wu, X. Zhang, D. Berman, and I. Cho.  A high-throughput reconfigurable processing array for neural networks.  In 2017 27th International Conference on Field Programmable Logic and Applications (FPL), pages 1–4, Sep. 2017.
  * [35] E. Wu, X. Zhang, D. Berman, I. Cho, and J. Thendean.  Compute-efficient neural-network acceleration.  In Proceedings of the 2019 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, FPGA 2019, Seaside, CA, USA, February 24-26, 2019, pages 191–200, 2019.
  * [36] Xilinx.  Vivado Design Suite User Guide, Using Constraints (UG903).  Xilinx.
  * [37] M. Yang, A. Almaini, L. Wang, and P. Wang.  An evolutionary approach for symmetrical field programmable gate array placement.  In Research in Microelectronics and Electronics, 2005 PhD, volume 1, pages 169–172. IEEE, 2005.


# On the Applications of Cyclotomic Fields in Introductory Number Theory

Kabalan Gaspard

(Date: June 22, 2011, re-edited February 11, 2012)

###### Abstract.

In this essay, we see how prime cyclotomic fields (cyclotomic fields obtained
by adjoining a primitive $p$-th root of unity to $\mathbb{Q}$, where $p$ is an
odd prime) can lead to elegant proofs of number theoretical concepts. We
namely develop the notion of primary units in a cyclotomic field, demonstrate
their equivalence to real units in this case, and show how this leads to a
proof of a special case of Fermat’s Last Theorem. We finally modernize
Dirichlet’s solution to Pell’s Equation.

Throughout this paper, unless specified otherwise, $\zeta\equiv\zeta_{p}\equiv
e^{\frac{2\pi\sqrt{-1}}{p}}$ where $p$ is an odd prime.
$K\equiv\mathbb{Q}(\zeta)$ and $\mathcal{O}_{K}$ is the ring of integers of
$K$. We assume knowledge of the basic properties of prime cyclotomic fields
that can be found in any introductory algebraic number theory textbook, namely
that:

  * •

$Gal(K:\mathbb{Q})\simeq U(\mathbb{Z}/p\mathbb{Z})$ (the group of units of
$\mathbb{Z}/p\mathbb{Z}$), which is cyclic and of order $p-1$.

  * •

$\mathcal{O}_{K}=\mathbb{Z}[\zeta_{p}]=\left\langle
1,\zeta_{p},...,\zeta_{p}^{p-2}\right\rangle_{\mathbb{Z}}$, where
$\left\\{1,\zeta_{p},...,\zeta_{p}^{p-2}\right\\}$ is a $\mathbb{Z}$-basis for
$\mathcal{O}_{K}$.

  * •

The only roots of unity in $\mathcal{O}_{K}$ (i.e. solutions in $\mathbb{C}$
to $x^{n}=1$ for some $n\in\mathbb{N}$) are of the form $\pm\zeta_{p}^{i}$,
$i\in\mathbb{Z}$.

We also assume elementary knowledge of quadratic characters, quadratic
reciprocity, and the Legendre symbol $\left(\dfrac{k}{p}\right)$.

##  1\. Primary elements in $\mathcal{O}_{K}$

######  Definition 1.

Let $\alpha\in\mathcal{O}_{K}$ with $\alpha$ prime to $p$. Then $\alpha$ is
_primary_ iff $\alpha$ is congruent to a rational integer modulo
$(1-\zeta_{p})^{2}$.

The definition of primary elements has historically been ambiguous in Number
Theory. In [2], Dalawat shows that definitions of primary elements in
$\mathcal{O}_{K}$ even differ by country (”$p$-primary”, ”primaire” and
”primär”) and, even though these definitions do form a chain of implications,
they are not equivalent.

We also note that it is not true that if $p$ an arbitrary odd prime and $\mu$
prime in $\mathcal{O}_{K}$, only one associate of $\mu$ is primary (for
example, according to the above definition, both $\pm(4+3\omega)$ are primary
in the ring of integers of $\mathbb{Q}(\omega)$ where
$\omega=e^{\frac{2\pi\sqrt{-1}}{3}}$).

######  Proposition 1.

Let $\alpha$ $\in\mathcal{O}_{K}$ (not necessarily prime) and suppose $\alpha$
prime to $p$ in $\mathcal{O}_{K}$. Then there exists a $k\in\mathbb{Z}$,
unique (modulo $p$), such that $\zeta_{p}^{k}\alpha$ is primary.

###### Proof.

Consider the ideal $P=(1-\zeta_{p})$ in $\mathcal{O}_{K}$. Then the norm of
the ideal $N(P)=\prod\limits_{i=1}^{p-1}(1-\zeta_{p}^{i})=p$ by the fact that
$Gal(K:\mathbb{Q})\simeq U(\mathbb{Z}/p\mathbb{Z})$. So $P$ is a prime ideal
and is thus of degree $1$. So by Dedekind’s Theorem in Algebraic Number
Theory, any element of $\mathcal{O}_{K}$ is the root of a monic polynomial of
degree $1$ in $\mathcal{O}_{K}/P$. So in the particular case of $\alpha$,
$\alpha-a_{0}=\overline{0}$ in $\mathcal{O}_{K}/P$ for some
$a_{0}\in\mathbb{Z}$. In other words, $\alpha\equiv a_{0}$ $(1-\zeta_{p})$. So
$\frac{\alpha-a_{0}}{(1-\zeta_{p})}\in\mathcal{O}_{K}$ and so, by the same
argument, $\frac{\alpha-a_{0}}{(1-\zeta_{p})}\equiv a_{1}$ $(1-\zeta_{p})$ for
some $a_{1}\in\mathbb{Z}$. We stop repeating this here because multiplying the
congruence by $(1-\zeta_{p})$, we now have a congruence modulo
$(1-\zeta_{p})^{2}$, which is what we want to consider. More precisely, we now
have $\alpha-a_{0}\equiv a_{1}(1-\zeta_{p})$ $\ (1-\zeta_{p})^{2}$, so
$\alpha\equiv a_{0}+a_{1}(1-\zeta_{p})$ $\ (1-\zeta_{p})^{2}$.

We want to eliminate the $(1-\zeta_{p})$ term by multiplying both sides by
$\zeta_{p}^{n}$ for some $n\in\mathbb{Z}$. Notice that
$\zeta_{p}=(1-(1-\zeta_{p}))$. So modulo $(1-\zeta_{p})^{2}$,

$\displaystyle\zeta_{p}^{n}\alpha$ $\displaystyle\equiv$
$\displaystyle\zeta_{p}^{n}a_{0}+a_{1}\zeta_{p}^{n}(1-\zeta_{p})$
$\displaystyle\equiv$ $\displaystyle
a_{0}(1-(1-\zeta_{p}))^{n}+a_{1}(1-\zeta_{p})(1-(1-\zeta_{p}))^{n}$
$\displaystyle\equiv$ $\displaystyle
a_{0}(1-n(1-\zeta_{p}))+a_{1}(1-\zeta_{p})(1-n(1-\zeta_{p}))\text{ }$

since considering $(1-(1-\zeta_{p}))^{n}$ as a polynomial in $(1-\zeta_{p})$,
$(1-\zeta_{p})^{2}$ divides $(1-\zeta_{p})^{i}$ for $i\geq 2$. So

$\zeta_{p}^{n}\alpha\equiv a_{0}+(a_{1}-na_{0})(1-\zeta_{p})\text{ \ \
}(1-\zeta_{p})^{2}$

Now $\alpha$ prime to $p$, so if $a_{0}\equiv 0$ $(p)$, then $a_{0}\equiv 0$
$(1-\zeta_{p})$, and so $\alpha\equiv 0$ $(1-\zeta_{p})$, which is a
contradiction. So $a_{0}\not\equiv 0$ $(p)$, and so $a_{1}-na_{0}\equiv 0$ has
a unique solution $k$ modulo $p$. Now $(1-\zeta_{p})\mid(1-\zeta_{p}^{2})$,
and
$N(\frac{1-\zeta_{p}^{2}}{1-\zeta_{p}})=\frac{N(1-\zeta_{p}^{2})}{N(1-\zeta_{p})}=1$,
so $(1-\zeta_{p}^{2})$ is associate to $(1-\zeta_{p})$. It follows that
$(1-\zeta_{p})^{2}\mid p$, and so $k$ is (still, since
$a_{1}-na_{0}\in\mathbb{Z}$) the unique integral solution modulo $p$ to
$a_{1}-na_{0}\equiv 0$ $(1-\zeta_{p})^{2}$. Then $\zeta_{p}^{k}\alpha\equiv
a_{0}$ $(1-\zeta_{p})^{2}$, and therefore $\zeta_{p}^{k}\alpha$ is primary.

######  Lemma 1.

Let $u$ be a unit in $\mathcal{O}_{K}$. Then
$\frac{u}{\overline{u}}=\zeta^{t}$ for some $t\in\mathbb{Z}$

###### Proof.

Write $\upsilon=\frac{u}{\overline{u}}$. Conjugation is a Galois automorphism
on $\mathcal{O}_{K}$ since $\overline{\zeta}=\zeta^{-1}=\zeta^{p-1}$. So
$\overline{u}$ is also a unit, and so $\upsilon\in\mathcal{O}_{K}$. Now let
$\sigma_{k}$ be the $(p-1)$ Galois automorphisms on $\mathcal{O}_{K}$ such
that $\sigma_{k}(\zeta)=\zeta^{k}$, $k\in\mathbb{Z}$. Then for all $1\leq
k\leq(p-1)$, $\sigma_{k}\upsilon=\frac{\sigma_{k}u}{\sigma_{k}\overline{u}}=$
$\frac{\sigma_{k}u}{\overline{\sigma_{k}u}}$ by the above remark. So
$\left|\sigma_{k}\upsilon\right|=\sigma_{k}\upsilon\overline{\sigma_{k}\upsilon}=1$.
So $\left|\sigma_{k}\upsilon\right|^{n}=1$ for any $n\in\mathbb{N}$.

Now consider the polynomial
$f(x)=\prod\limits_{k=1}^{p-1}(x-\sigma_{k}\upsilon)$. The coefficients of
this polynomial are elementary symmetric polynomials in
$\\{\sigma_{k}\upsilon:1\leq k\leq p-1\\}$, and so are invariant by action by
$Gal(K:Q)=\\{\sigma_{k}\upsilon:1\leq k\leq p-1\\}$. So
$f(x)\in\mathbb{Z}[x]$. But then the coefficient of $x^{k}$ is $s_{(p-1)-k}$
where $s_{j}$ is the $j^{th}$ elementary symmetric polynomial. But by the
previous paragraph,
$\left|s_{(p-1)-k}\right|\leq\sum\limits_{j=1}^{p-1-k}\left|\sigma_{k}\upsilon\right|^{k}\leq
p-1-k$. So there are finitely many possible such $f(x)\in\mathbb{Z}[x]$ since
the coefficients are bounded. So there are finitely many possible roots since
a polynomial of finite degree has a finite number of roots. But
$\left|\sigma_{k}\upsilon^{n}\right|=1$ for any $n\in\mathbb{N}$, so
$\\{\upsilon^{n}:n\in\mathbb{N}\\}$ satisfy the same argument. So we must have
$\upsilon^{n}=\upsilon^{n^{\prime}}$ for some $n,n^{\prime}\in\mathbb{Z}$. So
$\upsilon^{n-n^{\prime}}=1$, and it follows that $\upsilon$ is a root of unity
in $\mathcal{O}_{K}$.

So by the basic properties of prime cyclotomic fields, we must have
$\upsilon=\pm\zeta^{t}$ for some $t\in\mathbb{Z}$. Now consider congruence
modulo $\lambda=1-\zeta$. Then since
$\dfrac{1-\zeta^{k}}{1-\zeta}=\sum\limits_{i=1}^{k-1}\zeta^{i}\in\left\langle
1,\zeta_{p},...,\zeta_{p}^{p-2}\right\rangle_{\mathbb{Z}}=\mathcal{O}_{K}$,
$\zeta^{k}\equiv 1$ $(\lambda)$ for all $k\in\mathbb{Z}$. So since
$\overline{\zeta^{k}}=\zeta^{-k}\equiv 1\equiv\zeta^{k}$ $(\lambda)$,
$\alpha\equiv\overline{\alpha}$ $(\lambda)$ for all
$\alpha\in\mathcal{O}_{K}$. Namely,
$u\equiv\overline{u}=\pm\zeta^{-t}u\equiv\pm u$ $(\lambda)$. So if
$\upsilon=-\zeta^{t}$, $u\equiv-u$ $(\lambda)\Rightarrow 2u\equiv 0$
$(\lambda)$ which is impossible since $N(\lambda)=p\nmid N(2u)=2^{p-1}$ since
$p$ is odd. So $\upsilon=+\zeta^{t}$.

######  Theorem 1.

Let $u$ be a unit in $\mathcal{O}_{K}$. Then $u$ is real $\Leftrightarrow$ $u$
is primary in $\mathcal{O}_{K}$.

###### Proof.

Since $\mathcal{O}_{K}=\mathbb{Z}[\zeta_{p}]=\left\langle
1,\zeta_{p},...,\zeta_{p}^{p-2}\right\rangle_{\mathbb{Z}}$, we can write $u$
as $\sum\limits_{k=0}^{p-2}a_{k}\zeta^{k}$ for unique
$a_{0},...,a_{p-2}\in\mathbb{Z}$. And so, noting that
$\zeta^{p-1}=-\sum\limits_{i=0}^{p-2}\zeta^{i}$,
$\zeta^{-t}u=\sum\limits_{k=0}^{p-2}a_{k}\zeta^{k-t}=\sum\limits_{k=0}^{p-2}(a_{k+t}-a_{(p-1)+t})\zeta^{k}$
where $a_{k}$ is defined to be $a_{(k\text{ }\mathop{\mathrm{m}od}p)}$ for all
$k\notin\\{0,...,p-1\\}$ ($a_{p-1}=0$, trivially). And so
$\sum\limits_{k=0}^{p-2}(a_{p-k}-a_{1})\zeta^{k}=\overline{u}=$
$\zeta^{-t}u=\sum\limits_{k=0}^{p-2}(a_{k+t}-a_{(p-1)+t})\zeta^{k}$ by 1 and
therefore, since this representation is unique, we get

(1.1) $a_{k+t}-a_{(p-1)+t}=a_{p-k}-a_{1}\text{ for all }0\leq k\leq p-1$

Letting $k_{0}$ be the $\mathop{\mathrm{m}od}p$ solution to $k+t\equiv p-k$
$(p)$, we get $a_{k_{0}+t}=a_{p-k_{0}}$ and so (1.1) yields
$a_{(p-1)+t}=a_{1}$. (1.1) then becomes

(1.2) $a_{k+t}=a_{p-k}=a_{-k}\text{ for all }0\leq k\leq p-1$

Since replacing $k$ by $-(k+t)$ in (1.2) leaves the equation invariant, we get
$\frac{p-1}{2}$ pairs of equal terms with distinct indices amongst
$a_{0},...,a_{p-1}$ (the ’remaining’ term being $a_{k_{0}+t}$). Let
$b_{1},...,b_{\frac{p-1}{2}}$ be representatives of these distinct pairs, and
let $b_{k_{0}+t}=a_{k_{0}+t}$ (we have simply selected and reordered the
$a_{i}$’s).

Now by the proof of 1, there is a unique $c$ modulo $p$ such that $\zeta^{c}u$
is primary, and this $c$ is the solution to $ax\equiv b$ $(p)$ where $u\equiv
a+b\lambda$ $(\lambda^{2})$ where $\lambda=(1-\zeta)$. Now $u=$
$\sum\limits_{k=0}^{p-2}a_{k}\zeta^{k}$. Writing, as a polynomial,
$f(x)=\sum\limits_{k=0}^{p-2}a_{k}x^{k}$, we can find $a$ and $b$ by finding
the coefficients of $1$ and $x$ respectively of $f(1-x)$ since
$\zeta=1-\lambda$. Making elementary use of the Binomial Theorem, we see that
$f(1-x)=\sum\limits_{k=0}^{p-2}a_{k}(1-x)^{k}=\sum\limits_{k=0}^{p-2}a_{k}-\sum\limits_{k=0}^{p-2}ka_{k}x+...$
(we only need the first two terms). So $c$ is the solution to

(1.3)
$\left(\sum\limits_{k=0}^{p-2}a_{k}\right)x\equiv-\sum\limits_{k=0}^{p-2}ka_{k}\text{
}(p)$

Which, since $a_{p-1}=0$, is equivalent to

(1.4)
$\left(\sum\limits_{k=0}^{p-1}a_{k}\right)x\equiv-\sum\limits_{k=0}^{p-1}ka_{k}\text{
}(p)$

Now $k_{0}+t\equiv p-k_{0}$ $(p)\Rightarrow k_{0}+t\equiv-(k_{0}+t)+t$
$(p)\Rightarrow(k_{0}+t)\equiv 2^{-1}t\Rightarrow
b_{k_{0}+t}=a_{k_{0}+t}=a_{2^{-1}t}$. Finally, note that for
$a_{i}=a_{t-i}=b_{l}$ for $1\leq l\leq\frac{p-1}{2}$ by (1.2),
$ia_{i}+(t-i)a_{t-i}=tb_{l}$.

(1.4) then becomes
$\left(b_{k_{0}+t}+2\sum\limits_{k=1}^{\frac{p-1}{2}}b_{k}\right)x\equiv-\left((2^{-1}t\mathop{\mathrm{m}od}p)b_{k_{0}}+\sum\limits_{k=1}^{\frac{p-2}{2}}tb_{k}\right)$
$(p)$. It is clear that $c\equiv-2^{-1}t$ $(p)$ is the solution to this
congruence. By its uniqueness, we see that $u$ is primary $\Leftrightarrow
t\equiv 0$ $(p)\Leftrightarrow u=\zeta^{t}\overline{u}$ is real.

##  2\. Application to a Special Case of Fermat’s Last Theorem

Fermat’s well-known final theorem, proved by Andrew Wiles and Richard Taylor
in 1994, states that

$x^{n}+y^{n}=z^{n}$

where $x,y,z,n\in\mathbb{Z}$ has no non-trivial solutions $(x,y,z)$ for $n\geq
3$.

In fact, to prove this theorem, it suffices to prove that $x^{p}+y^{p}=z^{p}$
has no integral solutions for any positive odd prime $p$, since
$x_{0}^{n}+y_{0}^{n}=z_{0}^{n}\Rightarrow x_{1}^{p}+y_{1}^{p}=z_{1}^{p}$ where
$p$ is an odd prime dividing $n$ (exists since $n\geq 3$) and
$(x_{1},y_{1},z_{1})=(x_{0}^{n/p},y_{0}^{n/p},z_{0}^{n/p})$. In other words,
we can restrict our study to the case where $n$ is an odd prime.

There is a very elegant proof of a special case of this theorem using
cyclotomy. The main use of the concept here is that it allows us to transform
a ”sum of $n$-th powers” problem into a ”divisibility” problem since we can
now factor $x^{p}+y^{p}$ as $\prod\limits_{i=0}^{p-1}(x+\zeta_{p}^{i}y)$.

In this section, we shall lay out said proof. Let $K=\mathbb{Q}(\zeta)$ where
$\zeta=\zeta_{p}$. We will suppose that for some $(x_{0,}y_{0},z_{0})$ is a
solution to $x^{p}+y^{p}=z^{p}$ for some odd prime $p$. Then

(2.1) $x_{0}^{p}+y_{0}^{p}=z_{0}^{p}$

WLOG, we can take $x_{0}$, $y_{0}$ and $z_{0}$ to be pairwise relatively
prime, for if some $d\in\mathbb{Z}$ divides two of them, it must divide the
3${}^{\text{rd}}$, and then $x_{0}^{p}+y_{0}^{p}=z_{0}^{p}\Leftrightarrow
x_{1}^{p}+y_{1}^{p}=z_{1}^{p}$ where $x_{0},y_{0},z_{0}=dx_{1},dy_{1}$

$,dz_{1}$ respectively, with $x_{1},y_{1},z_{1}\in\mathbb{Z}$.

We shall now reduce the problem to a special case and suppose that $p$_does
not divide the class number_ $h$_of_ $O_{K}$, and that $p\nmid
x_{0}y_{0}z_{0}$. From (2.1), we shall reach a contradiction.

This case has been treated in Number Theory textbooks such as [1]. However,
using the equivalence of primary and real units in $\mathcal{O}_{K}$ when $K$
is a prime cyclotomic field, we can prove the result more rapidly.

######  Lemma 2.

Let $i\not\equiv j$ $(p)$. Then the ideals $I=(x_{0}+\zeta^{i}y_{0})$ and
$J=(x_{0}+\zeta^{j}y_{0})$ are relatively prime.

###### Proof.

Consider the ideal $I+J$. $J$ contains the element $-(x_{0}+\zeta^{j}y_{0})$,
so $x_{0}+\zeta^{i}y_{0}-(x_{0}+\zeta^{j}y_{0})=(\zeta^{i}-\zeta^{j})y_{0}\in
I+J$. Likewise, since $\mathcal{O}_{K}=\mathbb{Z}[\zeta]$,
$-\zeta^{j}(x_{0}+\zeta^{i}y_{0})=\zeta^{j}x_{0}+\zeta^{i+j}y_{0}\in I$ and
$\zeta^{i}(x_{0}+\zeta^{j}y_{0})=\zeta^{i}x_{0}+\zeta^{i+j}y_{0}\in J$. So
$\zeta^{i}x_{0}+\zeta^{i+j}y_{0}-\zeta^{j}(x_{0}+\zeta^{i}y_{0})=(\zeta^{i}-\zeta^{j})x_{0}\in
I+J$. Now $(x_{0},y_{0})=1\Rightarrow$ there exist $a,b\in\mathbb{Z}$ such
that $ax_{0}+by_{0}=1$. So
$a(\zeta^{i}-\zeta^{j})x_{0}+b(\zeta^{i}-\zeta^{j})y_{0}=(\zeta^{i}-\zeta^{j})\in
I+J$.

Now $N(\zeta^{i}-\zeta^{j})=p$ since $(N(\zeta^{i}-\zeta^{j}))^{2}=$
$\prod\limits_{k=1}^{p-1}(\zeta^{ik}-\zeta^{jk})^{2}=\prod\limits_{k=1}^{p-1}(-\zeta^{-k(j-i)})(1-\zeta^{k(j-i)})^{2}=\prod\limits_{k=1}^{p-1}(-\zeta^{-k})(1-\zeta^{k})^{2}=+\zeta^{-p\frac{p-1}{2}}\prod\limits_{k=1}^{p-1}(1-\zeta^{k})^{2}=1\cdot\left(\sum\limits_{k=1}^{p-1}1\right)^{2}=p^{2}$.
So $N(I+J)\mid p$. If $N(I+J)=p$, then since $I\subseteq I+J$, $p=N(I+J)\mid
N(I)=\prod\limits_{i=0}^{p-1}(x_{0}+\zeta^{i}y_{0})=x_{0}^{p}+y_{0}^{p}=z_{0}^{p}$.
So since $p$ is prime, $p\mid z_{0}\Rightarrow$ contradiction. So $N(I+J)=1$,
and therefore $I+J=\mathcal{O}_{K}$. So $I$ and $J$ are coprime since $P\mid
I$ and $P\mid J\Rightarrow P\mid I+J\Rightarrow P=\mathcal{O}_{K}$.

Now
$x_{0}^{p}+y_{0}^{p}=z_{0}^{p}\Rightarrow\prod\limits_{i=0}^{p-1}(x_{0}+\zeta^{i}y_{0})=(z_{0})^{p}$
as ideals. But $\\{(x_{0}+\zeta^{i}y_{0}):0\leq i\leq p-1\\}$ are pairwise
coprime. So by unique factorization of ideals, each of these ideals must be a
$p$-th power. So in particular, taking $i=1$, $(x_{0}+\zeta
y_{0})=\mathfrak{I}^{p}$ for some ideal $\mathfrak{I}$. So since $(x_{0}+\zeta
y_{0})$ is principal, $[\mathfrak{I]}$ has order dividing $p$ in the ideal
class group, but since $p\nmid h$, we must have that the order of
$[\mathfrak{I]}$ is $1$. So $\mathfrak{I}$ is principal. Let
$\mathfrak{I}=(\alpha)$. Then $(x_{0}+\zeta y_{0})=(\alpha^{p})$, and so
$x_{0}+\zeta y_{0}$ is associate to $\alpha^{p}$. We write $x_{0}+\zeta
y_{0}=u\alpha^{p}$ where $u$ is a unit in $\mathcal{O}_{K}$.

Then by 1 there exists a unique $c$ modulo $p$ such that $\zeta^{-c}u$ is
primary. Let $\zeta^{-c}u=u_{0}$ so that $u=\zeta^{c}u_{0}$ where $u_{0}$ is
primary. But $u_{0}$ is trivially a unit, and is therefore real by 1.

So $x_{0}+\zeta y_{0}=\zeta^{c}u_{0}\alpha^{p}$ where $u_{0}$ is real. Note
that modulo $p$,
$\alpha^{p}\equiv\left(\sum\limits_{i=0}^{p-2}a_{i}\zeta^{i}\right)^{p}\equiv\sum\limits_{i=0}^{p-2}a_{i}^{p}\zeta^{ip}\equiv\sum\limits_{i=0}^{p-2}a_{i}^{p}\in\mathbb{Z}$
$(p)$. So $\alpha^{p}\equiv\overline{\alpha^{p}}$ $(p)$. It follows that
$x_{0}+\zeta y_{0}=\zeta^{c}u_{0}\alpha^{p}\Rightarrow x_{0}+\zeta
y_{0}\equiv\zeta^{c}u_{0}\alpha^{p}$ $(p)\Rightarrow\overline{x_{0}+\zeta
y_{0}}\equiv\overline{\zeta^{c}u_{0}\alpha^{p}}$ $(p)\Rightarrow
x_{0}+\zeta^{-1}y_{0}\equiv\zeta^{-c}u_{0}\alpha^{p}$ $(p)$. So we now have
$x_{0}+\zeta y_{0}\equiv\zeta^{c}u_{0}\alpha^{p}$
$(p)\Rightarrow\zeta^{-c}x_{0}+\zeta^{1-c}y_{0}\equiv u_{0}\alpha^{p}$ $(p)$
and $x_{0}+\zeta^{-1}y_{0}\equiv\zeta^{-c}u_{0}\alpha^{p}$
$(p)\Rightarrow\zeta^{c}x_{0}+\zeta^{c-1}y_{0}\equiv u_{0}\alpha^{p}$ $(p)$.
Subtracting the latter congruence from the former yields

(2.2) $\zeta^{-c}x_{0}+\zeta^{1-c}y_{0}-\zeta^{c}x_{0}-\zeta^{c-1}y_{0}\equiv
0\text{ }(p)$

Now an element of $\mathcal{O}_{K}=\mathbb{Z}[\zeta]$ is divisible by $p$ if
and only if all of the coefficients as a polynomial in $\zeta$ are divisible
by $p$. $p\nmid x_{0},y_{0}$ since $p\nmid x_{0}y_{0}z_{0}$, so we must check
the cases where one of $\\{c,-c,1-c,c-1\\}$ is congruent to $-1$ modulo $p$ or
where two of $\\{c,-c,1-c,c-1\\}$ are equal modulo $p$. These cases can be
split as follows:

  * •

$c\equiv 0$ $(p)$ (so that $c\equiv-c$ $(p)$). Then $p\mid
y_{0}(\zeta-\zeta^{-1})=y_{0}(\sum\limits_{i=2}^{p-2}\zeta^{i}+1)\Rightarrow
p\mid y_{0}$ (even if $p=3$) $\Rightarrow$ contradiction.

  * •

$c\equiv 1$ $(p)$ (so that $1-c\equiv c-1$ $(p)$). Then $p\mid
x_{0}(\zeta^{-1}-\zeta)\Rightarrow p\mid x_{0}$ as in the previous case
$\Rightarrow$ contradiction.

  * •

$c\equiv 2^{-1}$ $(p)$ (so that $c\equiv 1-c$ $(p)$). Then
$p\mid(y_{0}-x_{0})\zeta^{c}+\zeta^{-c}(x_{0}-y_{0})$. So
$p\mid(x_{0}-y_{0})$. We then rewrite 2.1 as
$x_{0}^{p}+(-z_{0})^{p}=(-y_{0})^{p}$ (since $p$ is odd). Then with the same
argument we will get $p\mid(x_{0}+z_{0})$. But 2.1 yields
$x_{0}^{p}+y_{0}^{p}-z_{0}^{p}\equiv 0$ $(p)$ and so $x_{0}+y_{0}-z_{0}\equiv
0$ $(p)$. This yields $3x_{0}\equiv 0$ $(p)$. We suppose for now that $p>3$.
Then this yields $p\mid x_{0}\Rightarrow$ contradiction.

  * •

Letting one of $\\{c,-c,1-c,c-1\\}$ be congruent to $-1$ modulo $p$ will yield
one of the coefficients of the terms of (2.2) as $\pm(x_{0}-y_{0})$, giving
the same contradiction as in the previous case.

We therefore obtain a contradiction in all cases. We have, however, supposed
that $p>3\,$. A general study of the case where $p=3$ is done elegantly in
[4].

##  3\. An Approach to Pell’s Equation using cyclotomy

Pell’s Equation is

$x^{2}-dy^{2}=1\text{, \ \ }x,y\in\mathbb{Z}$

in $x$ and $y$, where $d\in\mathbb{Z}^{+}$. $d\leq 0$ trivially yields the
single solution $(1,0)$, and we can consider $d$ to be square-free, since any
square factor of $d$ can be incorporated into $y$.

The equation can be solved using cyclotomy and quadratic residues. A partial
solution was found by Dirichlet using this method, building upon the work of
Gauss [3]. In this section, we build upon Dirichlet’s work, explicitly writing
the solution and using the modern machinery of Galois Theory to streamline the
approach. Again, we let $p$ be an odd prime, and define
$p^{\ast}=(-1)^{\frac{p-1}{2}}p$, $i=\sqrt{-1}$, and start by introducing an
important lemma.

######  Lemma 3.

$\left\\{\begin{array}[]{l}q_{1}(x)=2\prod\limits_{\begin{subarray}{c}1\leq
k<p\\\
\QOVERD(){k}{p}=1\end{subarray}}(x-\zeta^{k})=f(x)+\sqrt{p^{\ast}}g(x)\\\
q_{-1}(x)=2\prod\limits_{\begin{subarray}{c}1\leq k<p\\\
\QOVERD(){k}{p}=-1\end{subarray}}(x-\zeta^{k})=f(x)-\sqrt{p^{\ast}}g(x)\end{array}\right.$
where $f(x),g(x)$ are polynomials in $\mathbb{Z}[x]$.

###### Proof.

Note that the product of the 2 above polynomials (on the left-hand side) is
$4\prod\limits_{1\leq k<p}(x-\zeta^{k})=4m_{p}(x)\in\mathbb{Z}[x]$. It is
therefore fixed by any Galois automorphism in $Gal(K:\mathbb{Q})$. Now taking
$\theta=\zeta^{\frac{p^{2}-1}{8}}\prod\limits_{k=1}^{\frac{p-1}{2}}(1-\zeta^{k})^{2}$,
we see that $\theta^{2}=p^{\ast}$ since
$(-1)^{\frac{p^{2}-1}{8}}\equiv\left(\frac{2}{p}\right)$ $($mod $2)$, and
trivially $\theta\in\mathcal{O}_{K}$. So $\sqrt{p^{\ast}}\in\mathcal{O}_{K}$,
Now an automorphism $\sigma$ in the Galois group fixes $p^{\ast}$ if and only
if $\sigma$ is a square. But this is if and only if $\sigma$ fixes all (and
only) the $\zeta^{k}$ such that $k$ is a quadratic residue modulo $p$. So
$\prod\limits_{\begin{subarray}{c}1\leq k<p\\\
\QOVERD(){k}{p}=1\end{subarray}}(x-\zeta^{k})\in L[x]$ where
$L=\mathbb{Q}(\sqrt{p^{\ast}})$. All the coefficients in $L[x]$ are of the
form $a+b\sqrt{p^{\ast}}$ where $a$ and $b$ are both rational, and
$\frac{1}{2}\cdot$ an algebraic integer (allowing for the fact that
$p^{\ast}\equiv 1$ $(4)$). The coefficients of
$2\prod\limits_{\begin{subarray}{c}1\leq k<p\\\
\QOVERD(){k}{p}=1\end{subarray}}(x-\zeta^{k})$ are therefore rational
algebraic integers and thus in $\mathbb{Z}$. We can now expand $q_{1}(x)$ and
rewrite it as $q_{1}(x)=f(x)+\sqrt{p^{\ast}}g(x)$ where $f(x),g(x)$ are
polynomials in $\mathbb{Z}[x]$.

A similar argument shows that $q_{-1}(x)\in L[x]$. Now let $\tau$ be the
Galois automorphism in $Gal(K:Q)$ defined by
$\tau(\sqrt{p^{\ast}})=-\sqrt{p^{\ast}}$ (noting that $K:L:\mathbb{Q}$ is a
tower of fields). Then by the above, and since $\tau^{2}$ must fix $q_{1}(x)$,
we must have that $\tau(\zeta^{k})=\zeta^{l}$ where
$\QOVERD(){k}{p}\QOVERD(){l}{p}=-1$. So since $\tau$ is a Galois automorphism
over $K$, we must have $\tau(q_{1}(x))=q_{-1}(x)$. This yields that
$q_{-1}(x)=f(x)-\sqrt{p^{\ast}}g(x)$.

We will primarily consider the case where $d$ is an odd prime. Pell’s Equation
then becomes

(3.1) $x^{2}-py^{2}=1$

By Lemma 3,

$4m_{p}(x)=q_{1}(x)q_{-1}(x)=f(x)^{2}-(p^{\ast})g(x)^{2}$

And so, replacing $x$ by $1$, we get

(3.2) $4p=x_{1}^{2}-p^{\ast}y_{1}^{2}\text{ where }x_{1}=f(1)\text{,
}y_{1}=g(1)$

Since $f(x),g(x)\in\mathbb{Z}[x]$, $x_{1},y_{1}\in\mathbb{Z}$, and we can see
that Lemma 3 relates to Pell’s Equation insofar as it gives us a pair
$(x_{1},y_{1})$ that verifies an equation very similar to (3.1).

$4p=x_{1}^{2}-p^{\ast}y_{1}^{2}\Rightarrow
x_{1}^{2}=4p+p^{\ast}y_{1}^{2}\Rightarrow p\mid x_{1}^{2}\Rightarrow p\mid
x_{1}$ since $p$ is prime. So letting $p\xi_{1}=x_{1}$, we can rewrite
equation (3.2) as $4p=p^{2}\xi_{1}^{2}-p^{\ast}y_{1}^{2}$, and so, dividing by
$p$,

(3.3) $p\xi_{1}^{2}-(-1)^{\frac{p-1}{2}}y_{1}^{2}=4$

We now analyze $q_{1}(x)$ and $q_{-1}(x)$ to obtain some insight as to the
values $x_{1}$ and $y_{1}$. $x^{2}\equiv(p-x)^{2}$ $(p)$, so all quadratic
residues are in $\\{x^{2}$ $(p):1\leq x\leq\frac{p-1}{2}\\}$. We can therefore
reorder the terms in $q_{1}(x)$ and write it as
$2\prod\limits_{k=1}^{\frac{p-1}{2}}(x-\zeta^{k^{2}})$, and so
$q_{1}(1)=2\prod\limits_{k=1}^{\frac{p-1}{2}}(1-\zeta^{k^{2}})$.

The value of $p^{\ast}$ depends on the value of $p$ modulo $4$ so we will
consider the two cases separately for simplicity.

Case 1:__ $p\equiv 1$ $(4)$.

Then (3.3) becomes $p\xi_{1}^{2}-y_{1}^{2}=4$ (or, to emphasize the similarity
to Pell’s Equation, $y_{1}^{2}-p\xi_{1}^{2}=-4$).

We then have two subcases.

If $p\equiv 1$ $(8)$, then $y_{1}^{2}-\xi_{1}^{2}\equiv 4$ $(8)$. Trivially
$y_{1}$ and $\xi_{1}$ must either be both odd or both even. But $1^{2}\equiv
3^{2}\equiv 5^{2}\equiv 7^{2}\equiv 1$ $(8)$, so if $y_{1}$ and $\xi_{1}$ were
both odd we would have $y_{1}^{2}-\xi_{1}^{2}\equiv 0$ $(8)\Rightarrow$
contradiction. It follows that $y_{1}$ and $\xi_{1}$ are both even, and we can
thus write $y_{2}=\frac{y_{1}}{2},\xi_{2}=\frac{\xi_{1}}{2}\in\mathbb{Z}$.
Then $y_{2}-p\xi_{2}^{2}=-1$. We can use the fact that
$(\sqrt{p})^{2}\in\mathbb{Z}$ to get rid of the minus sign in front of $1$.
$y_{2}^{2}-p\xi_{2}^{2}=-1$ yields
$(y_{2}-\sqrt{p}\xi_{2})(y_{2}+\sqrt{p}\xi_{2})=-1$, and so
$(y_{2}-\sqrt{p}\xi_{2})^{2}(y_{2}+\sqrt{p}\xi_{2})^{2}=1$. But
$(y_{2}\pm\sqrt{p}\xi_{2})^{2}=a\pm b\sqrt{p}$, $a,b\in\mathbb{Z}$. Taking
$(x,y)=(a,b)$, we have solved (3.1). Summarizing, we get a solution from

$\displaystyle(a,b)$ $\displaystyle=$
$\displaystyle\left(\frac{1}{4}(g(1)^{2}+\frac{f(1)^{2}}{p})\text{ },\text{
}\frac{f(1)g(1)}{2p}\right)\text{ }$ $\displaystyle\text{where we can directly
compute }f(1)\text{ and }g(1)$

If $p\equiv 5$ $(8)$, $y_{1}^{2}+3\xi_{1}^{2}\equiv 4$ $(8)$. Given that the
only quadratic residues modulo $8$ are $0,1,4$, we must have
$(y_{1}^{2},\xi_{1}^{2})\equiv(1,1),(0,4)$ or $(4,0)$ $\ (8)$.

We now use the fact that $8^{2}=2^{2\cdot 3}=4^{3}$ and consider
$(y_{1}+\sqrt{p}\xi_{1})^{3}=(y_{1}^{3}+3p\xi_{1}^{2}y_{1})+\sqrt{p}(p\xi_{1}^{3}+3y_{1}^{2}\xi_{1})=y_{2}+\sqrt{p}\xi_{2}$
and see that $y_{2}^{2}-p\xi_{2}^{2}=(y_{1}^{2}-p\xi_{1}^{2})^{3}=-4^{3}$.

But $y_{2}=y_{1}(y_{1}^{2}+3p\xi_{1}^{2})\equiv y_{1}(y_{1}^{2}-\xi_{1}^{2})$
$(8)$. $(y_{1}^{2},\xi_{1}^{2})\equiv(1,1)$ $(8)\Rightarrow$ $y_{2}\equiv 0$
$(8)$. $(y_{1}^{2},\xi_{1}^{2})\equiv(0,4)$ or $(4,0)$ $(8)\Rightarrow
y_{2}\equiv 4\cdot 4,$ $0\cdot 4$ or $\pm 2\cdot 4\equiv 0$ $(8)$. So in any
case $y_{2}\equiv 0$ $(8)$.

Similarly
$\xi_{2}=\xi_{1}(p\xi_{1}^{2}+3y_{1}^{2})\equiv\xi_{1}(5\xi_{1}^{2}+3y_{1}^{2})$
$(8)$. $(y_{1}^{2},\xi_{1}^{2})\equiv(1,1)$ $(8)\Rightarrow$
$\xi_{2}\equiv\xi_{2}(5+3)\equiv 0$ $(8)$.
$(y_{1}^{2},\xi_{1}^{2})\equiv(0,4)$ or $(4,0)$
$(8)\Rightarrow\xi_{2}\equiv\pm 2\cdot 4,$ $0\cdot 4$ or $4\cdot 0\equiv 0$
$(8)$. So in any case $\xi_{2}\equiv 0$ $(8)$.

So $8\mid y_{2},\xi_{2}$ and thus, writing
$y_{3}=\frac{y_{2}}{8},\xi_{3}=\frac{\xi_{2}}{8}\in\mathbb{Z}$, we get
$(y_{3}^{2}-p\xi_{3}^{2})=\frac{-4^{3}}{8^{2}}=-1$. As in the case where
$p\equiv 1$ $(8)$, writing $(y_{3}\pm\sqrt{p}\xi_{3})^{2}=a\pm b\sqrt{p}$,
$a,b\in\mathbb{Z}$, $(x,y)=(a,b)$ is a solution of (3.1). Summarizing, we get
a solution from

$(a,b)=\left(\begin{array}[]{c}\frac{1}{64}((g(1)^{3}+\frac{3f(1)^{2}g(1)}{p})^{2}+p(\frac{f(1)^{3}}{p^{2}}+3\frac{g(1)^{2}f(1)}{p})^{2})\text{
},\\\ \text{
}\frac{1}{32}(g(1)^{3}+3\frac{f(1)^{2}g(1)}{p})(\frac{f(1)^{3}}{p^{2}}+3\frac{g(1)^{2}f(1)}{p})\end{array}\right)$

Case 2: $p\equiv 3$ $(4)$.

Let $l=\frac{p-1}{2}$. $p\equiv 3$ $(4)\Rightarrow l$ is odd. We see that
$f(x)=\frac{1}{2}(q_{1}(x)+q_{-1}(x))=\prod\limits_{\begin{subarray}{c}1\leq
k<p\\\
\QOVERD(){k}{p}=1\end{subarray}}(x-\zeta^{k})+\prod\limits_{\begin{subarray}{c}1\leq
k<p\\\ \QOVERD(){k}{p}=-1\end{subarray}}(x-\zeta^{k})$. $f$ is of degree $l$.
We shall find a relation amongst the coefficients of $f$ by comparing
$f(\zeta)$ and $f(\overline{\zeta})=\overline{f(\zeta)}$ (since
$f(x)\in\mathbb{Z}[x]$). Trivially $\QOVERD(){1}{p}=1$, so
$\prod\limits_{\begin{subarray}{c}1\leq k<p\\\
\QOVERD(){k}{p}=1\end{subarray}}(\zeta-\zeta^{k})=0$ and so
$f(\zeta)=\prod\limits_{\begin{subarray}{c}1\leq k<p\\\
\QOVERD(){k}{p}=-1\end{subarray}}(\zeta-\zeta^{k})$. Also note that
$\QOVERD(){-1}{p}=(-1)^{\frac{p-1}{2}}=-1$, and so
$\QOVERD(){k}{p}=-\QOVERD(){-k}{p}$ for all $1\leq k\leq p-1$. So
$f(\zeta)=\prod\limits_{\begin{subarray}{c}1\leq k<p\\\
\QOVERD(){k}{p}=1\end{subarray}}(\zeta-\zeta^{-k})$. By the same line of
reasoning, $f(\overline{\zeta})=f(\zeta^{-1})=$
$\prod\limits_{\begin{subarray}{c}1\leq k<p\\\
\QOVERD(){k}{p}=1\end{subarray}}(\zeta^{-1}-\zeta^{k})$. So

$\displaystyle\frac{f(\zeta)}{f(\zeta^{-1})}$ $\displaystyle=$
$\displaystyle\prod\limits_{\begin{subarray}{c}1\leq k<p\\\
\QOVERD(){k}{p}=1\end{subarray}}\frac{(\zeta-\zeta^{-k})}{(\zeta^{-1}-\zeta^{k})}=(-1)^{l}\prod\limits_{\begin{subarray}{c}1\leq
k<p\\\ \QOVERD(){k}{p}=1\end{subarray}}\zeta^{1-k}$ $\displaystyle\text{since
there are precisely }l\text{ quadratic residues modulo }p$ $\displaystyle=$
$\displaystyle-\zeta^{l}\prod\limits_{\begin{subarray}{c}1\leq k<p\\\
\QOVERD(){k}{p}=1\end{subarray}}\zeta^{-k}$ $\displaystyle=$
$\displaystyle-\zeta^{l}$ $\displaystyle\text{since
}\sum\limits_{\begin{subarray}{c}1\leq k<p\\\
\QOVERD(){k}{p}=1\end{subarray}}k=p\frac{p-1}{2}+0\text{ since the Legendre
symbol is a }$ $\displaystyle\text{quadratic character modulo }p\text{ and
since }\left(\frac{0}{p}\right)=0\text{.}$

So $f(\zeta)=-\zeta^{l}f(\zeta^{-1})$. So writing
$f(x)=a_{l}x^{l}+a_{l-1}x^{l-1}+...+a_{1}x+a_{0}$, this yields
$a_{l}\zeta^{l}+a_{l-1}\zeta^{l-1}+...+a_{1}\zeta+a_{0}=-a_{0}\zeta^{l}-a_{1}\zeta^{l-1}-...-a_{l-1}\zeta-
a_{l}$, i.e.

(3.4)
$\sum\limits_{k=0}^{l}a_{k}\zeta^{k}=\sum\limits_{k=0}^{l}(-a_{k})\zeta^{l-k}$

Now it is trivial to see that $a_{l}=2$ by the above formula for $f(x)$. Also,
$q_{1}(x)=2\prod\limits_{\begin{subarray}{c}1\leq k<p\\\
\QOVERD(){k}{p}=1\end{subarray}}(x-\zeta^{k})$. The constant term of $q_{1}$
is $2(-1)^{l}\prod\limits_{\begin{subarray}{c}1\leq k<p\\\
\QOVERD(){k}{p}=1\end{subarray}}\zeta^{k}=-2\prod\limits_{1\leq k\leq
l}\zeta^{k^{2}}=-2\zeta^{\frac{l(l+1)(2l+1)}{6}}=-2\zeta^{p\frac{p^{2}-1}{24}}$.
Now $3\mid p^{2}-1$ since $p\neq 3$ ($p\equiv 3$ $(4)$), and $p^{2}\equiv 1$
$(8)$ since $p$ is odd. So $3\cdot 8=24\mid p^{2}-1$. So The constant term of
$q_{1}$ is $-2\cdot 1=-2$. But $q_{1}(x)=f(x)+\sqrt{p^{\ast}}g(x)$ where
$f(x),g(x)\in\mathbb{Z}[x]$. So we must have $a_{0}=-2$. Therefore
$a_{l}=-a_{0}$. So (3.4) now yields
$\sum\limits_{k=1}^{l-1}a_{k}\zeta^{k}=\sum\limits_{k=1}^{l-1}(-a_{k})\zeta^{l-k}=\sum\limits_{k=1}^{l-1}(-a_{l-k})\zeta^{k}$
(after replacing $k$ by $l-k$), and $\\{\zeta,...,\zeta^{l-1}\\}$ is a
$\mathbb{Z}$-linearly independent subset. So $a_{l-k}=-a_{l}$ for $1\leq k\leq
l-1$, and so by the above, $a_{l-k}=-a_{l}$ for all $0\leq k\leq l$. We can
therefore rewrite $f(x)$ as
$2(x^{l}-1)+b_{1}x(x^{l-2}-1)+b_{2}x^{2}(x^{l-4}-1)+...+b_{\frac{l-1}{2}}x^{\frac{l-1}{2}}(x-1)=\sum\limits_{k=0}^{\frac{l-1}{2}}b_{k}x^{k}(x^{l-2k}-1)$,
$b_{k}\in\mathbb{Z}$ for all $0\leq k\leq\frac{l-1}{2}$ (with $b_{0}=2$).

Replacing $x$ by $i=\sqrt{-1}$, we see that $x^{k}(x^{l-2k}-1)$ depends on
whether $p\equiv 3$ or $7$ $(8)$.

Let $p\equiv 3$ $(8)$. Then $l\equiv 1$ $(4)$ and simple calculation yields

$i^{k}(i^{l-2k}-1)=\left\\{\begin{array}[]{ll}1-i&\text{if }k\equiv 1,2\text{
}(4)\\\ -(1-i)&\text{if }k\equiv 0,3\text{ }(4)\end{array}\right.$

$p\equiv 7$ $(8)\Rightarrow l\equiv 3$ $(4)$, and the same type of calculation
yields

$i^{k}(i^{l-2k}-1)=\left\\{\begin{array}[]{ll}1+i&\text{if }k\equiv 3,2\text{
}(4)\\\ -(1+i)&\text{if }k\equiv 0,1\text{ }(4)\end{array}\right.$

Writing $i^{\ast}=\left\\{\begin{array}[]{ll}-i&\text{if }p\equiv 3\text{
}(8)\\\ +i&\text{if }p\equiv 7\text{ }(8)\end{array}\right.$, we see that
$f(i)=\sum\limits_{k=0}^{\frac{l-1}{2}}\pm
b_{k}(1+i^{\ast})=y_{2}(1+i^{\ast})$ where $y_{2}\in\mathbb{Z}$.

Now,

$\displaystyle g(x)$ $\displaystyle=$
$\displaystyle\frac{1}{2\sqrt{p^{\ast}}}(q_{1}(x)-q_{-1}(x))$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{p^{\ast}}}\left(\prod\limits_{\begin{subarray}{c}1\leq
k<p\\\
\QOVERD(){k}{p}=1\end{subarray}}(x-\zeta^{k})-\prod\limits_{\begin{subarray}{c}1\leq
k<p\\\ \QOVERD(){k}{p}=-1\end{subarray}}(x-\zeta^{k})\right)$

And so

$\displaystyle g(\zeta)$ $\displaystyle=$
$\displaystyle\boldsymbol{-}\frac{1}{\sqrt{p^{\ast}}}\left(\prod\limits_{\begin{subarray}{c}1\leq
k<p\\\ \QOVERD(){k}{p}=1\end{subarray}}(\zeta-\zeta^{-k})\right)$
$\displaystyle\text{and }g(\zeta^{-1})$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{p^{\ast}}}\left(\prod\limits_{\begin{subarray}{c}1\leq
k<p\\\ \QOVERD(){k}{p}=1\end{subarray}}(\zeta^{-1}-\zeta^{k})\right)$

A similar line of reasoning as for $f(x)$ gives us that
$g(\zeta)=+\zeta^{l}g(\zeta^{-1})$. Following the same steps as for $f(x)$, we
find that, writing $g(x)$ as
$\frac{1}{\sqrt{p^{\ast}}}\sum\limits_{k=0}^{l}a_{k}x^{k}$, we get
$a_{l-k}=+a_{l}$ for all $0\leq k\leq l$ (with $a_{l}=a_{0}=0$ this time). We
can therefore similarly rewrite $g(x)$ as
$\sum\limits_{k=0}^{\frac{l-1}{2}}b_{k}x^{k}(x^{l-2k}+1)$,
$b_{k}\in\mathbb{Z}$ (remembering that $g(x)\in\mathbb{Z}[x]$ by 3). A similar
argument shows that $g(i)=\sum\limits_{k=0}^{\frac{l-1}{2}}\pm
b_{k}(1-i^{\ast})=\xi_{2}(1-i^{\ast})$ where $\xi_{2}\in\mathbb{Z}$.

Now $l\equiv 3$ $(4)$, so
$q_{1}(i)q_{-1}(i)=4m_{p}(i)=4(1+i+...+i^{l})=4\cdot((1+i-1-i)+(1+i-1-i)+...+(1+i-1))=4i$

So $f(i)^{2}-p^{\ast}g(i)^{2}=f(i)^{2}+pg(i)^{2}=4i$, and so
$y_{2}^{2}(1+i^{\ast})^{2}+p\xi_{2}(1-i^{\ast})^{2}=2y_{2}^{2}i^{\ast}-2p\xi_{2}^{2}i^{\ast}=4i$
or, dividing by $2i^{\ast}=\pm 2i$,

$\displaystyle y_{2}^{2}-p\xi_{2}^{2}=\pm 2$ $\displaystyle\Rightarrow$
$\displaystyle(y_{2}+\sqrt{p}\xi_{2})^{2}(y_{2}-\sqrt{p}\xi_{2})^{2}=4$

Now $y_{2},\xi_{2}$ are odd, else $y_{2}^{2}-p\xi_{2}^{2}\equiv
y_{2}^{2}+\xi_{2}^{2}\equiv 0\not\equiv\pm 2$ $(4)$. So the coefficients of
$(y_{2}+\sqrt{p}\xi_{2})^{2}=(y_{2}^{2}+p\xi_{2}^{2})+2y_{2}\xi_{2}\sqrt{p}$
are even. We can thus write
$a=\frac{(y_{2}^{2}+p\xi_{2}^{2})}{2},b=y_{2}\xi_{2}\in\mathbb{Z}$ and get

$a^{2}-pb^{2}=\frac{(y_{2}+\sqrt{p}\xi_{2})^{2}(y_{2}-\sqrt{p}\xi_{2})^{2}}{2\cdot
2}=\frac{4}{4}=1$

This solves the equation, where

$\displaystyle(a,b)$ $\displaystyle=$
$\displaystyle\left(\frac{i^{\ast}}{4}(pg(i)^{2}-f(i)^{2})\text{ },\text{
}\frac{1}{2}g(i)f(i)\right)\text{ }$ $\displaystyle\text{where we can directly
compute }f(i)\text{ and }g(i)$

To apply this method to the general case of Pell’s Equation (where $d$ is
square-free but not necessarily prime), since $d$ is square-free, it can be
written as $d=\prod\limits_{k=1}^{r}p_{k}$ where the $p_{k}$’s are rational
primes. So it suffices to study the case where $d=pq$ for primes $p$ and $q$
and deduce the general case by induction. We will not describe said case in
depth here since this paper mainly focuses on prime cyclotomic fields, but we
remark that taking $\mathbb{Q}(\zeta_{pq})$,
$m_{pq}(x)=m_{p}(x)m_{q}(x)\frac{(x^{pq}-1)/(x-1)}{((x^{p}-1)/(x-1))\cdot((x^{q}-1)/(x-q))}=\frac{(x^{pq}-1)(x-1)}{(x^{p}-1)(x^{q}-1)}$
which can be shown to be irreducible by a similar method as the simple proof
for showing that $\sum\limits_{k=0}^{p-1}x^{k}$ is the minimal polynomial of
$\zeta_{p}$ in $\mathbb{Z}[x]$. Following the same reasoning as in the case
where $d=p$, we can write $4m_{pq}(x)=f(x)^{2}\pm pqg(x)^{2}$ where
$f(x),g(x)\in\mathbb{Z}$. The rest of the problem is solved in a similar
fashion as well.

Using some interesting approximation methods and quadratic number fields,
Ireland & Rosen [5] show that $x^{2}-dy^{2}=1$ has _infinitely many solutions_
for any square-free integer $d$ (including $d=2$), and that every solution has
the form $\pm(x_{n},y_{n})$ where
$x_{n}+\sqrt{d}y_{n}=(x_{1}+\sqrt{d}y_{1})^{n}$ for some solution
$(x_{1},y_{1})$ and $n\in\mathbb{Z}$.

Acknowledgment

_Many thanks to Professor Dan Segal, All-Souls College, Oxford, for his
advice._

## References

  * [1] Borevich, Z. I., and Shafarevich I. R., Number Theory, Academic Press, New York, 1973.
  * [2] C. S. Dalawat, Primary units in cyclotomic fields, Annales des sciences mathématiques du Québec to appear, 2011.
  * [3] G. L. Dirichlet, Sur la manière de résoudre l’équation $t^{2}-pu^{2}=1$ au moyen des fonctions circulaires, Journal für die reine und angewandte Mathematik 17, pp. 286-290, 1837.
  * [4] V. Flynn, Algebraic Number Theory Lecture Notes. University of Oxford. Oxford Mathematical Institute, Oxford, UK. 2011. Lecture Notes.
  * [5] K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, Springer-Verlag, New York, 1982.
  * [6] S. Lang, Algebraic Number Theory, Springer-Verlag, New York, 1986.
  * [7] L. C. Washington, Introduction to Cyclotomic Fields, Springer-Verlag, New York, 1982.


# 1st Place Solution for the UVO Challenge on Image-based Open-World
Segmentation 2021

Yuming Du1 Wen Guo2 Yang Xiao1 Vincent Lepetit1
1 LIGM, Ecole des Ponts, Univ Gustave Eiffel, CNRS, Marne-la-Vallée, France
2 Inria, Univ. Grenoble Alpes, CNRS, Grenoble INP, LJK, 38000 Grenoble, France
{yuming.du, yang.xiao<EMAIL_ADDRESS><EMAIL_ADDRESS>
https://github.com/dulucas/UVO_Challenge

###### Abstract

We describe our two-stage instance segmentation framework we use to compete in
the challenge. The first stage of our framework consists of an object
detector, which generates object proposals in the format of bounding boxes.
Then, the images and the detected bounding boxes are fed to the second stage,
where a segmentation network is applied to segment the objects in the bounding
boxes. We train all our networks in a class-agnostic way. Our approach
achieves the first place in the UVO 2021 Image-based Open-World Segmentation
Challenge.

##  1 Method

In this section, we present our method for open-world instance segmentation.
Our method consists of two stages, the first stage is an anchor-based object
detection network that predicts bounding boxes for objects in the images. The
second stage consists of a segmentation network, which takes the image and the
bounding box as input and segments the object in the bounding box. Thanks to
this architecture, we can train the detection network and segmentation network
separately on different datasets, instead of following an “end-to-end”
training approach. The large input size of segmentation network results in
finer and better mask predictions.

###  1.1 Detection

In this section, we introduce the object detection network we used and the
techniques adopted that help to improve the recall of the object detector. An
overview of our network architecture is shown in Figure 1.

---
Figure 1:  Overview of our detection network architecture. DCN stands for
Deformable Convolutional neural Network[4].

#### Baseline.

We adopt the Region Proposal Network (RPN) of [20] as our baseline network.
Our backbone network consists of a ResNet-50[12] network with the Feature
Pyramid Network (FPN) of [15] for multi-scale feature extraction. A
classification head and a regression head are used for predicting the
“objectness” of the region contents and for bounding box regression,
respectively.

#### Cascade Region Proposal Network (RPN).

To further improve the quality of the predicted object proposals, as in [24],
we adopt a two-stage cascade architecture for proposal generation. Only one
single anchor is used for each location in the feature maps. The predicted
bounding boxes from the first stage are used as the input for the second
stage. Adaptive convolution is used to solve the misalignment between the
anchors and the features throughout the stage. The Focal loss [16] is used for
classification and GIoU loss [21] for bounding box regression.

#### IoU Branch.

In addition to the classification and bounding box branches, we use an IoU
branch, which predicts the IoU between the predicted bounding boxes and the
ground truth bounding boxes. During inference, the objectness score is
calculated as the geometric mean of the predicted IoU score and the
classification score, as also done in [13, 9] for example.

#### Decoupled Heads.

Decoupled heads have been widely used in previous works [9, 23] and have been
demonstrated to be effective to ease the conflict between the classification
and regression tasks in object detection. We adopt decoupled heads in our
network. Heads across all pyramid levels share the same weights to save
memory. We further replace the first convolutional layer of the decoupled
heads with deformable convolutional layers [4] and we will show in the later
section that this could further improve our results.

#### Proposal Sampling.

Label assignment aims to define positive/negative samples during training. We
replace the IoU-based label assignment with the SimOTA label assignment [9] in
our network. SimOTA is a simplified version of OTA label assignment [8], which
formulates the label assignment as an Optimal Transport (OT) problem and finds
the negative/positive samples by measuring their transportation costs to
ground truth bounding boxes. Instead of using the Sinkhorn-Knopp algorithm,
SimOTA simply takes the top-K candidates that are centered at the center of
the ground truth bounding boxes. In addition to this, we adopt different
negative/positive label assignment strategies for classification head and
regression head. In particular, instead of using one SimOTA for both
classification and regression, we use two SimOTAs with different
hyperparameters for classification and regression respectively. Compared to
the SimOTA for classification, the one for regression assign more positive
samples for candidate anchors during training. For the regression head, we
loose the selection criterion to generate more positive samples.

#### Non-maximum suppression (NMS).

Non-maximum suppression is used to remove duplicate bounding boxes. We set our
NMS threshold to 0.8.

#### Feature Pyramid Network (FPN).

We further add CARAFE [25] blocks in our FPN [15] network for a better feature
upsampling.

#### Backbone.

We use the recent Swin-L transformer [18] as our backbone network.

###  1.2 Segmentation

The segmentation network we used for this challenge is based on the Upernet
[27] architecture and the Swin-L transformer [18] as the backbone network. The
input consists of images and predicted bounding boxes, the bounding boxes are
first used to crop the images to image patches. Then, the image patches are
all resized to 512$\times$512 regardless of their height/width ratios.

##  2 Dataset

###  2.1 Detection

ImageNet 22k is used to pre-train our backbone network. We then train our
detectors on the COCO dataset [17]. Finally, the pre-trained detectors are
fine-tuned on the UVO-Sparse dataset and the UVO-Dense dataset [26].

###  2.2 Segmentation

ImageNet 22k [5] is used to pre-train our backbone network. We then train our
segmentation network on a combination of the OpenImage [14], PASCALVOC [6],
and COCO [17] datasets. Finally, the pre-trained segmentation networks are
fine-tuned on the UVO-Sparse dataset and the UVO-Dense dataset [26].

---
Figure 2:  Some of our predictions on the UVO-Sparse test dataset. The
predicted bounding boxes and segmented objects are shown in red. Our
segmentation network can segment the object regardless the motion blur, strong
occlusion, extreme pose etc.

##  3 Implementation Details

###  3.1 Detection

We use MMDetection [1] to train our detectors. For the backbone network, we
get the Swin-L transformer pre-trained on ImageNet 22k from
111https://github.com/microsoft/Swin-Transformer. All our detectors are
trained with Detectron ‘1x’ setting. For data augmentation, we use the basic
data augmentation strategy as in [11] for all experiments. The center ratio of
both SimOTA samplers are set to 0.25, the top-K number for classification head
is set to 10, while the top-K number for regression head is set to 20 to
involve more positive samples. Four 3$\times$3 conv layers are used in the
classification branch and the regression head, IoU branch shares the same conv
layers with the regression branch. To train the detector with Swin-L
transformer backbone, we adopt the AdamW as the optimizer and set the init
learning rate to 1e-4. The batch size is set to 16. After training on COCO, we
fine-tune the detector on the combination of UVO-Sparse dataset and UVO-Dense
dataset for 6 epochs. All our detectors are trained in the class-agnostic way.
Test time augmentation is used during inference to further boost the network
performance.

###  3.2 Segmentation

We use MMSegmentation [2] to train our segmentation network. We use the same
backbone network as our detection network. During training, given an image and
an instance mask, we first generate a bounding box that envelopes the instance
mask, then a 20 pixel margin is added to the bounding box in all directions.
We use the generated bounding box to crop the image and resize the image patch
to 512$\times$512\. Random flipping, random photometric distortion, and random
bounding box jitter are used as data augmentation. We adopt ’poly’ learning
rate policy and set the initial learning rate to 6e-5. The batch size is set
to 32 and AdamW[19] is used as the optimizer. We first train our network on
the combination of the OpenImage [14], PASCALVOC [6] and COCO [17] datasets
for 300k iterations, then we finetune the network on the combination of the
UVO-Dense and UVO-Sparse datasets for 100k iterations with initial learning
rate set to 6e-6. All our segmentation networks are trained in a class-
agnostic way, thus, segmenting the object in the cropped path becomes a
foreground/background segmentation problem. Only flip test augmentation is
adopted during inference.

| $AR@100$ | $AR@300$ | $AR@1000$
---|---|---|---
Baseline (Res50-FPN RPN) | 44.6 | 52.9 | 58.3
\+ Cascasde RPN | 61.1 | 67.6 | 71.7
\+ SimOTA + IoU Branch | 62.6 | 68.1 | 71.7
\+ Decoupled Head | 64.5 | 69.8 | 73.1
\+ Two samplers | 64.8 | 70.1 | 73.6
\+ CARAFE | 65.2 | 70.4 | 73.9
\+ DCNv2 | 65.6 | 70.8 | 74.2
\+ Swin-L | 70.7 | 74.9 | 77.4

Table 1: Ablation study on the different components of our method on COCO
val2017.

Teams | $AR@100$ | $AP$ |<EMAIL_ADDRESS>|<EMAIL_ADDRESS>| $AR@1$ | $AR@10$
---|---|---|---|---|---|---
lll_uvo | 33.39 | 22.60 | 41.23 | 22.08 | 7.49 | 27.49
FUFU | 36.58 | 21.43 | 41.04 | 20.62 | 6.83 | 26.63
FUFUUVO | 38.36 | 21.47 | 42.24 | 20.44 | 6.42 | 26.37
CASIT_UVO | 39.33 | 21.59 | 42.32 | 20.38 | 6.45 | 26.37
Jinzhao_Zhou(80_1) | 39.91 | 22.30 | 43.76 | 20.77 | 6.86 | 27.45
Baseline by host | 41.43 | 23.62 | 45.06 | 22.83 | 6.98 | 27.76
WRTC | 58.06 | 39.22 | 64.07 | 41.62 | 9.17 | 40.05
UAT | 60.61 | 38.40 | 62.17 | 40.86 | 9.40 | 41.32
Ours | 61.77 | 39.73 | 59.87 | 42.95 | 9.71 | 40.61

Table 2: Challenge final results on the UVO-Sparse test dataset. Our method
surpasses the baseline and other teams by a large margin.

##  4 Ablation Study

###  4.1 Detection

In this section, we ablate the different components in our detection network.
We train and evaluate our detectors using COCO train2017/val2017. The results
are shown in Table 2.

##  5 Visualization

We visualize the results predicted by our segmentation network given images
and bounding boxes in Figure 2. Our method results in high quality mask
predictions.

##  6 Potential Improvements

#### More training data.

We only pre-train our detectors on the COCO dataset, while recent works[22]
show that pre-training on some large datasets like [22, 14] can further
improve the performance of detectors. With more classes and more objects of
different shapes and geometries, the detectors might learn a better
representation which helps to find more objects and better localize them.

#### Data augmentation.

Our detectors are all trained using naive data augmentation like resize, flip,
etc. Recent works [10, 7, 3] show that object detectors can largely benefit
from strong data augmentation. Adding data augmentation might further improve
the performance of our network.

#### Misc.

Some hyperparameters are still chosen arbitrarily, including the number of
training epochs for fine-tuning on the UVO-Sparse and UVO-Dense datasets and
the hyperparameters for label assignment. Tuning these hyperparameters could
lead to better performance.

## References

  * [1] Kai Chen, Jiaqi Wang, Jiangmiao Pang, Yuhang Cao, Yu Xiong, Xiaoxiao Li, Shuyang Sun, Wansen Feng, Ziwei Liu, Jiarui Xu, Zheng Zhang, Dazhi Cheng, Chenchen Zhu, Tianheng Cheng, Qijie Zhao, Buyu Li, Xin Lu, Rui Zhu, Yue Wu, Jifeng Dai, Jingdong Wang, Jianping Shi, Wanli Ouyang, Chen Change Loy, and Dahua Lin.  MMDetection: Open mmlab detection toolbox and benchmark.  arXiv preprint arXiv:1906.07155, 2019.
  * [2] MMSegmentation Contributors.  MMSegmentation: Openmmlab semantic segmentation toolbox and benchmark.  https://github.com/open-mmlab/mmsegmentation, 2020.
  * [3] Ekin D Cubuk, Barret Zoph, Dandelion Mane, Vijay Vasudevan, and Quoc V Le.  Autoaugment: Learning augmentation policies from data.  arXiv preprint arXiv:1805.09501, 2018.
  * [4] Jifeng Dai, Haozhi Qi, Yuwen Xiong, Yi Li, Guodong Zhang, Han Hu, and Yichen Wei.  Deformable convolutional networks.  In Proceedings of the IEEE international conference on computer vision, pages 764–773, 2017.
  * [5] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei.  ImageNet: A Large-Scale Hierarchical Image Database.  In CVPR09, 2009.
  * [6] Mark Everingham, Luc Van Gool, Christopher KI Williams, John Winn, and Andrew Zisserman.  The pascal visual object classes (voc) challenge.  International journal of computer vision, 88(2):303–338, 2010.
  * [7] Hao-Shu Fang, Jianhua Sun, Runzhong Wang, Minghao Gou, Yong-Lu Li, and Cewu Lu.  Instaboost: Boosting instance segmentation via probability map guided copy-pasting.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 682–691, 2019.
  * [8] Zheng Ge, Songtao Liu, Zeming Li, Osamu Yoshie, and Jian Sun.  Ota: Optimal transport assignment for object detection.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 303–312, 2021.
  * [9] Zheng Ge, Songtao Liu, Feng Wang, Zeming Li, and Jian Sun.  Yolox: Exceeding yolo series in 2021.  arXiv preprint arXiv:2107.08430, 2021.
  * [10] Golnaz Ghiasi, Yin Cui, Aravind Srinivas, Rui Qian, Tsung-Yi Lin, Ekin D Cubuk, Quoc V Le, and Barret Zoph.  Simple copy-paste is a strong data augmentation method for instance segmentation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2918–2928, 2021.
  * [11] Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick.  Mask r-cnn.  In Proceedings of the IEEE international conference on computer vision, pages 2961–2969, 2017.
  * [12] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [13] Borui Jiang, Ruixuan Luo, Jiayuan Mao, Tete Xiao, and Yuning Jiang.  Acquisition of localization confidence for accurate object detection.  In Proceedings of the European conference on computer vision (ECCV), pages 784–799, 2018.
  * [14] Ivan Krasin, Tom Duerig, Neil Alldrin, Vittorio Ferrari, Sami Abu-El-Haija, Alina Kuznetsova, Hassan Rom, Jasper Uijlings, Stefan Popov, Shahab Kamali, Matteo Malloci, Jordi Pont-Tuset, Andreas Veit, Serge Belongie, Victor Gomes, Abhinav Gupta, Chen Sun, Gal Chechik, David Cai, Zheyun Feng, Dhyanesh Narayanan, and Kevin Murphy.  Openimages: A public dataset for large-scale multi-label and multi-class image classification.  Dataset available from https://storage.googleapis.com/openimages/web/index.html, 2017.
  * [15] Tsung-Yi Lin, Piotr Dollár, Ross Girshick, Kaiming He, Bharath Hariharan, and Serge Belongie.  Feature pyramid networks for object detection.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2117–2125, 2017.
  * [16] Tsung-Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár.  Focal loss for dense object detection.  In Proceedings of the IEEE international conference on computer vision, pages 2980–2988, 2017.
  * [17] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick.  Microsoft coco: Common objects in context.  In European conference on computer vision, pages 740–755. Springer, 2014.
  * [18] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo.  Swin transformer: Hierarchical vision transformer using shifted windows.  arXiv preprint arXiv:2103.14030, 2021.
  * [19] Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization.  arXiv preprint arXiv:1711.05101, 2017.
  * [20] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun.  Faster r-cnn: Towards real-time object detection with region proposal networks.  Advances in neural information processing systems, 28:91–99, 2015\.
  * [21] Hamid Rezatofighi, Nathan Tsoi, JunYoung Gwak, Amir Sadeghian, Ian Reid, and Silvio Savarese.  Generalized intersection over union: A metric and a loss for bounding box regression.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 658–666, 2019.
  * [22] Shuai Shao, Zeming Li, Tianyuan Zhang, Chao Peng, Gang Yu, Xiangyu Zhang, Jing Li, and Jian Sun.  Objects365: A large-scale, high-quality dataset for object detection.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 8430–8439, 2019.
  * [23] Zhi Tian, Chunhua Shen, Hao Chen, and Tong He.  Fcos: Fully convolutional one-stage object detection.  In Proceedings of the IEEE/CVF international conference on computer vision, pages 9627–9636, 2019.
  * [24] Thang Vu, Hyunjun Jang, Trung X Pham, and Chang D Yoo.  Cascade rpn: Delving into high-quality region proposal network with adaptive convolution.  arXiv preprint arXiv:1909.06720, 2019.
  * [25] Jiaqi Wang, Kai Chen, Rui Xu, Ziwei Liu, Chen Change Loy, and Dahua Lin.  Carafe: Content-aware reassembly of features.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 3007–3016, 2019.
  * [26] Weiyao Wang, Matt Feiszli, Heng Wang, and Du Tran.  Unidentified video objects: A benchmark for dense, open-world segmentation.  arXiv preprint arXiv:2104.04691, 2021.
  * [27] Tete Xiao, Yingcheng Liu, Bolei Zhou, Yuning Jiang, and Jian Sun.  Unified perceptual parsing for scene understanding.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 418–434, 2018.