For more information about this meeting, contact Victor Nistor, Stephanie Zerby, Mark Levi, Jinchao Xu.

Title: | Commuting Projections on Graphs and Two-Level Methods |

Seminar: | CCMA Luncheon Seminar |

Speaker: | Ludmil Zikatanov, Penn State Math |

Abstract: |

Motivated by the increasing importance of large-scale networks typically modeled by graphs we study properties associated with the popular graph Laplacian. We exploit its mixed formulation based on its natural factorization as product of two operators. The goal is to construct a coarse version of the mixed graph Laplacian operator with the purpose to construct two-level, and by recursion, a multilevel hierarchy of graphs and associated operators. In many situations in practice having a coarse (i.e., reduced dimension) model that maintains some inherent features of the original large-scale graph and respective graph Laplacian offers potential to develop efficient algorithms to analyze the underlined network modeled by this large-scale graph. One possible application of such a hierarchy is to develop multilevel methods that have the potential to be of optimal complexity. One result that we will report is the construction of a projection from the edge-space onto a properly constructed coarse edge-space associated with the edges of the coarse graph. This projection commutes with the discrete divergence operator, and the pair of coarse edge-space and coarse vertex-space offer the potential to construct two-level, and by recursion, multilevel methods for the mixed formulation of the graph Laplacian. The performance of one two-level method with overlapping Schwarz smoothing and correction based on the constructed coarse spaces for solving such mixed graph Laplacian systems is illustrated on a two of graph examples. This is a joint work with Panayot Vassilevski. |

### Room Reservation Information

Room Number: | MB114 |

Date: | 03 / 01 / 2013 |

Time: | 12:20pm - 01:30pm |