Personal tools
You are here: Home CG seminar 2020 Using Delaunay Triangulations to Cluster Eigenvalues of Matrices
« November 2019 »
November
SuMoTuWeThFrSa
12
3456789
10111213141516
17181920212223
24252627282930
Log in


Forgot your password?
 

Using Delaunay Triangulations to Cluster Eigenvalues of Matrices

Wednesday, November 6th, 2019, 16:10

Checkpoint 480

underline

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.
 
Document Actions