MATRIX PROFILE AND WAVEFRONT REDUCTION BASED ON THE GRAPH THEORY AND WAVEFRONT MINIMIZATION

摘要

An effective hybrid renumbering method for reducing the profile and wavefront of a sparse matrix is presented. The method is an innovative combination of the classical graph theory approach and the wavefront minimization technique. A rooted level structure is generated first and the level of each node is determined. Then, for each element, the element level is defined as the minimal level of the nodes the element is connected to. Using element levels as weighting factors, the node and element numbering are then reassigned by minimizing wavefront on an element-by-element basis. The method can be used to generate node or element numbering for efficient implementation of finite element analyses using active column solvers or frontal solvers. It can also be applied to sparse matrices with a symmetric pattern of zeros. Because of the use of element levels, the entire structure of the matrix to be renumbered is taken into account during the local element-based wavefront minimization process. Therefore, the algorithm presented here combines the effectiveness of wavefront minimization schemes in local renumbering with the reliability of classical graph theory methods for global renumbering.