This thesis concerns two related data analysis pipelines, using topological and geometrical methods respectively, to extract relevant information. The first pipeline, referred to as the topological data analysis (TDA) pipeline, constructs a filtered simplicial complex on a given data set in order to describe its shape. The shape is described using a persistence module, which characterizes the topological features of the filtration, and the final step of the pipeline extracts algebraic invariants from this object. The second pipeline, referred to as the geometric data analysis (GDA) pipeline, associates an algebraic variety to a given data set and aims to describe the structure of this variety. Its structure is described using homology, an invariant which for most algebraic varieties can only be computed numerically using sampling methods.

In Paper A we consider invariants on multi-parameter persistence modules. We explain how to convert discrete invariants into stable ones via what we call hierarchical stabilization. We illustrate  this process by constructing stable invariants for multi-parameter persistence modules with respect to the interleaving distance and so called simple noise systems. For one parameter, we recover the standard barcode information. For more than one parameter we prove that  the constructed invariants are in general NP-hard to calculate. A consequence is that computing the feature counting function, proposed by Scolamiero et. al. (2016), is NP-hard.

In Paper B we introduce an efficient algorithm to compute a minimal presentation of a multi-parameter persistent homology module, given a chain complex of free modules as input.  Our approach extends previous  work on this problem in the 2-parameter case, and draws on ideas underlying the F4 and F5 algorithms for Gröbner basis computation. In the r-parameter case, our algorithm computes a presentation for the homology of C ->^F A ->^G B, with modules of rank l,n,m respectively, in O(r²n^r+1 + n^rm + n^r-1m² + rn² l) arithmetic operations. We implement this approach in our new software Muphasa, written in C++. In preliminary computational experiments on synthetic TDA examples,      we compare our approach to a version of a classical approach based on Schreyer's algorithm, and find that ours is substantially faster and more memory efficient. In the course of developing our algorithm for computing presentations, we also introduce algorithms for the closely related problems of computing Gröbner bases for the image and kernel of the morphism G.  This algorithm runs in time O(n^rm + n^r-1m²) and memory O(n² + mn + nr + K), where K is the size of the output.

Paper C analyzes the complexity of fitting a variety, coming from a class of varieties, to a configuration of points in R^N. The complexity measure, called the algebraic complexity, computes the Euclidean Distance Degree (EDD) of a certain variety called the hypothesis variety as the number of points in the configuration increases. Finally, we establish a connection to complexity of architectures of polynomial neural networks. For the problem of fitting an (N-1)-sphere to a configuration of m points in R^N, we give a closed formula for the algebraic complexity of the hypothesis variety as m grows for the case of N=1. For the case N>1 we conjecture a generalization of this formula supported by numerical experiments.

In Paper D we present an efficient algorithm to produce a provably dense sample of a smooth compact variety. The procedure is partly based on computing bottlenecks of the variety. Using geometric information such as the bottlenecks and the local reach we also provide bounds on the density of the sample needed in order to guarantee that the homology of the variety can be recovered from the sample. An implementation of the algorithm is provided together with numerical experiments and a computational     comparison to the algorithm by Dufresne et. al. (2019).

Den här avhandling rör två relaterade data-analys flöden, som använder topologiska respektive geometriska metoder, för att extrahera relevant information. Det första flödet, kallat topological data analysis (TDA) pipeline, konstruerar ett så kallat “filtrerat simpliciellt komplex” på en given datamängd i syfte att beskriva formen på datamängden. Formen beskrivs genom en så kallad persistensmodul, som karaktäriserar de topologiska egenskaperna hos filtreringen, och det slutgiltiga steget i flödet är att extrahera algebraiska invarianter från detta objekt. Det andra flödet, kallat geometric data analysis (GDA) pipeline, associerar en algebraisk varieté till en given datamängd och syftar till att beskriva dess struktur. Strukturen beskrivs med hjälp av homologi, en invariant som för de flesta algebraiska varieteter bara kan beräknas numeriskt med hjälp av testmetoder. 

I Paper A studerar vi invarianter för persistensmoduler med flera parametrar. Vi förklarar vi hur man konverterar diskreta invarianter till stabila via det vi kallar hierarkisk stabilisering. Vi illustrerar denna process genom att konstruera stabila invarianter för persistensmoduler med flera parametrar med avseende på interleaving-metriken och så kallade simple noise systems. För endast en parameter återfår vi barcode-invarianten. För mer än en parameter bevisar vi att de konstruerade invarianterna i allmänhet är NP-svåra att beräkna. En konsekvens är att beräkning av feature counting-funktionen, föreslagen av Scolamiero et. al. (2016), är NP-svår. 

I Paper B introducerar vi en effektiv algoritm för att beräkna en minimal presentation av en multi-parameter persistensmodul, givet ett kedjekomplex av fria moduler som input. Vårt tillvägagångssätt bygger på tidigare arbete med detta problem i fallet med två parametrar och bygger på idéer som ligger till grund för F4 och F5-algoritmerna för att beräkna Gröbner baser. I r-parameter fallet beräknar vi en presentation av homologin för CF−→ AG−→ B med moduler av respektive rang l, n och m med O(r2 nr+1 + nr m + nr−1 m2 + r n2l) aritmetiska operationer. Vi har implementerat vår algoritm i den nya mjukvaran Muphasa, skriven i C++. I preliminära experiment på syntetiska TDA-exempel jämför vi vår strategi med en version av en klassisk algoritm baserat på Schreyer’s algoritm med resultatet att vår algoritm är väsentligt snabbare och mer minneseffektiv. Under utvecklingen av vår algoritm för minimala presentationer så introducerar vi också algoritmer för närbesläktade problem för att beräkna en Gröbner-bas för bilden och kärnan till morfismen G. Vår algoritm i det fallet har tidskomplexiteten O(nr m +nr−1 m2) och minneskomplexitet O(n2 + m n +n r + K),där K är storleken på resultatet. 

Paper C analyserar komplexiteten av att anpassa en algebraisk varietet, som kommer från en klass av varieteter, till en konfiguration av punkter i RN. Komplexitetsmåttet, kallat algebraisk komplexitet, beräknar den Euklidiska avståndsgraden (EDD) för en viss varietet som kallas hypotesvarieteten när antalet punkter i konfigurationen ökar. Slutligen visar vi en koppling till komplexiteten av arkitekturer i polynomiella neurala nätverk. För problemet med att anpassa en (N −1)-sfär till en konfiguration av m punkter i RN, ger vi en sluten formel för hypotesvarietetens algebraiska komplexitet när m växer för fallet N = 1. För fallet N > 1 formulerar vi en förmodan som generaliserar denna formel med stöd av numeriska experiment. 

I Paper D presenterar vi en effektiv algoritm för att producera en bevisligt tät delmängd av en slät och kompakt algebraisk varieté. Algoritmen är delvis baserat på beräkningen av flaskhalsar av varieteten. Med hjälp av geometrisk information så som flaskhalsar och lokal räckvidd ger vi också övre gränser för densiteten som krävs för delmängden för att garantera att varietetens homologi kan återvinnas. En implementation av algoritmen tillhandahålls tillsammans med numeriska experiment och en jämförelse med algoritmen av Dufresne et. al. (2019).