Fall 2014

Eigenpairs of Homogeneous Polynomial Systems

Tuesday, Dec. 15, 2015 11:15 am11:50 am PST

Add to Calendar


Calvin Lab

Let n,d>0 and f be a system of n complex homogeneous polynomials of degree d in n variables. We call a point (v,l) in C^n\{0} x C an eigenpair of f, if f(v)=l*v. In this case we call v an eigenvector and l an eigenvalue of f. 

This talk consists of two parts. In the first part  I want to present the probability distribution of l, when the  coefficients of f in the Bombieri-Weyl basis are iid complex centered gaussian random variables and |v|=1 is chosen uniform at random from all eigenvectors of f (I will also explain why this is possible). It turns out that the distribution of 2l is mixed from chi-square-distributions with weights from the truncated geometric distribution.

In the second part I want to present recent results about numerically computing eigenpairs. We call a point (z,t) in C^n\{0} x C an h-eigenpair of f if f(z)=t^(d-1)*z. This equation is homogeneous with n equations and n+1 variables. The main tool to approximate solutions of such systems are homotopy methods. I will explain why the homotopy method for arbitrary systems of n equations in n+1 variables is not a good choice for the h-eigenpair problem.  Further, I will describe a randomized algorithm that for almost all systems approximates h-eigenpairs almost surely. Its average number of arithmetic operations is polynomial in the input size.