This paper is the experimental follow-up to Langville and Stewart (2002), where the theoretical background for the nearest Kronecker product (NKP) preconditioner was developed. Here we test the NKP preconditioner on both Markov chains (MCs) and stochastic automata networks (SANs). We conclude that the NKP preconditioner is not appropriate for general MCs, but is very effective for a MC stored as a SAN.

This paper examines numerical issues in computing solutions to networks of stochastic automata. It is well-known that when the matrices that represent the automata contain only constant values, the cost of performing the operation basic to all iterative solution methods, that of matrix-vector multiply, is given by ρ N = Π N i-1 n i × Σ N i=1 n i , where n i is the number of states in the i th automaton and N is the number of automata in the network. We introduce the concept of a generalized tensor product and prove a number of lemmas concerning this product. The result of these lemmas allows us to show that this relatively small number of operations is sufficient in many practical cases of interest in which the automata contain functional and not simply constant transitions. Furthermore, we show how the automata should be ordered to achieve this.

This paper describes an iterative aggregation/disaggregation method for computing the stationary probability vector of a nearly completely decomposable Markov chain. The emphasis is on the implementation of the algorithm and on the results that are obtained when it is applied to three modeling examples that have been used in the analysis of computer/communication systems. Where applicable, a comparison with standard iterative and direct methods for solving the same problems, is made. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

The commenter points out an error made in the paper by P. Nain et al. (see ibid., vol.36, p.806-15, July 1988) and shows that correcting this error requires a state space that has an exponential size. The authors reply that the errors cannot easily be corrected and that their model provides a good approximation model for HYMAP.>

A hybrid multiple access protocol (HYMAP) was proposed by M. Rios and N.D. Georganas (1985), combining the best features of CSMA/CD and of a conflict-free protocol. Control is transferred from one protocol to the other according to state information sensed on the channel. The performance of HYMAP was evaluated by computer simulation. An exact analysis of this hybrid protocol is presented. Since HYMAP permits free access of new arrivals during collision resolution, the mean length of the conflict-free period is determined by solving a large system of linear equations. The basic mean performance measures (throughput, delay) can then be easily computed and compared to the performance of CSMA/CD.>

A closed cyclic queueing system with multiple classes is analyzed numerically. The queueing system was originally motivated by a need to model circuit switching traffic in a data multiplexing scheme which provides both circuit and switching capabilities. The queueing system consists of two nodes, a primary and a secondary node. Customers in the primary node may require a random number of servers simultaneously. The secondary node simply provides the means of modeling the arrival process to the primary node. An efficient numerical procedure is used to obtain performance measures such as throughput, queue-length distribution, and utilization.

In this paper an approximate numerical solution for a multiclass preemptive priority single server queue is developed. The arrival process of each class follows a Poisson distribution. The service time distribution must have a rational Laplace transform, but is otherwise arbitrary and may be different for different classes. The work reported here was motivated by a desire to compute the equilibrium probability distribution of networks containing preemptive priority servers. Such networks are frequently encountered when modeling computer systems, medical care delivery systems and communication networks. We wish to use an iterative technique which constructs a series of two station networks consisting of one station from the original network and one “complementary” station whose behavior with respect to the original station mimics that of the rest of the network. At each iteration, it is necessary to compute the equilibrium probability distribution of one or more preemptive priority queues.

Iterative aggregation/disaggregation methods provide an efficient approach for computing the stationary probability vector of nearly uncoupled (also known as nearly completely decomposable) Markov chains. Three such methods that have appeared in the literature recently are considered and their similarities and differences are outlined. Specifically, it is shown that the method of Takahashi corresponds to a modified block Gauss-Seidel step and aggregation, whereas that of Vantilborgh corresponds to a modified block Jacobi step and aggregation. The third method, that of Koury et al., is equivalent to a standard block Gauss-Seidel step and iteration. For each of these methods, a lemma is established, which shows that the unique fixed point of the iterative scheme is the left eigenvector corresponding to the dominant unit eigenvalue of the stochastic transition probability matrix. In addition, conditions are established for the convergence of the first two of these methods; convergence conditions for the third having already been established by Stewart et al. All three methods are shown to have the same asymptotic rate of convergence.

In this paper we derive a number of results concerning the behavior of closed load-independent exponential queueing networks. It is shown that if the service rate of any station is increased (decreased), then the throughput of the network itself also increases (decreases). This is not true for product form networks in general. In addition, if the service rate at server i is increased then both the mean queue length and mean waiting time at server i decrease while both these quantities increase at all stations j ≠ i. The opposite effect is observed if the senrvice rate at station i is decreased. The main result of the paper is a proof of the conjective that corresponding to any general closed queueing network consisting of M stations and in which N customers circulate according to the elements of an irreducible stochastic routing matrix Q, there exists a closed load-independent exponential queueing network with the same M, N, and Q such that the mean number of customers at each station in the exponential network is equal to that in the general network. If the network throughput is specified, it is shown that this exponential network iS unique.

A FORTRAN algorithm m presented for obtaining the set of elgenvalues of largest absolute magnitude of a matrix together with the corresponding left or right eigenvectors The method m particularly suitable for large sparse matrices.

complement to [1] where the description, test results, and references are given.