AF: Medium: Generalized Algebraic Graph Theory: Algorithms and Analysis

PI将开发新的方法来分析，推理和预测图形和网络。 图表和网络出现在整个社会和科学中。 它们包括道路和运输网络、通信网络、电力网络和社交网络。 它们是计算机科学中最主要的数据抽象之一，用于对从基因组学到图像处理和机器学习等领域的抽象交互进行建模。该项目有两个主要研究方向。 第一个是开发更快的算法来执行现有的分析。 第二是发展新的方法来理解图和网络的结构。 在该项目期间，PI还将开发和分发课程材料，以教授该领域的最新发展，将就相关材料进行公开讲座，将培训研究生和本科生进行研究，并将开发其他人可以用来执行这些分析的软件。本项目研究的基本对象是图结构块矩阵（GSBM）-块矩阵，其非零结构对应于图的边。 该项目的第一部分将涉及开发快速算法，用于求解GSBM中的线性方程组，这些线性方程组可以写成正半不定矩阵的总和，每个矩阵对应于图形的一个边缘。 这些GSBM是拉普拉斯矩阵的推广，并出现在许多应用领域，包括优化，计算科学和图像处理。 该项目的第二部分将涉及谱图理论的推广，以研究随机选择块矩阵的GSBMs的预期特征多项式。 谱图理论是分析图和网络的最有用的工具之一。 将理论扩展到随机GSBMs应该能够进行标准方法无法进行的分析。

The PI will develop new methods for analyzing, reasoning about, and making predictions about graphs and networks. Graphs and networks appear throughout society and science. They include road and transportation networks, communication networks, power networks and social networks. They are one of the dominant abstractions of data in Computer Science, and are used to model abstract interactions in fields ranging from Genomics to Image Processing and Machine Learning.The project has two major research thrusts. The first is the development of faster algorithms for performing existing analyses. The second is the development of new approaches to understanding the structure of graphs and networks. During the project, the PI will also develop and distribute course materials to teach recent developments in the field, will give public lectures on related material, will train graduate and undergraduate students in research, and will develop software that others can use to perform these analyses.The fundamental object to be studied in this project are graph structured block matrices (GSBMs)---block matrices whose nonzero structure corresponds to the edges of a graph. The first part of the project will involve the development of fast algorithms for the solution of systems of linear equations in GSBMs that can be written as a sum of positive semindefinte matrices with each matrix corresponding to one edge of the graph. These GSBMs are generalizations of Laplacian matrices and arise in many application areas, including Optimization, Computational Science, and Image Processing. The second part of the project will involve the generalization of spectral graph theory to the study of the expected characteristic polynomials of GSBMs with randomly chosen block matrices. Spectral graph theory has been one of the most useful tools for analyzing graphs and networks. The extension of the theory to random GSBMs should enable analyses that are not possible with the standard approach.