Research project is (co) funded by the Slovenian Research Agency.
UL Member: Faculty of Mathematics and Physics
Code: N1-0154
Project: Probabilistic methods for joint and singular eigenvalue problems
Period: 1. 1. 2021 - 31. 12. 2023
Range per year: 0,73 FTE, category: C
Head: Bor Plestenjak
Research activity: Natural sciences and mathematics
Research Organisations, researchers, citations for bibliographic records
Project description:
Computing eigenvalues and eigenvectors of a matrix is one of the most central numerical linear algebra problems, for which highly sophisticated algorithms and reliable black-box implementations have been developed. Significantly less attention has been paid to a range of non-standard eigenvalue problems, for which the availability of algorithms and software is, in turn, limited. The underlying theme of this project is that randomization helps transform such problems into standard eigenvalue problems, enabling the use of efficient off-the-shelf solvers without compromising numerical robustness. The major deliverables of the project are algorithms and software that guarantee high accuracy with very high probability at moderate cost, together with a demonstration of their value in a range of applications.
With applications in signal processing, data analysis and many other areas, joint eigenvalue problems represent an important class of problems considered in this project. They require the simultaneous diagonalization or triangularization of a family of matrices. In contrast to the optimization-based approaches often used to address this task, this project plans to analyze, improve and extend randomized techniques based on solving standard eigenvalue problems for one or several random linear combinations of these matrices. This will result in algorithms that are simple to implement, robust to noise, and capable of solving large-scale problems, significantly extending the scope and complexity of applications.
When generalized or polynomial eigenvalue problems are singular, the second class of problems considered in this project, the definition and numerical computation of eigenvalues becomes subtle. In fact, it is well known that even tiny perturbations of the data may induce arbitrary changes in the eigenvalues. Despite this anomaly, such singular problems have important applications, in particular in engineering, where they arise from electric circuits or mechanical systems modelled by differential-algebraic equations. In this project, random perturbations and projections will be used to turn singular into regular eigenvalue problems. Guided by probabilistic analyses, algorithms will be developed that return, with very high probability, eigenvalues of the original singular problem in a numerically robust manner.
Multiparameter eigenvalue problems feature aspects from both problem classes. On the one hand, they are frequently reformulated as joint eigenvalue problems and, on the other hand, this reformulation often leads to singular eigenvalue problems, especially in applications related to bivariate polynomial root-finding. We will combine and adapt the randomized techniques to this case, taking the structure induced by the original multivariate eigenvalue problem into account.
