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

点击翻译按钮获取中文摘要

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.