  This paper introduces progressive algorithms for the topological analysis of
scalar data. Our approach is based on a hierarchical representation of the
input data and the fast identification of topologically invariant vertices,
which are vertices that have no impact on the topological description of the
data and for which we show that no computation is required as they are
introduced in the hierarchy. This enables the definition of efficient
coarse-to-fine topological algorithms, which leverage fast update mechanisms
for ordinary vertices and avoid computation for the topologically invariant
ones. We demonstrate our approach with two examples of topological algorithms
(critical point extraction and persistence diagram computation), which generate
interpretable outputs upon interruption requests and which progressively refine
them otherwise. Experiments on real-life datasets illustrate that our
progressive strategy, in addition to the continuous visual feedback it
provides, even improves run time performance with regard to non-progressive
algorithms and we describe further accelerations with shared-memory
parallelism. We illustrate the utility of our approach in batch-mode and
interactive setups, where it respectively enables the control of the execution
time of complete topological pipelines as well as previews of the topological
features found in a dataset, with progressive updates delivered within
interactive times.
