Ebook: Linear Algebra, Markov Chains, and Queueing Models

This IMA Volume in Mathematics and its Applications LINEAR ALGEBRA, MARKOV CHAINS, AND QUEUEING MODELS is based on the proceedings of a workshop which was an integral part of the 1991-92 IMA program on "Applied Linear Algebra". We thank Carl Meyer and R.J. Plemmons for editing the proceedings. We also take this opportunity to thank the National Science Founda­ tion, whose financial support made the workshop possible. A vner Friedman Willard Miller, Jr. xi PREFACE This volume contains some of the lectures given at the workshop Lin­ ear Algebra, Markov Chains, and Queueing Models held January 13-17, 1992, as part of the Year of Applied Linear Algebra at the Institute for Mathematics and its Applications. Markov chains and queueing models play an increasingly important role in the understanding of complex systems such as computer, communi­ cation, and transportation systems. Linear algebra is an indispensable tool in such research, and this volume collects a selection of important papers in this area. The articles contained herein are representative of the underlying purpose of the workshop, which was to bring together practitioners and re­ searchers from the areas of linear algebra, numerical analysis, and queueing theory who share a common interest of analyzing and solving finite state Markov chains. The papers in this volume are grouped into three major categories-perturbation theory and error analysis, iterative methods, and applications regarding queueing models.

---

This volume contains articles focusing on the use of linear algebra as an indispensable tool in researching Markov chains and queueing models. Markov chains and queueing models play an increasingly important role in the understanding of complex systems, such as computer, communication, and transportation systems. The articles contained herein bring together practitioners and researchers from the areas of linear algebra, numerical analysis, and queueing theory, who share a common interest of analyzing and solving finite state Markov chains. The articles are grouped into three major categories: perturbation theory and error analysis; iterative methods; and applications regarding queueing models. These papers aim to provide the reader with an enlarged perspective of some of the major issues which are of current concern to both the pure and applied communities.

---

This volume contains articles focusing on the use of linear algebra as an indispensable tool in researching Markov chains and queueing models. Markov chains and queueing models play an increasingly important role in the understanding of complex systems, such as computer, communication, and transportation systems. The articles contained herein bring together practitioners and researchers from the areas of linear algebra, numerical analysis, and queueing theory, who share a common interest of analyzing and solving finite state Markov chains. The articles are grouped into three major categories: perturbation theory and error analysis; iterative methods; and applications regarding queueing models. These papers aim to provide the reader with an enlarged perspective of some of the major issues which are of current concern to both the pure and applied communities.
Content:
Front Matter....Pages i-xvi
Error Bounds for the Computation of Null Vectors with Applications to Markov Chains....Pages 1-12
The Influence of Nonnormality on Matrix Computations....Pages 13-27
Componentwise Error Analysis for Stationary Iterative Methods....Pages 29-46
The Character of a Finite Markov Chain....Pages 47-58
Gaussian Elimination, Perturbation Theory, and Markov Chains....Pages 59-69
Algorithms for Periodic Markov Chains....Pages 71-88
Iterative Methods for Queueing Networks with Irregular State-Spaces....Pages 89-109
Analysis of P-Cyclic Iterations for Markov Chains....Pages 111-124
Iterative Methods for Finding the Stationary Vector for Markov Chains....Pages 125-136
Local Convergence of (Exact and Inexact) Iterative Aggregation....Pages 137-143
Automated Generation and Analysis of Markov Reward Models Using Stochastic Reward Nets....Pages 145-191
Means and Variances in Markov Reward Systems....Pages 193-204
A Direct Algorithm for Computing the Stationary Distribution of a P-Cyclic Markov Chain....Pages 205-209
Approximate Analysis of a Discrete-Time Queueing Model of the Shared Buffer ATM Switch....Pages 211-229
Algorithms for Infinite Markov Chains with Repeating Columns....Pages 231-265
CRAY-2 Memory Organization and Interprocessor Memory Contention....Pages 267-294

---

This volume contains articles focusing on the use of linear algebra as an indispensable tool in researching Markov chains and queueing models. Markov chains and queueing models play an increasingly important role in the understanding of complex systems, such as computer, communication, and transportation systems. The articles contained herein bring together practitioners and researchers from the areas of linear algebra, numerical analysis, and queueing theory, who share a common interest of analyzing and solving finite state Markov chains. The articles are grouped into three major categories: perturbation theory and error analysis; iterative methods; and applications regarding queueing models. These papers aim to provide the reader with an enlarged perspective of some of the major issues which are of current concern to both the pure and applied communities.
Content:
Front Matter....Pages i-xvi
Error Bounds for the Computation of Null Vectors with Applications to Markov Chains....Pages 1-12
The Influence of Nonnormality on Matrix Computations....Pages 13-27
Componentwise Error Analysis for Stationary Iterative Methods....Pages 29-46
The Character of a Finite Markov Chain....Pages 47-58
Gaussian Elimination, Perturbation Theory, and Markov Chains....Pages 59-69
Algorithms for Periodic Markov Chains....Pages 71-88
Iterative Methods for Queueing Networks with Irregular State-Spaces....Pages 89-109
Analysis of P-Cyclic Iterations for Markov Chains....Pages 111-124
Iterative Methods for Finding the Stationary Vector for Markov Chains....Pages 125-136
Local Convergence of (Exact and Inexact) Iterative Aggregation....Pages 137-143
Automated Generation and Analysis of Markov Reward Models Using Stochastic Reward Nets....Pages 145-191
Means and Variances in Markov Reward Systems....Pages 193-204
A Direct Algorithm for Computing the Stationary Distribution of a P-Cyclic Markov Chain....Pages 205-209
Approximate Analysis of a Discrete-Time Queueing Model of the Shared Buffer ATM Switch....Pages 211-229
Algorithms for Infinite Markov Chains with Repeating Columns....Pages 231-265
CRAY-2 Memory Organization and Interprocessor Memory Contention....Pages 267-294
....