# High-Performance Sorting-Based $k$-mer Counting in Distributed Memory with
Flexible Hybrid Parallelism

Yifan Li<EMAIL_ADDRESS>Tsinghua University30 Shuangqing
RdBeijingChina43017-6221 and  Giulia Guidi<EMAIL_ADDRESS>Cornell
University107 Hoy RdIthacaNYUSA

(2024)

###### Abstract.

In generating large quantities of DNA data, high-throughput sequencing
technologies require advanced bioinformatics infrastructures for efficient
data analysis. $k$-mer counting, the process of quantifying the frequency of
fixed-length $k$ DNA subsequences, is a fundamental step in various
bioinformatics pipelines, including genome assembly and protein prediction.
Due to the growing volume of data, the scaling of the counting process is
critical.

In the literature, distributed memory software uses hash tables, which exhibit
poor cache friendliness and consume excessive memory. They often also lack
support for flexible parallelism, which makes integration into existing
bioinformatics pipelines difficult. In this work, we propose HySortK, a highly
efficient sorting-based distributed memory $k$-mer counter. HySortK reduces
the communication volume through a carefully designed communication scheme and
domain-specific optimization strategies. Furthermore, we introduce an abstract
task layer for flexible hybrid parallelism to address load imbalances in
different scenarios.

HySortK achieves a 2-10$\times$ speedup compared to the GPU baseline on 4 and
8 nodes. Compared to state-of-the-art CPU software, HySortK achieves up to
2$\times$ speedup while reducing peak memory usage by 30% on 16 nodes.
Finally, we integrated HySortK into an existing genome assembly pipeline and
achieved up to $1.8\times$ speedup, proving its flexibility and practicality
in real-world scenarios.

Distributed Memory, Performance Analysis, $k$-mer Counting, Computational
Biology, Parallel Radix Sort, Genome Analysis

††copyright: acmlicensed††journalyear: 2024††copyright:
rightsretained††conference: The 53rd International Conference on Parallel
Processing; August 12–15, 2024; Gotland, Sweden††booktitle: The 53rd
International Conference on Parallel Processing (ICPP ’24), August 12–15,
2024, Gotland, Sweden††doi: 10.1145/3673038.3673072††isbn:
979-8-4007-1793-2/24/08

##  1\. Introduction

A $k$-mer, i.e. a substring of fixed length $k$, plays a crucial role in
various bioinformatics pipelines (Hofmeyr et al., 2020; Guidi et al., 2021b;
Selvitopi et al., 2020; Nurk et al., 2020). $K$-mer counting is a common
operation where we count the frequency of $k$-mers in a given dataset of DNA
sequences, also known as _reads_. Usually, the distribution of $k$-mers or
$k$-mers with frequencies in a certain range is collected for further
analysis. In genome assembly and pangenomics analysis, for example, $k$-mers
are used to identify potential seed matches between sequences for subsequent
fine-grained alignment, commonly known as the “seed and extend” pattern (Yan
et al., 2021; Guidi et al., 2021b; Rautiainen and Marschall, 2020).
Furthermore, statistical studies, including recent machine learning approaches
(Dhibar and Jana, 2023), treat $k$-mers as features in datasets for learning
and inference purposes. Precise and efficient counting of $k$-mer frequencies
is at the core of all these applications.

In recent years, advances in high-throughput sequencing technologies have led
to an exponential increase in the size of genomic datasets. In particular,
long-read sequencing technologies, characterized by a longer sequence (read)
length, have gained popularity. This increase in data promotes new
applications or studies with greater precision but also poses a challenge for
bioinformatics software. The size of input data frequently surpasses the
memory capacity of a single machine, resulting in performance degradation when
relying on I/O performance or, in some cases, out-of-memory failures. The
$k$-mer counting task is sensitive to the growing amount of data, as this is
usually the first stage of a workflow and filtering the input data is often
not an option (Georganas et al., 2015; Baaijens et al., 2022; Breitwieser et
al., 2018). Therefore, there is an urgent need for efficient $k$-mer counters
with distributed memory.

However, parallelizing $k$-mer counting in distributed memory is a non-trivial
task. The runtimes of MetaHipMer2, a short-read _de novo_ metagenome
assembler, show that the $k$-mer counting stage can take almost 50% of the
total time (Awan et al., 2021). In contrast to other stages, it is not
possible to partition the input data directly into non-contiguous regions of
the genome and treat the $k$-mer count in an embarrassingly parallel manner.
Due to the short $k$-mer length, the error rate of the experimental sequencing
process, and the intrinsic repetitiveness of biological sequences, there is no
guarantee that the instances of a $k$-mer subsequence will appear in a precise
and individual part of the generated dataset (Guidi et al., 2021a). Both data
structure and algorithms must be adapted for a distributed memory scenario.
Crucially, when leveraging the computing power of multiple machines or nodes,
a substantial portion of the total time is spent on communication. Optimizing
communication is critical.

To overcome these challenges, we propose a novel radix sort-based distributed
memory $k$-mer counter: HySortK 111Our code is available
athttps://github.com/CornellHPC/HySortK. To date, most distributed memory
software has relied on hash tables to determine the$k$-mer frequency (Hofmeyr
et al., 2020; Guidi et al., 2021b; Nisa et al., 2021; Pan et al., 2018). Yet,
concurrent access to hash tables can be difficult, they consume more memory
and are not very efficient due to their random memory access pattern. In
contrast, we take a different approach by using array data structures for
$k$-mer storing and relying on radix sort and linear scan to determine their
frequency. Radix sorting can be performed in-place, reducing peak memory usage
and eliminating the need for the Bloom filter. This eliminates the need for a
round of data exchange and significantly reduces communication time. In
addition, we introduce a domain-specific compression method to reduce the
communication volume. To maintain high performance and support flexible hybrid
parallelization (i.e., any number of MPI processes and OpenMP threads per
processor), we introduce an abstraction layer of tasks between MPI processes
and OpenMP threads. Furthermore, with task-based parallelization, we can
effectively address load-balancing issues. Our main contributions include:

  * •

Here, we redesign the distributed $k$-mer counting task as a sort-based
problem instead of a hash table-based problem, which reduces random memory
access and memory usage. In HySortK, we improve the supermer strategy and use
a hash function to ensure order. Our supermer partitioning introduces a new
method to find minimizers for consecutive $k$-mers in a genomic sequence.

  * •

HySortK uses flexible hybrid MPI and OpenMP parallelization so that it can be
seamlessly integrated into existing pipelines with improved performance.
HySortK was integrated into a _de novo_ long-read genome assembly workflow.
The hybrid approach enables us to introduce a task abstraction layer to
address load imbalances in specific scenarios.

  * •

HySortK is $2$-$10\times$ faster than GPU approaches. It has shown up to
$2\times$ speedup and up to $3\times$ lower memory usage compared to state-of-
the-art CPU software. Finally, integration into a distributed memory genome
assembly workflow has resulted in an end-to-end speedup of up to $1.8\times$.

##  2\. Background

In this section, we describe $k$-mer counting, common parallel approaches to
its implementation, and existing parallel sorting approaches. Finally, we
describe the supermer optimization strategy.

###  2.1. $k$-mer Counting

The $k$-mer counting process involves counting the occurrence of subsequences
with a length of $k$ nucleotides (A, C, T, G) in genomic or transcriptomic
data. It is common for a genomics pipeline to begin by enumerating $k$-mer
frequencies in the input data (Nurk et al., 2020; Jonkheer et al., 2022). The
resulting $k$-mer histogram is critical for understanding the distribution of
genomic subsequences, profiling genomic and metagenomic data, identifying
scientifically relevant $k$-mers based on their abundance, and more. The
histogram serves as the basis for various downstream analyses, such as the
representation of a de Bruijn graph (Georganas et al., 2015), the generation
of large-scale sequence search indices (Jonkheer et al., 2022), and weighted
locus locality-sensitive hashing (Marçais et al., 2019).

Figure 1. Overview of the common paradigm for distributed memory $k$-mer
counting pipelines using hash-tables.

The input irregularity due to biology and the experimental sequencing process
poses a major challenge for the parallelization of $k$-mer counting in
distributed memory. In particular, the distribution of $k$-mers in the
biological input is not fixed and can only be determined at runtime. In the
literature, scalable distributed memory $k$-mer counting mainly relies on hash
tables.

###  2.2. Parallel $k$-mer Counting

This section provides an overview of common practices for counting $k$-mers in
distributed memory. Common distributed $k$-mer counter software, including
DEDUKT (Nisa et al., 2021), a GPU-based tool, the $k$-mer counting module of
ELBA (Guidi et al., 2021b), a distributed memory _de novo_ long-read genome
assembler, and the $k$-mer counting module of PaKman (Ghosh et al., 2020)
follow the general approach proposed by Georganas et al. (Georganas et al.,
2014). It includes three main stages: (1) local reading and parsing of
$k$-mers, (2) exchange of $k$-mers, and (3) local counting of $k$-mers. In
addition, DEDUKT uses the $supermer$ concept to reduce communication. The
process of encoding and decoding $k$-mers is added to the first and last
stages, and the exchange of $k$-mers is replaced by the exchange of supermers
in the second stage.

In Figure 1, the sequences from the input file are divided evenly between the
processes using a greedy algorithm. The processes then independently read
batches of sequences, encode the sequences, and parse them into $k$-mers (1).
The processes use the same hash function and mod operation as a mapping
function to compute an identifier (ID) for each $k$-mer and divide the local
$k$-mer set into groups based on such function. The uniform hash function
ensures that $k$-mers with the same value have the same identifier.

The second stage (2) is the most communication-intensive, in which the
$k$-mers are distributed in groups to different target processes based on
their respective IDs. Depending on the application, we may want to exchange
only the $k$-mer itself or both the $k$-mer and its _extension_ information.
The extension information of a $k$-mer includes the ID of the read (i.e., a
DNA sequence) from which the $k$-mer was extracted and the position of the
$k$-mer in this read. This stage, which resembles an all-to-all exchange, can
extend over several rounds due to memory constraints or a large number of
processes. A common strategy is a two-pass approach that aims to filter out
erroneous $k$-mers and reduce memory footprint. This often comes at the cost
of increased communication. Before the first communication run, where $k$-mers
are exchanged, a Hyperloglog data structure (Flajolet et al., 2007) is used to
estimate the number of unique $k$-mers instances. Hyperloglog data structures
are first built locally and then merged globally. The communication volume
during this phase does not depend on the size of the data set but is a
function of the parameter $k$. The time required is negligible and we do not
consider it as a pass, even though it is referred to as the first pass in
Georganas et al. (Georganas et al., 2014). Once the number of unique $k$-mers
is estimated, a Bloom filter is constructed accordingly. In the first pass,
$k$-mers are exchanged without the extension information and inserted into the
Bloom filter of the target process. In the second pass, $k$-mers are then
exchanged together with the extension information, if this information is
needed. In the target process, the hash table created in the first pass is
used to filter out singletons, which are considered to be the result of
sequencing errors.

In the third stage (3), the counting takes place, which requires no additional
communication. Using a hash table-based approach, the $k$-mers coming through
the Bloom filter in the second exchange pass are often inserted into a
temporary array and then inserted into the hash table. The hash table serves
as a counter, recording the value of the $k$-mer, its appearance frequency,
and the possible extension information. Each local hash table entry
corresponds to a ¡key, value¿ pair, where the key is the $k$-mer itself and
the value is the frequency. The $k$-mer value must be stored as collisions are
possible and correctness should be ensured if the chaining or open addressing
method is used. The method described above can generally be regarded as a
distributed hash table approach.

###  2.3. Parallel Sorting

The exponential growth of data in various areas has made more efficient
sorting methodologies necessary. As modern hardware is mostly composed of
multicore architectures, the literature focuses on the use of thread-level
parallelism to increase performance.

In most cases, one of two strategies is used for multicore sorting: top-down
or bottom-up (Cho et al., 2015). In the first strategy, the input dataset is
first partitioned based on the key, with each group then sorted independently.
In contrast, the second approach divides the dataset without a specific rule
to facilitate load balancing and the results are merged after each partition
has been sorted independently.

The radix sort algorithm is well suited for multicore parallelization (Kokot
et al., 2017a). Its theoretical complexity is $\mathcal{O}(n\cdot d)$, which
makes it more efficient for large input data than comparison-based algorithms,
where $n$ is the number of items to be sorted and $d$ is a constant dependent
on $k$. In contrast, comparison-based algorithms have a higher lower bound of
$\mathcal{O}(n\log n)$. PARADIS (Cho et al., 2015) is a parallel in-place
radix sort algorithm known for its low memory footprint and its use of
adaptive load balancing to minimize overall processing time. RADULS, another
parallel radix sort algorithm, was developed for the efficient management of
very large datasets (Kokot et al., 2017a). It is cache-friendly optimized for
modern hardware and requires more physical memory as it is not an in-place
algorithm. RADULS has been successfully implemented in a shared memory $k$-mer
counter (Kokot et al., 2017b). Our $k$-mer counter, HySortK, uses both PARADIS
and RADULS and switches between the two depending on the available memory.

###  2.4. Supermer

