A Randomized Homotopy for the Hermitian Eigenpair Problem

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal

3 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)281 - 312
Journal / PublicationFoundations of Computational Mathematics
Volume15
Issue number1
Online published23 Oct 2014
Publication statusPublished - Feb 2015

Abstract

We describe and analyze a randomized homotopy algorithm for the Hermitian eigenvalue problem. Given an nxn Hermitian matrix A, the algorithm returns, almost surely, a pair (lambda, v) which approximates, in a very strong sense, an eigenpair of A. We prove that the expected cost of this algorithm, where the expectation is both over the random choices of the algorithm and a probability distribution on the input matrix A, is O(n(6)), that is, cubic on the input size. Our result relies on a cost assumption for some pseudorandom number generators whose rationale is argued by us.

Research Area(s)

  • Complexity analysis, Eigenpair computation, Homotopy methods