Empirical Complexity of Continuation Eigenpairs Computation

Abstract

A homotopy algorithm for computing an eigenpair of a complex matrix was recently proposed by Armentano et al. The article where the algorithm is described analyzes its average complexity for matrices with independent and identically distributed Gaussian entries. Whereas the cost for each iteration is fixed—it is O(n³)—the number of iterations depends on the input matrix and can widely vary. Its average is shown to be bounded by O(n⁴). In this thesis we empirically estimate the average number of iterations for Gaussian matrices as above as well as for other classes of random matrices. In all our experiments we find that this average number of iterations is sublinear.

Date of Award	2 Jul 2019
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Felipe CUCKER (Supervisor)