English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

The graph Laplacian is a standard tool in data science, machine learning, andimage processing. The corresponding matrix inherits the complex structure ofthe underlying network and is in certain applications densely populated. Thismakes computations, in particular matrix-vector products, with the graphLaplacian a hard task. A typical application is the computation of a number ofits eigenvalues and eigenvectors. Standard methods become infeasible as thenumber of nodes in the graph is too large. We propose the use of the fastsummation based on the nonequispaced fast Fourier transform (NFFT) to performthe dense matrix-vector product with the graph Laplacian fast without everforming the whole matrix. The enormous flexibility of the NFFT algorithm allowsus to embed the accelerated multiplication into Lanczos-based eigenvaluesroutines or iterative linear system solvers and even consider other than thestandard Gaussian kernels. We illustrate the feasibility of our approach on anumber of test problems from image segmentation to semi-supervised learningbased on graph-based PDEs. In particular, we compare our approach with theNystr\"om method. Moreover, we present and test an enhanced, hybrid version ofthe Nystr\"om method, which internally uses the NFFT.

NFFT meets Krylov methods: Fast matrix-vector products for the graph Laplacian of fully connected networks