Traditionally, solving a system of linear equations XM = B by Gaussian elimination has been formulated as a graph elimination problem. The matrix M is represented by a directed graph (or an undirected graph when M is symmetric). The elimination ordering of variables is found to greatly affect the time complexity of the solution process if M is sparse. As the problem of finding the optimal ordering, i.e., the one which gives the fewest operation counts, is NP-complete, many heuristics have been found to obtain a near-optimal ordering for the problem. All these algorithms do not consider the numerical values of the non-zero entries of M. We refer to this approach as the conventional approach. In this paper, it is shown that queueing problem for solving πQ = 0 and πe = 1 can also be represented as a graph elimination problem where π is the stationary distribution vector and Q is the rate transition matrix. It is also shown that the elimination speed can be increased substantially if the numerical values are also considered when Q has certain ‘repeated structures’, which is common in the context of queueing problems with finite buffer. An approach which takes advantage of the repeated structure of Q to construct fast algorithms for the solution of the queueing problem is developed. Application of the approach to solving different complex queueing problems is discussed in Part II of this paper.