The $k$-mer counting problem makes it possible to adopt some domain-specific
optimization strategies, such as the $supermer$ concept. A $supermer$, or
super $k$-mer, is a contiguous sequence of DNA bases. The length of each
supermer is greater than or equal to $k$, the length of $k$-mers. It is
important to note that $k$-mers extracted from the supermer should have the
same target process. The overlapping subsequence of these $k$-mers is not
exchanged repeatedly, which reduces the communication volume many times over.
However, the naïve way of assigning $k$-mers to processes can lead to a low
probability that adjacent $k$-mers belong to the same process. Therefore,
$m$-mer and $minimizer$ are proposed to address this problem.

A $m$-mer is defined as a length $m$ subsequence of DNA bases, where $m$ is
smaller than $k$. Each $k$-mer thus includes multiple $m$-mers. A minimizer is
the $m$-mer of a $k$-mer with the lowest score for a function $f$. The target
process of the $k$-mer is no longer determined by the hash value of the
$k$-mer itself but by the hash value of the minimizer. Consecutive $k$-mers
are likely to share the same minimizer, which increases the probability that
adjacent $k$-mers will be assigned to the same target process. As a result,
supermers reduce the data exchange volume many times over.

The supermer concept was originally proposed by MSP (Li et al., 2015). Later
$k$-mer counters, such as KMC3 (Kokot et al., 2017b) and DEDUKT (Nisa et al.,
2021), have also adopted this approach. The literature has focused on choosing
a reasonable score function $f$. Computational complexity and load balance are
the main concerns when choosing a score function. Common score functions
include modified lexical ordering and randomized arithmetic computation.

##  3\. Methodologies

In this section, we describe our approach and the optimization strategies we
have implemented. Our approach has four main differences compared to state-of-
the-art CPU-based software:

  1. (a)

First, the method for counting $k$-mers is changed from a hash-table-based
approach to a sorting-based approach;

  2. (b)

Our approach uses the $supermer$ concept to reduce the volume of data
exchange. To improve the traditional supermer approach (Li et al., 2015), we
use a hash function to determine the order of $m$-mers and a linear method to
find the minimizers of consecutive $k$-mers independent of the length $k$. The
optimized supermer strategy improves load balance with negligible additional
computation.

  3. (c)

By combining the sort-based approach and careful supermer optimization,
HySortK significantly reduces the memory footprint, making a BLOOM filter
superfluous. Consequently, the exchange no longer takes place in two passes.
Each $k$-mer is exchanged at most once, which further reduces the
communication volume.

  4. (d)

HySortK uses a task abstraction layer to enable flexible hybrid
parallelization with OpenMP and MPI. In addition, the task design enables the
detection of frequent $k$-mers (or _heavy hitters_) with low overhead, while
providing efficient methods to address load imbalance.

###  3.1. Sorting-Based $k$-mer Counting

A key component of HySortK is the sorting-based approach, which is both
flexible and efficient. Similar strategies have been identified in KMC3 (Kokot
et al., 2017b), but to the best of our knowledge not for distributed memory.
The latest version of kmerind (Pan et al., 2018) introduces a sorting-based
approach. However, it is based on inter-process sample sort and is slower than
kmerind based on hash tables.

In this section, we present our approach, address the challenges arising from
the popular hash table approach, and explain how our approach addresses these
challenges.

The backbone of HySortK is similar to the approach described in Section 2.2.
In the first stage, the sequences are parsed locally into $k$-mers, in the
second stage $k$-mers are exchanged across processes, and in the third stage,
the $k$-mers are counted locally in each process. The differences between the
hash table approach and the sorting approach are mainly consolidated in the
third stage.

In particular, the $k$-mers remain in the receive buffer after the exchange
phase and wait for the local count. HySortK does not create redundant copies
as it computes a parallel multithreaded in-place radix sort to reorder the
$k$-mer instances according to the value directly in the buffered data. Only
when more memory resources are available, HySortK switches to a more efficient
radix sort algorithm that requires an auxiliary array for counting. In both
cases, it is guaranteed that $k$-mers with the same value fall into adjacent
places after sorting. The threads scan the sorted array to count the time of
occurrence of each $k$-mer, which is a linear time complexity operation.
Depending on the application, we can record only the final counting histogram
or copy the $k$-mers that meet our requirements to another array for further
indexing and querying.

Our approach relies on the efficiency of the sort algorithm. Radix sort is
chosen because its time complexity is $\mathcal{O}(n\cdot d)$, where $n$ is
the size of the $k$-mer array and $d$ is a constant with respect to $k$, the
length of each $k$-mer. In HySortK, we use the PARADIS and RADULS sorting
algorithm, as proposed by (Cho et al., 2015) (Kokot et al., 2017a). RADULS is
faster but uses more memory. In HySortK, the processes read the system status
after the exchange phase to estimate the available memory. If sufficient
memory is available for out-of-place sorting, RADULS is used, otherwise
PARADIS.

Hash tables often suffer from slow performance and high memory usage, as they
require up to twice the memory of the stored data due to the additional
structures required and a standard load factor of 0.7 (Richter et al., 2015).
Efforts to reduce memory usage include filtering out infrequent elements
(e.g., singletons) and using Counting Bloom Filter (Ge et al., 2020), however,
these strategies may limit functionality or accuracy, respectively, and may
not be suitable for every application. Conversely, our sorting approach hardly
requires any additional space when memory resources are limited. HySortK
eliminates the need to discard singletons, thereby avoiding the earlier steps
of constructing the Bloom filter, saving considerable time while still
achieving superior memory efficiency.

Concurrency is a major challenge for hash tables when numerous insert
operations are required, such as when $k$-mer counting. One solution is to
manage the shared memory in a kind of distributed memory, where each thread is
responsible for a partition of $k$-mers. Pan et al. (Pan et al., 2018) chose
this approach to reduce communication time, as it theoretically does not
involve overhead. Empirically, however, this approach has proven to be
inefficient, as both Pan et al. and this work in Section 4 show. The sorting
approach facilitates multithreading scaling. Using less than or equal to 16
threads in our evaluation, linear or near-linear scaling can be achieved for
parallel sorting algorithms. The task abstraction layer we introduced provides
further relief. The overall performance gain from our optimization strategies
is $2-5\times$ compared to a baseline implementation with hash tables.

###  3.2. Optimized Supermer Strategy

Communication between nodes is often a bottleneck in distributed memory
$k$-mer counting. The supermer strategy presented in Section 2 is therefore
used to reduce the communication volume. In HySortK, we adopt and improve this
strategy by introducing a more efficient method for finding minimizers of
consecutive $k$-mers.

Figure 2. Overview of sorting-based $k$-mer counting using the supermer
strategy.

In HySortK, we use the same hash function to determine the minimizers of
$k$-mers and the corresponding destination process for each $minimizer$. The
hash value of each $m$-mer serves as its score, where the $m$-mer with the
lowest value is called the minimizer. The remainder of the hash value, divided
by the number of processes, determines the target for $k$-mers associated with
that minimizer. The goal is to balance the number of $k$-mers going to each
target to avoid load imbalance and longer execution times. Both the selection
of the minimizer and the decision on the target based on the minimizer are
critical to the performance of the supermer strategy.

The randomness of the hash function makes it a suitable choice for the score
function. A variety of hash functions are available, and empirically, we find
that a single hash function suffices for both finding minimizers and deciding
destinations. Research on the use of universal hash functions (Carter and
Wegman, 1977) as scoring functions is limited because these functions can
assign the same hash value to different elements, which can lead to different
minimizers and thus target processes being assigned to $k$-mers with the same
value. In addition, they usually require more computation than simpler
methodologies.

To solve the first problem, we use the same hash function to search for
minimizers and to decide on the target to ensure correctness even if different
minimizers are assigned to $k$-mers with the same value. In the rare case that
multiple $m$-mers of a $k$-mer collide in their hash value, the $k$-mer will
be assigned to the same target regardless of which $m$-mer is chosen as the
minimizer. Even if two different hash functions are used, a simple strategy
can be applied to eliminate all potential errors. If multiple $m$-mers of a
single $k$-mer have the same hash value, a secondary comparison using the
lexical order can eliminate the uncertainty in the choice of minimizer and
effectively solve the problem.

To address the second problem, we choose a hash function that requires a
reasonable computation and propose a method to efficiently find minimizers.
Murmurhash3, previously used for hashing $k$-mers, is used due to its
randomness and low computational requirement. Computing the hash value of an
$m$-mer for minimizer saves computation in the decision process for the
target. Our evaluation shows that using a hash function can lead to an
increase in runtime of up to $2\times$ compared to a simple scoring function
such as lexical ordering. However, the overhead is negligible when considering
the overall runtime of the pipeline.

Furthermore, we optimize the strategy to find minimizers of consecutive
$k$-mers. Let us assume the length of a read (i.e., a DNA sequence) is $n$,
and we want to identify minimizers for its $k$-mers. DEDUKT (Nisa et al.,
2021) computes the $m$-mers for each $k$-mer independently, which can result
in redundant computation. The sliding window concept introduced by Li et al.
(Li et al., 2015) for finding minimizers involves scanning through the
$k$-mers in a read while preserving the score and position of the current
minimizer. The minimizer is updated if a better score is found; otherwise,
it’s retained. This method, though efficient, requires recalculating the valid
minimizers when the current one has “expired”, which can result in a high
computation.

Here, we implement an improved sliding window maximum value algorithm. First,
the read operation is performed as described by Li et al. (Li et al., 2015),
but instead of keeping a single variable for the current $minimizer$, a deque
is kept. Each element in the deque stores the score and position of a valid
$m$-mer. The elements in the deque are ordered monotonically, i.e. the
$m$-mers in the deque have increasing scores, which ensures that the front of
the deque stores the current $minimizer$. So when we move the sliding window
forward, we add at most one new $m$-mer to the deque and remove at most one.
To remove an expiring $m$-mer in the deque, we check the front part of the
deque. If the front element is the expiring $m$-mer, it is removed; otherwise
nothing is done. To insert an $m$-mer, we remove elements at the end of the
deque until the score of the end element is lower than that of the new $m$-mer
or the deque is empty, and then insert the new $m$-mer at the end. Correctness
is ensured by rule (a), which removes expired $k$-mers, and rule (b), which
stores $k$-mers in order within the deque. The sliding window only saves valid
minimizers, whereby the front element of the deque is always the current
minimizer. Thus, new entries either have a lower score or replace less
relevant entries, which ensures that the minimal element remains at the front.
Removed entries are replaced by better minimizers that appear later.

Our $supermer$ strategy resulted in $80\%$ less communication and a $3\times$
speedup in the exchange phase at $k=31$. Using Murmurhash3 as a scoring
function on a 31 GB _H. sapiens_ dataset, we obtained a balanced partitioning
of 256 batches with a standard deviation of batch size more than $10\ times$
smaller than the standard partitioning of KMC3, and a max-to-min ratio of only
$1.06$.

Figure 3. Overview of HySortK paradigm for distributed memory $k$-mer counting
with hybrid task parallelism.

###  3.3. Communication Optimization

HySortK reduces communication by replacing the two-pass approach with a one-
pass approach and applying the $supermer$ strategy. HySortK also introduces
two strategies to further reduce communication time in the second stage in
Figure 1, i.e. the most communication-intensive stage. The first strategy is
to overlap communication with computation while the second uses data
compression. Our data compression does not result in any data loss. HySortK
provides exact $k$-mer count.

####  3.3.1. Communication and computation overlap

Communication is divided into rounds. Each process is allowed to send a
limited number of bytes to other processes in a communication round. In
HySortK, we use Alltoall instead of Alltoallv because the regular pattern of
Alltoall generally provides better performance. However, when using Alltoall,
padding is required, which can lead to longer communication times if the
partition of $supermers$ is unbalanced. The non-blocking version Ialltoall is
called to support the overlap. Two send and receive buffers are allocated for
each process. The pointers to these buffers are swapped after each round.
Therefore, the data exchange for round $n$ can take place simultaneously with
the parsing of the receive buffer for round $n-1$ and the preparation of the
send buffer for round $n+1$.

####  3.3.2. Data compression

In genomics applications, such as genome assembly (Guidi et al., 2021b),
information about the extension of $k$-mers is sometimes required for
downstream analysis. Common information includes the read_id and pos_in_read
(i.e., location at which the $k$-mer is found in the sequence) for each
$k$-mer. Under a reasonable choice of $k$ (typically less than 63), this
information consumes more bytes than the $k$-mer value itself. Compression of
this extension information is therefore highly beneficial. In HySortK we
compress this information using domain-specific knowledge. The length of long
read sequences is usually between $1000$ and $20,000$ bases (Logsdon et al.,
2020), much larger than the total number of processes in most scenarios.
Consequently, there is a high probability that consecutive $k$-mers going to
the same destination process will have the same read_id, and the difference in
pos_in_read is usually small and in the range of a int8. So instead of using a
int32 field to capture the pos_in_read, we use a smaller int8 field to capture
the difference of its position to the last $k$-mer travelling to the same
destination. The same strategy applies to the read_id field. An additional
byte is reserved for each $k$-mer to indicate which type of compression
strategy is used. If the difference does not fit into the smaller field, the
entire extension information is exchanged. An encoder on the sending side
calculates the difference and decides whether to compress or not, while a
decoder on the receiving side analyses the information. This can also be
overlapped with the communication.

