Local fill reduction techniques for sparse symmetric linear systems

被引：0
作者：
Gunther Reißig
机构：
[1] Fakultät IV – Fachgebiet Regelungssysteme,
[2] TU Berlin,undefined
来源：
Electrical Engineering | 2007年 / 89卷
关键词：
Sparse linear systems; Fill reduction; Pivot ordering;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
Local algorithms for obtaining pivot orderings for sparse symmetric coefficient matrices are reviewed together with their mathematical background, appropriate data structures and details of efficient implementation. Heuristics that go beyond the classical Minimum Degree and Minimum Local Fill scoring functions are discussed, illustrated, improved and extensively tested on a test suite of matrices from various applications. Our tests indicate that the presented techniques have the potential of accelerating circuit simulation significantly.
引用
收藏
页码：639 / 652
页数：13
相关论文
共 30 条
[1]  
George A(1973)Nested dissection of a regular finite element mesh SIAM J Numer Anal 10 345-363
[2]  
Feldmann U(1992)Algorithms for modern circuit simulation Int J Electron Commun (AEÜ) 46 274-285
[3]  
Wever UA(1988)The Parallel Comput 7 135-147
[4]  
Zheng Q(1981) forms of factorization methods. I.Vector computers SIAM J Algebraic Discrete Methods 2 77-79
[5]  
Schultz R(1957)Computing the minimum fill-in is NP-complete Manage Sci 3 255-269
[6]  
Wriedt H(1967)The elimination form of the inverse and its application to linear programming Proc IEEE 55 1801-1809
[7]  
Ortega JM(1961)Direct solution of sparse network equations by optimally ordered triangular factorization SIAM Rev 3 119-130
[8]  
Yannakakis M(1999)The use of linear graphs in Gauss elimination SIAM J Matrix Anal Appl 20 902-914
[9]  
Markowitz HM(1998)Performance of greedy ordering heuristics for sparse Cholesky factorization SIAM J Matrix Anal Appl 19 682-695
[10]  
Tinney WF(1989)Node selection strategies for bottom-up sparse matrix ordering SIAM Rev 31 1-19
123