Algebraic and combinatorial tools for optimal multilevel algorithmsSpectral graph theory Combinatorial scientific computingCombinatorial linear algebra and scientific computingSlide 4Slide 5Slide 6contributionsSlide 8why planar systems?why laplacians?Outlineplanar multi-way edge partitioningplanar multi-way edge partitioning is it possible for any planar graph?a quick time outline of multi-way edge partitioning in linear timemulti-way edge partitioning in linear time the set of independent k-neighborhoodsmulti-way edge partitioning in linear time decomposition into Voronoi regionsmulti-way vertex partitioning in linear time decomposition into Voronoi regionsmulti-way edge partitioning in linear time decomposition into Voronoi-Pair regionsmulti-way edge partitioning in linear time covering each long path with coresSlide 20multi-way vertex partitioning in linear time into expander graphsmulti-way vertex partitioning in linear time into “isolated” expander graphsplanar multi-way vertex partitioning local sparsificationplanar multi-way vertex partitioning global sparsificationplanar multi-way vertex partitioning the numerical insightplanar multi-way vertex partitioning decomposing the global sparse graphSlide 27solving Laplacian systems multilevel algorithmssolving Laplacian systems hierarchies of graphsthe approximation measure algebraically naturalthe approximation measure “naturally” naturalthe approximation measure combinatorially naturalSlide 33solving requirement and complexity the guiding goalevolution of graph approximations aka graph preconditionersevolution of preconditioning the recent historythe key in the analysis of preconditioners aka the Splitting Lemmathe key in the analysis of preconditioners aka the Splitting Lemmathe key in the construction of preconditioners aka the Splitting Lemmaoptimal planar preconditionersSlide 41hey... great algorithm! (you ‘re just another theorist.... this will never be practical!)Slide 43spectral perturbation theory for LaplaciansSlide 45sleek proofs via spectral graph theorySlide 47Slide 481Algebraic and combinatorial tools for optimal multilevel algorithms Yiannis KoutisCarnegie Mellon University2 May 3, 2007Spectral graph theory Combinatorial scientific computingStart with a system Ax =bThe problem of fill3 May 3, 2007Combinatorial linear algebra and scientific computingStart with a system Ax =b4 May 3, 2007Combinatorial linear algebra and scientific computingStart with a system Ax =bComplete Mess!15 May 3, 2007Combinatorial linear algebra and scientific computingStart with a system Ax =b16 May 3, 2007Combinatorial linear algebra and scientific computingMatrices viewed as graphs [direct methods]:Planar positive definite matrices in O(n1.5) time [George], [Lipton, Rose,Tarjan]Graphs viewed as matrices [iterative methods]: Approximate sparsest cut in O(m polylog(n)) time [Spielman,Teng]Find eigenvector of the Laplacian of the graphA wonderful theory of graph approximations where combinatorics and algebra work in synergy7 May 3, 2007contributionsLinear work parallel algorithms forCombinatorial problems:Multi-way planar edge partitioningMulti-way planar vertex partitioningAlgebraic problems:Solving systems with planar LaplaciansSolving systems with a priori known structural properties8 May 3, 2007contributionsTheory for Perturbations of graph eigenvectorsStructure of eigenvectors with respect to edge cutsApplications to Classical algebraic multigrid algorithmsGraph-theoretic approach to design and analysis9 May 3, 2007why planar systems?•images are formulated as rectangular grids [up to 1 billion nodes]•million of images must be processed every day (mammograms, OCT retinal)•weights vary by a factor of 106•PDEs discretized with finite elements [Boman,Hendrickson,Vavasis 05]Leo Grady@ Siemens10 May 3, 2007why laplacians?adjacency: A(i,j) = wi,jdegree sequence: D(i,i) = j wi,jLaplacian: L = D-A Normalized: N = D-1/2 L D-1/2Random walk matrix: I-0.5D-1Lcut structure of the graph [Cheeger], Euclidean commute timespectral properties of the Laplaciancapturecombinatorial properties of the graph11 May 3, 2007Outlineplanar multi-way edge partitioningplanar multi-way vertex partitioningsolving linear systems: introductionsolving planar Laplaciansa bit of perturbation theory12 May 3, 2007planar multi-way edge partitioningPartitioning the edges into disjoint clusters with small boundariesn/k1/2 edges delimiting pieces of size O(k)13 May 3, 2007planar multi-way edge partitioning is it possible for any planar graph?planar separator theorem: every planar graph can be split roughly in half by removing n1/2 vertices.+ recursive bisection+ a few bells and whistles = O(n/k1/2) edges that delimit pieces of size O(k)In O(nlog n) time: recursively apply planar separator [Fre87]In our work: O(kn) time using a localized approach14 May 3, 2007a quick time outline of multi-way edge partitioning in linear time triangulate graphform k-neighborhood of every face2nd layer partial layer15 May 3, 2007multi-way edge partitioning in linear timethe set of independent k-neighborhoodsa set of independent k-neighborhoods [no blue neighborhoods intersect]the set is maximal [Every red neighborhood intersects a blue neighborhood]16 May 3, 2007multi-way edge partitioning in linear timedecomposition into Voronoi regionsevery exterior face is assigned to “closest” blue neighborhood17 May 3, 2007multi-way vertex partitioning in linear timedecomposition into Voronoi regionsevery exterior face is assigned to “closest” blue neighborhoodn/k connected Voronoi regions: faces in Voronoi graph18 May 3, 2007multi-way edge partitioning in linear timedecomposition into Voronoi-Pair regionspaths from center faces of neighborhoods to surrounding Voronoi nodesgraph decomposed into constant size Voronoi-Pairs that are easy to deal withhow many paths did we add? O(n/k) still too many?19 May 3, 2007multi-way edge partitioning in linear timecovering each long path with corestotal boundary = cores + exposed part = O(k1/2)n/k paths * k1/2 boundary = O(n/k1/2) edgesN vwe are done!!20 May 3, 2007Outlineplanar multi-way edge partitioningplanar multi-way vertex partitioningsolving linear systems: introductionsolving planar Laplaciansa bit of perturbation theory21 May 3,