A Linear Time Implementation of Profile Reduction Algorithms for Sparse Matrices
L. Marro · SIAM Journal on Scientific and Statistical Computing · 1986
The profile reduction method is intended for time and storage reduction in solving a linear system of equations $Mx = b$ using direct methods. A Frontal Increase Minimization strategy (FIM strategy) is a generalization of the so-called King’s numbering criterion. This class of strategy is used in some other classical algorithms (Levy’s, Snay’s, Gibbs’s algorithms). Although efficient, these algorithms are far greater time consumers in their original implementation than other classical profile reduction algorithms (e.g., Reverse Cuthill McKee algorithm). In this paper we first apply the principles given by the authors to propose a unified “classical”implementation of the above mentioned algorithms. Then we provide some time complexity estimates for this implementation. Secondly, we describe an improved implementation of the FIM strategy algorithms using a new insight into the numbering process and best appropriate data structures. This implementation is proven linear in time complexity with respect to the number of nonzeros in M for all the above-mentioned algorithms. Finally, we provide practical execution times on a collection of test problems, highlighting the improvement achieved by the new implementation and its efficiency for small problems. The evaluation of the performance/cost ratio of the FIM strategy algorithms in the new implementation shows that they are competitive compared to other classical profile reduction algorithms.