Yv
Y. van Gennip
info
Please Note
<p>This page displays the records of the person named above and is not linked to a unique person identifier. This record may need to be merged to a profile.</p>
6 records found
1
Optimal transport studies how one distribution of mass can be transformed into another at least total cost. This thesis implements a numerical method dor the dynamic formulation due to Benamou and Brenier, and extends it to a position-dependent cost. After reviewing the Monge, Kantorovich and Benamou--Brenier formulations and the equivalence between the static and dynamic pictures, the standard quadratic kinetic energy cost is solved with the ALG2 augmented-Lagrangian scheme. The solver is derived in full (through a convexifying change of variables, a saddle-point reformulation and an augmented Lagrangian) and validated in two independent ways: against the closed-form cost of a translation, and against an independent solver that computes the exact discrete transport plan, exact up to the spatial discretisation. These checks are accompanied by systematic studies of the solver's sensitivity to the penalty parameter, the grid resolution and the convergence tolerance.
The principal contribution is a weighted, position-dependent cost, in which each velocity component is weighted by 1/x. Re-deriving the ALG2 scheme for this cost turns the constant-coefficient solve at the core of the iteration into a variable-coefficient one, which is discretised with a conservative finite-difference scheme. A direct comparison of the two solvers shows that the weight acts on the total transport cost as an approximately uniform, analytically predictable surcharge of roughly a factor two, while reshaping the velocity field in a strongly shape-dependent way, tilting the flow toward the regions where movement is cheaper. In one dimension the weighted scheme converges without difficulty, although its convergence is harder to certify. The solver's residual more often flattens out before reaching the strict tolerance. Extended to two dimensions, it reproduces the expected constant-speed geodesic for the uniform cost, but becomes unstable when the singular weight acts along both spatial axes at once. This is a specific and clearly identified limitation, and the natural starting point for future work. ...
The principal contribution is a weighted, position-dependent cost, in which each velocity component is weighted by 1/x. Re-deriving the ALG2 scheme for this cost turns the constant-coefficient solve at the core of the iteration into a variable-coefficient one, which is discretised with a conservative finite-difference scheme. A direct comparison of the two solvers shows that the weight acts on the total transport cost as an approximately uniform, analytically predictable surcharge of roughly a factor two, while reshaping the velocity field in a strongly shape-dependent way, tilting the flow toward the regions where movement is cheaper. In one dimension the weighted scheme converges without difficulty, although its convergence is harder to certify. The solver's residual more often flattens out before reaching the strict tolerance. Extended to two dimensions, it reproduces the expected constant-speed geodesic for the uniform cost, but becomes unstable when the singular weight acts along both spatial axes at once. This is a specific and clearly identified limitation, and the natural starting point for future work. ...
Optimal transport studies how one distribution of mass can be transformed into another at least total cost. This thesis implements a numerical method dor the dynamic formulation due to Benamou and Brenier, and extends it to a position-dependent cost. After reviewing the Monge, Kantorovich and Benamou--Brenier formulations and the equivalence between the static and dynamic pictures, the standard quadratic kinetic energy cost is solved with the ALG2 augmented-Lagrangian scheme. The solver is derived in full (through a convexifying change of variables, a saddle-point reformulation and an augmented Lagrangian) and validated in two independent ways: against the closed-form cost of a translation, and against an independent solver that computes the exact discrete transport plan, exact up to the spatial discretisation. These checks are accompanied by systematic studies of the solver's sensitivity to the penalty parameter, the grid resolution and the convergence tolerance.
The principal contribution is a weighted, position-dependent cost, in which each velocity component is weighted by 1/x. Re-deriving the ALG2 scheme for this cost turns the constant-coefficient solve at the core of the iteration into a variable-coefficient one, which is discretised with a conservative finite-difference scheme. A direct comparison of the two solvers shows that the weight acts on the total transport cost as an approximately uniform, analytically predictable surcharge of roughly a factor two, while reshaping the velocity field in a strongly shape-dependent way, tilting the flow toward the regions where movement is cheaper. In one dimension the weighted scheme converges without difficulty, although its convergence is harder to certify. The solver's residual more often flattens out before reaching the strict tolerance. Extended to two dimensions, it reproduces the expected constant-speed geodesic for the uniform cost, but becomes unstable when the singular weight acts along both spatial axes at once. This is a specific and clearly identified limitation, and the natural starting point for future work.
The principal contribution is a weighted, position-dependent cost, in which each velocity component is weighted by 1/x. Re-deriving the ALG2 scheme for this cost turns the constant-coefficient solve at the core of the iteration into a variable-coefficient one, which is discretised with a conservative finite-difference scheme. A direct comparison of the two solvers shows that the weight acts on the total transport cost as an approximately uniform, analytically predictable surcharge of roughly a factor two, while reshaping the velocity field in a strongly shape-dependent way, tilting the flow toward the regions where movement is cheaper. In one dimension the weighted scheme converges without difficulty, although its convergence is harder to certify. The solver's residual more often flattens out before reaching the strict tolerance. Extended to two dimensions, it reproduces the expected constant-speed geodesic for the uniform cost, but becomes unstable when the singular weight acts along both spatial axes at once. This is a specific and clearly identified limitation, and the natural starting point for future work.
The maximum-independent-set problem is a fundamental graph problem with applications in situations where one wants to select as many mutually compatible objects as possible, such as non-conflicting tasks or choices. This problem is computationally difficult to solve exactly on large graphs. This motivates the use of heuristic algorithms. However, heuristic performance can depend strongly on the structure of the input graph, so it is not enough to ask which algorithm performs best on average. It is also important to understand when and why a heuristic fails.
This Bachelor End Project studies heuristic algorithms for the maximum-independent-set problem from a structural point of view. We compare three methods: a minimum-degree Greedy algorithm, Lotka–Volterra dynamics, and simulated annealing, using an exact solver as a benchmark on small graphs. The goal is not only to compare solution sizes, but also to identify the graph structures and parameter choices that cause each method to perform poorly.
The results show that the algorithms fail for different structural reasons. Greedy can perform poorly when the minimum-degree rule is locally attractive but globally misleading. In the tested bad examples, Greedy selects vertices that look good by degree, but this choice blocks access to a much larger independent set. Lotka–Volterra dynamics can converge to maximal independent sets that are not maximum. This behavior is influenced by the initial condition and becomes more important when the graph contains many competing maximal independent sets. Simulated annealing is affected by the structure of the energy landscape. In particular, the experiments suggest that failure is not caused only by a single large energy barrier, but also by the presence of many competing trap states.
The parameter experiments support these interpretations. Increasing the Lotka–Volterra competition parameter τ strengthens early suppression between neighboring vertices but often leads to smaller independent sets. For simulated annealing, increasing the penalty parameter α makes edge conflicts more expensive and helps the algorithm reach feasible states earlier, but it can also reduce exploration through temporary conflict states. Longer cooling schedules improve performance, especially on larger or more crowded instances, but require more computation.
Overall, the thesis shows that the performance of maximum-independent-set heuristics cannot be explained by graph size alone. The relevant difficulty depends on graph structure, the number of competing maximal independent sets, the initial condition, and the algorithm parameters. This gives a more diagnostic view of heuristic performance: instead of treating Greedy, Lotka–Volterra, and simulated annealing as black-box methods, the thesis identifies structural warning signs that indicate when each method is likely to struggle. ...
This Bachelor End Project studies heuristic algorithms for the maximum-independent-set problem from a structural point of view. We compare three methods: a minimum-degree Greedy algorithm, Lotka–Volterra dynamics, and simulated annealing, using an exact solver as a benchmark on small graphs. The goal is not only to compare solution sizes, but also to identify the graph structures and parameter choices that cause each method to perform poorly.
The results show that the algorithms fail for different structural reasons. Greedy can perform poorly when the minimum-degree rule is locally attractive but globally misleading. In the tested bad examples, Greedy selects vertices that look good by degree, but this choice blocks access to a much larger independent set. Lotka–Volterra dynamics can converge to maximal independent sets that are not maximum. This behavior is influenced by the initial condition and becomes more important when the graph contains many competing maximal independent sets. Simulated annealing is affected by the structure of the energy landscape. In particular, the experiments suggest that failure is not caused only by a single large energy barrier, but also by the presence of many competing trap states.
The parameter experiments support these interpretations. Increasing the Lotka–Volterra competition parameter τ strengthens early suppression between neighboring vertices but often leads to smaller independent sets. For simulated annealing, increasing the penalty parameter α makes edge conflicts more expensive and helps the algorithm reach feasible states earlier, but it can also reduce exploration through temporary conflict states. Longer cooling schedules improve performance, especially on larger or more crowded instances, but require more computation.
Overall, the thesis shows that the performance of maximum-independent-set heuristics cannot be explained by graph size alone. The relevant difficulty depends on graph structure, the number of competing maximal independent sets, the initial condition, and the algorithm parameters. This gives a more diagnostic view of heuristic performance: instead of treating Greedy, Lotka–Volterra, and simulated annealing as black-box methods, the thesis identifies structural warning signs that indicate when each method is likely to struggle. ...
The maximum-independent-set problem is a fundamental graph problem with applications in situations where one wants to select as many mutually compatible objects as possible, such as non-conflicting tasks or choices. This problem is computationally difficult to solve exactly on large graphs. This motivates the use of heuristic algorithms. However, heuristic performance can depend strongly on the structure of the input graph, so it is not enough to ask which algorithm performs best on average. It is also important to understand when and why a heuristic fails.
This Bachelor End Project studies heuristic algorithms for the maximum-independent-set problem from a structural point of view. We compare three methods: a minimum-degree Greedy algorithm, Lotka–Volterra dynamics, and simulated annealing, using an exact solver as a benchmark on small graphs. The goal is not only to compare solution sizes, but also to identify the graph structures and parameter choices that cause each method to perform poorly.
The results show that the algorithms fail for different structural reasons. Greedy can perform poorly when the minimum-degree rule is locally attractive but globally misleading. In the tested bad examples, Greedy selects vertices that look good by degree, but this choice blocks access to a much larger independent set. Lotka–Volterra dynamics can converge to maximal independent sets that are not maximum. This behavior is influenced by the initial condition and becomes more important when the graph contains many competing maximal independent sets. Simulated annealing is affected by the structure of the energy landscape. In particular, the experiments suggest that failure is not caused only by a single large energy barrier, but also by the presence of many competing trap states.
The parameter experiments support these interpretations. Increasing the Lotka–Volterra competition parameter τ strengthens early suppression between neighboring vertices but often leads to smaller independent sets. For simulated annealing, increasing the penalty parameter α makes edge conflicts more expensive and helps the algorithm reach feasible states earlier, but it can also reduce exploration through temporary conflict states. Longer cooling schedules improve performance, especially on larger or more crowded instances, but require more computation.
Overall, the thesis shows that the performance of maximum-independent-set heuristics cannot be explained by graph size alone. The relevant difficulty depends on graph structure, the number of competing maximal independent sets, the initial condition, and the algorithm parameters. This gives a more diagnostic view of heuristic performance: instead of treating Greedy, Lotka–Volterra, and simulated annealing as black-box methods, the thesis identifies structural warning signs that indicate when each method is likely to struggle.
This Bachelor End Project studies heuristic algorithms for the maximum-independent-set problem from a structural point of view. We compare three methods: a minimum-degree Greedy algorithm, Lotka–Volterra dynamics, and simulated annealing, using an exact solver as a benchmark on small graphs. The goal is not only to compare solution sizes, but also to identify the graph structures and parameter choices that cause each method to perform poorly.
The results show that the algorithms fail for different structural reasons. Greedy can perform poorly when the minimum-degree rule is locally attractive but globally misleading. In the tested bad examples, Greedy selects vertices that look good by degree, but this choice blocks access to a much larger independent set. Lotka–Volterra dynamics can converge to maximal independent sets that are not maximum. This behavior is influenced by the initial condition and becomes more important when the graph contains many competing maximal independent sets. Simulated annealing is affected by the structure of the energy landscape. In particular, the experiments suggest that failure is not caused only by a single large energy barrier, but also by the presence of many competing trap states.
The parameter experiments support these interpretations. Increasing the Lotka–Volterra competition parameter τ strengthens early suppression between neighboring vertices but often leads to smaller independent sets. For simulated annealing, increasing the penalty parameter α makes edge conflicts more expensive and helps the algorithm reach feasible states earlier, but it can also reduce exploration through temporary conflict states. Longer cooling schedules improve performance, especially on larger or more crowded instances, but require more computation.
Overall, the thesis shows that the performance of maximum-independent-set heuristics cannot be explained by graph size alone. The relevant difficulty depends on graph structure, the number of competing maximal independent sets, the initial condition, and the algorithm parameters. This gives a more diagnostic view of heuristic performance: instead of treating Greedy, Lotka–Volterra, and simulated annealing as black-box methods, the thesis identifies structural warning signs that indicate when each method is likely to struggle.
We tackle the well-posedness of certain dynamical systems that result in non-autonomous quasi-linear problems in a critical setting, where the coefficients defining the flux and the Neumann boundary conditions depend on the solution itself. We want to show the existence and uniqueness of these solutions on a very short timescale.
The local well-posedness of quasi-linear problems in a critical setting by the maximal $L^p$-regularity theory from Chapter 18 of Hytönen, van Neerven, Veraar, and Weis (2024) are investigated, where we use the non-autonomous setting with non-constant domains from Di Giorgio, Lunardi, and Schnaubelt (2005). Dominant examples in the literature of such problems are problems with multidimensional, non-constant Neumann boundary conditions influencing the domain of the operator. In this thesis, we look for ways to ensure the short-timescale existence and uniqueness of solutions to these problems and research the possibility of applying them to the model problem with Neumann boundary conditions. By applying non-autonomous linear theory from Chapter 3 Part II of Yagi (2010), we find a result that allows us to determine the existence and uniqueness of short timescale mild solutions. When applied, however, we see that, unlike the work of Yagi (2010), we can only guarantee the local well-posedness of the model Neumann problem by using averaging functions because of our more strict critical setting. In the future, results can be based on different regularity types, or the given result can be applied on spaces with negative smoothness. ...
The local well-posedness of quasi-linear problems in a critical setting by the maximal $L^p$-regularity theory from Chapter 18 of Hytönen, van Neerven, Veraar, and Weis (2024) are investigated, where we use the non-autonomous setting with non-constant domains from Di Giorgio, Lunardi, and Schnaubelt (2005). Dominant examples in the literature of such problems are problems with multidimensional, non-constant Neumann boundary conditions influencing the domain of the operator. In this thesis, we look for ways to ensure the short-timescale existence and uniqueness of solutions to these problems and research the possibility of applying them to the model problem with Neumann boundary conditions. By applying non-autonomous linear theory from Chapter 3 Part II of Yagi (2010), we find a result that allows us to determine the existence and uniqueness of short timescale mild solutions. When applied, however, we see that, unlike the work of Yagi (2010), we can only guarantee the local well-posedness of the model Neumann problem by using averaging functions because of our more strict critical setting. In the future, results can be based on different regularity types, or the given result can be applied on spaces with negative smoothness. ...
We tackle the well-posedness of certain dynamical systems that result in non-autonomous quasi-linear problems in a critical setting, where the coefficients defining the flux and the Neumann boundary conditions depend on the solution itself. We want to show the existence and uniqueness of these solutions on a very short timescale.
The local well-posedness of quasi-linear problems in a critical setting by the maximal $L^p$-regularity theory from Chapter 18 of Hytönen, van Neerven, Veraar, and Weis (2024) are investigated, where we use the non-autonomous setting with non-constant domains from Di Giorgio, Lunardi, and Schnaubelt (2005). Dominant examples in the literature of such problems are problems with multidimensional, non-constant Neumann boundary conditions influencing the domain of the operator. In this thesis, we look for ways to ensure the short-timescale existence and uniqueness of solutions to these problems and research the possibility of applying them to the model problem with Neumann boundary conditions. By applying non-autonomous linear theory from Chapter 3 Part II of Yagi (2010), we find a result that allows us to determine the existence and uniqueness of short timescale mild solutions. When applied, however, we see that, unlike the work of Yagi (2010), we can only guarantee the local well-posedness of the model Neumann problem by using averaging functions because of our more strict critical setting. In the future, results can be based on different regularity types, or the given result can be applied on spaces with negative smoothness.
The local well-posedness of quasi-linear problems in a critical setting by the maximal $L^p$-regularity theory from Chapter 18 of Hytönen, van Neerven, Veraar, and Weis (2024) are investigated, where we use the non-autonomous setting with non-constant domains from Di Giorgio, Lunardi, and Schnaubelt (2005). Dominant examples in the literature of such problems are problems with multidimensional, non-constant Neumann boundary conditions influencing the domain of the operator. In this thesis, we look for ways to ensure the short-timescale existence and uniqueness of solutions to these problems and research the possibility of applying them to the model problem with Neumann boundary conditions. By applying non-autonomous linear theory from Chapter 3 Part II of Yagi (2010), we find a result that allows us to determine the existence and uniqueness of short timescale mild solutions. When applied, however, we see that, unlike the work of Yagi (2010), we can only guarantee the local well-posedness of the model Neumann problem by using averaging functions because of our more strict critical setting. In the future, results can be based on different regularity types, or the given result can be applied on spaces with negative smoothness.
A large number of modern learning problems involve working with highly interrelated and interconnected data. Graph-based learning is an emerging technique for approaching such problems, by representing this data as a graph (a.k.a. a network). That is, the points of data are represented by the vertices of the graph, and then the edges linking these vertices represent the relationships between the points of data. This provides a unified perspective for thinking about all sorts of interrelated data: the vertices could represent pixels in an image or people in a social network, and the underlying framework would be the same...
...
...
A large number of modern learning problems involve working with highly interrelated and interconnected data. Graph-based learning is an emerging technique for approaching such problems, by representing this data as a graph (a.k.a. a network). That is, the points of data are represented by the vertices of the graph, and then the edges linking these vertices represent the relationships between the points of data. This provides a unified perspective for thinking about all sorts of interrelated data: the vertices could represent pixels in an image or people in a social network, and the underlying framework would be the same...
The graph Laplacian is a tool which is commonly used in different applications, amongst which spectral clustering. This report contains a research in different def- initions for the graph Laplacian applied on directed graphs, since it is rarely used in applications neither occurs often in literature. Two definitions are discussed into more detail. The first definition considers a directed graph as a bipartite graph between the node set containing all nodes with outgoing edges and the node set containing all nodes with incoming edges. A Laplacian is defined on both sets distinctly and later on the two Laplacians are convexly combined to define a Laplacian on the whole directed graph. The second definition considers a random walk on a directed graph. We will see why a random walk on a directed graph is equivalent to a finite Markov Chain with a corresponding transition probability matrix. This definition will be used for clustering. The method for clustering as well as the definition for the directed graph Lapla- cian require a unique stationary distribution associated with the transition proba- bilities on the node set of the graph. The existence and uniqueness of the stationary distribution became an important part of this report, because the given data set has to meet up with these properties to be able to use this method. Furthermore, the introduced definitions are used in a MATLAB based model, to get more insights about the spectrum of the directed graph Laplacian. The biggest conclusions to be drawn are that for strongly connected directed graphs, it seems that there is a correlation between the multiplicity of eigenvalues that are close to 1 and the numbers of subsets such that all nodes in the subset are adjacent.
...
The graph Laplacian is a tool which is commonly used in different applications, amongst which spectral clustering. This report contains a research in different def- initions for the graph Laplacian applied on directed graphs, since it is rarely used in applications neither occurs often in literature. Two definitions are discussed into more detail. The first definition considers a directed graph as a bipartite graph between the node set containing all nodes with outgoing edges and the node set containing all nodes with incoming edges. A Laplacian is defined on both sets distinctly and later on the two Laplacians are convexly combined to define a Laplacian on the whole directed graph. The second definition considers a random walk on a directed graph. We will see why a random walk on a directed graph is equivalent to a finite Markov Chain with a corresponding transition probability matrix. This definition will be used for clustering. The method for clustering as well as the definition for the directed graph Lapla- cian require a unique stationary distribution associated with the transition proba- bilities on the node set of the graph. The existence and uniqueness of the stationary distribution became an important part of this report, because the given data set has to meet up with these properties to be able to use this method. Furthermore, the introduced definitions are used in a MATLAB based model, to get more insights about the spectrum of the directed graph Laplacian. The biggest conclusions to be drawn are that for strongly connected directed graphs, it seems that there is a correlation between the multiplicity of eigenvalues that are close to 1 and the numbers of subsets such that all nodes in the subset are adjacent.