##### Personal tools
You are here: Home 2020 Using Delaunay Triangulations to Cluster Eigenvalues of Matrices
« December 2020 »
December
SuMoTuWeThFrSa
12345
6789101112
13141516171819
20212223242526
2728293031

# Using Delaunay Triangulations to Cluster Eigenvalues of Matrices

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

##### Document Actions 