Numerical algorithms for nonlinear eigenproblems with eigenvector nonlinearities
Time: Fri 2021-12-17 14.00
Location: F3, Lindstedtsvägen 26, Stockholm
Subject area: Applied and Computational Mathematics, Numerical Analysis
Doctoral student: Parikshit Upadhyaya , Numerisk analys, NA
Opponent: Professor Robert Corless, Ontario Research Centre for Computer Algebra
Supervisor: Professor Elias Jarlebring, Numerisk analys, NA
Eigenproblems and their nonlinear generalizations appear as important problems in a wide variety of fields, ranging from quantum chemistry and vibration analysis to macroeconomics and data science. Hence, the development and analysis of numerical algorithms to solve such problems has a broad multiplicative effect on our ability to answer several crucial scientific questions. In this thesis, we focus on numerical algorithms for a specific type of such a problem which is called a nonlinear eigenproblem with eigenvector nonlinearity (NEPv), where as the name suggests, the nonlinear terms depend on the eigenvectors.
The most widely used numerical algorithm to solve the NEPv in the field of quantum chemistry is the self-consistent field (SCF) iteration, combined with its variants. In Paper A, we analyze the convergence of the SCF iteration by casting it as fixed-point iteration with the density matrix as its state. This allows us to formulate an exact expression for the Jacobian of the fixed-point map in terms of the eigenvalues and eigenvectors of the problem, which then leads to upper bounds for the convergence factor of the SCF iteration. These upper bounds provide a tool to interpret the convergence in terms of higher gaps between occupied and unoccupied eigenvalues, which is an improvement over previous bounds that take into account only the smallest gap.
A natural candidate for solving systems of nonlinear equations is Newton's method. However, a straightforward application of Newton's method to the general NEPv leads to an update equation that is too expensive to solve in each step of the method. In Paper B, we study two different implicit modifications of the update equation, which make it nonlinear in terms of the next eigenvector iterate. However, the two resulting nonlinear equations can be reformulated under certain minor assummptions to lead to explicit procedures or algorithms to execute them. One of the algorithms turns out to be the SCF iteration. The other algorithm was previously unknown to the best of our knowledge and we prove that it displays quadratic convergence, along with other attractive properties.
In Paper C, we show that for a certain class of NEPv where the nonlinearity can be written as a sum of rational functions of the eigenvector multiplied by constant coefficient matrices, there is an exact companion linearization that linearizes it to a multiparameter eigenvalue problem (MEP). This MEP has a certain symmetric structure and its set of solutions contains solutions to the NEPv. This leads to algorithms that solve the NEPv by solving the resulting MEP instead. We propose two such algorithms that exploit the structure in the MEP, the inverse iteration that solves the MEP by linearizing it to a generalized eigenvalue problem and the symmetric residual inverse iteration which is computationally less expensive than its non-symmetric version. We also develop theory that characterizes spurious solutions, that is solutions to the MEP that do not lead to solutions to the NEPv.
Paper D shows how the p-Laplacian eigenproblem for spectral clustering can be formulated as specific type of NEPv, which we call a generalized nonlinear eigenproblem with one eigenvector nonlinearity or a generalized NEPv1. This formulation allows us to use the SCF iteration to solve the p-Laplacian eigenproblem. We present two different generalized NEPv1-formulations whose solutions are contained in the set of solutions to the p-Laplacian eigenproblem. A regularization of one of the formulations that make it differentiable combined with an adaptation of the SCF iteration leads to a previously unexplored approach for p-spectral clustering, which connects the fields of quantum chemistry and data science.