The overlapping of computation and communication led to a $1.4\times$ speedup.
The compression strategy reduced the communication volume by $50\%$ and led to
a further speedup of about $1.3\times$ when extension information is included.

###  3.4. Task Abstraction Layer

To support flexible hybrid parallelism, we have chosen a parallel radix sort
algorithm that can take advantage of multithreading. However, both RADULS and
PARADIS exhibit poor weak scaling performance once the number of threads
exceeds 16 in our experiments. To address this problem, we introduce task
parallelism in HySortK, which serves as an abstraction layer between processes
and threads. Distributed memory $k$-mer counters usually partition $k$-mers
into $p$ batches, where $p$ is the number of processes, similar to a
distributed hash table. Conversely, in HySortK, we partition the $k$-mers into
$s$ batches, where $s$ is a parameter chosen at runtime. Each batch is also
referred to as a _task_ , and each task is treated as an independent
processing unit, ensuring that $k$-mers with the same value can never belong
to two different tasks. Each task can be processed independently during the
sorting and linear scan phases.

In the last stage, in which $k$-mers are sorted and counted, the available
computing resources of a process are assigned to workers. A worker can
initiate several OpenMP threads, with each thread bound to a physical core.
Each worker is assigned some tasks and sorts them using the available
resources. Each worker processes the tasks independently, as shown on the
right in Figure 3.

By implementing hybrid task-based parallelism, we can utilize the numerous
physical cores of modern CPUs. By not starting too many processes on a single
node or using fine-grained parallelization at the thread level, we can reduce
scheduling overhead (Bull, 1999). In addition, instead of using all available
threads to sort an array, which can lead to sublinear weak scaling, we divide
the available cores into workers. The number of threads per worker is
constant.

The flexibility of task parallelism is also beneficial for the NUMA
architecture of modern machines: threads in different NUMA nodes can be
assigned to different tasks, eliminating implicit communication between NUMA
nodes. In practice, it is recommended to use at least one MPI process per NUMA
domain, since the threads of a process share certain data structures, such as
the MPI receive buffer. The default number of threads per worker is set to
$4$, which empirically provides great overall performance and flexibility.

Compared to the extreme cases where only one process or one process per
physical core is used, the hybrid approach of HySortK implemented using the
task abstraction layer achieves a speedup of up to $5.7\times$ on a 128-core
machine.

###  3.5. Optimized Load Balance

It is crucial to avoid load imbalances when implementing $k$-mer counting in
distributed memory. If using a bulk-synchronous parallel programming model
such as MPI, any load imbalance on one process can cause unnecessary wait
times for other processes, resulting in an overall slowdown. It is therefore
important to distribute the workload evenly across the processes. The task
abstraction of HySortK provides greater scheduling flexibility thus
eliminating low-to-medium load imbalances. Despite this, load imbalance can
still occur with certain input data.

Supermers are constructed and grouped, and the root process retrieves data
about the size of each task before assigning it to a target process. The
supermers are then routed for processing based on the assignment. The goal is
to minimize the largest sum of task sizes for a single process, similar to
solving the NP-complete Partition Problem (Karp, 2010). In HySortK, we use a
greedy approach to obtain an approximately optimal assignment. First, we
define an upper threshold for the sum of task sizes that is close to the
average size per process. Then, we try to assign the tasks to the processes
without exceeding the threshold. If the assignment is not successful, we
increase the threshold and try again. The procedure is repeated until a
successful assignment is made.

The hash function alone cannot guarantee that there is no severe load
imbalance due to an inherent feature of DNA data, namely genomic repetition.
For example, the human genome contains numerous repeats of $(AATGG)_{n}$
(Jaishree and Wang, 1994). This means that many of the $k$-mers extracted from
these areas have the same value. Consequently, regardless of the scoring
function used, the $supermers$ created from these areas will go to the same
target process, resulting in an unbalanced load in both the exchange and
counting stages. These frequent $k$-mers are often referred to as “heavy
hitters”.

In some studies, load imbalance in $k$-mer counting is addressed by
customizing the ordering of $m$-mers, but this approach does not completely
solve the problem. Tools such as HipMer identify and treat the heavy hitters
differently, which are first counted locally and then reduced globally
(Georganas et al., 2015). This reduces the imbalance during the local count,
but the imbalance remains during the exchange phase as $k$-mers still need to
be sent to their target process. In addition, detecting and filtering out
heavy hitters is resource-intensive. Conversely, our task-based design
provides a simple way to address this load imbalance. HySortK can collect
statistical information about the size of each task and use this information
as an indicator for the presence of potential heavy hitters.

If the task size reaches a certain threshold, which is typically the average
task size multiplied by a constant, we conclude that the task contains heavy
hitters and requires special handling. Compared to identifying specific
$k$-mers, identifying these tasks is effortless. Once these heavy-hitter tasks
are identified, we transform them locally, i.e. we no longer keep the
$supermers$, but the $k$-mers are extracted from the $supermers$, sorted, and
then counted locally. Then, tuples of ($k$-mer, count), which are referred to
as $kmerlist$ representation, are sent to the target processes. Once the
target processes have received the $kmerlist$, they perform another round of
sorting and counting the tuples. In the meantime, the other (non-heavy-hitter)
tasks are processed normally.

Our strategy shown in Figure 3 solves the load imbalance in both the exchange
and counting stages. In the exchange stage, for heavy-hitter tasks, the
$supermer$ compression strategy is no longer applicable, and an additional
field is used to store the count. The communication volume of a heavy-hitter
task is therefore generally larger than that of a normal task. However, the
$kmerlist$ representation eliminates the need to send identical $k$-mers
multiple times from the same process. The task abstraction further mitigates
the load imbalance in the exchange stage. Finally, $kmerlist$ is beneficial
for the counting stage, as fewer elements need to be sorted.

##  4\. Experimental Results

Table 1 summarizes the input data used in our experiments. HySortK takes FASTA
files as input. Unless otherwise noted, the experiments were performed on the
Perlmutter supercomputer (CPU node) at National Energy Research Scientific
Computing (NERSC). Each CPU node has 512 GB of total memory and two 64-core
AMD EPYC 7763 (Milan) CPUs. The nodes are connected via HPE Slingshot NIC with
a 3-hop Dragonfly topology. IO time is not included except for the last test
as it is beyond the scope of this paper and may vary due to the machine’s
storage system, network status, and overall IO traffic. The lower bound of the
valid $k$-mer frequency is set to 2 and the upper bound to 50. The extension
information of $k$-mers is not included unless otherwise specified.

Dataset name | Size (GB)
---|---
_A. baumannii_ | 0.2
_C. elegans_ | 4.5
_Citrus_ | 17.0
_H. sapiens_ 10x | 31.0
_H. sapiens_ (Short Read) | 36.0
_H. sapiens_ 52x | 156.0
Table 1. A summary of the data used in Section 4. Data are publicly available
at https://portal.nersc.gov/project/m1982/bella/ and
https://www.ncbi.nlm.nih.gov/sra/ERX009609.

###  4.1. Optimization Strategies

####  4.1.1. Task Abstraction Layer

Using _H. sapiens_ 52x, we evaluated the optimization strategies proposed in
Section 3.4 and 3.5 to understand their impact on performance. First, we used
a baseline that combined $supermer$ and sorting-based counting and completed
the task in $26.5$ seconds. Then we included the task abstraction layer, which
was designed to address the inefficiencies in processing low to medium load
imbalances. This approach split the workload across multiple tasks and
assigned multiple workers per process, resulting in a reduced runtime of
$23.4$ seconds, that is $1.13\times$ speedup, and demonstrating improved load
imbalance handling.

A more significant improvement was achieved through the integration of our
heavy hitter strategy. This fully optimized approach, which uses a flexible
task abstraction layer, significantly outperformed previous approaches by
completing in just $15.4$ seconds, a $1.72\times$ speedup. Using this
approach, tasks that are most likely to contain heavy hitter $k$-mers are
transformed from computation- and communication-intensive to communication-
intensive only. The task abstraction layer can then effectively address the
load imbalance in the communication stage.

To further validate the impact of our task abstraction layer and the ability
to implement fine-grained hybrid parallelism, we evaluate the impact of the
avg_task_per_worker parameter. Our results indicate that a higher number
generally achieves better performance. On the _H. sapiens_ 52x dataset using
32 nodes, setting tpw (tasks per worker) to 3 resulted in performance that was
$1.59\times$ faster than when tpw was set to 1 and $1.12\times$ faster than
when tpw was set to 2. This illustrates the advantage of assigning more tasks
per worker and validates the use of our task abstraction layer. They also show
that this abstraction has the potential to improve computational efficiency in
complex data processing scenarios.

Processes per node | 4 | 8 | 16 | 32 | 64
---|---|---|---|---|---
_C. elegans_ (2 nodes) |  6.26 |  3.13 | 2.62 | 2.50 | 2.46
_H. sapiens_ 10x (4 nodes) | 20.70 | 10.95 | 9.31 | 8.89 | 8.68
Table 2. HySortK end-to-end runtime (s) varying the processes per node. Batch size | 10,000 | 20,000 | 40,000 | 80,000 | 160,000
---|---|---|---|---|---
_Citrus_ (4 nodes) | 1.59 | 1.83 | 1.68 | 1.49 | 1.46
_H. sapiens_ 52x (32 nodes) | 4.83 | 4.47 | 4.12 | 4.00 | 4.21
Table 3. HySortK communication time (s) varying batch sizes.  $m$ | 7 | 13 | 17 | 21 | 27
---|---|---|---|---|---
_C. elegans_ (1 node) | 10.41 | 4.26 | 4.48 | 4.91 |  6.55
_H. sapiens_ 10x (4 nodes) | 27.73 | 8.09 | 8.51 | 9.53 | 14.71
Table 4. HySortK end-to-end runtime (s) varying $m$ at $k=31$.

####  4.1.2. Hybrid OpenMP and MPI

To further evaluate the performance of our hybrid approach, we tested HySortK
under different PPN (process per node) scenarios. The number of nodes is fixed
in each test group. All available cores are used in each test, i.e.
$OMP\\_THREADS\cdot MPI\\_PROCESSES=256\cdot NODE\\_NUM$. Table 2 shows that
the best performance is achieved with at least 16 processes per node on two
different input data. The performance decreases rapidly if less than 16
processes per node are used. The results are consistent with the theory. Each
Perlmutter CPU node has two sockets, 8 NUMA domains, and 16 CCX (Core Complex)
sharing the L3 cache. By allocating at least one process on each CCX domain,
the implicit communication between the domains is eliminated.

####  4.1.3. Batch Size and Overlapping

In Section 3.3 we described how communication takes place in rounds. The
sending size (or batch size) is limited for each round. The preparation of the
sending buffer and the parsing of the receiving buffer overlap with
communication, along with other calculations. A small message size can lead to
a high communication overhead, while a large message size can lead to a low
overlap. To find the best size, we tested the performance of HySortK at
different batch sizes. Table 3 shows that with $80,000$ we minimize
unnecessary overhead while maximizing the effective use of our computational
resources, which increases performance.

####  4.1.4. Length of $m$

The length of $supermers$ and their distribution depend largely on $m$, which
influences the runtime, as shown in Table 4 for $k=31$. A smaller $m$ gives a
lower probability that adjacent $k$-mers fall into the same task. However,
there is a trade-off between the load imbalance, if $m$ is too small, and the
total communication volume, if $m$ is too large. In Table 4, both the
communication and the sorting phase suffer from an imbalanced task size at
$m=7$. Empirically, we found that $m=k/2$ is optimal for a smaller $k$, while
for a larger $k$ a constant of $m=23$ has an ideal performance.

###  4.2. Scaling Performance

Figure 4. HySortK strong scaling performance on the _H. sapiens_ 10x dataset
using $k=31$.

Figure 5. HySortK weak scaling performance using $k=31$.

Figures 4 and 5 show the overall performance of HySortK using 16 processes per
node (see Section 4.1.2), using all cores. The circle marker indicates the
scaling efficiency. The scaling efficiency is high for smaller node counts and
gradually decreases when the ratio of data size to core count is relatively
small. The decrease in efficiency is mainly due to the increase in
communication. On the _H. sapiens_ 10x dataset in Figure 4, we achieve
superlinear scaling efficiency. On one node, we are forced to use the more
memory-efficient but slower PARADIS sorting algorithm in HySortK due to
limited available memory. Given more nodes, HySortK automatically switches to
the more efficient RADULS sorting algorithm.

Figure 6. Comparison between HySortK and KMC3 (Kokot et al., 2017b) on
multiple input data and varying $k$ length.

Figure 5 illustrates the weak scaling performance of HySortK on the _H.
sapiens_ (Short Read) dataset. The preparation, exchange, and filter stages
correspond to stage 1, stage 2, and stage 3 in the distributed $k$-mer
counting paradigm (Section 2.2), respectively. To perform this experiment, we
divided the data set into different batches of 2 GB. The number of batches
increases proportionally with the number of nodes. HySortK achieved a weak
scaling efficiency of about $80\%$ on 8 nodes. Both the preparation and
filtering stages exhibit perfect weak scaling, while the performance of the
communication stage decreases as the number of nodes increases. This is to be
expected, as the processes run independently during the preparation and
filtering phases. In the communication phase, the average communication volume
is constant, but the communication overhead increases as the number of nodes
increases.

