Codes

NFFT Meets Krylov Methods

Abstract: The graph Laplacian is a standard tool in data science, machine learning, and image processing. The corresponding matrix inherits the complex structure of the underlying network and is in certain applications densely populated. This makes computations, in particular matrix-vector products, with the graph Laplacian a hard task. A typical application is the computation of a number of its eigenvalues and eigenvectors. Standard methods become infeasible as the number of nodes in the graph is too large. We propose the use of the fast summation based on the nonequispaced fast Fourier transform (NFFT) to perform the dense matrix-vector product with the graph Laplacian fast without ever forming the whole matrix. The enormous flexibility of the NFFT algorithm allows us to embed the accelerated multiplication into Lanczos-based eigenvalues routines or iterative linear system solvers and even consider other than the standard Gaussian kernels. We illustrate the feasibility of our approach on a number of test problems from image segmentation to semi-supervised learning based on graph-based PDEs. In particular, we compare our approach with the Nyström method. Moreover, we present and test an enhanced, hybrid version of the Nyström method, which internally uses the NFFT.

Publication: D. Alfke, D. Potts, M. Stoll, and T. Volkmer, NFFT Meets Krylov Methods: Fast Matrix-Vector Products for the Graph Laplacian of Fully Connected Networks. Frontiers in Applied Mathematics and Statistics, 4 (2018). Available online at https://doi.org/10.3389/fams.2018.00061.

Software: We provide the MATLAB software NFFT-Lanczos-Example showcasing the basic usage of our proposed method.

Chebyshev Semi-Iteration

In our paper

Publication: All-at-once preconditioning in PDE-constrained optimization; Tyrone Rees; Martin Stoll; Andy Wathen; Kybernetika : Vol. 46 (2); 2010

the algorithm listing the Chebyshev semi-iteration contains two errors. Line 6 and Line 8 should contain μ instead of ω with μ depending on the spectrum of the matrix.

Software: For an example code follow CSI Code .

Multilayer Graphs and Semi-Supervised learning

In our manuscript

Publication: K. Bergermann, M. Stoll, and T. Volkmer, Semi-supervised Learning for Aggregated Multilayer Graphs Using Diffuse Interface Methods and Fast Matrix Vector Products, SIAM Journal on Mathematics of Data Science, 3(2), p.758-785, 2021. Available online at https://doi.org/10.1137/20M1352028.

we consider semi-supervsied learning using multilayer graphs.

Software: Find the corresponding codes by following this link .

Low-Rank Tensor Method for Isogeometric Analysis

Publication: A. Bünger, S. Dolgov, and M. Stoll, A Low-Rank Tensor Method for PDE-Constrained Optimization with Isogeometric Analysis. SIAM Journal on Scientific Computing, 42(1) (2020). Available online at https://doi.org/10.1137/18M1227238.

Software: We provide the MATLAB software LowRankIGA containing the codes used in our publication as well as a usage example.

Multiplex urban public transport networks

In our manuscript

Publication: K. Bergermann and M. Stoll, Orientations and matrix function-based centralities in multiplex network analysis of urban public transport, Applied Network Science, 6, 90, 2021. Available online at https://doi.org/10.1007/s41109-021-00429-9.

we consider orientations and matrix function-based centralities for multiplex urban public transport networks.

Data: Find the corresponding GTFS data set for Germany by following this link.

Software: python codes are available by following this link.

Matrix function-based centralities for multiplex networks

In our manuscript

Publication: K. Bergermann and M. Stoll, Fast computation of matrix function-based centrality measures for layer-coupled multiplex networks, Physical Review E, 105(3), 034305, 2022. Available online at by https://doi.org/10.1103/PhysRevE.105.034305.

we generalize matrix function-based centrality measures to layer-coupled multiplex networks and present efficient numerical methods for the fast approximation of the involved matrix function expressions, which rely on Krylov subspace methods, Gauss quadrature, and stochastic trace estimation.

Software: Matlab codes are available by following this link.