@book{stewart_2014, title={A first course in probability}, publisher={[Place of publication not identified]: [CreateSpace Independent Publishing Platform]}, author={Stewart, W. J.}, year={2014} }
@article{fourneau_plateau_stewart_2008, title={An algebraic condition for product form in stochastic automata networks without synchronizations}, volume={65}, DOI={10.1016/j.peva.2008.04.007}, abstractNote={We consider Stochastic Automata Networks (SANs) in continuous time and we prove a sufficient condition for the steady-state distribution to have product form. We consider synchronization-free SANs in which the transitions of one automaton may depend upon the states of the other automata. This model can represent efficiently multidimensional Markov chains whose transitions are limited to one component but whose rates may depend on the state of the chain. The sufficient condition we obtain is quite simple and our theorem generalizes former results on SANs as well as results on modulated Markovian queues, such as Boucherie’s theory on competing Markov chain, on reversible queues considered by Kelly and on modulated Jackson queueing networks studied by Zhu. The sufficient condition and the proof are purely algebraic and are based on the intersection of kernels for a certain set of matrices.}, number={11-12}, journal={Performance Evaluation}, author={Fourneau, J. M. and Plateau, B. and Stewart, W. J.}, year={2008}, pages={854–868} }
@article{sbeity_brenner_plateau_stewart_2008, title={Phase-type distributions in stochastic automata networks}, volume={186}, ISSN={["1872-6860"]}, DOI={10.1016/j.ejor.2007.02.019}, abstractNote={Stochastic automata networks (Sans) are high-level formalisms for modeling very large and complex Markov chains in a compact and structured manner. To date, the exponential distribution has been the only distribution used to model the passage of time in the evolution of the different San components. In this paper we show how phase-type distributions may be incorporated into Sans thereby providing the wherewithal by which arbitrary distributions can be used which in turn leads to an improved ability for more accurately modeling numerous real phenomena. The approach we develop is to take a San model containing phase-type distributions and to translate it into another, stochastically equivalent, San model having only exponential distributions. In the San formalism, it is the events that are responsible for firing transitions and our procedure is to associate a stochastic automaton with each event having a phase-type distribution. This automaton models the distribution of time until the event occurs. In this way, the size of the elementary matrices remain small, because the size of the automata are small: the automata are either those of the original San, or are those associated with the phase-type events and are of size k, the number of phases in the representation of the distribution.}, number={3}, journal={EUROPEAN JOURNAL OF OPERATIONAL RESEARCH}, author={Sbeity, I. and Brenner, L. and Plateau, B. and Stewart, W. J.}, year={2008}, month={May}, pages={1008–1028} }
@article{benoit_plateau_stewart_2006, title={Memory-efficient Kronecker algorithms with applications to the modelling of parallel systems}, volume={22}, ISSN={["1872-7115"]}, DOI={10.1016/j.future.2006.02.006}, abstractNote={We present a new algorithm for computing the solution of large Markov chain models whose generators can be represented in the form of a generalized tensor algebra, such as networks of stochastic automata. The tensor structure inherently involves a product state space but, inside this product state space, the actual reachable state space can be much smaller. For such cases, we propose an improvement of the standard numerical algorithm, the so-called “shuffle algorithm”, which necessitates only vectors of the size of the actual state space. With this contribution, numerical algorithms based on tensor products can now handle larger models.}, number={7}, journal={FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE}, author={Benoit, Anne and Plateau, Brigitte and Stewart, William J.}, year={2006}, month={Aug}, pages={838–847} }
@article{langville_stewart_2004, title={Kronecker product approximate preconditioner for SANs}, volume={11}, ISSN={["1099-1506"]}, DOI={10.1002/nla.344}, abstractNote={Many very large Markov chains can be modelled efficiently as stochastic automata networks (SANs). A SAN is composed of individual automata which, for the most part, act independently, requiring only infrequent interaction. SANs represent the generator matrix Q of the underlying Markov chain compactly as the sum of Kronecker products of smaller matrices. Thus, storage savings are immediate. The benefit of a SAN's compact representation, known as the descriptor, is often outweighed by its tendency to make analysis of the underlying Markov chain tough. While iterative or projections methods have been used to solve the system πQ=0, the time until these methods converge to the stationary solution π is still unsatisfactory. SAN's compact representation has made the next logical research step of preconditioning thorny. Several preconditioners for SANs have been proposed and tested, yet each has enjoyed little or no success. Encouraged by the recent success of approximate inverses as preconditioners, we have explored their potential as SAN preconditioners. One particularly relevant finding on approximate inverse preconditioning is the nearest Kronecker product approximation discovered by Pitsianis and Van Loan. In this paper, we extend the nearest Kronecker product technique to approximate the Q matrix for an SAN with a Kronecker product, A1 ⊗ A2 ⊗…⊗ AN. Then, we take M = A 1−1 ⊗ A 2−1 ⊗…⊗ A N−1 as our SAN NKP preconditioner. Copyright © 2004 John Wiley & Sons, Ltd.}, number={8-9}, journal={NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS}, author={Langville, AN and Stewart, WJ}, year={2004}, pages={723–752} }
@article{benoit_fernandes_plateau_stewart_2004, title={On the benefits of using functional transitions and Kronecker algebra}, volume={58}, ISSN={["1872-745X"]}, DOI={10.1016/j.peva.2004.04.002}, abstractNote={Much attention has been paid recently to the use of Kronecker or tensor product modelling techniques for evaluating the performance of parallel and distributed systems. While this approach facilitates the description of such systems and mimimizes memory requirements, it has suffered in the past from the fact that computation times have been excessively long. In this paper we propose a suite of modelling strategems and numerical procedures that go a long way to alleviating this drawback. Of particular note are the benefits obtained by using functional transitions that are implemented via a generalized tensor algebra. Examples are presented which illustrate the reduction in computation time as each suggested improvement is deployed.}, number={4}, journal={PERFORMANCE EVALUATION}, author={Benoit, A and Fernandes, P and Plateau, B and Stewart, WJ}, year={2004}, month={Dec}, pages={367–390} }
@article{langville_stewart_2004, title={Special issue devoted to papers presented at the Conference on the Numerical Solution of Markov Chains 2003 - Preface}, volume={386}, ISSN={["1873-1856"]}, DOI={10.1016/j.laa.2004.02.016}, journal={LINEAR ALGEBRA AND ITS APPLICATIONS}, author={Langville, AN and Stewart, WJ}, year={2004}, month={Jul}, pages={1–2} }
@article{langville_stewart_2004, title={Testing the nearest Kronecker product preconditioner on Markov chains and stochastic automata networks}, volume={16}, ISSN={["1526-5528"]}, DOI={10.1287/ijoc.1030.0041}, abstractNote={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.}, number={3}, journal={INFORMS JOURNAL ON COMPUTING}, author={Langville, AN and Stewart, WJ}, year={2004}, pages={300–315} }
@article{langville_stewart_2004, title={The Kronecker product and stochastic automata networks}, volume={167}, ISSN={["1879-1778"]}, DOI={10.1016/j.cam.2003.10.010}, abstractNote={This paper can be thought of as a companion paper to Van Loan's The Ubiquitous Kronecker Product paper (J. Comput. Appl. Math. 123 (2000) 85). We collect and catalog the most useful properties of the Kronecker product and present them in one place. We prove several new properties that we discovered in our search for a stochastic automata network preconditioner. We conclude by describing one application of the Kronecker product, omitted from Van Loan's list of applications, namely stochastic automata networks.}, number={2}, journal={JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS}, author={Langville, AN and Stewart, WJ}, year={2004}, month={Jun}, pages={429–447} }
@inbook{benoit_brenner_fernandes_plateau_stewart_2003, title={The PEPS software tool}, volume={2794}, ISBN={3540408142}, DOI={10.1007/978-3-540-45232-4_7}, abstractNote={Peps is a software package for solving very large Markov models expressed as Stochastic Automata Networks (San). The San formalism defines a compact storage scheme for the transition matrix of the Markov chain and it uses tensor algebra to handle the basic vector matrix multiplications. Among the diverse application areas to which Peps may be applied, we cite the areas of computer and communication performance modeling, distributed and parallel systems and finite capacity queueing networks. This paper presents the numerical techniques included in version 2003 of the Peps software, the basics of its interface and three practical examples.}, booktitle={Computer performance evaluation: Modelling techniques and tools: 13th international conference, TOOLS 2003, Urbana, IL, USA, September 2-5, 2003}, publisher={Berlin; New York: Springer}, author={Benoit, A. and Brenner, L. and Fernandes, P. and Plateau, B. and Stewart, W. J.}, editor={P. Kemper, W. H. SandersEditor}, year={2003}, pages={98–115} }
@article{jungblut-hessel_plateau_stewart_ycart_2001, title={Fast simulation for road traffic network}, volume={35}, ISSN={["0399-0559"]}, DOI={10.1051/ro:2001108}, abstractNote={Dans cet article, nous presentons une methode pour realiser des simulations rapides de grands systemes Markoviens. Cette methode est basee sur l'utilisation de trois concepts: l'uniformisation de chaine de Markov, une dynamique liee aux evenements et la modularite. Une application de trafic urbain illustre les performances de notre approche.}, number={2}, journal={RAIRO-RECHERCHE OPERATIONNELLE-OPERATIONS RESEARCH}, author={Jungblut-Hessel, R and Plateau, B and Stewart, WJ and Ycart, B}, year={2001}, pages={229–250} }
@article{dayar_stewart_2000, title={Comparison of partitioning techniques for two-level iterative solvers on large, sparse Markov chains}, volume={21}, ISSN={["1095-7197"]}, DOI={10.1137/S1064827598338159}, abstractNote={Experimental results for large, sparse Markov chains, especially the ill-conditioned nearly completely decomposable (NCD) ones, are few. We believe there is need for further research in this area, specifically to aid in the understanding of the effects of the degree of coupling of NCD Markov chains and their nonzero structure on the convergence characteristics and space requirements of iterative solvers. The work of several researchers has raised the following questions that led to research in a related direction: How must one go about partitioning the global coefficient matrix into blocks when the system is NCD and a two-level iterative solver (such as block SOR) is to be employed? Are block partitionings dictated by the NCD form of the stochastic one-step transition probability matrix necessarily superior to others? Is it worth investigating alternative partitionings? Better yet, for a fixed labeling and partitioning of the states, how does the performance of block SOR (or even that of point SOR) compare to the performance of the iterative aggregation-disaggregation (IAD) algorithm? Finally, is there any merit in using two-level iterative solvers when preconditioned Krylov subspace methods are available? We seek answers to these questions on a test suite of 13 Markov chains arising in 7 applications.}, number={5}, journal={SIAM JOURNAL ON SCIENTIFIC COMPUTING}, author={Dayar, T and Stewart, WJ}, year={2000}, month={May}, pages={1691–1705} }
@inbook{stewart_2000, title={Numerical analysis methods}, volume={1769}, ISBN={3540671935}, DOI={10.1007/3-540-46506-5_15}, abstractNote={In the context of Performance Evaluation (PE), numerical analysis methods refer to those methods which work with a Markov chain representation of the system under evaluation and use techniques from the domain of numerical analysis to compute stationary and/or transient state probabilities or other measures of interest. As is evident from reading through this book, the use of mathematical models to analyze complex systems has a long history. With the advent of high powered workstations and cheap memory, these applications have greatly expanded. More and more frequently, however, the characteristics of the system to be modeled are such that analytical solutions do not exist or are unknown so that systems engineers turn to computing numerical solutions rather than analytical solutions.}, booktitle={Performance evaluation: Origins and directions}, publisher={Berlin; New York: Springer}, author={Stewart, W. J.}, editor={G. Haring, C. Lindemann and Reiser, M.Editors}, year={2000}, pages={355–376} }
@article{sidje_stewart_1999, title={A numerical study of large sparse matrix exponentials arising in Markov chains}, volume={29}, DOI={10.1016/S0167-9473(98)00062-0}, abstractNote={Krylov subspace techniques have been shown to yield robust methods for the numerical computation of large sparse matrix exponentials and especially the transient solutions of Markov Chains. The attractiveness of these methods results from the fact that they allow us to compute the action of a matrix exponential operator on an operand vector without having to compute, explicitly, the matrix exponential in isolation. In this paper we compare a Krylov-based method with some of the current approaches used for computing transient solutions of Markov chains. After a brief synthesis of the features of the methods used, wide-ranging numerical comparisons are performed on a power challenge array supercomputer on three different models.}, number={3}, journal={Computational Statistics & Data Analysis}, author={Sidje, R. B. and Stewart, W. J.}, year={1999}, pages={345–368} }
@book{davis_chu_mcconnell_dolan_norris_ortiz_plemmon_ridgeway_scaife_stewart_et al._1998, title={Cornelius Lanczos: Collected published papers with commentaries}, ISBN={0929493003}, publisher={Raleigh, NC: College of Physical and Mathematical Sciences, North Carolina State University}, author={Davis, W. R. and Chu, M. T. and McConnell, J. R. and Dolan, P. and Norris, L. K. and Ortiz, E. and Plemmon, R. J. and Ridgeway, D. and Scaife, B.K.P. and Stewart, W. J. and et al.}, year={1998} }
@article{fernandes_plateau_1998, title={Efficient descriptor-vector multiplications in stochastic automata networks}, volume={45}, ISSN={["1557-735X"]}, DOI={10.1145/278298.278303}, abstractNote={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 rN=i=1 ni×i=1 ni where ni is the number of states in the ith 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.}, number={3}, journal={JOURNAL OF THE ACM}, author={Fernandes, P and Plateau, B}, year={1998}, month={May}, pages={381–414} }
@article{fernandes_plateau_stewart_1998, title={Optimizing tensor product computations in stochastic automata networks}, volume={32}, DOI={10.1051/ro/1998320303251}, abstractNote={In this paper we consider some numerical issues in computing solutions to networks of stochastic automata (SAN). In particular our concern is with keeping the amount of computation per iteration to a minimum, since iterative methods appear to be the most effective in determining numerical solutions. In a previous paper we presented complexity results concerning the vector-descriptor multiplication phase of the analysis. In this paper our concern is with optimizations related to the implementation of this algorithm. We also consider the possible benefits of grouping automata in a SAN with many small automata, to create an equivalent SAN having a smaller number of larger automata.}, number={3}, journal={RAIRO. Recherche Operationnelle = Operations Research}, author={Fernandes, P. and Plateau, B. and Stewart, W. J.}, year={1998}, pages={325–351} }
@article{dayar_stewart_1997, title={Quasi lumpability, lower-bounding coupling matrices, and nearly completely decomposable Markov chains}, volume={18}, ISSN={["0895-4798"]}, DOI={10.1137/S0895479895294277}, abstractNote={In this paper, it is shown that nearly completely decomposable (NCD) Markov chains are quasi-lumpable. The state space partition is the natural one, and the technique may be used to compute lower and upper bounds on the stationary probability of each NCD block. In doing so, a lower-bounding nonnegative coupling matrix is employed. The nature of the stationary probability bounds is closely related to the structure of this lower-bounding matrix. Irreducible lower-bounding matrices give tighter bounds compared with bounds obtained using reducible lower-bounding matrices. It is also noticed that the quasi-lumped chain of an NCD Markov chain is an ill-conditioned matrix and the bounds obtained generally will not be tight. However, under some circumstances, it is possible to compute the stationary probabilities of some NCD blocks exactly.}, number={2}, journal={SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS}, author={Dayar, T and Stewart, WJ}, year={1997}, month={Apr}, pages={482–498} }
@book{stewart_1995, title={Computations with Markov chains: Proceedings of the 2nd International Workshop on the Numerical Solution of Markov Chains}, ISBN={0792395506}, publisher={Boston: Kluwer Academic Publishers}, author={Stewart, W. J.}, year={1995} }