###  4.3. Shared-Memory Performance

To show the competitiveness of our approach, we compared HySortK with KMC3, a
popular shared-memory $k$-mer counter. KMC3 does not support distributed
memory parallelization. It uses disk space to count $k$-mers when there is not
enough RAM space to perform the computation on a single node. To make the
comparison fair, we use the -r option to force KMC3 to run in RAM-only mode,
which does not allow the tool to use the hard disk. The selected input data
fits into RAM. IO time is excluded for both KMC3 and our software. The process
per node is set to $16$, the batch size to $80,000$, and $m=\\{11,17,23\\}$
for $k=\\{17,31,55\\}$ respectively for HySortK by default in Section 4.3 and
4.4.

Figure 6 demonstrates we achieved competitive or better performance than KMC3
on various input data. Both KMC3 and HySortK use a sorting-based approach, so
we conclude that the performance gain comes from our task-based
parallelization scheme. It provides flexibility, handles many available
threads more efficiently, and copes better with NUMA or multi-socket
scenarios.

###  4.4. Distributed-Memory Performance

In this section, we compare HySortK with kmerind and the $k$-mer analysis
module of MetaHipMer2. kmerind is a distributed memory CPU $k$-mer counter. It
uses optimized, cache-friendly hash tables to store the $k$-mers, while
supporting the overlap of communication and computation. For the experiments,
we used the ROBINHOOD, MURMUR64avx, CRC32C variant of the improved kmerind
$k$-mer counter as it shows the best performance (Pan et al., 2018).
MetaHipMer2 is a _de novo_ meta-genome short-read assembler written in UPC++.
Its $k$-mer analysis module computes the $k$-mer count on GPUs and also uses
the supermer strategy. Despite our best efforts, we were unable to run DEDUKT
on our machine. SWAPCounter (Ge et al., 2020) is excluded from the comparison
due to its inaccurate output.

Figure 7. Comparison of runtime and memory usage between HySortK and kmerind
(Pan et al., 2018) on _H. sapiens_ 10x with $k=31$.

Figures 7 and 8 report the runtime comparison between HySortK and kmerind on
two different datasets. The missing bar in Figure 7 indicates that kmerind ran
out of memory under that setting. Our $k$-mer counter is competitive or better
than kmerind in every scenario. Our RAM usage is 25% to 70% lower than
kmerind’s, as shown in Figure 7 on the right y-axis. For the large _H.
sapiens_ 52x dataset, HySortK scales efficiently to 64 nodes thanks to the
task layer and heavy hitter strategy, and does not suffer serious performance
degradation as the number of nodes increases. In contrast, kmerind can only
scale to 32 nodes, and the runtime increases as the number of nodes increases.

Figure 9 compares the runtime of HySortK and MetaHipMer2 (MHM2) $k$-mer
analysis on the _C. elegans_ dataset. MHM2 is run on Perlmutter GPU nodes.
Each GPU node has 1 EPYC 7763 CPU, 4 NVIDIA A100 GPUs, and 4 HPE Slingshot11
NICs. HySortK consistently outperformed MHM2 many times over. Our hypothesis
is that communication, including inter-CPU communication and CPU-GPU
communication, is the bottleneck for MHM2. The performance gap decreases as we
increase the number of nodes. As $k$ increases, the $supermers$ become longer,
which reduces the total communication volume and leads to speedup.

Figure 8. Comparison of runtime and memory usage between HySortK and kmerind
(Pan et al., 2018) with _H. sapiens_ 52x and $k=31$.

Figure 9. Comparison between HySortK and MHM2 (Awan et al., 2021) on the _C.
elegans_ dataset varying $k$ length and number of nodes.

###  4.5. Integration into Real-World Pipeline

To test our hypothesis that flexible hybrid parallelization can increase the
efficiency of the entire pipeline, we integrated our $k$-mer counter into the
distributed-memory ELBA _de novo_ long-read assembly pipeline. ELBA’s overlap
detection, contig generation and transitive reduction modules already support
hybrid OpenMP and MPI parallelization, while the $k$-mer counter stage does
not use the hybrid parallelism, thus hindering the overall efficiency of the
pipeline in shared memory scenarios. ELBA is usually only executed with MPI
processes and without OpenMP parallelization to account for the lack of
multithreading parallelism in the $k$-mer counter. In addition, ELBA requires
not only the frequency of a specific $k$-mer, but also the origin of such a
$k$-mer in the input sequences. Therefore, we used the extension version of
HySortK.

Figure 10 illustrates the runtime breakdown with the _A. baumannii_ dataset on
a single node using 64 cores. Assigning one core per MPI process (no OpenMP
parallelism) can lead to an increased runtime for transitive reduction and
contig generation (left bar in Figure 10). On the other hand, using hybrid MPI
and OpenMP parallelism makes $k$-mer counting much more time-consuming since
the original $k$-mer counter in ELBA does not support OpenMP (middle bar in
Figure 10). In contrast, we can leverage the hybrid parallelism when
integrating HySortK. Our $k$-mer counter integrated into the ELBA pipeline
significantly outperforms the original counter in a hybrid parallelization
scenario (right bar in Figure 10) and the original counter running exclusively
under MPI. Consequently, we achieve a speedup of 1.8$\times$ and 1.3$\times$
for the entire pipeline compared to the original pipeline running with 1
thread per process and 16 threads per process, respectively.

Figure 10. ELBA with and without HySortK at 64 processes and 1 thread (64p1t)
or 4 processes and 16 threads (4p16t).

##  5\. Conclusions

Recent advances in high-throughput sequencing technologies have led to an
exponential increase in the volume of genomic data. In many genomic processing
pipelines, $k$-mer counting is an important step and often the first, meaning
that this step cannot escape the data size through a filtering process.
Therefore, highly parallel and memory-efficient $k$-mer counting on large-
scale machines is crucial to accelerate genomic research.

In this work, we presented HySortK, a highly efficient sorting-based $k$-mer
counting algorithm implemented for distributed memory systems, which reduces
random memory access and memory usage compared to conventional hash table-
based approaches. In addition, we introduced an improved supermer strategy to
reduce the communication volume and the task abstraction layer to improve load
balancing. HySortK consistently outperformed both shared memory and
distributed memory software, even when using GPUs with a speedup of $2\times$
to $10\times$ and with up to $3\times$ less memory. Future work includes
implementing the supermer strategy with the $kmerlist$ task to further reduce
the communication volume.

Finally, we showed how the task abstraction layer facilitates parallelism and
improves performance; we believe that such abstraction has the potential to
improve computational efficiency in complex data processing scenarios.

###### Acknowledgements.

The work was developed during the first author’s participation in an exchange
program at Cornell University. This project received support from the Center
for Research on Programmable Plant Systems under National Science Foundation
Grant No. DBI-2019674. This research used resources of the National Energy
Research Scientific Computing Center, a DOE Office of Science User Facility
supported by the Office of Science of the U.S. Department of Energy under
Contract No. DE-AC02-05CH11231 and award DDR-ERCAP0027296.

## References

  * (1)
  * Awan et al. (2021) Muaaz Gul Awan, Steven Hofmeyr, Rob Egan, Nan Ding, Aydin Buluc, Jack Deslippe, Leonid Oliker, and Katherine Yelick. 2021.  Accelerating large scale de novo metagenome assembly using GPUs. In _Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis_. 1–11.
  * Baaijens et al. (2022) Jasmijn A Baaijens, Paola Bonizzoni, Christina Boucher, Gianluca Della Vedova, Yuri Pirola, Raffaella Rizzi, and Jouni Sirén. 2022.  Computational graph pangenomics: a tutorial on data structures and their applications.  _Natural Computing_ 21, 1 (2022), 81–108.
  * Breitwieser et al. (2018) Florian P Breitwieser, Daniel N Baker, and Steven L Salzberg. 2018.  KrakenUniq: confident and fast metagenomics classification using unique k-mer counts.  _Genome biology_ 19 (2018), 1–10.
  * Bull (1999) J Mark Bull. 1999.  Measuring synchronisation and scheduling overheads in OpenMP. In _Proceedings of First European Workshop on OpenMP_ , Vol. 8. 49.
  * Carter and Wegman (1977) J Lawrence Carter and Mark N Wegman. 1977.  Universal classes of hash functions. In _Proceedings of the ninth annual ACM symposium on Theory of computing_. 106–112.
  * Cho et al. (2015) Minsik Cho, Daniel Brand, Rajesh Bordawekar, Ulrich Finkler, Vincent Kulandaisamy, and Ruchir Puri. 2015.  PARADIS: an efficient parallel algorithm for in-place radix sort.  _Proceedings of the VLDB Endowment_ 8, 12 (2015), 1518–1529.
  * Dhibar and Jana (2023) Saikat Dhibar and Biman Jana. 2023.  Accurate Prediction of Antifreeze Protein from Sequences through Natural Language Text Processing and Interpretable Machine Learning Approaches.  _The Journal of Physical Chemistry Letters_ 14, 48 (2023), 10727–10735.  https://doi.org/10.1021/acs.jpclett.3c02817 arXiv:https://doi.org/10.1021/acs.jpclett.3c02817  PMID: 38009833.
  * Flajolet et al. (2007) Philippe Flajolet, Éric Fusy, Olivier Gandouet, and Frédéric Meunier. 2007.  Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm.  _Discrete mathematics & theoretical computer science_ Proceedings (2007).
  * Ge et al. (2020) Jianqiu Ge, Jintao Meng, Ning Guo, Yanjie Wei, Pavan Balaji, and Shengzhong Feng. 2020.  Counting kmers for biological sequences at large scale.  _Interdisciplinary Sciences: Computational Life Sciences_ 12 (2020), 99–108.
  * Georganas et al. (2015) Evangelos Georganas, Aydın Buluç, Jarrod Chapman, Steven Hofmeyr, Chaitanya Aluru, Rob Egan, Leonid Oliker, Daniel Rokhsar, and Katherine Yelick. 2015.  HipMer: an extreme-scale de novo genome assembler. In _Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis_. 1–11.
  * Georganas et al. (2014) Evangelos Georganas, Aydin Buluç, Jarrod Chapman, Leonid Oliker, Daniel Rokhsar, and Katherine Yelick. 2014.  Parallel de bruijn graph construction and traversal for de novo genome assembly. In _SC’14: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis_. IEEE, 437–448.
  * Ghosh et al. (2020) Priyanka Ghosh, Sriram Krishnamoorthy, and Ananth Kalyanaraman. 2020.  Pakman: a scalable algorithm for generating genomic contigs on distributed memory machines.  _IEEE Transactions on Parallel and Distributed Systems_ 32, 5 (2020), 1191–1209.
  * Guidi et al. (2021a) Giulia Guidi, Marquita Ellis, Daniel Rokhsar, Katherine Yelick, and Aydın Buluç. 2021a.  BELLA: Berkeley efficient long-read to long-read aligner and overlapper. In _SIAM Conference on Applied and Computational Discrete Algorithms (ACDA21)_. SIAM, 123–134.
  * Guidi et al. (2021b) Giulia Guidi, Oguz Selvitopi, Marquita Ellis, Leonid Oliker, Katherine Yelick, and Aydın Buluç. 2021b.  Parallel string graph construction and transitive reduction for de novo genome assembly. In _2021 IEEE International Parallel and Distributed Processing Symposium (IPDPS)_. IEEE, 517–526.
  * Hofmeyr et al. (2020) Steven Hofmeyr, Rob Egan, Evangelos Georganas, Alex C Copeland, Robert Riley, Alicia Clum, Emiley Eloe-Fadrosh, Simon Roux, Eugene Goltsman, Aydın Buluç, et al. 2020\.  Terabase-scale metagenome coassembly with MetaHipMer.  _Scientific reports_ 10, 1 (2020), 10689.
  * Jaishree and Wang (1994) TN Jaishree and Andrew H-J Wang. 1994.  Human chromosomal centromere (AATGG) n sequence forms stable structures with unusual base pairs.  _FEBS letters_ 347, 1 (1994), 99–103.
  * Jonkheer et al. (2022) Eef M Jonkheer, Dirk-Jan M van Workum, Siavash Sheikhizadeh Anari, Balázs Brankovics, Jorn R de Haan, Lidija Berke, Theo AJ van der Lee, Dick de Ridder, and Sandra Smit. 2022.  PanTools v3: functional annotation, classification and phylogenomics.  _Bioinformatics_ 38, 18 (2022), 4403–4405.
  * Karp (2010) Richard M Karp. 2010.  _Reducibility among combinatorial problems_.  Springer.
  * Kokot et al. (2017a) Marek Kokot, Sebastian Deorowicz, and Agnieszka Debudaj-Grabysz. 2017a.  Sorting data on ultra-large scale with RADULS: New incarnation of radix sort. In _Beyond Databases, Architectures and Structures. Towards Efficient Solutions for Data Analysis and Knowledge Representation: 13th International Conference, BDAS 2017, Ustroń, Poland, May 30-June 2, 2017, Proceedings 13_. Springer, 235–245.
  * Kokot et al. (2017b) Marek Kokot, Maciej Długosz, and Sebastian Deorowicz. 2017b.  KMC 3: counting and manipulating k-mer statistics.  _Bioinformatics_ 33, 17 (2017), 2759–2761.
  * Li et al. (2015) Yang Li et al. 2015\.  MSPKmerCounter: a fast and memory efficient approach for k-mer counting.  _arXiv preprint arXiv:1505.06550_ (2015).
  * Logsdon et al. (2020) Glennis A Logsdon, Mitchell R Vollger, and Evan E Eichler. 2020.  Long-read human genome sequencing and its applications.  _Nature Reviews Genetics_ 21, 10 (2020), 597–614.
  * Marçais et al. (2019) Guillaume Marçais, Dan DeBlasio, Prashant Pandey, and Carl Kingsford. 2019.  Locality-sensitive hashing for the edit distance.  _Bioinformatics_ 35, 14 (2019), i127–i135.
  * Nisa et al. (2021) Israt Nisa, Prashant Pandey, Marquita Ellis, Leonid Oliker, Aydın Buluç, and Katherine Yelick. 2021.  Distributed-memory k-mer counting on GPUs. In _2021 IEEE International Parallel and Distributed Processing Symposium (IPDPS)_. IEEE, 527–536.
  * Nurk et al. (2020) Sergey Nurk, Brian P Walenz, Arang Rhie, Mitchell R Vollger, Glennis A Logsdon, Robert Grothe, Karen H Miga, Evan E Eichler, Adam M Phillippy, and Sergey Koren. 2020.  HiCanu: accurate assembly of segmental duplications, satellites, and allelic variants from high-fidelity long reads.  _Genome research_ 30, 9 (2020), 1291–1305.
  * Pan et al. (2018) Tony C Pan, Sanchit Misra, and Srinivas Aluru. 2018.  Optimizing high performance distributed memory parallel hash tables for DNA k-mer counting. In _SC18: International Conference for High Performance Computing, Networking, Storage and Analysis_. IEEE, 135–147.
  * Rautiainen and Marschall (2020) Mikko Rautiainen and Tobias Marschall. 2020.  GraphAligner: rapid and versatile sequence-to-graph alignment.  _Genome biology_ 21, 1 (2020), 253.
  * Richter et al. (2015) Stefan Richter, Victor Alvarez, and Jens Dittrich. 2015.  A seven-dimensional analysis of hashing methods and its implications on query processing.  _Proc. VLDB Endow._ 9, 3 (nov 2015), 96–107.  https://doi.org/10.14778/2850583.2850585
  * Selvitopi et al. (2020) Oguz Selvitopi, Saliya Ekanayake, Giulia Guidi, Georgios A Pavlopoulos, Ariful Azad, and Aydın Buluç. 2020.  Distributed many-to-many protein sequence alignment using sparse matrices. In _SC20: International Conference for High Performance Computing, Networking, Storage and Analysis_. IEEE, 1–14.
  * Yan et al. (2021) Yiqing Yan, Nimisha Chaturvedi, and Raja Appuswamy. 2021.  Accel-Align: a fast sequence mapper and aligner based on the seed–embed–extend method.  _BMC bioinformatics_ 22, 1 (2021), 1–20.


