Implementing Sparse Matrix Ordering Using Hypergraph Partitioning

Lu Yao; Yi Yang; Zheng Hua Wang; Wei Cao

doi:10.4028/www.scientific.net/AMR.706-708.1890

Paper Titles

Design of the Post-Processor for Rotors Dynamics Based on the STEP Standard
p.1871

Human Face Detection Method Based on Skin Color Model
p.1877

A Face Detection Method Based on Log-Gabor Filters
p.1882

Human Motion Tracking Based on B-Spline Snake Algorithm
p.1886

Implementing Sparse Matrix Ordering Using Hypergraph Partitioning
p.1890

Multi-Domain Modeling Simulation and Application Based on MapleSim
p.1894

Research and Application of Equipment Fault Diagnosis Based on Cloud Computing
p.1898

Research on Application of Intelligence Schedule of City Pubic Traffic Vehicles Based on Genetic Algorithm
p.1902

Simulation of A/D Conversion with LabView
p.1907

HomeAdvanced Materials ResearchAdvanced Materials Research Vols. 706-708Implementing Sparse Matrix Ordering Using...

Implementing Sparse Matrix Ordering Using Hypergraph Partitioning

Abstract:

Matrix ordering is a key technique when applying Cholesky factorization method to solving sparse symmetric positive definite system Ax = b. Much effort has been devoted to the development of powerful heuristic ordering algorithms. This paper implements a sparse matrix ordering scheme based on hypergraph partitioning. The novel nested dissection ordering scheme achieve the vertex separator by hypergraph partitioning. Experimental results show that the novel scheme produces results that are substantially better than METIS.

You might also be interested in these eBooks

Mechatronics and Intelligent Materials III

View Preview

Info:

Periodical:

Advanced Materials Research (Volumes 706-708)

Pages:

1890-1893

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.706-708.1890

Citation:

Cite this paper

Online since:

June 2013

Authors:

Lu Yao, Yi Yang, Zheng Hua Wang, Wei Cao

Keywords:

Hypergraph Partitioning, Matrix Ordering, Nested Dissection

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] I.S. Duff: Combinatorial problems in solving linear systems (LIP Research Report, Germany 2009).

Google Scholar

[2] A. George: SIAM Journal of Num. Ana. Vol. 10 (1973), p.345

Google Scholar

[3] Ü.V. Çatalyürek, C. Aykanat and E. Kayaaslan: Hypergraph partitioning-based fill-reducing ordering (Technical Report, Germany 2009).

DOI: 10.1137/090757575

Google Scholar

[4] L. Kou, L. Stockmeyer and C. K. Wong: Covering edges by cliques with regard to keyword conflicts and intersection graphs (Communications of the ACM, America 1978).

DOI: 10.1145/359340.359346

Google Scholar

[5] J. Gramm, J. Guo, F. Huffner and R. Niedermeier, in: Proceedings of the Eighth Workshop on Algorithm Engineering (2004), in press.

Google Scholar

[6] G. Karypis and V. Kumar, in: Proceedings of the 36th Design Automation Conference (1999), in press.

Google Scholar

[7] Information on http://www.cise.ufl.edu/research/sparse/

Google Scholar