We show how to efficiently solve a clustering problem that arises in a method to evaluate functions of matrices . The problem requires finding the connected components of a graph whose vertices are eigenvalues of a real or complexmatrix . We have implemented both algorithms using CGAL, amature and sophisticated computational-geometry software library, and wedemonstrate that the new algorithm is much faster in practice than the naive algorithm . To the best of our knowledge, this is the first application of computational geometry to solve a real-world problem innumerical linear algebra, and correct a misrepresentation in the original statement of the problem . We also present a tight analysis of the naïve algorithm, showing that it performs $\Theta(n\log n)$ work, and that the algorithm is better in practice to the naivealgorithm. We also show that we also present our own analysis of

Author(s) : Nir Goren, Dan Halperin, Sivan Toledo

Links : PDF - Abstract

Code :

Keywords : algorithm - problem - analysis - present - computational -

Leave a Reply

Your email address will not be published. Required fields are marked *