東華大學圖書館 |

語系: 繁體中文

說明(常見問題)

回圖書館首頁

手機版館藏查詢

登入

回首頁

切換: 標籤 | MARC模式 | ISBD

Algorithm Design Using Spectral Grap...

Peng, Richard.

FindBook

Google Book

Amazon

博客來

Algorithm Design Using Spectral Graph Theory.

紀錄類型:	書目-語言資料,印刷品 : Monograph/item
正題名/作者:	Algorithm Design Using Spectral Graph Theory./
作者:	Peng, Richard.
面頁冊數:	168 p.
附註:	Source: Dissertation Abstracts International, Volume: 75-02(E), Section: B.
Contained By:	Dissertation Abstracts International75-02B(E).
標題:	Computer Science. -
電子資源:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3574871
ISBN:	9781303520365

Algorithm Design Using Spectral Graph Theory.
Peng, Richard.

Algorithm Design Using Spectral Graph Theory. - 168 p.

Source: Dissertation Abstracts International, Volume: 75-02(E), Section: B.

Thesis (Ph.D.)--Carnegie Mellon University, 2013.

Spectral graph theory is the interplay between linear algebra and combinatorial graph theory. Laplace's equation and its discrete form, the Laplacian matrix, appear ubiquitously in mathematical physics. Due to the recent discovery of very fast solvers for these equations, they are also becoming increasingly useful in combinatorial optimization, computer vision, computer graphics, and machine learning.

ISBN: 9781303520365Subjects--Topical Terms:

626642
Computer Science.

Algorithm Design Using Spectral Graph Theory.
LDR:02682nam a2200313 4500 001 1958945
005 20140512081855.5
008 150210s2013 ||||||||||||||||| ||eng d
020 $a 9781303520365
035 $a (MiAaPQ)AAI3574871
035 $a AAI3574871
040 $a MiAaPQ $c MiAaPQ
100 1 $a Peng, Richard. $3 2094200
245 1 0 $a Algorithm Design Using Spectral Graph Theory.
300 $a 168 p.
500 $a Source: Dissertation Abstracts International, Volume: 75-02(E), Section: B.
500 $a Adviser: Gary L. Miller.
502 $a Thesis (Ph.D.)--Carnegie Mellon University, 2013.
520 $a Spectral graph theory is the interplay between linear algebra and combinatorial graph theory. Laplace's equation and its discrete form, the Laplacian matrix, appear ubiquitously in mathematical physics. Due to the recent discovery of very fast solvers for these equations, they are also becoming increasingly useful in combinatorial optimization, computer vision, computer graphics, and machine learning.
520 $a In this thesis, we develop highly efficient and parallelizable algorithms for solving linear systems involving graph Laplacian matrices. These solvers can also be extended to symmetric diagonally dominant matrices and M-matrices, both of which are closely related to graph Laplacians. Our algorithms build upon two decades of progress on combinatorial preconditioning, which connects numerical and combinatorial algorithms through spectral graph theory. They in turn rely on tools from numerical analysis, metric embeddings, and random matrix theory.
520 $a We give two solver algorithms that take diametrically opposite approaches. The first is motivated by combinatorial algorithms, and aims to gradually break the problem into several smaller ones. It represents major simplifications over previous solver constructions, and has theoretical running time comparable to sorting. The second is motivated by numerical analysis, and aims to rapidly improve the algebraic connectivity of the graph. It is the first highly efficient solver for Laplacian linear systems that parallelizes almost completely.
520 $a Our results improve the performances of applications of fast linear system solvers ranging from scientific computing to algorithmic graph theory. We also show that these solvers can be used to address broad classes of image processing tasks, and give some preliminary experimental results.
590 $a School code: 0041.
650 4 $a Computer Science. $3 626642
650 4 $a Applied Mathematics. $3 1669109
690 $a 0984
690 $a 0364
710 2 $a Carnegie Mellon University. $b Computer Science. $3 2094137
773 0 $t Dissertation Abstracts International $g 75-02B(E).
790 $a 0041
791 $a Ph.D.
792 $a 2013
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3574871