[Preface]
[Organization]
[Acknowledgements]
[Ordering Information]
Preface and Acknowledgments xv
1 MARKOV CHAINS 3
1.1 Introduction 3
1.2 Markov Chains 4
1.3 Discrete-Time Markov Chains 5
1.3.1 Definition 5
1.3.2 The Chapman--Kolmogorov Equations 6
1.3.3 Classification of States 8
1.3.4 Irreducibility 13
1.3.5 Probability Distributions 14
1.3.6 Steady-State Distributions of Ergodic Markov Chains 16
1.4 Continuous-Time Markov Chains 17
1.4.1 Definitions 17
1.4.2 Transition Probabilities and Transition Rates 18
1.4.3 The Embedded Markov Chain 20
1.4.4 The Chapman--Kolmogorov Equations 22
1.4.5 Probability Distributions 22
1.5 Nonnegative Matrices 24
1.5.1 Definition 24
1.5.2 Nonnegative Decomposable Matrices 25
1.5.3 The Theorem of Perron--Frobenius 26
1.6 Stochastic Matrices 28
1.6.1 Definition 28
1.6.2 Some Properties of Stochastic Matrices 28
1.6.3 Effect of the Discretization Parameter, \Delta t 31
1.6.4 Eigenvalues of Decomposable Stochastic Matrices 33
1.6.5 Eigenvectors of Decomposable Stochastic Matrices 35
1.6.6 Nearly Decomposable Stochastic Matrices 38
1.7 Cyclic Stochastic Matrices 39
1.7.1 Definition 39
1.7.2 Eigenvalues of Cyclic Stochastic Matrices 40
1.7.3 Example: A Decomposable System with Cyclic Subgroups 40
1.8 Indicators of State Clustering 42
1.8.1 Significance of Subdominant, Right-Hand Eigenvectors 42
1.8.2 A Resource Pool Example 44
1.9 Queueing Models 49
1.9.1 Specification 50
1.9.2 Markov Chain Analysis of Queueing Networks 53
1.9.3 Example 1: Two Stations in Tandem 54
1.9.4 Example 2: One Coxian and Two Exponential Servers 57
2 DIRECT METHODS 61
2.1 Introduction 61
2.2 Direct Methods 63
2.2.1 Gaussian Elimination 63
2.2.2 The LU Decomposition 66
2.2.3 The LDU Decomposition 68
2.2.4 Inverse Iteration 68
2.3 Direct Methods and Markov Chains 70
2.3.1 Handling the Singularity 71
2.3.2 To Transpose or Not to Transpose 77
2.4 Implementation Considerations 78
2.4.1 Implementation in Two-Dimensional Storage Arrays 78
2.4.2 Compact Storage Schemes for Direct Methods 78
2.4.3 Simultaneous Row Generation and Reduction 81
2.4.4 Back-Substitution and Normalization 84
2.5 The GTH Advantage 84
2.6 Sample Experiments with Direct Methods 87
2.6.1 An Interactive Computer System Model 88
2.6.2 Two Coxian Queues: A Highly Structured Example 91
2.7 Stability, Conditioning, and Error Analysis 101
2.7.1 Stable Algorithms and Well-Conditioned Problems 101
2.7.2 Floating-Point Representation of Real Numbers 104
2.7.3 Backward Error Analysis 106
2.7.4 Error Analysis for Gaussian Elimination 109
2.7.5 Condition Numbers, Residuals, and the Group Inverse 117
3 ITERATIVE METHODS 121
3.1 The Power Method 121
3.1.1 Introduction 121
3.1.2 Application to an Arbitrary Matrix, A 122
3.1.3 Application to a Stochastic Matrix, P 124
3.1.4 Comparison with Matrix Powering 125
3.2 Jacobi, Gauss--Seidel, SOR, and Symmetric SOR 125
3.2.1 The Nonhomogeneous Case 126
3.2.2 The Method of Jacobi 127
3.2.3 The Method of Gauss--Seidel 128
3.2.4 The SOR Method 131
3.2.5 The Symmetric SOR Method: SSOR 132
3.2.6 Examples 133
3.3 Block Iterative Methods 138
3.3.1 MATLAB Code and Examples 141
3.4 Preconditioned Power Iterations 143
3.4.1 Gauss--Seidel, SOR, and SSOR Preconditionings 144
3.4.2 ILU Preconditioning 144
3.4.3 Examples 146
3.4.4 Summary 150
3.5 Implementation Considerations 151
3.5.1 Sparse Storage Schemes 151
3.5.2 Choice of an Initial Iteration Vector 155
3.5.3 Normalization of Successive Approximations 156
3.5.4 Testing for Convergence 156
3.5.5 Choosing a Relaxation Parameter for SOR 159
3.5.6 The Effect of State Space Orderings on Convergence 163
3.6 Convergence Properties 169
3.6.1 Definitions 169
3.6.2 Convergence Theorems 170
3.6.3 Application to Markov Chains 176
4 PROJECTION METHODS 177
4.1 Introduction 177
4.1.1 Preliminaries 177
4.1.2 General Projection Processes 179
4.1.3 Projection Processes for Linear Systems 179
4.1.4 Projection Processes for Eigenvalue Problems 181
4.1.5 Application to Markov Chains 181
4.2 Simultaneous Iteration 182
4.2.1 A Generic Subspace Iteration Algorithm 182
4.2.2 ``LOPSI'': A Lopsided Simultaneous Iteration Algorithm 184
4.3 Krylov Subspaces 187
4.3.1 Gram--Schmidt Orthogonalization Procedures 188
4.4 GMRES and the Method of Arnoldi 190
4.4.1 Arnoldi for Eigensolutions 190
4.4.2 FOM --- The Full Orthogonalization Method 192
4.4.3 GMRES --- The Generalized Minimal Residual Method 194
4.4.4 Application to Markov Chains 196
4.4.5 Examples 196
4.4.6 Iterative, Incomplete, and Preconditioned Methods 197
4.4.7 Examples, continued 199
4.4.8 Implementation 201
4.4.9 The Complete Iterative GMRES Algorithm with Preconditioning 205
4.5 Lanczos and Conjugate Gradients 207
4.5.1 The Symmetric Lanczos Algorithm 207
4.5.2 The Unsymmetric Lanczos Algorithm 210
4.5.3 The ``Look-Ahead'' Lanczos Algorithm 214
4.5.4 CG -- The Conjugate Gradient Algorithm 215
4.5.5 CGNR --- Conjugate Gradient for the Normal Equations 218
4.5.6 BCG and CGS --- Conjugate Gradient for Nonsymmetric Systems 220
4.5.7 Preconditioning 222
4.5.8 Examples 224
4.6 MATLAB Programs 225
5 BLOCK HESSENBERG MATRICES AND SOLUTION BY RECURSION 231
5.1 Hessenberg Matrices 231
5.1.1 Definitions 231
5.1.2 Standard Queueing Recursions as Forward
Substitutions 232
5.1.3 Block Hessenberg Matrices 233
5.2 Block Recursive Methods 234
5.2.1 The Recursive Procedure 235
5.2.2 Example: A Telephone System with N Lines and K Operators 240
5.3 The Matrix-Geometric Approach 258
5.3.1 Introduction 258
5.3.2 Matrix Geometric Solutions: The Matrix R 258
5.3.3 Implementation: Computing R and \pi_0 260
5.3.4 Example: The \lambda/C_2/1 Queue 262
5.3.5 Alternative Methods for Finding R 264
5.3.6 The Quasi-Birth-Death (QBD) Case 266
5.4 Explicit Solution of Matrix-Geometric Problems 270
5.4.1 Queueing Systems for Which R May Be Explicitly Computed 272
5.4.2 Systems for Which R Must Be Computed Explicitly 278
5.4.3 Systems for Which R Must Be Computed Iteratively 280
5.4.4 Example: A Markovian Queue with N Servers Subject to Breakdowns and Repairs 281
6 DECOMPOSITIONAL METHODS 285
6.1 NCD Markov Chains 285
6.1.1 Introduction and Background 285
6.1.2 Definitions 286
6.1.3 Block Solutions 287
6.1.4 The Coupling Matrix 289
6.1.5 The NCD Approximation --- A Rayleigh--Ritz Refinement Step 292
6.2 Stochastic Complementation 294
6.2.1 Definition 294
6.2.2 Properties of the Stochastic Complement 296
6.2.3 Computing Stationary Distributions by Stochastic Complementation 299
6.2.4 Relationship with Block Gaussian Elimination 300
6.2.5 Computational Aspects of Stochastic Complementation 302
6.3 Iterative Aggregation/Disaggregation Methods 307
6.3.1 Introduction 307
6.3.2 The Basic IAD Algorithm 307
6.3.3 The Takahashi IAD Algorithm 311
6.3.4 Other IAD Variants 316
6.3.5 Restructuring an NCD Matrix 316
6.3.6 Implementation Considerations 320
6.3.7 MATLAB Experiments 323
6.3.8 A Large Experiment 325
6.4 Convergence Properties and Behavior 332
6.4.1 Necessary Conditions for a ``Regular'' NCD Stochastic Matrix 332
6.4.2 Three Lemmas to Characterize Approximations 336
6.4.3 A Convergence Theorem 340
7 P-CYCLIC MARKOV CHAINS 343
7.1 Introduction 343
7.2 Directed Graphs and P-Cyclic Matrices 348
7.2.1 Graph Terminology and Definitions 348
7.2.2 Primitive and Cyclic Matrices 352
7.3 P-Cyclic Markov Chains 355
7.3.1 The Embedded Markov Chain 355
7.3.2 Markov Chains with Periodic Graphs 355
7.3.3 Computation of the Periodicity 356
7.4 Numerical Methods Applied to P-Cyclic Matrices 359
7.4.1 Direct Methods 359
7.4.2 The Gauss--Seidel Iterative Method 360
7.4.3 Numerical Experiments 361
7.5 Reduced Schemes 364
7.5.1 Reduced Schemes Associated with a Stochastic Matrix 364
7.5.2 Reduced Schemes Associated with an Infinitesimal Generator 366
7.5.3 Numerical Methods Based on the Reduced Scheme 367
7.5.4 Numerical Experiments 369
7.6 IAD Methods for NCD, P-Cyclic Markov Chains 371
7.6.1 Iterative Aggregation/Disaggregation (IAD) Methods 372
7.6.2 Ordering for Periodicity and Decomposability 372
7.6.3 Application to P-Cyclic Matrices 373
7.7 Block SOR and Optimum Relaxation 374
7.7.1 Introduction 374
7.7.2 A 3-Cyclic Queueing Network Example 377
7.7.3 A P-step Iteration Procedure 380
7.7.4 Convergence Conditions for Block SOR 391
7.7.5 Applicable Values for the Relaxation Parameter 394
7.7.6 Convergence Testing in the Extended Sense 398
7.7.7 Optimal Convergence Factors and Associated \omega values 400
7.7.8 Computing the Subvector Multipliers 403
8 TRANSIENT SOLUTIONS 407
8.1 Introduction 407
8.2 Uniformization 408
8.2.1 The Basic Concepts 408
8.2.2 The Truncation Error 410
8.2.3 Implementation 411
8.3 Methods Applicable to Small State Spaces 413
8.3.1 Matrix Decompositional Methods 414
8.3.2 Matrix Scaling and Powering 416
8.4 Ordinary Differential Equation (ODE) Solvers 422
8.4.1 Ordinary Differential Equations 423
8.4.2 Numerical Solutions and Stability 426
8.4.3 Elementary Numerical Algorithms 429
8.4.4 Stiff ODEs 434
8.4.5 Single-Step Methods 436
8.4.6 Multistep Methods 444
8.4.7 Software Sources and Comparisons 450
8.5 Krylov Subspace Methods 453
8.5.1 Introduction 453
8.5.2 The Basic Krylov Subspace Approach 454
8.5.3 Corrected Schemes and Error Bounds 457
8.5.4 Error Estimates and Step Size Control 458
8.6 Selected Experiments 460
9 STOCHASTIC AUTOMATA NETWORKS 463
9.1 Introduction 463
9.2 Noninteracting Stochastic Automata 464
9.2.1 Independent, Two-Dimensional Markov Chains 464
9.2.2 Basic Properties of Tensor Algebra 464
9.2.3 Probability Distributions 466
9.3 Interacting Stochastic Automata 467
9.3.1 A Simple Example 467
9.3.2 Functional Transition Rates and Synchronizing Events 467
9.3.3 The Effect of Synchronizing Events 469
9.3.4 The Effect of Functional Transition Rates 472
9.4 Computing Probability Distributions 474
9.5 Multiplication with a Vector 475
9.5.1 The Nonfunctional Case 476
9.5.2 Multiplication in the Presence of Functional Elements 479
9.5.3 The Use of Symmetric Permutations 480
9.5.4 When All Else Fails 481
9.6 Iterative Solution Methods 483
9.6.1 Unpreconditioned Methods 483
9.6.2 Preconditioning 484
9.7 A Queueing Network Example 486
10 SOFTWARE 491
10.1 The Categories of Available Software 491
10.1.1 Introduction 491
10.1.2 Libraries of Numerical Algorithms 492
10.1.3 Queueing Networks 493
10.1.4 Stochastic Petri Nets 496
10.1.5 Other Software 498
10.2 MARCA --- MARkov Chain Analyzer 500
10.2.1 Basic Concepts and Terminology 500
10.2.2 Model Definition in MARCA 503
10.2.3 Numerical Methods 504
10.3 XMARCA: A Graphical Interface for Queueing Networks 505
10.3.1 Introduction 505
10.3.2 Building a Queueing Network Model 506
10.3.3 Converting the Graphical Representation 509
10.3.4 Matrix Generation and Numerical Solutions 509
10.3.5 Displaying Results 512
Bibliography 513
Index 529