Empirical Complexity of Continuation Eigenpairs Computation


Student thesis: Master's Thesis

View graph of relations


Related Research Unit(s)


Awarding Institution
Award date2 Jul 2019


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(n3)—the number of iterations depends on the input matrix and can widely vary. Its average is shown to be bounded by O(n4). 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.