# Using Delaunay Triangulations to Cluster Eigenvalues of Matrices

### Wednesday, November 6th, 2019, 16:10

### Checkpoint 480

### Using Delaunay Triangulations to Cluster Eigenvalues of Matrices

### Sivan Toledo, TAU

### Abstract:

A function f(A) of a square real or complex matrix A is a matrix with the same eigenvectors but with eigenvalues that have been transformed by some scalar function, such as f(x)=sin(x) or f(x)=sign(x). For a few simple functions, there are O(n^3) algorithms to compute f(A). For most, there is not. One algorithm that can often achieve performance close to O(n^3) and is very general is a block recurrence in which A is first transformed to its Schur form A=U*T*U', where U is unitary and T upper triangular. Then the eigenvalues of A, which are the diagonal elements of T, are clustered and the Schur form is reordered so that clusters are contiguous. Then some other algorithm to evaluate f(A) is applied to diagonal blocks of T that correspond to clusters, such as a Pade approximation. Then the algorithm solves for the offdiagonals of f(A) by solving Sylvester equations. If the clusters are far apart enough, the Sylverster solver tends to be numerically stable (we would love to guarantee it, but it's too hard). It turns out that the clustering problem is equivalent to the partitioning of a graph, whose vertices are the eigenvalues, into connected components. Our main result shows that we can replace the graph that arises in this problem by the Delaunay triangulation of the eigenvalues, thereby reducing the complexity from quadratic to O(n log n).

This is joint work with Nir Goren and Dan Halperin.