11 November 2021

Talk @ Numerical Methods and Scientific Computing (NMSC) conference

Presenting today at the Numerical Methods and Scientific Computing conference that is taking place this week in Luminy at the CIRM conference center. This meeting is dedicated to Claude Brezinski for his 80th birthday, to whom I make my very best wishes. Thanks to the whole organizing comitte for the kind invitation! Below you can find the title of my talk, a link to the abstract as well as the slides of the presentation (in case you wish to have a look at them)

Title: Optimal L-shaped matrix reordering via nonlinear matrix eigenvectors

Abstract: We are interested in finding a permutation of the entries of a given square matrix $A$, so that the maximum number of its nonzero entries are moved to one of the corners in a L-shaped fashion.
If we interpret the nonzero entries of the matrix as the edges of a graph, this problem boils down to the so-called core–periphery structure, consisting of two sets: the core, a set of nodes that is highly connected across the whole graph, and the periphery, a set of nodes that is well connected only to the nodes that are in the core.
Matrix reordering problems have applications in sparse factorizations and preconditioning, while revealing core–periphery structures in networks has applications in economic, social and communication networks. This optimal reordering problem is a hard combinatorial optimization problem, which we relax into the continuous problem:

\begin{equation}\label{eq:1ft} \max f(x) := \sum_{ij}|A_{ij}| \max\{x_i,x_j\} \qquad \mathrm{s.t.} \qquad \|x\|=1 \end{equation}

While $f$ is still highly nonconvex and thus hardly treatable, we show that the global maximum of $f$ coincides with the nonlinear Perron eigenvector of a suitably defined parameter dependent matrix $M(x)$, i.e. the positive solution to the nonlinear eigenvector problem $M(x) x = \lambda x$. Using recent advances in nonlinear Perron–Frobenius theory, we show that \eqref{eq:1ft} has a unique solution and we propose a nonlinear power-method type scheme that allows us to solve \eqref{eq:1ft} with global convergence guarantees and effectively scales to very large and sparse matrices. We present several numerical experiments showing that the new method largely outperforms baseline techniques.