Personal tools
 

Nested Dissection and Persistent Homology

— filed under:

Dr. Don Sheehy, University of Connecticut

What
  • Topology Seminar
When Mon, Feb 03, 2014
from 11:00 AM to 11:50 AM
Where RH 316
Add event to calendar vCal
iCal
Nested dissection is a way of solving systems of linear equations by divide and conquer.  For many linear systems that occur naturally in many settings, nested dissection gives a guaranteed improvement over naive Gaussian elimination.  These are the so-called beta-separable systems, where beta is a constant that governs how big the improvement will be.  In this talk, I will give some historical background, going back to Strassen's fast matrix multiplication algorithm.  Then, I will show how one might apply this technique to computing persistent homology.  Moreover, I will show that for a wide class of inputs that come up in persistent homology, the resulting systems are beta-separable, yielding an improvement in the asymptotic running time of the persistence algorithm.  
 
This is joint work with Primoz Skraba and Michael Kerber.
« September 2017 »
September
SuMoTuWeThFrSa
12
3456789
10111213141516
17181920212223
24252627282930