Abstract
We study the problem of modifying a given elimination ordering through local reorderings. We present new theoretical results on equivalent orderings, including a new characterization of such orderings. Based on these results, we define the notion of k-optimality for an elimination ordering, and we describe how to use this in a practical context to modify a given elimination ordering to obtain less fill. We experiment with different values of k, and report on percentage of fill that is actually reduced from an already good initial ordering, like Minimum Degree.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Blair, J.R.S., Heggernes, P., Telle, J.A.: A practical algorithm for making filled graphs minimal. Theor. Comput. Sci. 250, 125–141 (2001)
Blair, J.R.S., Peyton, B.W.: An introduction to chordal graphs and clique trees. In: Sparse Matrix Computations: Graph Theory Issues and Algorithms, pp. 1–30. Springer, Heidelberg (1993)
Dahlhaus, E.: Minimal elimination ordering inside a given chordal graph. In: Möhring, R.H. (ed.) WG 1997. LNCS, vol. 1335, pp. 132–143. Springer, Heidelberg (1997)
Dirac, G.A.: On rigid circuit graphs. Anh. Math. Sem. Univ. Hamburg 25, 71–76 (1961)
Fulkerson, D.R., Gross, O.A.: Incidence matrices and interval graphs. Pacific Journal of Math. 15, 835–855 (1965)
Gavril, F.: The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Combin. Theory Ser. B 16, 47–56 (1974)
George, J.A., Liu, J.W.H.: Computer Solution of Large Sparse Positive Definite Systems. Prentice-Hall Inc., Englewood Cliffs (1981)
Liu, J.W.H.: Equivalent sparse matrix reorderings by elimination tree rotations. SIAM J. Sci. Stat. Comput. 9(3), 424–444 (1988)
Boisvert, R., Pozo, R., Remington, K., Miller, B., Lipman, R.: NIST Matrix Market, http://math.nist.gov/MatrixMarket/
Parter, S.: The use of linear graphs in Gauss elimination. SIAM Review 3, 119–130 (1961)
Peyton, B.W.: Minimal orderings revisited. SIAMJ. Matrix Anal. Appl. 23(1), 271–294 (2001)
Rose, D., Tarjan, R.E., Lueker, G.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5, 146–160 (1976)
Rose, D.J.: Triangulated graphs and the elimination process. J.Math. Anal. Appl. 32, 597–609 (1970)
Villanger, Y.: Lex M versus MCS-M. Reports in Informatics 261, University of Bergen, Norway (2004)
Yannakakis, M.: Computing the minimum fill-in is NP-complete. SIAM J. Alg. Disc. Meth. 2, 77–79 (1981)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Heggernes, P., Villanger, Y. (2006). Simple and Efficient Modifications of Elimination Orderings. In: Dongarra, J., Madsen, K., Waśniewski, J. (eds) Applied Parallel Computing. State of the Art in Scientific Computing. PARA 2004. Lecture Notes in Computer Science, vol 3732. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11558958_95
Download citation
DOI: https://doi.org/10.1007/11558958_95
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29067-4
Online ISBN: 978-3-540-33498-9
eBook Packages: Computer ScienceComputer Science (R0)