Empirical Complexity of Continuation Eigenpairs Computation
Student thesis: Master's Thesis
Related Research Unit(s)
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.