# Ricci flow starting from an embedded closed convex surface in
$\mathbb{R}^{3}$

Jiuzhou Huang and Jiawei Liu  Jiuzhou Huang
Department of Mathematics and Statistics
McGill University
Montreal
Quebec
H3A 0B9
Canada<EMAIL_ADDRESS>Jiawei Liu
Department of Mathematics and Statistics
McGill University
Montreal
Quebec
H3A 0B9
Canada<EMAIL_ADDRESS>
###### Abstract.

In this paper, we establish the existence and uniqueness of Ricci flow that
admits an embedded closed convex surface in $\mathbb{R}^{3}$ as metric initial
condition. The main point is a family of smooth Ricci flows starting from
smooth convex surfaces whose metrics converge uniformly to the metric of the
initial surface in intrinsic sense.

###### Key words and phrases:

Ricci flow, embedded closed convex surface

AMS Mathematics Subject Classification.

##  1\. Introduction

Since Ricci flow was introduced by Hamilton [6] in 1982, it has many
applications in differential geometry and topology, such as the solutions of
Poincaré conjecture [8, 9] and differentiable sphere theorem [3] etc. Another
important application of Ricci flow is the smoothing of initial condition. In
[18, 19], Simon proved the existence of Ricci flow that admits a class of
irregular metric spaces with dimension two or three as metric initial
condition. This is an approximation of the metric space by Ricci flow. Based
on Simon’s work, Richard [13, 14] studied the existence and uniqueness of
Ricci flow whose metric initial condition is a closed Alexandrov surface with
curvature bounded from below, which gives a canonical smoothing of such
surface via Ricci flow. The works of Simon and Richard are related to the
Gromov-Hausdorff convergence. In this paper, we consider stronger convergence
of Ricci flow for embedded closed convex surface in $\mathbb{R}^{3}$ (see
Theorem 1.3).

Before stating our results, we first recall Simon [18, 19] and Richard’s
results [13, 14]. One key point in [19] is the following estimates.

######  Theorem 1.1.

(Theorem $7.1$ in [19]) Let $(M,g_{0})$ be a complete smooth three (or two)
manifold without boundary such that

(1.1) $\begin{split}&(a)\ Ricci(g_{0})\geqslant k;\\\ &(b)\
vol(^{g_{0}}B_{1}(x))\geqslant v_{0}>0\text{ for all }x\in M;\\\ &(c)\
\sup_{M}|Riem(g_{0})|<\infty.\end{split}$

Then there are constants $c_{1}=c_{1}(v_{0},k)>0$, $c_{2}=c_{2}(v_{0},k)>0$,
$S=S(v_{0},k)>0$ and $K=K(v_{0},k)$ and a solution $(M,g(t))_{t\in[0,T)}$ to
Ricci flow which satisfies $T\geqslant S$, and

(1.2) $\begin{split}&(a_{t})\ Ricci(g(t))\geqslant-K^{2};\\\ &(b_{t})\
vol(^{g_{t}}B_{1}(x))\geqslant\frac{v_{0}}{2}>0\text{ for all }x\in M\ and\
t\in(0,T);\end{split}$ (1.3) $\begin{split}&(c_{t})\
\sup_{M}|Riem(g(t))|\leqslant\frac{K^{2}}{t}\text{ for all }t\in(0,T);\\\
&(d_{t})\ d(p,q,s)-c_{2}(\sqrt{t}-\sqrt{s})\leqslant d(p,q,t)\leqslant
e^{c_{1}(t-s)}d(p,q,s),\\\ &\ \ \qquad\text{ for all }0<s\leqslant t<T\ and\
p,\ q\in M.\end{split}$

(Note that the estimates are trivial for $t=0$.)

Based on this result, the following existence and uniqueness of Ricci flow
were proved in [19, 14].

######  Theorem 1.2.

(Theorem $1.9$ in [19] and Theorem $0.5$ in [14]) Let $(X,d)$ be a closed
Alexandrov surface with curvature bounded from below by $-K$. Then there is a
smooth Ricci flow $(M,g(t))_{t\in(0,T)}$ admitting $(X,d)$ as metric initial
condition in the sense that the Riemannian distances $d_{g(t)}$ uniformly
converge as $t$ goes to $0$ to a distance $\tilde{d}$ on $M$ such that
$(M,\tilde{d})$ is isometric to $(X,d)$.

Moreover, if there is another smooth Ricci flow $(N,h(t))_{t\in(0,T)}$ also
admitting $(X,d)$ as metric initial condition in above sense, then there is a
diffeomorphism $\varphi:M\rightarrow N$ such that $g(t)=\varphi^{*}h(t)$.

Their ideas are as follows. They first construct a sequence of smooth
manifolds $(M_{i},g_{i})$ that converges to $(X,d)$ in Gromov-Hausdorff
distance and keeps the uniform properties in $(\ref{0416})$. For every $i$,
there is a smooth Ricci flow $(M_{i},g_{i}(t))_{t\in[0,T)}$ starting from
$(M_{i},g_{i})$. Then by using Theorem 1.1 and taking the limit as
$i\to\infty$, they get the Ricci flow $(M,g(t))_{t\in(0,T)}$ that converge to
$(X,d)$ in Gromov-Hausdorff distance.

A natural question is when such a Ricci flow will converge to the initial
metric in classical sense, and what kind of uniqueness one can claim. In this
paper, when the metric initial condition $(X,d)$ is an embedded closed convex
surface in $\mathbb{R}^{3}$, we prove that the Ricci flow will converge in
intrinsic sense to $(X,d)$ as $t\to 0$ and that such flows keep the isometries
between their metric initial conditions. We would like to remark that the
convex surface in this paper is in the sense of Alexandrov (see section 2),
unless otherwise specified.

Our first result is the following existence theorem.

######  Theorem 1.3.

If $(X,d)$ is an embedded closed convex surface in $\mathbb{R}^{3}$, then
there exists a $T>0$ and a smooth Ricci flow $(X,g(t))_{t\in(0,T)}$ such that
the distance functions $d_{g(t)}$ induced by $g(t)$ converge uniformly to $d$
as $t\to 0$, that is,

(1.4) $\lim_{t\to 0}\max_{p,q\in X}|d_{g(t)}(p,q)-d(p,q)|=0.$

The difference between Theorem 1.2 and Theorem 1.3 is that we remove the
isometry between $(M,\tilde{d})$ and $(X,d)$ in Theorem 1.2 when the metric
initial condition $(X,d)$ is an embedded closed convex surface in
$\mathbb{R}^{3}$. This is due to the existence of smooth convex surfaces that
approximate $(X,d)$ in Hausdorff distance (Lemma 3.1) instead of the Gromov-
Hausdorff convergence in [13, 18, 19]. In fact, removing the isometry is
crucial for proving the uniqueness of such Ricci flow and then study the
rigidity problem of closed convex surfaces (see our project in Section 4).

From now on, unless otherwise specified, by saying that $(X,g(t))_{t\in(0,T)}$
is a Ricci flow admitting an embedded closed convex surface $(X,d)$ in
$\mathbb{R}^{3}$ as metric initial condition, we mean that it is a Ricci flow
in the sense of Theorem 1.3.

Since every closed convex surface can be embedded in $\mathbb{R}^{3}$ as the
boundary of a convex body by using Alexandrov’s embedding theorem (Theorem
2.4). By Theorem 1.3, we have the following existence result.

######  Corollary 1.4.

For any closed convex surface $(X,d)$, there exists a $T>0$ and a smooth Ricci
flow $g(t)$ with ${t\in(0,T)}$ admitting $(X,d)$ as metric initial condition
in the sense that $(\tilde{X},g(t))_{t\in(0,T)}$ is a Ricci flow admitting
$(\tilde{X},\tilde{d})$ as metric initial condition, where
$(\tilde{X},\tilde{d})$ is an isometric embedding of $(X,d)$ into
$\mathbb{R}^{3}$.

The second result in this paper is the following uniqueness theorem.

######  Theorem 1.5.

Assume that $(X_{1},d_{1})$ and $(X_{2},d_{2})$ are two non-degenerate
embedded closed convex surfaces in $\mathbb{R}^{3}$ and
$f:(X_{1},d_{1})\rightarrow(X_{2},d_{2})$ is an isometry. Let
$(X_{1},g_{1}(t))_{t\in(0,T)}$ and $(X_{2},g_{2}(t))_{t\in(0,T)}$ be Ricci
flows admitting $(X_{1},d_{1})$ and $(X_{2},d_{2})$ as metric initial
conditions respectively. Then $g_{1}(t)=f^{*}g_{2}(t)$.

Theorem 1.5 gives the exact expression of the diffeomorphism in Theorem 1.2
when the metric initial condition is an embedded closed convex surface in
$\mathbb{R}^{3}$. This result means that Ricci flows obtained in Theorem 1.3
keep the isometries between their metric initial conditions. The point here is
to prove that the isometry between the two metric initial conditions is
differentiable (Theorem 3.7), which implies that the pull back metrics under
this isometry still satisfy Ricci flow. Then Theorem 1.5 follows from
Proposition $0.6$ in [14].

If the metric initial conditions are closed convex surfaces, we have the
following uniqueness result.

######  Corollary 1.6.

Assume that $(X_{1},d_{1})$ and $(X_{2},d_{2})$ are two isometric closed
convex surfaces with non-degenerate isometric embeddings in $\mathbb{R}^{3}$,
and that $g_{1}(t)$ and $g_{2}(t)$ with $t\in(0,T)$ are Ricci flows admitting
$(X_{1},d_{1})$ and $(X_{2},d_{2})$ as metric initial conditions in the sense
of Corollary 1.4. Then $g_{1}(t)$ and $g_{2}(t)$ are isometric.

######  Remark 1.7.

