===============================================================
Seed finding in the Acts Software Package: Algorithms and Optimizations
Seed finding is an important and computationally expensive problem in
the reconstruction of charged particle tracks; finding solutions to this
problem involves forming triples (\emph{seeds}) of discrete points at
which particles were detected (\emph{spacepoints}) in the detector
volume. This combinatorial process scales cubically with the number of
spacepoints, which in turn is expected to increase in future collision
experiments as well as in upgrades to current experiments such as the
HL-LHC (\emph{High-Luminosity Large Hadron Collider}). The Acts (\emph{A
Common Tracking Software}) software package provides a broad range of
algorithms -- including seeding -- for the reconstruction of charge
particle tracks in a broad range of detectors. In order to provide
competitive performance -- in terms of computation as well as physics --
for future experiments, the Acts software provides highly optimized seed
finding algorithms which can be configured for different detector
geometries. In this talk, we describe the seeding algorithms in traccc
which reduce the combinatorial explosion problem through the use of
structured grids and $k$-dimensional search trees. We compare the
performance of these algorithms in CPU- and GPU-based environments.
Finally, we discuss strategies for reducing the volume of output seeds
-- which impacts the performance of other algorithms such as
combinatorial Kalman filtering -- such as seed filtering and seed merging.
===============================================================