Empirical Complexity of Continuation Eigenpairs Computation

連續矩陣特徵值特徵向量計算的實驗複雜度

Student thesis: Master's Thesis

View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Awarding Institution
Supervisors/Advisors
Award date2 Jul 2019

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(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.