Let $\varphi_{1}:(X_{1},d_{1})\rightarrow(\tilde{X}_{1},\tilde{d}_{1})$ and
$\varphi_{2}:(X_{2},d_{2})\rightarrow(\tilde{X}_{2},\tilde{d}_{2})$ be
isometric embeddings of $(X_{1},d_{1})$ and $(X_{2},d_{2})$ into
$\mathbb{R}^{3}$ respectively, and $f:(X_{1},d_{1})\rightarrow(X_{2},d_{2})$
be the isometry in Corollary 1.6. From Theorem 1.5, $F:=\varphi_{2}\circ
f\circ\varphi_{1}^{-1}$ is the isometry between $g_{1}(t)$ and $g_{2}(t)$ in
Corollary 1.6, that is, $g_{1}(t)=F^{*}g_{2}(t)$.

The motivation of this paper is to use Ricci flow to study convex surfaces in
the sense of Alexandrov. This kind of surfaces is a generalization of smooth
convex surfaces to non-smooth case, and share many similarities with the
latter. One example is Pogorelov’s famous rigidity theorem [10], which
generalizes Cohn-Vesson’s classical rigidity result [5] about smooth convex
surfaces to Alexandrov sense. Since there is no regularity assumption on such
surfaces, Pogorelov’s theorem is not only non-trivial but also difficult to
access. In the future work, we hope to use the results in this paper to study
Pogorelov’s rigidity theorem.

The paper is organized as follows. In section 2, we recall some basic facts
about convex surfaces in the sense of Alexandrov. Then, in the third section,
we prove the existence and uniqueness of Ricci flow in the sense of Theorem
1.3. Finally, we introduce our project which aims to study the rigidity of
convex surfaces by using Ricci flow.

Acknowledgements. The authors would like to convey their gratitude to their
supervisor Professor Pengfei Guan for suggesting this problem and his
attentive guidance and several valuable comments on improving this paper.

##  2\. Preliminaries

In this section, we recall some basic results about convex surfaces in the
sense of Alexandrov. These are mainly taken from [2, 11], see also the
Appendix of [14].

Let $(X,d)$ be a metric space, it is called a geodesic metric space if any two
points $a$ and $b$ in $X$ can be connected by a continuous path of shortest
length on $X$. Suppose $(X_{1},d_{1})$ and $(X_{2},d_{2})$ are two metric
spaces, an isometry between $X_{1}$ and $X_{2}$ is a bijection $f:X_{1}\to
X_{2}$ such that

$d_{2}(f(a),f(b))=d_{1}(a,b),\ \ \ for\ all\ a,\ b\in X_{1}.$

Let $a$, $b$ and $c$ be three different points in a geodesic metric space
$(X,d)$, we define the comparison angle $\tilde{\angle}a_{b}^{c}$ as the angle
at $\tilde{a}$ of the comparison triangle $\tilde{a}\tilde{b}\tilde{c}$ in
$S_{0}$ whose sides have length $d_{0}(\tilde{a},\tilde{b})=d(a,b)$,
$d_{0}(\tilde{a},\tilde{c})=d(a,c)$ and $d_{0}(\tilde{b},\tilde{c})=d(b,c)$,
where $S_{0}$ is the Euclidean space, and $d_{0}$ is the standard distance in
$S_{0}$.

######  Definition 2.1.

Let $(X,d)$ be a geodesic metric space, it is said to satisfy the convexity
condition if for any point $a\in X$, and any two shortest paths
$(\gamma_{1}(s))_{s\in[0,T]}$ and $(\gamma_{2}(s))_{s\in[0,T]}$ in $X$
parametrized by arc length issuing from $a$, the comparison angle
$\tilde{\angle}a_{\gamma_{1}(s)}^{\gamma_{2}(t)}$ is an non-increasing
function of $s$ and $t$.

######  Definition 2.2.

Let $(X,d)$ be a geodesic metric space, it is called a closed convex surface
in the sense of Alexandrov, if it is at the same time a compact topological
surface without boundary, and satisfies the convexity condition.

We also have the following equivalent definition.

######  Definition 2.3.

A closed convex surface in the sense of Alexandrov is a geodesic metric space
$(X,d)$ which is at the same time a compact topological surface without
boundary and a metric space with non-negative curvature in the sense of
Alexandrov.

A geodesic metric space has non-negative curvature in the sense of Alexandrov
if its geodesic triangles are bigger than the geodesic triangles in $S_{0}$.
To be more precise, a geodesic metric space $(X,d)$ has non-negative curvature
in the sense of Alexandrov if and only if the following condition is
satisfied:

Let $a$, $b$ and $c$ be any three points in $(X,d)$, and $m$ be any point on a
shortest path from $b$ to $c$. Let $\tilde{a}$, $\tilde{b}$ and $\tilde{c}$ be
points in $S_{0}$ such that $d_{0}(\tilde{a},\tilde{b})=d(a,b)$,
$d_{0}(\tilde{a},\tilde{c})=d(a,c)$ and $d_{0}(\tilde{b},\tilde{c})=d(b,c)$.
If $\tilde{m}$ is a point on $\tilde{b}\tilde{c}$ such that
$d_{0}(\tilde{b},\tilde{m})=d(b,m)$. Then $d(a,m)\geqslant
d_{0}(\tilde{a},\tilde{m})$.

In the following, we call a closed convex surface in the sense of Alexandrov a
closed convex surface if there is no confusion. By Toponogov’s theorem, every
closed smooth surface with non-negative Gauss curvature is a closed convex
surface. The boundary of a convex set with the induced metric in
$\mathbb{R}^{3}$ is also a closed convex surface (Theorem $10.2.6$ in [4]).
Alexandrov proved the following isometric embeding theorem.

######  Theorem 2.4.

(Page 269 in [2]) Any closed convex surface $(X,d)$ can be isometrically
embedded into $\mathbb{R}^{3}$ as the boundary of a (possibly degenerate)
convex body.

The following lemma will be used in the proof of Theorem 1.3. Its geometric
meaning is that the Hausdorff distance of two convex surfaces in
$\mathbb{R}^{3}$ controls their intrinsic distance functions.

######  Lemma 2.5.

(Theorem $2$ in Chapter $3$ of [2]) For every closed convex surface $F$ and
for every $\varepsilon>0$, there exists a $\delta>0$ such that whenever the
deviation of a closed convex surface $S$ from $F$ is less than $\delta$ and
the distance of some points $X$ and $Y$ on $F$ from some points $A$ and $B$ on
$S$ are also less than $\delta$, we have

$|d_{F}(X,Y)-d_{S}(A,B)|<\varepsilon,$

where $d_{F}$ and $d_{S}$ are the distance functions on $F$ and $S$
respectively.

##  3\. Existence and Uniqueness of Ricci flow

In this section, assuming that $(X,d)$ is an embedded closed convex surface in
$\mathbb{R}^{3}$, we prove the existence and uniqueness of the Ricci flow that
admits $(X,d)$ as a metric initial condition.

###  3.1. Existence of the Ricci flow

In this subsection, we prove the existence of Ricci flow
$(X,g(t))_{t\in(0,T)}$ that admits $(X,d)$ as metric initial condition. First,
note that, for every embedded closed convex surface $(X,d)$ in
$\mathbb{R}^{3}$, it can be seen as the boundary of a convex body $K$. Then
there is a sequence of smooth convex bodies $K_{i}$ that converges to $K$ in
Hausdorff distance (Theorem $3.4.1$ in [15]). In particular, $\partial K_{i}$
converges to $X$ in Hausdorff distance as well. By Lemma 2.5, $\partial K_{i}$
with induced metric in $\mathbb{R}^{3}$ (denoted by $(X_{i},\tilde{g}_{i})$)
converge to $(X,d)$ in intrinsic sense. More precisely, we have the following
lemma.

######  Lemma 3.1.

Let $(X,d)$ be an embedded closed convex surface in $\mathbb{R}^{3}$. Then
there exists a sequence of closed smooth convex surfaces
$\\{(X_{i},\tilde{g}_{i})\\}_{i=1}^{\infty}$ and bijections
$f_{i}:X\rightarrow X_{i}$ such that $d_{i}(x,y)$ converges to $d(x,y)$
uniformly for $x,\ y\in X$ as $i\to\infty$, where
$d_{i}(x,y)=\tilde{d}_{i}(f_{i}(x),f_{i}(y))$, and $\tilde{d}_{i}$ is the
distance on $X_{i}$ induced by $\tilde{g}_{i}$.

Now we prove Theorem 1.3 by using Lemma 3.1.

Proof of Theorem 1.3. First, for a sequence of subsets in the same metric
space, Gromov-Hausdorff distance by definition is not greater than Hausdorff
distance. Thus the Hausdorff convergence of $(X_{i},\tilde{g}_{i})$ to $(X,d)$
in Lemma 3.1 implies the Gromov-Hausdorff convergence of
$(X_{i},\tilde{g}_{i})$ to $(X,d)$. Suppose

(3.5) $diam(X,d)\leqslant D\ \ \ and\ \ \ vol(X)\geqslant\tilde{\nu}_{0}>0$

for some positive constants $D$ and $\tilde{\nu}_{0}$. Since the diameter and
volume are continuous with respect to Gromov-Hausdorff convergence with
sectional curvature bounded from below, and all the surfaces
$(X_{i},\tilde{g}_{i})$ and $(X,d)$ are convex, we have

(3.6) $diam(X_{i},\tilde{g}_{i})\leqslant 2D\ \ \ and\ \ \
^{\tilde{g}_{i}}vol(X_{i})\geqslant\frac{\tilde{\nu}_{0}}{2}>0$

for $(X_{i},\tilde{g}_{i})$ with large $i$. By Bishop-Gromov comparison
theorem, we get

(3.7)
$\frac{vol(^{\tilde{g}_{i}}B_{1}(x))}{vol(B_{1}(x))}\geqslant\frac{vol(^{\tilde{g}_{i}}B_{2D}(x))}{vol(B_{2D}(x))}=\frac{{}^{\tilde{g}_{i}}vol(X_{i})}{vol(B_{2D}(x))}\geqslant\frac{\tilde{\nu}_{0}}{2vol(B_{2D}(x))},$

which implies that

(3.8)
$vol(^{\tilde{g}_{i}}B_{1}(x))\geqslant\tilde{\nu}_{0}\frac{vol(B_{1}(x))}{2vol(B_{2D}(x))}:=\nu_{0}>0.$

Due to Theorem 1.1, we know that there are smooth Ricci flows
$(X_{i},g_{i}(t))_{t\in[0,T)}$ with $g_{i}(0)=\tilde{g}_{i}$ satisfying

$\begin{split}&(a^{\prime}_{t})\ Ricci(g_{i}(t))\geqslant 0\ for\ all\
t\in[0,T);\\\ &(b^{\prime}_{t})\
vol(^{g_{i}(t)}B_{1}(x))\geqslant\frac{\nu_{0}}{2}>0,\ for\ all\ x\in X\ and\
t\in[0,T);\\\ &(c^{\prime}_{t})\
\sup_{X_{i}}|Riem(g_{i}(t))|\leqslant\frac{K}{t}\ for\ all\ t\in[0,T);\\\
&(d^{\prime}_{t})\ d_{g_{i}(s)}(p,q)-c_{2}(\sqrt{t}-\sqrt{s})\leqslant
d_{g_{i}(t)}(p,q)\leqslant e^{c_{1}(t-s)}d_{g_{i}(s)}(p,q),\\\ &\ \ \ \ \ \
for\ all\ 0\leqslant s\leqslant t\in[0,T)\ and\ p,\ q\in X_{i},\end{split}$

where $K=K(\nu_{0})$, $c_{1}=c_{1}(\nu_{0})$, $c_{2}=c_{2}(\nu_{0})$ and
$T=T(\nu_{0})$ are constants independent of $i$. Combining $(c^{\prime}_{t})$
and Shi’s higher derivative estimates [16, 17] with Arzela-Ascoli theorem,
there exists a subsequence (which we also denote by $g_{i}(t)$) converges to a
metric $g(t)$ on $X$, and $(X,g(t))_{t\in(0,T)}$ is a smooth Ricci flow. Let
$s\to 0$ in $(d^{\prime}_{t})$, for all $t\in(0,T)$ and $p,\ q\in X$, we have

(3.9) $\tilde{d}_{i}(f_{i}(p),f_{i}(q))-c_{2}\sqrt{t}\leqslant
d_{g_{i}(t)}(f_{i}(p),f_{i}(q))\leqslant
e^{c_{1}t}\tilde{d}_{i}(f_{i}(p),f_{i}(q)).$

Since $X_{i}$ converges to $X$ in Hausdorff distance and $g_{i}(t)$ converges
to $g(t)$ in local smooth sense of $(0,T)$, by letting $i\to\infty$ and using
Lemma 3.1, we have

(3.10) $d(p,q)-c_{2}\sqrt{t}\leqslant d_{g(t)}(p,q)\leqslant
e^{c_{1}t}d(p,q).$

Then the uniform convergence of $d_{g(t)}$ to $d$ follows by letting $t\to 0$
in $(\ref{041601})$. $\square$

###  3.2. Uniqueness

In this subsection, we prove the uniqueness of Ricci flow that admits a non-
degenerate embedded closed convex surface in $\mathbb{R}^{3}$ as a metric
initial condition. The point is to give an exact expression of the initial
metric $d$ (Theorem 3.6) firstly, and then to prove that the isometry between
the two metric initial conditions is differentiable (Theorem 3.7).

