このエントリーをはてなブックマークに追加
ID 15729
JaLCDOI
Sort Key
19
FullText URL
Author
Taniguchi Takeo
Abstract
In this paper the minimum fill-in problem which arises at the application of the sparse matrix method for linear sparse systems is discussed from the graphtheoretic viewpoint and the author gives some results which can be directly introduced in the design of, so called, the optimal elimination ordering algorithm which gives the minimum fill-in(the number of zeros in coefficient matrix which become non-zero during the elimination process). Through this investigation only graphs are treated instead of the coefficient matrices for linear systems, and the elimination process for a matrix is equivalated to the vertx eliminations for the graph. Then, the results by the theoretical investigation are summarized as following: 1. Optimal elimination for each subgraph which is subdivided appropriately from whole graph leads to the global optimum. 2. In each subgraph there are only two kind of eliminations. Furthermore, some numerical experiments show the characteristics of the subset of vertices, which subdivide a subgraph from the residual.
Publication Title
Memoirs of the School of Engineering, Okayama University
Published Date
1979-03-05
Volume
volume13
Publisher
岡山大学工学部
Publisher Alternative
School of Engineering, Okayama University
Start Page
239
End Page
248
ISSN
0475-0071
NCID
AA00733903
Content Type
Departmental Bulletin Paper
OAI-PMH Set
岡山大学
language
英語
File Version
publisher
NAID
Eprints Journal Name
mfe