Computational Mathematics Seminar
2024/25
Meetings are held in room 1106 at the Mathematics and Computer Science Faculty on Thursdays 10:15 am (CET)
For questions please contact jakub.leskiewicz@doctoral.uj.edu.pl
Meetings are held in room 1106 at the Mathematics and Computer Science Faculty on Thursdays 10:15 am (CET)
For questions please contact jakub.leskiewicz@doctoral.uj.edu.pl
Title: PersiSort: A New Perspective on Adaptive Sorting Based on Persistence
Abstract: Adaptive sorting exploits the structure of a partially
sorted list—in particular, the sorted segments of a list
called runs—to improve its performance. Persistent ho-
mology, on the other hand, is a topological data anal-
ysis tool that captures a space’s topological features at
different scales. In this paper, we combine these two
seemingly unrelated concepts and introduce a new per-
spective on adaptive sorting. We introduce a new stable
sorting algorithm, referred to as the Persistence Sort (or
PersiSort in short), which utilizes the persistence pairs
among the local extrema of a list. Given a list of n ele-
ments containing r runs with run entropy H, we prove,
for the first time, that any adaptive sorting algorithm
that uses the two-way-merge subroutine (AdaptMerge)
of Carlsson et al. (1990) performs O (nH) = O (n log r)
comparisons to merge precomputed runs based on its
predetermined merge policy, and is therefore worst-case
optimal. Using PersiSort, we then provide a new way
to analyze adaptive sorting with a persistence-based ar-
rangement of runs. Unlike previous work such as Power-
Sort and TimSort, PersiSort does not consider the num-
ber of elements in each run but the values of elements
in the sorting process. We finally discuss the scenar-
ios when PersiSort outperforms several state-of-the-art
adaptive sorting algorithms.
Title: to be announced
Abstract: -
Title: Classification and Hierarchical Refinement Using Conley Index
Abstract: Research conducted over the last decades in the field of rigorous analysis of vector fields using numerical methods resulted in developing a pipeline, allowing for concise representation of regions on the manifold that exhibit interesting dynamical behavior.
The vector field is converted into a combinatorial structure, which is then decomposed into disjoint closed sets called Morse sets.
For each Morse set, Conley index is computed, leading to construction of a graph representing the behavior of the flow. This talk focuses on improvements to combinatorialization and Conley index computation parts of the pipeline, former based on local refinement of the combinatorial structure, and the latter on method of fast computation of upper bound on Conley index, leading to a substantial performance gains.
The talk is based on paper:
Chen, Guoning, et al. Morse Set Classification and Hierarchical Refinement Using Conley Index. , 2009
Title: Pseudo-normal form near saddle-center or saddle-focus equilibria
Abstract: The paper introduces the pseudo-normal form, which generalizes the notion of normal form around an equilibrium. Existence of such normal form for four dimensional case in a neighborhood of a saddle-center or a saddle-focus equilibrium point is proved constructively. It is given as a recurrent scheme providing coefficients of transformation and the new form order by order. Its convergence is proved for a general analytic system. If the system is Hamiltonian or reversible, this pseudo-normal form coincides with the Birkhoff normal form.
Source: A. Delshams, J. T. Lázaro, "Pseudo-normal form near saddle-center or
saddle-focus equilibria" 2005
Title: Morse Decompositions for Coverage Tasks
Abstract: Coverage tasks require the robot to pass over all points within its free space. In this presentation, I will focus on solutions based on exact cellular decompositions. Specifically, I will present a method introduced in the referenced article that defines exact cellular decompositions, where the critical points of Morse functions indicate the locations of cell boundaries. Within each cell, the structure of the space is effectively uniform, allowing for the use of simple control strategies for coverage. A general framework is introduced in which different Morse functions are considered, resulting in various coverage patterns.
Based on: Acar EU, Choset H, Rizzi AA, Atkar PN, Hull D. Morse Decompositions for Coverage Tasks. The International Journal of Robotics Research. 2002;21(4):331-344. doi:10.1177/027836402320556359
Title: Topological simplification guided by the depth poset
Abstract: Topological simplification is the process of reducing the complexity of the structure of a topological space
while maintaining the essential features. Especially may be seen as reordering cells of complex, in
a way which eliminates some persistent homology groups, without affecting the rest. There are
multiple solutions for 2-dimensional complexes; however, for the general case, the problem becomes more
complicated. We present a new approach based on the concept of depth posets.
In my talk at the beginning I will shortly introduced persistent homology and discrete morse theory, next present idea
of depth posets. Later I will define the subproblem of "safe topological simplification", present some classical
theorems and new ones, which are results of my common work together with Dr. Michał Lipiński and Bartosz Furmanek.
Talk will be based on three papers:
Topological simplification guided by the depth poset (work in progress)
Bartosz Furmanek, Jakub Leśkiewicz, Michał Lipiński
Optimal topological simplification of discrete functions on surfaces.
Ulrich Bauer, Carsten Lange, and Max Wardetzky.
The poset of cancellations in a filtered complex.
Herbert Edelsbrunner, Michał Lipiński, Marian Mrozek, and Manuel Soriano Trigueros.
Title: Efficient computation of Vietoris–Rips persistence barcodes
Abstract: Ripser is an algorithm for efficiently computing Vietoris–Rips persistence barcodes in topological data analysis by avoiding the explicit construction of large boundary matrices through implicit representations and optimizations like clearing and the identification of apparent and emergent pairs. This approach significantly reduces memory usage and computation time, and by also leveraging persistent cohomology, Ripser becomes one of the most effective tools for analyzing complex datasets. Talk based on paper: Ulrich Bauer, "Ripser: efficient computation of Vietoris–Rips persistence barcodes" 2021.
Title: Efficient computation of Vietoris–Rips persistence barcodes
Abstract: Ripser is an algorithm for efficiently computing Vietoris–Rips persistence barcodes in topological data analysis by avoiding the explicit construction of large boundary matrices through implicit representations and optimizations like clearing and the identification of apparent and emergent pairs. This approach significantly reduces memory usage and computation time, and by also leveraging persistent cohomology, Ripser becomes one of the most effective tools for analyzing complex datasets. Talk based on paper: Ulrich Bauer, "Ripser: efficient computation of Vietoris–Rips persistence barcodes" 2021.
Title: Samoczynne sprawdzanie poprawności dowodów
Abstract: Niedawne osiągnięcia na przecięciu teorii typów oraz logiki rzucają nowe światło na sztukę dowodzenia twierdzeń. Zachęcają do ostrożnego składania logicznych kroków w sposób zgodny ze składnią danych zasad. Te zasady, na mocy teorii typów, mogą przyjąć formę języka programowania, zaś kompilacja napisanego w tym języku programu jest równoznaczna ze stwierdzeniem poprawności odpowiadającemu programowi dowodowi. W czasie wystąpienia przedstawię jak to możliwe oraz dlaczego jest to pomocne — a może nawet nieuniknione — narzędzie, zarówno dla naukowca tudzież rzemieślnika.
źródła :
Rijke, Egbert. "Introduction to homotopy type theory." arXiv preprint arXiv:2212.11082 (2022).
Thompson, Simon. Type theory and functional programming. Addison Wesley, 1991.
Title: to be announced
Abstract: -
Title: A novel Persistence Framework for graph based multivector fields on Markov chain.
Abstract: In this talk, we will introduce a novel persistence framework for Morse decompositions in Markov chains using combinatorial multivector fields. Our approach provides a structured method to analyze recurrence and stability in finite-state stochastic processes. In our setting filtrations are governed by transition probabilities rather than spatial distances. We construct multivector fields directly from Markov transition matrices, treating states and transitions as elements of a directed graph. By applying Morse decomposition to the induced multivector field, we obtain a hierarchical structure of invariant sets that evolve under changes in transition probabilities. This structure naturally defines a persistence diagram, where each Morse set is indexed by its topological and dynamical complexity via homology and Conley index dimensions.
Title: Reconstruction and Interpolation of Manifolds
Abstract: In this talk, we will present a geometric framework for reconstructing Riemannian manifolds from finite data in metric space. Centered around a constructive version of the geometric Whitney problem, we will discuss conditions under which a metric space X, that is locally close to Rⁿ and satisfies a δ-intrinsic property, can be approximated by a complete n-dimensional Riemannian manifold M. The manifold M is shown to be quasi-isometric to X, with explicit bounds on sectional curvature and injectivity radius derived from the geometry of X. This result provides a rigorous bridge between discrete metric spaces and continuous smooth geometry, with implications for manifold learning, topological data analysis, and geometric reconstruction.
The talk will be based on article: "Reconstruction and Interpolation of Manifolds. I: The Geometric Whitney Problem", written by: Charles Fefferman, Hariharan Narayanan, Sergei Ivanov, Yaroslav Kurylev, Matti Lassas.
Title: Symmetric periodic orbits near binary collision in a restricted four-body problem for the figure-eight choreography
Abstract: This talk presents research on symmetric periodic orbits in a restricted four-body problem, where three bodies of equal mass move along the well-known figure-eight choreography, and a fourth massless particle interacts gravitationally with them. The focus is on motions close to binary collisions between the massless particle and one of the main bodies. To regularize the equations of motion, appropriate coordinate transformations are applied, enabling numerical study of near-collision dynamics. By exploiting reversing symmetries, boundary conditions leading to periodic orbits are derived. Numerical solutions are obtained using the AUTO software package and the Julia programming language. The results reveal the existence of two types of near-collision periodic orbits — with large and small eccentricities — and suggest the potential for infinitely many such orbits. These findings have implications both theoretical (e.g., in the context of the Saari conjecture) and astrophysical. Based on: A. Bengochea, J. Burgos-García, E. Pérez-Chavela "Symmetric periodic orbits near binary collision in a restricted four-body problem for the figure-eight choreography" 2024.
Title: Rigorous Numerics for ODEs Using Chebyshev Series and Domain Decomposition & Wertykalne orbity Lapunowa w kołowym ograniczonym problemie trzech ciał - komputerowo wspierany dowód.
Abstract:
Celem seminarium jest prezentacja ścisłych metod numerycznych dla równań różniczkowych zwyczajnych (ODE), opartych na rozwinięciach w szereg Czebyszewa. Omówiona zostanie teoria stojąca za reprezentacją rozwiązań ODE w przestrzeni współczynników wielomianów Czebyszewa, a także zastosowanie tych metod do problemów brzegowych dla orbit okresowych. Szczególną uwagę poświęcono zastosowaniu algorytmu opartego na metodzie Newtona-Kantorowicza i arytmetyce przedziałowej, które umożliwiają matematycznie ścisłą weryfikację istnienia rozwiązania. Jako przykład praktyczny przedstawiono analizę fragmentu orbity okresowej w układzie Lorenza, porównując uzyskane wyniki z klasycznymi metodami, takimi jak metoda Taylora dostępna w bibliotece CAPD. Seminarium oparte jest na pracy "Rigorous Numerics for ODEs Using Chebyshev Series and Domain Decomposition" autorstwa J.B. van den Berga i R. Sheombarsinga.
Tematem seminarium jest analiza istnienia wertykalnych orbit Lapunowa w kołowym ograniczonym problemie trzech ciał (CR3BP) z wykorzystaniem komputerowych metod weryfikacji. Wykorzystano zaawansowane narzędzia numeryczne, w tym metody przedziałowe i sekcje Poincarégo, które umożliwiły ścisłe udowodnienie istnienia rozwiązań. Prezentowane wyniki obliczeń potwierdzają występowanie wertykalnych orbit Lapunowa w układzie CR3BP.
[1] G. Gómez, W.S. Koon, M.W. Lo, J.E. Marsden, J. Masdemont, S.D. Ross. Invariant manifolds, the spatial three-body problem and space mission design. Advances in the Astronautical Sciences, 109, 01 2001.
[2] Damennick B. Henry, Daniel J. Scheeres. Fully numerical computation of heteroc-linic connection families in the spatial three-body problem. Communications in Nonlinear Science and Numerical Simulation, 130, 2024.
[3] V.G. Szebehely. Theory of Orbits, the Restricted Problem of Three Bodies. Acade-mic Press, 1967.
[4] Irmina Walawska, Daniel Wilczak. Validated numerics for period-tupling and touch-and-go bifurcations of symmetric periodic orbits in reversible systems. Communi-cations in Nonlinear Science and Numerical Simulation, 74:30–54, Lipiec 2019.[6] Daniel Wilczak, Roberto Barrio. Distribution of stable islands within chaotic areas in the non-hyperbolic and hyperbolic regimes in the henon-heiles system. Nonlinear Dynamics, 09 2020
Title: Finding the Homology of Submanifolds with High Confidence from Random Samples
Abstract: In this talk, we present a topological and probabilistic approach to recovering the homology of compact submanifolds embedded in Euclidean space from random samples. Motivated by problems in high-dimensional data analysis, we consider the case where data points are sampled from a distribution supported on or near a smooth submanifold M contained in R^N. We provide conditions under which the union of open Euclidean balls of fixed radius, centered at these random samples, is homotopy equivalent to the manifold M, thus enabling reliable inference of its homology groups. Our results yield explicit estimates for the required sample size based on geometric features such as the condition number of the manifold and remain valid even in the presence of noise. This work offers a rigorous foundation for manifold learning and topological data analysis, combining differential geometry, computational topology, and learning theory into a unified method for topological inference from finite and noisy data. The talk is based on the article "Finding the Homology of Submanifolds with High Confidence from Random Samples" by Partha Niyogi, Stephen Smale, and Shmuel Weinberger.
Title: PersiSort: A New Perspective on Adaptive Sorting Based on Persistence
Abstract: Adaptive sorting exploits the structure of a partially
sorted list—in particular, the sorted segments of a list
called runs—to improve its performance. Persistent ho-
mology, on the other hand, is a topological data anal-
ysis tool that captures a space’s topological features at
different scales. In this paper, we combine these two
seemingly unrelated concepts and introduce a new per-
spective on adaptive sorting. We introduce a new stable
sorting algorithm, referred to as the Persistence Sort (or
PersiSort in short), which utilizes the persistence pairs
among the local extrema of a list. Given a list of n ele-
ments containing r runs with run entropy H, we prove,
for the first time, that any adaptive sorting algorithm
that uses the two-way-merge subroutine (AdaptMerge)
of Carlsson et al. (1990) performs O (nH) = O (n log r)
comparisons to merge precomputed runs based on its
predetermined merge policy, and is therefore worst-case
optimal. Using PersiSort, we then provide a new way
to analyze adaptive sorting with a persistence-based ar-
rangement of runs. Unlike previous work such as Power-
Sort and TimSort, PersiSort does not consider the num-
ber of elements in each run but the values of elements
in the sorting process. We finally discuss the scenar-
ios when PersiSort outperforms several state-of-the-art
adaptive sorting algorithms.
Title: A combinatorial Analog of the Poincaré-Hopf Index Theorem
Abstract: Poincaré-Hopf Index Theorem is a theorem in differential geometry that relates properties of vector fields defined on a compact manifold to the topology of said manifold. It states that, for a vector field defined on a compact manifold M with isolated zeroes, the sum of indices of its critical points is equal to the Euler characteristic of M. In my talk I am going to state and prove an analogous theorem for directed graphs. To this end I am going go define indices for vertices and faces of a graph G, discuss how they relate to indices of critical points of certain vector fields defined on a surface into which G can be embedded, and show that their sum is equal to the Euler characteristic of G.
Based on:
Leon Glass, A Combinatorial Analog of the Poincaré Index Theorem, Journal of Combinatorial Theory (B) 15, 264-268 (1973), https://doi.org/10.1016/0095-8956(73)90040-3
Title: Simple Homotopy Theory
Abstract: Given two CW complexes K and L, we say that K collapses onto L, if there exists a „free” pair of cells, which can be removed from K, yielding L. Combination of such collapses and their inversions called an expansion is called a formal deformation. Finally, a map homotopic to a formal deformation is a simple-homotopy equivalence. Of course simple-homotopy equivalence is a homotopy equivalence, however the answer to the reverse question is false. The obstruction is so-called Whitehead torsion of a homotopy equivalence of CW complexes.
Last time we have defined the Whitehead group of the CW complex L — elements of the group Wh(L) are equivalence classes of (K,L), where K is a CW complex which deformation retracts onto L under certain relation. We have also proven that each equivalence class contains a special representative — one with only r and r+1 cells where r is sufficiently big. Moreover, r cells are attached trivially to a basepoint in L and number of r cells is the same as r+1 cells. This time we will show that this information will allow us to assign to a such element an invertible matrix (in fact, an element of GL(R)/E(R), where E(R) is a subgroup of elementary matrices and R is discussed). It will arise as an expression of some connecting homomorphism in some homotopy long exact sequence of a triple. However, the crucial step is to endow those relative homotopy groups with a ring structure. The ring depends on the fundamental group of the complex L.
This series of talks is based on the book „A course in Simple-Homotopy Theory” by Marshall M. Cohen. Presentation of the book will be continued in the future by Jakub Leśkiewicz, Jakub Mazur and me.
Title: Simple Homotopy Theory
Abstract: -
Title: Introduction to Simple homotopy theory.
Abstract: My presentation will serve as an introduction to presenting the book A Course in Simple Homotopy Theory. I will cover fundamental topics necessary to understand its content and the upcoming seminars in this series. The topics discussed will include:
Fundamental group
Higher homotopy groups
Relative homotopy groups
Long exact sequence
Covering spaces
Seifert-van Kampen theorem
CW complexes
Whitehead theorem
Cellular homology.
Due to the large scope of the material, I will primarily focus on definitions, examples, and theorems, without going into the details of proofs. The presentation of the book will be continued in the following weeks by Jakub Mazur and Bartosz Furmanek.
Title: Equivalence of Leray and Szymczak Functors.
Abstract: In discrete multivalued Conley theory, there is no homotopy along the flow lines. In order to deal with the dependence of the index on the index pairs, one applies the Leray functor, which is an endofunctor on the category of endomorphisms of the category of linear relations (whose objects are R-modules and morphisms relations which agree with addition and ring multiplication). The Leray functor is a normal functor, that is for any pair (V,f), where V is R-module and f is its endomorphism, endomorphism of L(V,f) is an isomorphism. It turns out that every normal functor factors through a universal one, called the Szymczak functor. While Szymczak functor is highly general, determining whether Szym(V,f) is isomorphic to Szym(V’,f’) is computationally expensive. However, if we restrict to the subcategory of modules of finite length (both Noetherian and Artinian), it turns out that determining the isomorphism above is equivalent to determining if L(V,f) and L(V’,f’) are isomorphic, which is significantly easier to verify. This assumption is satisfied by e.g. finitely generated vector spaces and finite modules. The talk is based on joint work with Mateusz Przybylski and Filip Łanecki.
The last meeting will start by examining the situation by hand in a full subcategory of End FRel(Z/p) consisting of the zero space and Z/p field itself. Afterwards we are going to prove main theorems: L(V,f) is isomorphic to L(V’f’) for (V,f) (V’f’) objects in End FRel(R) if and only if Szym(V,f) is isomorphic to Szym(V’,f’) in Szym FRel(R); furthermore if f and f’ are isomorphisms in End FRel(R), then actually (V,f) and (V’f’) are isomorphic in End FRel(R); we will also prove that LM LE (V,f) is isomorphic to LE LM (V,f) for (V,f) in End FRel(R) — that is, the choice of L as LM LE does not matter. Finally, we are going to present an example showing that the assumption on finite length of the considered modules is crucial.
Title: Equivalence of Leray and Szymczak Functors.
Abstract: In discrete multivalued Conley theory, there is no homotopy along the flow lines. In order to deal with the dependence of the index on the index pairs, one applies the Leray functor, which is an endofunctor on the category of endomorphisms of the category of linear relations (whose objects are R-modules and morphisms relations which agree with addition and ring multiplication). The Leray functor is a normal functor, that is for any pair (V,f), where V is R-module and f is its endomorphism, endomorphism of L(V,f) is an isomorphism. It turns out that every normal functor factors through a universal one, called the Szymczak functor. While Szymczak functor is highly general, determining whether Szym(V,f) is isomorphic to Szym(V’,f’) is computationally expensive. However, if we restrict to the subcategory of modules of finite length (both Noetherian and Artinian), it turns out that determining the isomorphism above is equivalent to determining if L(V,f) and L(V’,f’) are isomorphic, which is significantly easier to verify. This assumption is satisfied by e.g. finitely generated vector spaces and finite modules. The talk is based on joint work with Mateusz Przybylski and Filip Łanecki.
During the first two meetings we have explained the motivation coming from the discrete Conley theory. We have also defined the FRel(R) category and Szymczak functor. This time we will finish the construction of the Leray functor on End FRel(R) and possibly investigate its (appropriately defined) equivalence with the Szymczak functor.
Title: Equivalence of Leray and Szymczak Functors.
Abstract: In discrete multivalued Conley theory, there is no homotopy along the flow lines. In order to deal with the dependence of the index on the index pairs, one applies the Leray functor, which is an endofunctor on the category of endomorphisms of the category of linear relations (whose objects are R-modules and morphisms relations which agree with addition and ring multiplication). The Leray functor is a normal functor, that is for any pair (V,f), where V is R-module and f is its endomorphism, endomorphism of L(V,f) is an isomorphism. It turns out that every normal functor factors through a universal one, called the Szymczak functor. While Szymczak functor is highly general, determining whether Szym(V,f) is isomorphic to Szym(V’,f’) is computationally expensive.
However, if we restrict to the subcategory of modules of finite length (both Noetherian and Artinian), it turns out that determining the isomorphism above is equivalent to determining if L(V,f) and L(V’,f’) are isomorphic, which is significantly easier to verify. This assumption is satisfied by e.g. finitely generated vector spaces and finite modules. The talk is based on joint work with Mateusz Przybylski and Filip Łanecki.
During the first meeting we have explained the motivation behind Leray and Szymczak functors coming from the Discrete Conley Theory. We have also defined FRel(R) category and introduced normal functors. This time we will define those functors in FRel(R) setting and investigate their (appropriately defined) equivalence.
Title: Equivalence of Leray and Szymczak Functors.
Abstract: In discrete multivalued Conley theory, there is no homotopy along the flow lines. In order to deal with the dependence of the index on the index pairs, one applies the Leray functor, which is an endofunctor on the category of endomorphisms of the category of linear relations (whose objects are R-modules and morphisms relations which agree with addition and ring multiplication). The Leray functor is a normal functor, that is for any pair (V,f), where V is R-module and f is its endomorphism, endomorphism of L(V,f) is an isomorphism. It turns out that every normal functor factors through a universal one, called the Szymczak functor. While Szymczak functor is highly general, determining whether Szym(V,f) is isomorphic to Szym(V’,f’) is computationally expensive.
However, if we restrict to the subcategory of modules of finite length (both Noetherian and Artinian), it turns out that determining the isomorphism above is equivalent to determining if L(V,f) and L(V’,f’) are isomorphic, which is significantly easier to verify. This assumption is satisfied by e.g. finitely generated vector spaces and finite modules. The talk is based on joint work with Mateusz Przybylski and Filip Łanecki.
Title: Computational approach to dynamics based on topological methods.
Abstract: A computational study of dynamical systems either given explicitly by a formula or only via a finite sample requires combinatorial tool. Among such tools is the concept of combinatorial multivector field, an extension of Forman’s concept of combinatorial vector field which may be studied by algorithmic means. The construction of a combinatorial multivector field combined with transversality may lead to computer-assisted proofs. However, the construction itself is a challenge. In this talk we plan to show a construction of multivector fields from a continous vector field that leads to computer assisted proof.
Title: -
Abstract: -
Title: Solving Differential-algebraic Equations by Taylor Series (I): Computing Taylor Coefficients
Abstract: Presented paper is a part of a series on the DAETS code for solving DAE initial value problems using Taylor series expansion, explains the method for computing Taylor coefficients (TCs) with automatic differentiation. It covers fully implicit, nonlinear DAEs with higher-order derivatives. The paper provides algorithmic details and proves that the method either successfully computes the TCs of the local solution or identifies specific error conditions.
References: "Solving Differential-algebraic Equations by Taylor Series (I): Computing Taylor Coefficients" Nedialko S. Nedialkov and John D. Pryce BIT, Submitted March 2005
Title: Rigorous validation of a Hopf bifurcation in the Kuramoto–Sivashinsky PDE
Abstract: We will review computer-assisted proof techniques to prove that a branch of non-trivial equilibrium solutions in the Kuramoto–Sivashinsky partial differential equation undergoes a Hopf bifurcation. Furthermore, this will provide an essentially constructive proof of the family of time-periodic solutions near the Hopf bifurcation.
This talk will be based on the work of the same name by van den Berg, Jan Bouwe; Queirolo, Elena.
References: van den Berg, J. B., & Queirolo, E. (2022). Rigorous validation of a Hopf bifurcation in the Kuramoto–Sivashinsky PDE. Communications in Nonlinear Science and Numerical Simulation, 108, 1-22. [106133]. doi.org/10.1016/j.cnsns.2021.106133
Title: Zbieżność wyższego rzędu dla inkluzji różniczkowych (Higher Order Method for Differential Inclusions)
Abstract: Inkluzje różniczkowe są uogólnieniem równań różniczkowych zwyczajnych i można je postrzegać jako jako systemy (niestacjonarne) zależne od czasu. Wykorzystywane mogą być m.in. w analizie złożonych systemów lub w teorii sterowania. Podczas seminarium zreferuję pracę, której autorzy proponują algorytm znajdowania rozwiązań inkluzji różniczkowych, zdolny do osiągnięcia kwadratowej i sześciennej zbieżności. Zaprezentuję wyniki otrzymane i umieszczone w artykule dla wybranych nieliniowych systemów.
References: "Higher Order Method for Differential Inclusions" (2020) arxiv.org/abs/2001.11330
Title: Neural ODEs and its applications
Abstract: During our meetings, we will focus on findings from the article Neural Ordinary Differential Equations by Chen et. al. (2019). We will talk about the most important issues related to ODENets - a family of neural networks aimed at learning representations based on the latent state dynamics of the network. We will introduce the most important concepts related to flow-based generative models. We will also present selected applications of the presented methods.
References: Neural Ordinary Differential Equations by Chen et. al. (2019)
https://doi.org/10.48550/arXiv.1806.07366
Title: Neural ODEs and its applications
Abstract: During our meetings, we will focus on findings from the article Neural Ordinary Differential Equations by Chen et. al. (2019). We will talk about the most important issues related to ODENets - a family of neural networks aimed at learning representations based on the latent state dynamics of the network. We will introduce the most important concepts related to flow-based generative models. We will also present selected applications of the presented methods.
References: Neural Ordinary Differential Equations by Chen et. al. (2019)
https://doi.org/10.48550/arXiv.1806.07366
Title: Abstract Domains for Constraint Programming with Differential Equations
Abstract: Cyber-physical systems and their physical parts are frequently described by ordinary differential equations (ODEs). In the presented article, framework for validating such systems is proposed. Validation begins with the correct over-approximation of the reachability states of the given system. Then, the proposed solution employs abstract domains to solve constraint satisfaction problems involving ODEs, introducing two kinds of abstract domains that aim to leverage the continuity of ODE solutions.
Based on the article: Abstract domains for constraint programming with differential equations by Ziat et al. (2020)
https://doi.org/10.1145/3427762.3429453
Title: Equivalence of strength of the Szymczak and Leray functors
Abstract: A necessary step in the construction of a Conley Index is choosing the right normal functor. The functor described by Szymczak is the most powerful choice, as it preserves the most information about the system. However, it is usually difficult to compute. On the contrary, the Leray functor is very straightforward to compute, at least on categories of modules. We will present the generalised construction of the Leray functor on any abelian category and show that on certain subcategories it has the same classifying power as the Szymczak functor.
Title: Komputerowo wspierany dowód dyfuzji w problemie trzech ciał
Abstract: W referacie przedstawię główne tezy przygotowanej przeze mnie rozprawy doktorskiej pod tytułem "Komputerowo wspierany dowód dyfuzji w problemie trzech ciał". W rozprawie tej przedstawiony został komputerowo wspierany dowód dyfuzji w eliptycznym ograniczonym problemie trzech ciał na płaszczyźnie. Rozważany jest kołowy ograniczony problem trzech ciał na płaszczyźnie. Wprowadzając parametr zaburzenia, otrzymujemy problem eliptyczny. Niezaburzony układ zachowuje energię, lecz można pokazać, że dla dostatecznie małej perturbacji istnieją orbity ze zmianą energii, która nie zależy od rozmiaru tej perturbacji. W dowodzie badamy przecięcia rozmaitości stabilnej i niestabilnej normalnie hiperbolicznego cylindra, wykorzystując odwzorowanie rozpraszające oraz teorię śledzenia. Udowadniamy istnienie pseudo-orbit, które śledzą właściwe orbity układu o interesujących nas zmianach energii.
Rozprawa: http://wms.mat.agh.edu.pl/~nwodka/Rozprawa%20doktorska_Natalia_Wodka-Cholewa.pdf
Title: A Dynamic Look at Persistent Homology
Abstract: In the present-day methodology of persistent homology dominates the approach grounded on an algebraic decomposition theorem of persistence modules. However, the original approach by Edelsbrunner, Letscher, Zomorodian (2002), based on a simplicial complex and the concept of a filter has more geometric flavor with birth-death pairing of cells. A filter may be interpreted as a Morse function on the simplicial complex.
This Morse function induces a combinatorial dynamical system via a class of birth-death pairs, called shallow pairs. Other birth-death pairs may
be indicated by heteroclinic connections in this dynamical system. They require cancellation of shallow pairs to become visible as new shallow
pairs in the reduced complex. This leads to depth poset, a poset structure in the collection of birth-death pairs. The induced dynamical
system together with the depth poset may be used to get more insight into the shape of data.
Based on research in progress with Herbert Edelsbrunner.
Title: Vines and Vineyards by Updating Persistence in Linear Time
Abstract: The original algorithm that computes persistence diagrams takes worst-case time cubic in the number of simplices. The main result is an algorithm that maintains the pairing in worst-case linear time per transposition in the ordering. A side-effect of the algorithm’s analysis is an elementary proof of the stability of persistence diagrams in the special case of piecewise-linear functions. The algorithm can be used to compute 1-parameter families of diagrams.
Based on the article: Vines and vineyards by updating persistence in linear time by
D. Cohen-Steiner, H. Edelsbrunner and D. Morozov.
Title: Kompleks Viertorisa-Ripsa
Abstract: Kompleks Viertorisa-Ripsa jest abstrakcyjnym kompleksem symplicjalnym zdefiniowanym dla zbioru punktów w przestrzeni Euklidesowej który istotnie korzysta z odległości między punktami. Stanowi on łatwo obliczalną aproksymację dla typu homotopii zbioru z którego pochodzą punkty. Można pokazać dobre zachowanie tej konstrukcji w przypadku planarnym.
Title: Optimal approximation of solutions to SDEs driven by countably dimensional Wiener process
Abstract: In this talk we focus on numerical approximation of stochastic differential equations (SDEs) with countably dimensional noise
structure. First, we cover pointwise approximation problem for jump-diffusion SDEs with jumps driven by Poisson random measure [1].
Second, we investigate global approximation for models with additive noise [2]. Our analysis is performed in the spirit of Information-based
Complexity (IBC). In both cases, we deliver asymptotic lower error bounds holding for any algorithm in the predefined classes of methods.
We also construct implementable (randomised or with adaptive step-size control) Euler-Maruyama schemes which asymptotically attain these
estimates. Finally, we report results of numerical experiments conducted via CUDA API on Nvidia graphic cards and multiprocessing library on
CPUs.
References:
[1] Przybyłowicz, P., Sobieraj, M., Stępień, Ł.: Efficient approximation
of SDEs driven by countably dimensional Wiener process and Poisson
random measure, SIAM J. Numer. Anal. 60 (2022), 824–855.
[2] Stępień, Ł.: Adaptive step-size control for SDEs driven by countably
dimensional Wiener process, Numer. Algor. (2023).
Title: Global dynamics for steep sigmoidal nonlinearities in two dimensions (III)
Abstract: I will present the article „Global dynamics for steep sigmoidal nonlinearities in two dimensions” written by T. Gedeon, S. Harker, H. Kokubu, K. Mischaikow and H. Oka. Its focus is the construction of mathematical, combinatorial model of dynamics given by biological structures known as regulatory networks. In the first seminar I will present motivation and goals. It will be followed by remarks on some basic concepts (lattice, Morse sets, multivalued maps) and lastly I will be focusing on building two concepts: switching system and associated continuous switching system.
Title: Vines and Vineyards
by Updating Persistence in Linear Time
Abstract: In this talk we will first introduce persistent homology and the stability theorem for persistence diagram, then we will talk about vine and vineyards of pairwise distance function.
Title: Global dynamics for steep sigmoidal nonlinearities in two dimensions (II)
Abstract: I will present the article „Global dynamics for steep sigmoidal nonlinearities in two dimensions” written by T. Gedeon, S. Harker, H. Kokubu, K. Mischaikow and H. Oka. Its focus is the construction of mathematical, combinatorial model of dynamics given by biological structures known as regulatory networks. In the first seminar I will present motivation and goals. It will be followed by remarks on some basic concepts (lattice, Morse sets, multivalued maps) and lastly I will be focusing on building two concepts: switching system and associated continuous switching system.
Title: Global dynamics for steep sigmoidal nonlinearities in two dimensions (I)
Abstract: I will present the article „Global dynamics for steep sigmoidal nonlinearities in two dimensions” written by T. Gedeon, S. Harker, H. Kokubu, K. Mischaikow and H. Oka. Its focus is the construction of mathematical, combinatorial model of dynamics given by biological structures known as regulatory networks. In the first seminar I will present motivation and goals. It will be followed by remarks on some basic concepts (lattice, Morse sets, multivalued maps) and lastly I will be focusing on building two concepts: switching system and associated continuous switching system.
Title: Application of Radii Polynomial Approach to the Swift-Hohenberg differential equation (II)
Abstract: I will present the extension of Newton’s method to work with infinite dimensional Banach spaces. The main goal of this is to develop an abstract framework, called Radii Polynomial Approach, for rigorous numerical solving initial condition of differential equations. The main idea is that solving differential equation is equivalent to finding a zero of differential operator which is a map between functional spaces. Later I will show the application of Radii Polynomial Approach to find periodic orbit of Swift-Hohenberg equation which forces chaotic behavior of the system. The presentation is based on the article “Introduction to rigorous numerics in dynamics: general functional analytic setup and an example that forces chaos” by Jan Bouwe van den Berg.
Title: Application of Radii Polynomial Approach to the Swift-Hohenberg differential equation
Abstract: I will present the extension of Newton’s method to work with infinite dimensional Banach spaces. The main goal of this is to develop an abstract framework, called Radii Polynomial Approach, for rigorous numerical solving initial condition of differential equations. The main idea is that solving differential equation is equivalent to finding a zero of differential operator which is a map between functional spaces. Later I will show the application of Radii Polynomial Approach to find periodic orbit of Swift-Hohenberg equation which forces chaotic behavior of the system. The presentation is based on the article “Introduction to rigorous numerics in dynamics: general functional analytic setup and an example that forces chaos” by Jan Bouwe van den Berg.
Title: An Introduction to an Introduction to Homotopy Type Theory (II)
Abstract: Homotopy Type Theory is an alternative foundational theory of mathematics. One of its major strengths is its ability to be mechanised — that is, explained to a computer. It naturally leads to functional programming and, at the same time, proof theory, allowing automated proof checking and maybe even proof searching. We are going to start with Intentional Type Theory and try to get a broad overview of the subject and its connections to constructive and classical mathematics, programming and logic.
Title: An Introduction to an Introduction to Homotopy Type Theory (I)
Abstract: Homotopy Type Theory is an alternative foundational theory of mathematics. One of its major strengths is its ability to be mechanised — that is, explained to a computer. It naturally leads to functional programming and, at the same time, proof theory, allowing automated proof checking and maybe even proof searching. We are going to start with Intentional Type Theory and try to get a broad overview of the subject and its connections to constructive and classical mathematics, programming and logic.
Title: Combinatorial approach to sampled dynamics based on surrogate Gaussian Process modeling (III)
Abstract: We propose a novel method combining combinatorial topological dynamics and Gaussian Process (GP) modeling, whereby we can characterize the global dynamics from a finite amount of data, with high confidence. More specifically, the data is used to construct a surrogate GP model. We then describe the dynamics using algebraic topological invariants inferred from a combinatorial multivector field built on the basis of the GP model. Our experiments show that relatively sparse data is sufficient to obtain a qualitative description of the underlying dynamics with high confidence.
In the talk I will also present the basics of both concepts: combinatorial multivector fields introduced by M. Mrozek [M. Mrozek, Conley-Morse-Forman theory for combinatorial multivector fields on Lefschetz complexes, Foundations of Computational Mathematics 17(2017), 1585--1633 ] and GP modeling.
Title: Combinatorial approach to sampled dynamics based on surrogate Gaussian Process modeling (II)
Abstract: We propose a novel method combining combinatorial topological dynamics and Gaussian Process (GP) modeling, whereby we can characterize the global dynamics from a finite amount of data, with high confidence. More specifically, the data is used to construct a surrogate GP model. We then describe the dynamics using algebraic topological invariants inferred from a combinatorial multivector field built on the basis of the GP model. Our experiments show that relatively sparse data is sufficient to obtain a qualitative description of the underlying dynamics with high confidence.
In the talk I will also present the basics of both concepts: combinatorial multivector fields introduced by M. Mrozek [M. Mrozek, Conley-Morse-Forman theory for combinatorial multivector fields on Lefschetz complexes, Foundations of Computational Mathematics 17(2017), 1585--1633 ] and GP modeling.
Title: Combinatorial approach to sampled dynamics based on surrogate Gaussian Process modeling (I)
Abstract: We propose a novel method combining combinatorial topological dynamics and Gaussian Process (GP) modeling, whereby we can characterize the global dynamics from a finite amount of data, with high confidence. More specifically, the data is used to construct a surrogate GP model. We then describe the dynamics using algebraic topological invariants inferred from a combinatorial multivector field built on the basis of the GP model. Our experiments show that relatively sparse data is sufficient to obtain a qualitative description of the underlying dynamics with high confidence.
In the talk I will also present the basics of both concepts: combinatorial multivector fields introduced by M. Mrozek [M. Mrozek, Conley-Morse-Forman theory for combinatorial multivector fields on Lefschetz complexes, Foundations of Computational Mathematics 17(2017), 1585--1633 ] and GP modeling.
Title: Wprowadzenie do metod ścisłej analizy numerycznej. (3)
Abstract: Opowiem o podstawowych narzędziach ścisłej analizy numerycznej i ich przykładowych zastosowaniach.
room 0094
Title: Wprowadzenie do metod ścisłej analizy numerycznej. (2)
Abstract: Opowiem o podstawowych narzędziach ścisłej analizy numerycznej i ich przykładowych zastosowaniach.
Title: Wprowadzenie do metod ścisłej analizy numerycznej.
Abstract: Opowiem o podstawowych narzędziach ścisłej analizy numerycznej i ich przykładowych zastosowaniach.
room 0094
Title: Informal introduction to persistent homology.
Abstract: Homology theory makes topology a computational subject. The discovery of persistent homology about 25 years ago facilitated applications of topology in data analysis and today Topological Data Analysis (TDA) is a very hot subject. In the talk I'll present basics of persistent homology together with the algorithm for its computation.