Let $(X,g(t))_{t\in(0,T)}$ be the Ricci flow obtained in subsection 3.1. It is
easy to see that its Gaussian curvature $K_{g(t)}$ is positive. In fact, the
non-negativity of the Gaussian curvature $K_{\tilde{g}_{i}}$ of the smooth
convex surfaces $(X_{i},\tilde{g}_{i})$ implies that the Gauss curvature
$K_{g_{i}(t)}$ along Ricci flow $(X_{i},g_{i}(t))_{t\in[0,T)}$ is also non-
negative by applying maximum principle to the evolution equation of
$K_{g_{i}(t)}$,

(3.11) $\frac{\partial}{\partial
t}K_{g_{i}(t)}=\Delta_{g_{i}(t)}K_{g_{i}(t)}+|Ric_{g_{i}(t)}|^{2}_{g_{i}(t)}.$

From Gauss-Bonnet theorem for $g_{i}(t)$ and the fact that $g_{i}(t)$
converges to $g(t)$ smoothly, for $t\in(0,T)$, $K_{g(t)}$ is non-negative and
satifies

(3.12) $\int_{X}K_{g(t)}dV_{g(t)}=4\pi.$

Hence there must be a point $x_{0}$ such that $K_{g(t)}$ is positive at
$x_{0}$. Then strong maximum principle implies that $K_{g(t)}$ is positive
everywhere.

Fix $t_{0}\in(0,T)$ and denote $(X,g(t_{0}))=(X,g_{t_{0}})$. By the
Uniformization theorem, there is a conformal equivalence (holomorphic
isomorphism) $\Phi:(\mathbb{S}^{2},\tilde{h})\rightarrow(X,g_{t_{0}})$, where
$\tilde{h}$ is a smooth metric of positive constant curvature, i.e.
$\Phi^{*}(g_{t_{0}})=e^{\tilde{u}(t_{0},x)}\tilde{h}(x)$ for some smooth
function $\tilde{u}(t_{0},x)$ on $\mathbb{S}^{2}$. On the other hand, the
2-dimensional Ricci flow can be written as

(3.13) $\frac{\partial}{\partial t}g(t)=-R_{g(t)}g(t).$

Hence we can write
$g(t)=e^{-\int_{t_{0}}^{t}R_{g(s)}ds}g_{t_{0}}:=\tilde{\omega}(t,x)g_{t_{0}}$,
which implies that

$g(t)=\tilde{\omega}(t,x)(\Phi^{-1})^{*}(e^{\tilde{u}(t_{0},x)}\tilde{h}(x))=\tilde{\omega}(t,x)e^{\tilde{u}(t_{0},\Phi^{-1}(x))}\tilde{h}(\Phi^{-1}(x)):=e^{2u(t,x)}h(x).$

where $h(x):=\tilde{h}(\Phi^{-1}(x))$ and
$u(t,x):=\frac{\ln(\tilde{\omega}(t,x))+\tilde{u}(t_{0},\Phi^{-1}(x))}{2}$. We
call $u(t):=u(t,x)$ the conformal potential along Ricci flow
$(X,g(t))_{t\in(0,T)}$. From (3.13), the evolution equation of $u(t)$ reads

(3.14) $\frac{\partial u(t)}{\partial
t}=e^{-2u(t)}(\Delta_{h}u(t)-K_{h})=-K_{g(t)}.$

Since $K_{g(t)}$ is positive, $u(t)$ increases as $t$ decreases to $0$, and
$u(t)\geqslant u(T)$ for $t\in(0,T]$. It is proved in Lemma $2.2$ of [14] that
$u(t)$ is uniformly bounded in $L^{1}$-sense and converges to an integrable
function $u_{0}(x)$ in $L^{1}$-sense. Here, we prove that $u(t)$ is uniformly
bounded for $t\in(0,T]$ in the classical sense (so $u_{0}(x)$ is also bounded
in the classical sense).

Before starting the proof, we remark that every Ricci flow
$(X,g(t))_{t\in(0,T)}$ admitting $(X,d)$ as metric initial condition can be
obtained through the process in subsection 3.1. This is due to Proposition
$0.6$ in [14]. Hence we only need to consider the uniqueness for the Ricci
flow obtained in subsection 3.1.

######  Lemma 3.2.

Assume that $(X,d)$ is a non-degenerate embedded closed convex surface in
$\mathbb{R}^{3}$. Let $(X,g(t))_{t\in(0,T]}$ be a Ricci flow admitting $(X,d)$
as metric initial condition. Then the conformal potential $u(t)$ along
$(X,g(t))_{t\in(0,T]}$ is uniformly bounded. Thus, $u_{0}(x)$ is bounded on
$X$.

To prove this lemma, we first prove that the smooth approximating metrics
$\tilde{g}_{i}$ obtained in Lemma 3.1 are uniformly equivalent to the standard
metric $\delta$ on the unit sphere $\mathbb{S}^{2}$. Let $(X,g)$ be a smooth
embedded closed convex surface in $\mathbb{R}^{3}$, $\rho$ be the radial
function of $(X,g)$, and $v=\frac{1}{\rho}$. Then the induced metric on $X$
and the second fundamental form can be written as

(3.15) $\begin{split}&g_{ij}=\rho^{2}\delta_{ij}+\rho_{i}\rho_{j},\\\
&h_{ij}=\frac{1}{\sqrt{\rho^{2}+|\nabla_{\delta}\rho|^{2}}}(\rho^{2}\delta_{ij}+2\rho_{i}\rho_{j}-\rho\rho_{ij})\\\
&\ \ \ \
=\frac{\rho^{3}}{\sqrt{\rho^{2}+|\nabla_{\delta}\rho|^{2}}}(v_{ij}+v\delta_{ij}),\end{split}$

where the derivatives are taken with respect to the connection of
$(\mathbb{S}^{2},\delta)$.

######  Lemma 3.3.

There is a uniform constant $C$ such that

(3.16) $\frac{1}{C}\delta\leqslant\tilde{g}_{i}\leqslant C\delta\ \ \ for\
large\ i.$

###### Proof.

Let ${}^{i}\rho$ be the radial function of $(X_{i},\tilde{g}_{i})$ and
${}^{i}v=\frac{1}{{}^{i}\rho}$. We claim that

(3.17) $\max_{\mathbb{S}^{2}}(|\nabla_{\delta}\ ^{i}v|^{2}+\
^{i}v^{2})\leqslant\max_{\mathbb{S}^{2}}\ ^{i}v^{2}.$

Define $f=|\nabla_{\delta}\ ^{i}v|^{2}+(1+\eta)\ ^{i}v^{2}$ for $\eta>0$. At
the maximum point of $f$, we have

(3.18) $0=\nabla_{\delta l}f=\nabla_{\delta l}(|\nabla_{\delta}\
^{i}v|^{2}+(1+\eta)\ ^{i}v^{2})=2\ ^{i}v_{j}(\ ^{i}v_{lj}+(1+\eta)\
^{i}v\delta_{lj}).$

Since $(X_{i},\tilde{g}_{i})$ is convex, $(\ ^{i}h_{lj})\geqslant 0$ and then
$(^{i}v_{lj}+\ ^{i}v\delta_{lj})\geqslant 0$. Then we have
$(^{i}v_{lj}+(1+\eta)\ ^{i}v\delta_{lj})>0$. Hence $\nabla_{\delta}v=0$ at the
maximum point of $f$, which implies

(3.19) $\max_{\mathbb{S}^{2}}(|\nabla_{\delta}\ ^{i}v|^{2}+(1+\eta)\
^{i}v^{2})\leqslant(1+\eta)\max_{\mathbb{S}^{2}}\ ^{i}v^{2}.$

Let $\eta\to 0$, we complete the proof of the claim.

Since $(X,d)$ is non-degenerate and $(X_{i},\tilde{g}_{i})$ converges to
$(X,d)$ in Hausdorff sense, there exists a constant $C$ such that for large
$i$,

(3.20) $\frac{1}{C}\leqslant\ ^{i}\rho\leqslant C.$

From the claim, $|\nabla_{\delta}\ ^{i}\rho|^{2}$ are also uniformly bounded
for large $i$. Taking trace with respect to $\delta$ on both sides of
$(\tilde{g}_{i})_{lj}=\ ^{i}\rho^{2}\delta_{lj}+\ ^{i}\rho_{l}\ ^{i}\rho_{j}$,
we conclude that there exists uniform constant $C$ such that

(3.21) $tr_{\delta}\tilde{g}_{i}\leqslant C\ \ \ and\ \ \
tr_{\delta}\tilde{g}_{i}\geqslant\frac{1}{C}>0\ \ for\ large\ i.$

Therefore, there is a uniform constant $C$ such that

(3.22) $\frac{1}{C}\delta\leqslant\tilde{g}_{i}\leqslant C\delta$

for large $i$.

Next, we extend this equivalence to Ricci flow.

######  Lemma 3.4.

Let $(X,g(t))_{t\in[0,T]}$ be a 2-dimensional smooth Ricci flow with initial
metric $g_{0}$, then we have

(3.23) $g(t)\leqslant e^{L_{1}T}g_{0}\ \ \ and\ \ \ tr_{g(t)}g_{0}\leqslant
L_{2}(\frac{dV_{g_{0}}}{dV_{g(T)}})^{2},$

where $-L_{1}$ is the lower bound of $R_{g_{0}}$, and $L_{2}$ depends on
$L_{1}$, $T$.

###### Proof.

Applying maximum principle to the evolution equation of the scalar curvature
$R_{g(t)}$

(3.24) $\frac{\partial}{\partial
t}R_{g(t)}=\Delta_{g(t)}R_{g(t)}+2|Ric_{g(t)}|_{g(t)}^{2},$

we get

(3.25) $R_{g(t)}\geqslant R_{g_{0}}\geqslant-L_{1}.$

In dimension $2$, Ricci flow can be written as

(3.26) $\frac{\partial}{\partial t}g(t)=-R_{g(t)}g(t)\leqslant L_{1}g(t).$

Hence we have $g(t)\leqslant e^{L_{1}t}g_{0}$ and get the first estimate in
$(\ref{01003})$.

For the second estimates, we need the following inequality.

(3.27) $n\Big{(}\frac{detg_{1}}{detg_{2}}\Big{)}^{\frac{1}{n}}\leqslant
tr_{g_{2}}g_{1}\leqslant
n\Big{(}\frac{detg_{1}}{detg_{2}}\Big{)}(tr_{g_{1}}g_{2})^{n-1},$

where $g_{1}$ and $g_{2}$ are any two smooth $n$-dimensional metrics. In our
case,

(3.28) $tr_{g(t)}g_{0}\leqslant
2\Big{(}\frac{detg_{0}}{detg(t)}\Big{)}(tr_{g_{0}}g(t))=2\Big{(}\frac{dV_{g_{0}}}{dV_{g(t)}}\Big{)}^{2}(tr_{g_{0}}g(t)).$

Hence we only need to prove that $dV_{g(t)}$ is bounded from below uniformly.
The volume form evolves as

(3.29) $\frac{\partial}{\partial t}dV_{g(t)}=-RdV_{g(t)}\leqslant
L_{1}dV_{g(t)},$

which implies that $e^{-L_{1}t}dV_{g(t)}$ decrease and then
$dV_{g(t)}\geqslant e^{-L_{1}(T-t)}dV_{g(T)}\geqslant e^{-L_{1}T}dV_{g(T)}$.
So we have

(3.30) $tr_{g(t)}g_{0}\leqslant
4\Big{(}\frac{dV_{g_{0}}}{e^{-L_{1}T}dV_{g(T)}}\Big{)}^{2}e^{L_{1}T}.$

Let $L_{2}=4e^{3L_{1}T}$, we complete this Lemma.

For the sequence of smooth Ricci flow $(X_{i},g_{i}(t))_{t\in[0,T]}$ with
$\tilde{g}_{i}$ as initial condition, we have by Lemma 3.3 and Lemma 3.4, that

(3.31) $g_{i}(t)\leqslant C\delta\ \ \ and\ \ \ tr_{g_{i}(t)}\delta\leqslant
4C^{3}(\frac{dV_{\delta}}{dV_{g_{i}(T)}})^{2},$

where $C$ is the constant in Lemma 3.3. Letting $i\to\infty$ gives

(3.32) $g(t)\leqslant C\delta\ \ \ and\ \ \ tr_{g(t)}\delta\leqslant
4C^{3}(\frac{dV_{\delta}}{dV_{g(T)}})^{2}\ \ \ for\ t\in(0,T],$

which is equivalent to

(3.33) $\frac{1}{A}\delta\leqslant g(t)\leqslant C\delta\ \ \ for\ t\in(0,T],$

where $A$ depends on $C$ and $T$. In fact, we proved the following Lemma.

######  Lemma 3.5.

Assume that $(X,d)$ is a non-degenerate embedded closed convex surface in
$\mathbb{R}^{3}$. Let $(X,g(t))_{t\in(0,T]}$ be a Ricci flow admitting $(X,d)$
as a metric initial condition. Then there exists a constant $C$ such that

