AF: Small: Spectral Graph Theory, Point Clouds, and Linear Equation Solvers

该奖项是根据2009年美国复苏和再投资法案（公法111-5）资助的。计算机科学中最重要的两个抽象概念是图和点云。图抽象了事物之间的关系：如果与顶点相关联的对象是相关的，则图中的两个顶点通过一条边连接。有向边表示从一个顶点到另一个顶点的连接。社交网络和网络都被建模为图形：顶点可以代表朋友之间有边的人，或者它们可以代表网页，有向边代表链接。点云是一组向量，每个向量提供一个数值属性列表。在许多计算机科学应用中，人们将一个向量与被检查的每个对象联系起来。例如，一个人可以用数字来评价一种化学物质的不同性质，或者一个人有多喜欢某种类型的电影。这个项目将通过将点云转换成图形来统一这两种抽象。每个向量都成为图中的一个顶点，连接两个顶点的边的强度表示相应向量的相似度。这种转换将使图论中开发的许多技术能够应用于点云的研究。该项目的技术目标包括确定与点云相关联的最佳图，开发用于构建这种图的有效算法，以及开发分析图的新方法。特别地，将发展有向图的谱分析。在这个项目中，研究生和本科生都将接受研究方面的培训。在项目过程中编写的教育材料将通过互联网传播，并纳入正在编写的书籍中。

This award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5).Two of the most important abstractions in Computer Science are graphs and point clouds. A graph abstracts relations between things: two vertices in a graph are connected by an edge if the objects associated with the vertices are related. Directed edges indicate a connection from one vertex to another. Both social networks and the web are modeled as graphs: vertices could represent people with edges between friends, or they may represent web pages with directed edges representing links. Point clouds are sets of vectors, each vector providing a list of numerical attributes. In many computer science applications, one associates a vector with each object being examined. For example, one may rate on a numerical scale different properties of a chemical, or how much a person likes movies from certain genres.This project will unify these two abstractions by translating point clouds into graphs. Each vector becomes a vertex in a graph, with the strength of the edge connecting two vertices indicating the degree of similarity of the corresponding vectors. This translation will enable the application of numerous techniques that have been developed in graph theory to the study of point clouds.Technical objectives of the project include the determination of the best graph to associate with a point cloud, the development of efficient algorithms for the construction of such a graph, and the development of new approaches to the analysis of graphs. In particular, a spectral analysis of directed graphs will be developed.Both graduate students and undergraduates will be trained in research while working on this project. Educational materials developed during the course of the project will be disseminated through the internet as well as incorporated into a book under development.