### 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.

Original language | English (US) |
---|---|

Title of host publication | Proceedings - 2015 IEEE 29th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2015 |

Publisher | Institute of Electrical and Electronics Engineers Inc. |

Pages | 812-821 |

Number of pages | 10 |

ISBN (Electronic) | 0769555101, 9780769555102 |

DOIs | |

State | Published - Sep 29 2015 |

Event | 29th IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2015 - Hyderabad, India Duration: May 25 2015 → May 29 2015 |

### Publication series

Name | Proceedings - 2015 IEEE 29th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2015 |
---|

### Other

Other | 29th IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2015 |
---|---|

Country | India |

City | Hyderabad |

Period | 5/25/15 → 5/29/15 |

### Keywords

- Calculus
- Handheld computers
- Harmonic analysis
- Laplace equations
- Linear algebra
- Linear systems
- Synchronization

### ASJC Scopus subject areas

- Computer Networks and Communications
- Hardware and Architecture

## Fingerprint Dive into the research topics of 'Graph Laplacians and Least Squares on Graphs'. Together they form a unique fingerprint.

## Cite this

*Proceedings - 2015 IEEE 29th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2015*(pp. 812-821). [7284395] (Proceedings - 2015 IEEE 29th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2015). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/IPDPSW.2015.73