(3.34) $\frac{1}{C}\delta\leqslant g(t)\leqslant C\delta\ \ \ for\ t\in(0,T].$

Now Lemma 3.2 follows immediately.

Proof of Lemma 3.2. Since $g(t)=e^{2u(t)}h(x)$ is uniform equivalent to
$\delta$ for $t\in(0,T]$, $u(t)$ is uniformly bounded. Since $u(t)$ increases
to $u_{0}$ as $t$ decreases to $0$, $u_{0}$ is also bounded. $\square$

Next, for an $L^{1}$-function $u$ and a smooth Riemannian metric $h$ on $M$,
there is a metric $d_{h,u}$ defined as

(3.35)
$d_{h,u}(x,y)=\inf_{\gamma\in\Gamma(x,y)}\int_{0}^{1}e^{u(\gamma(\tau))}|\dot{\gamma}(\tau)|_{h}d\tau,$

where $\Gamma(x,y)$ is the space of $C^{1}$ paths $\gamma$ from $[0,1]$ to $M$
with $\gamma(0)=x$ and $\gamma(1)=y$. This metric was studied by Reshetnyak
[12]. For more details, please see the appendix of [14].

In [14], when $(X,d)$ is a compact Alexandrov surface with curvature bounded
from below, the metric $d_{g(t)}$ induced by $g(t)$ (here, $g(t)$ is a Ricci
flow on $M$ with metric initial condition $(X,d)$ in the sense of Theorem 1.2)
converges to $d_{h,u_{0}}$ uniformly, where $u_{0}$ is the $L^{1}$-limit of
the conformal potential $u(t)$ along Ricci flow $(M,g(t))_{t\in(0,T]}$ as
$t\to 0$ in [14]. But $d$ may not be $d_{h,u_{0}}$ there. In fact, we can only
conclude that $(M,d_{h,u_{0}})$ is isometric to $(X,d)$ from the Lemma $2.4$
in [14] . In our case when $(X,d)$ is a non-degenerate embedded closed convex
surface in $\mathbb{R}^{3}$, we prove that indeed $d=d_{h,u_{0}}$.

######  Theorem 3.6.

Assume that $(X,d)$ is a non-degenerate embedded closed convex surface in
$\mathbb{R}^{3}$. Let $(X,g(t))_{t\in(0,T]}$ be the Ricci flow admitting
$(X,d)$ as a metric initial condition and $u(t)$ be the conformal potential
along $(X,g(t))_{t\in(0,T]}$. Then

(3.36) $d=d_{h,u_{0}},$

where $u_{0}(x)$ is the pointwise limit of $u(t,x)$ as $t\to 0$.

###### Proof.

By definition $(\ref{01009})$, and the definition of confromal potential
$g(t)=e^{2u(t,x)}h(x)$, we have

(3.37)
$\begin{split}d_{h,u(t)}(x,y)&=\inf_{\gamma\in\Gamma(x,y)}\int_{0}^{1}e^{u(t,\gamma(\tau))}|\dot{\gamma}(\tau)|_{h}d\tau\\\
&=\inf_{\gamma\in\Gamma(x,y)}\int_{0}^{1}|\dot{\gamma}(\tau)|_{g_{t}(\tau)}d\tau=d_{g(t)}(x,y).\end{split}$

By Lemma $2.4$ in [14], $d_{h,u(t)}$ converges to $d_{h,u_{0}}$ uniformly as
$t\to 0$. Since we have proved that $d_{g(t)}$ converges to $d$ uniformly as
$t\to 0$ on $X$, then $(\ref{0415})$ follows by letting $t\to 0$ on both sides
of $(\ref{01011})$.

We now prove a regularity theorem for the isometry between the metric spaces
$(X_{1},e^{2u_{1}}h_{1})$ and $(X_{2},e^{2u_{2}}h_{2})$, where $u_{1}$ and
$u_{2}$ are two bounded functions, and $h_{1}$ and $h_{2}$ are pull back
metrics of two metrics on $\mathbb{S}^{2}$ with constant Gaussian curvature.

######  Theorem 3.7.

Assume that $F:(X_{1},e^{2u_{1}}h_{1})\rightarrow(X_{2},e^{2u_{2}}h_{2})$ is
an isometry. Then $F$ is differentiable, where $u_{1}$ and $u_{2}$ are two
bounded functions, and $h_{1}$ and $h_{2}$ are two pull back metrics of the
metrics on $\mathbb{S}^{2}$ with constant Gaussian curvature.

###### Proof.

Since $F$ is an isometry, $F$ is bi-Lipschitz and then it is differentiable
almost everywhere. Write locally $h_{1}=\lambda_{1}(du^{2}+dv^{2})$ and
$h_{2}=\lambda_{2}(dx^{2}+dy^{2})$ for some positive functions $\lambda_{1}$
and $\lambda_{2}$. At differentiable point of $F$, we have

$\begin{split}e^{2u_{1}}\lambda_{1}(du^{2}+dv^{2})&=e^{2u_{1}}h_{1}=F^{*}(e^{2u_{2}}h_{2})=e^{2u_{2}\circ
F}(\lambda_{2}\circ F)F^{*}h_{2}\\\ &=e^{2u_{2}\circ F}(\lambda_{2}\circ
F)\big{(}(x_{u}du+x_{v}dv)^{2}+(y_{u}du+y_{v}dv)^{2}\big{)}\\\
&=e^{2u_{2}\circ F}(\lambda_{2}\circ
F)\big{(}(x^{2}_{u}+y^{2}_{u})du^{2}+(x^{2}_{v}+y^{2}_{v})dv^{2}+2(x_{u}x_{v}+y_{u}y_{v})dudv\big{)}\end{split}$

Since $u_{1}$ and $u_{2}$ are bounded functions, we have

(3.38) $x_{u}x_{v}+y_{u}y_{v}=0\ \ \ and\ \ \
x_{u}^{2}+y_{u}^{2}=x_{v}^{2}+y_{v}^{2},$

which is equivalent to the fact that

(3.39) $x_{u}=-y_{v}\ and\ x_{v}=y_{u}\ \ \ or\ \ \ x_{u}=y_{v}\ and\
x_{v}=-y_{u}.$

Then we know that $F$ is differentiable everywhere by using the analytic
extension theorem in [1].

Since $u(t)$ increases to $u_{0}$ and both of them are bounded, by using
$(\ref{01011})$ and Lebesgue’s monotone convergence theorem, we conclude that
$d=d_{h,u_{0}}$ is the metric induced by $e^{2u_{0}}h$.

Proof of Theorem 1.5. By Theorem 3.6, $d_{i}=d_{h_{i},u_{i}}$ $(i=1,2)$ is the
metric induced by $e^{2u_{i}}h_{i}$, where $u_{i}=\lim\limits_{t\to
0}u_{i}(t)$, $u_{i}(t)$ is the conformal potential along
$(X_{i},g_{i}(t))_{t\in(0,T]}$ and $h_{i}$ is the pull back metric of a metric
on $\mathbb{S}^{2}$ with constant Gaussian curvature.

From Theorem 3.7, the isometry $f$ is differentiable. Then
$(X_{1},f^{*}g_{2}(t))_{t\in(0,T)}$ is also a Ricci flow admitting
$(X_{1},d_{1})$ as metric initial condition in the sense that the distance
fucntion induced by $f^{*}g_{2}(t)$ converges uniformly to $d_{1}$ as $t\to
0$. By using Proposition $0.6$ in [14], we have $g_{1}(t)=f^{*}g_{2}(t)$.
$\square$

##  4\. Further discussions

In this section, we introduce our project which aims to study Pogorelov’s
uniqueness theorem by Ricci flow.

Pogorelov’s uniqueness theorem [11] states that any two closed isometric
convex surfaces with induced metrics in $\mathbb{R}^{3}$ are congruent. It is
a generalization of the classical Cohn-Vesson’s rigidity theorem [5].

Our basic idea to study this theorem is to use Ricci flow to construct two
families of smooth convex surfaces approximating the two isometric closed
convex surfaces in Pogorelov’s theorem. We then apply Cohn-Vesson’s rigidity
theorem to the smooth surfaces and take a limit as $t\to 0$ to see if “the
limit of Cohn-Vesson’s rigidity theorem will imply Pogorelov’s rigid theorem”.
More precisely, given two isometric embedded closed convex surfaces
$(X_{1},d_{1})$ and $(X_{2},d_{2})$ in $\mathbb{R}^{3}$, Theorem 1.3 implies
that there are two Ricci flows $(X_{1},g_{1}(t))_{t\in(0,T)}$ and
$(X_{2},g_{2}(t))_{t\in(0,T)}$ admitting $(X_{1},d_{1})$ and $(X_{2},d_{2})$
as metric initial conditions. Then for every positive time $t$, we embed the
Ricci flow $(X_{1},g_{1}(t))$ and $(X_{2},g_{2}(t))$ smoothly and
isometrically into $\mathbb{R}^{3}$ as $(X^{t}_{1},G_{1}(t))$ and
$(X^{t}_{2},G_{2}(t))$ respectively. The validity for these embeddings is due
to the fact that $(X_{1},g_{1}(t))$ and $(X_{2},g_{2}(t))$ are smooth strictly
convex surfaces and the solvability of Weyl’s problem proved by Nirenberg [7].
By Theorem 1.5, $(X^{t}_{1},G_{1}(t))$ and $(X^{t}_{2},G_{2}(t))$ are
isometric. Then Cohn-Vesson’s rigidity theorem implies that there is a
congruence $F(t)\in O(3)$ between them. We hope to investigate the limits of
$(X^{t}_{1},G_{1}(t))$ and $(X^{t}_{2},G_{2}(t))$ as $t\to 0$. If
$(X^{t}_{1},G_{1}(t))$ and $(X^{t}_{2},G_{2}(t))$ converge to $(X_{1},d_{1})$
and $(X_{2},d_{2})$ in Hausdorff distance up to an isometry in $O(3)$
respectively, the compactness of $O(3)$ will imply the congruence between
$(X_{1},d_{1})$ and $(X_{2},d_{2})$.

## References

  * [1] M. Arsove, The Looman-Menchoff theorem and some subharmonic function analogues, Proceedings of the American Mathematical Society, 6 (1955), 94-105.
  * [2] A. Alexandrov, A. D. Alexandrov selected works, Part II, Intrinsic geometry of convex surfaces, Edited by S. Kutateladze, Translated from Russian by S. Vakhrameyev, Chapman and Hall/CRC, Boca Raton, FL, (2006).
  * [3] S. Brendle and R. Schoen, Manifolds with 1/4-pinched curvature are space forms, Journal of the American Mathematical Society, 22 (2009), 287-307.
  * [4] D. Burago, Y. Burago and S. Ivanov, A course in metric geometry, Graduate Studies in Math, 33 (2001), American Mathematical Society, Providence, RI .
  * [5] S. Cohn-Vossen, Unstarre geschlossene Flächen, Mathematische Annalen, 102 (1930), 10-29.
  * [6] R. Hamilton, Three-manifolds with positive Ricci curvature, Journal of Differential Geometry, 17 (1982), 255-306.
  * [7] L. Nirenberg, The Weyl and Minkowski problems in differential geometry in the large, Communications on Pure and Applied Mathematics, 6 (1953), 337-394.
  * [8] G. Perelman, The entropy formula for the Ricci flow and its geometric applications, arXiv: math.DG/0211159.
  * [9] G. Perelman, Ricci flow with surgery on three manifolds, arXiv: math.DG/0303109.
  * [10] A. V. Pogorelov, The rigidity of general convex surfaces. (Russian) Doklady Akad. Nauk SSSR (N.S.) 79, (1951). 739-742.
  * [11] A. V. Pogorelov, Extrinsic geometry of convex surfaces, Translated from Russian by Israel Program for Scientific Translations, Translations of Mathematical Monographs, 35 (1973), American Mathematical Society, Providence, RI.
  * [12] Y. G. Reshetnyak, Two-dimensional manifolds of bounded curvature, Geometry IV, 70 (1993), Springer, Berlin, 3-163.
  * [13] T. Richard, Lower bounds on Ricci flow invariant curvatures and geometric applications, Journal für die Reine und Angewandte Mathematik, 703 (2015), 27-41.
  * [14] T. Richard, Canonical smoothing of compact Aleksandrov surfaces via Ricci flow, Annales scientifiques de l’École normale supérieure, 51 (2018), 263-279.
  * [15] R. Schneider, Convex bodies: the Brunn-Minkowski theory, Second expanded edition, Encyclopedia of Mathematics and its Applications, 151 (2014), Cambridge University Press, Cambridge.
  * [16] W. X. Shi, Deforming the metric on complete Riemannian manifolds, Journal of Differential Geometry, 30 (1989), 223-301.
  * [17] W. X. Shi, Ricci deformation of the metric on complete noncompact Riemannian manifolds, Journal of differential geometry, 30 (1989), 303-394.
  * [18] M. Simon, Ricci flow of almost non-negatively curved three manifolds, Journal für die Reine und Angewandte Mathematik, 630 (2009), 177-217.
  * [19] M. Simon, Ricci flow of non-collapsed three manifolds whose Ricci curvature is bounded from below, Journal für die Reine und Angewandte Mathematik, 662 (2012), 59-94.