@inproceedings{360ca494831f45d082f3c96afb782f4d,

title = "Graph Laplacians and Least Squares on Graphs",

abstract = "There are several classes of operators on graphs to consider in deciding on a collection of building blocks for graph algorithms. One class involves traditional graph operations such as breadth first or depth first search, finding connected components, spanning trees, cliques and other sub graphs, operations for editing graphs and so on. Another class consists of linear algebra operators where the matrices somehow depend on a graph. It is the latter class of operators that this paper addresses. We describe a least squares formulation on graphs that arises naturally in problems of ranking, distributed clock synchronization, social choice, arbitrage detection, and many other applications. The resulting linear systems are analogous to Poisson's equations. We show experimental evidence that some iterative methods that work very well for continuous domains do not perform well on graphs whereas some such methods continue to work well. By studying graph problems that are analogous to discretizations of partial differential equations (PDEs) one can hope to isolate the specific computational obstacles that graph algorithms present due to absence of spatial locality. In contrast, such locality is inherent in PDE problems on continuous domains. There is also evidence that PDE based methods may suggest improvements suitable for implementation on graphs.",

keywords = "Calculus, Handheld computers, Harmonic analysis, Laplace equations, Linear algebra, Linear systems, Synchronization",

author = "Hirani, {Anil N.} and Kaushik Kalyanaraman and Seth Watts",

note = "Funding Information: Acknowledgment: The work of ANH and KK was supported in part by NSF Grant No. DMS-0645604. We thank Rich Lehoucq and Han Wang for useful discussions. Publisher Copyright: {\textcopyright} 2015 IEEE.; 29th IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2015 ; Conference date: 25-05-2015 Through 29-05-2015",

year = "2015",

month = sep,

day = "29",

doi = "10.1109/IPDPSW.2015.73",

language = "English (US)",

series = "Proceedings - 2015 IEEE 29th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2015",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "812--821",

booktitle = "Proceedings - 2015 IEEE 29th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2015",

address = "United States",

}