Personal tools
You are here: Home CG seminar 2020 Using Delaunay Triangulations to Cluster Eigenvalues of Matrices
« December 2020 »
Log in

Forgot your password?

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


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