Dario A. Bini, Guy Latouche, and Beatrice Meini
- Published in print:
- 2005
- Published Online:
- September 2007
- ISBN:
- 9780198527688
- eISBN:
- 9780191713286
- Item type:
- book
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198527688.001.0001
- Subject:
- Mathematics, Numerical Analysis
The book deals with the numerical solution of structured Markov chains which include M/G/1 and G/M/1-type Markov chains, QBD processes, non-skip-free queues, and tree-like stochastic processes and ...
More
The book deals with the numerical solution of structured Markov chains which include M/G/1 and G/M/1-type Markov chains, QBD processes, non-skip-free queues, and tree-like stochastic processes and has a wide applicability in queueing theory and stochastic modeling. It presents in a unified language the most up to date algorithms, which are so far scattered in diverse papers, written with different languages and notation. It contains a thorough treatment of numerical algorithms to solve these problems, from the simplest to the most advanced and most efficient. Nonlinear matrix equations are at the heart of the analysis of structured Markov chains, they are analysed both from the theoretical, from the probabilistic, and from the computational point of view. The set of methods for solution contains functional iterations, doubling methods, logarithmic reduction, cyclic reduction, and subspace iteration, all are described and analysed in detail. They are also adapted to interesting specific queueing models coming from applications. The book also offers a comprehensive and self-contained treatment of the structured matrix tools which are at the basis of the fastest algorithmic techniques for structured Markov chains. Results about Toeplitz matrices, displacement operators, and Wiener-Hopf factorizations are reported to the extent that they are useful for the numerical treatment of Markov chains. Every and all solution methods are reported in detailed algorithmic form so that they can be coded in a high-level language with minimum effort.Less
The book deals with the numerical solution of structured Markov chains which include M/G/1 and G/M/1-type Markov chains, QBD processes, non-skip-free queues, and tree-like stochastic processes and has a wide applicability in queueing theory and stochastic modeling. It presents in a unified language the most up to date algorithms, which are so far scattered in diverse papers, written with different languages and notation. It contains a thorough treatment of numerical algorithms to solve these problems, from the simplest to the most advanced and most efficient. Nonlinear matrix equations are at the heart of the analysis of structured Markov chains, they are analysed both from the theoretical, from the probabilistic, and from the computational point of view. The set of methods for solution contains functional iterations, doubling methods, logarithmic reduction, cyclic reduction, and subspace iteration, all are described and analysed in detail. They are also adapted to interesting specific queueing models coming from applications. The book also offers a comprehensive and self-contained treatment of the structured matrix tools which are at the basis of the fastest algorithmic techniques for structured Markov chains. Results about Toeplitz matrices, displacement operators, and Wiener-Hopf factorizations are reported to the extent that they are useful for the numerical treatment of Markov chains. Every and all solution methods are reported in detailed algorithmic form so that they can be coded in a high-level language with minimum effort.
John C Gower and Garmt B Dijksterhuis
- Published in print:
- 2004
- Published Online:
- September 2007
- ISBN:
- 9780198510581
- eISBN:
- 9780191708961
- Item type:
- book
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198510581.001.0001
- Subject:
- Mathematics, Probability / Statistics
Procrustean methods are used to transform one set of data to represent another set of data as closely as possible. This book unifies several strands in the literature and contains new algorithms. It ...
More
Procrustean methods are used to transform one set of data to represent another set of data as closely as possible. This book unifies several strands in the literature and contains new algorithms. It focuses on matching two or more configurations by using orthogonal, projection, and oblique axes transformations. Group-average summaries play an important part, and links with other group-average methods are discussed. The text is multi-disciplinary and also presents a unifying ANOVA framework.Less
Procrustean methods are used to transform one set of data to represent another set of data as closely as possible. This book unifies several strands in the literature and contains new algorithms. It focuses on matching two or more configurations by using orthogonal, projection, and oblique axes transformations. Group-average summaries play an important part, and links with other group-average methods are discussed. The text is multi-disciplinary and also presents a unifying ANOVA framework.
Rob H. Bisseling
- Published in print:
- 2004
- Published Online:
- September 2007
- ISBN:
- 9780198529392
- eISBN:
- 9780191712869
- Item type:
- book
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198529392.001.0001
- Subject:
- Mathematics, Applied Mathematics
This book explains the use of the bulk synchronous parallel (BSP) model and the BSPlib communication library in parallel algorithm design and parallel programming. The main topics treated in the book ...
More
This book explains the use of the bulk synchronous parallel (BSP) model and the BSPlib communication library in parallel algorithm design and parallel programming. The main topics treated in the book are central to the area of scientific computation: solving dense linear systems by Gaussian elimination, computing fast Fourier transforms, and solving sparse linear systems by iterative methods based on sparse matrix-vector multiplication. Each topic is treated in depth, starting from the problem formulation and a sequential algorithm, through a parallel algorithm and its cost analysis, to a complete parallel program written in C and BSPlib, and experimental results obtained using this program on a parallel computer. Throughout the book, emphasis is placed on analyzing the cost of the parallel algorithms developed, expressed in three terms: computation cost, communication cost, and synchronization cost. The book contains five example programs written in BSPlib, which illustrate the methods taught. These programs are freely available as the package BSPedupack. An appendix on the message-passing interface (MPI) discusses how to program in a structured, bulk synchronous parallel style using the MPI communication library, and presents MPI equivalents of all the programs in the book.Less
This book explains the use of the bulk synchronous parallel (BSP) model and the BSPlib communication library in parallel algorithm design and parallel programming. The main topics treated in the book are central to the area of scientific computation: solving dense linear systems by Gaussian elimination, computing fast Fourier transforms, and solving sparse linear systems by iterative methods based on sparse matrix-vector multiplication. Each topic is treated in depth, starting from the problem formulation and a sequential algorithm, through a parallel algorithm and its cost analysis, to a complete parallel program written in C and BSPlib, and experimental results obtained using this program on a parallel computer. Throughout the book, emphasis is placed on analyzing the cost of the parallel algorithms developed, expressed in three terms: computation cost, communication cost, and synchronization cost. The book contains five example programs written in BSPlib, which illustrate the methods taught. These programs are freely available as the package BSPedupack. An appendix on the message-passing interface (MPI) discusses how to program in a structured, bulk synchronous parallel style using the MPI communication library, and presents MPI equivalents of all the programs in the book.
Rolf Niedermeier
- Published in print:
- 2006
- Published Online:
- September 2007
- ISBN:
- 9780198566076
- eISBN:
- 9780191713910
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198566076.003.0012
- Subject:
- Mathematics, Combinatorics / Graph Theory / Discrete Mathematics
This chapter gives a summary of what happens in Part II and Part III.
This chapter gives a summary of what happens in Part II and Part III.
Rolf Niedermeier
- Published in print:
- 2006
- Published Online:
- September 2007
- ISBN:
- 9780198566076
- eISBN:
- 9780191713910
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198566076.003.0016
- Subject:
- Mathematics, Combinatorics / Graph Theory / Discrete Mathematics
This chapter concludes the book, summarizes the ideas discussed, and puts forward a list of three central challenges for parameterized algorithm design.
This chapter concludes the book, summarizes the ideas discussed, and puts forward a list of three central challenges for parameterized algorithm design.
Neil Tennant
- Published in print:
- 2012
- Published Online:
- September 2012
- ISBN:
- 9780199655755
- eISBN:
- 9780191742125
- Item type:
- book
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199655755.001.0001
- Subject:
- Philosophy, Logic/Philosophy of Mathematics, Metaphysics/Epistemology
This account of rational belief revision explains how a rational agent ought to proceed when adopting a new belief — a difficult matter if the new belief contradicts the agent’s old beliefs. Belief ...
More
This account of rational belief revision explains how a rational agent ought to proceed when adopting a new belief — a difficult matter if the new belief contradicts the agent’s old beliefs. Belief systems are modeled as finite dependency networks. So one can attend not only to what the agent believes, but also to the variety of reasons the agent has for so believing. The computational complexity of the revision problem is characterized. Algorithms for belief revision are formulated, and implemented in Prolog. The implementation tests well on a range of simple belief‐revision problems that pose a variety of challenges for any account of belief‐revision. The notion of ‘minimal mutilation’ of a belief system is explicated precisely. The proposed revision methods are invariant across different global justificatory structures (foundationalist, coherentist, etc.). They respect the intuition that, when revising one's beliefs, one should not hold on to any belief that has lost all its former justifications. The limitation to finite dependency networks is shown not to compromise theoretical generality. This account affords a novel way to argue that there is an inviolable core of logical principles. These principles, which form the system of Core Logic, cannot be given up, on pain of not being able to carry out the reasoning involved in rationally revising beliefs. The book ends by comparing and contrasting the new account with some major representatives of earlier alternative approaches, from the fields of formal epistemology, artificial intelligence and mathematical logic.Less
This account of rational belief revision explains how a rational agent ought to proceed when adopting a new belief — a difficult matter if the new belief contradicts the agent’s old beliefs. Belief systems are modeled as finite dependency networks. So one can attend not only to what the agent believes, but also to the variety of reasons the agent has for so believing. The computational complexity of the revision problem is characterized. Algorithms for belief revision are formulated, and implemented in Prolog. The implementation tests well on a range of simple belief‐revision problems that pose a variety of challenges for any account of belief‐revision. The notion of ‘minimal mutilation’ of a belief system is explicated precisely. The proposed revision methods are invariant across different global justificatory structures (foundationalist, coherentist, etc.). They respect the intuition that, when revising one's beliefs, one should not hold on to any belief that has lost all its former justifications. The limitation to finite dependency networks is shown not to compromise theoretical generality. This account affords a novel way to argue that there is an inviolable core of logical principles. These principles, which form the system of Core Logic, cannot be given up, on pain of not being able to carry out the reasoning involved in rationally revising beliefs. The book ends by comparing and contrasting the new account with some major representatives of earlier alternative approaches, from the fields of formal epistemology, artificial intelligence and mathematical logic.
V. F. Gantmakher
- Published in print:
- 2005
- Published Online:
- September 2007
- ISBN:
- 9780198567561
- eISBN:
- 9780191718267
- Item type:
- book
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198567561.001.0001
- Subject:
- Physics, Condensed Matter Physics / Materials
This book contains modern concepts about the physics of electrons in solids. It is written using a minimum of mathematics, with the emphasis on various physical models aimed at stimulating creative ...
More
This book contains modern concepts about the physics of electrons in solids. It is written using a minimum of mathematics, with the emphasis on various physical models aimed at stimulating creative thinking. The book aims to aid in the choice of the most efficient scheme of an experiment or the optimal algorithm of a calculation. Boltzmann and hopping types of conductivity are compared. The qualitative theory of weak localization is presented and its links with the true localization and metal-insulator transitions. Processes that determine the structure of impurity bands are revealed. The concepts introduced in this book are applied to descriptions of granular metals and quasicrystals, as well as the integer quantum Hall effect, emphasizing their universality.Less
This book contains modern concepts about the physics of electrons in solids. It is written using a minimum of mathematics, with the emphasis on various physical models aimed at stimulating creative thinking. The book aims to aid in the choice of the most efficient scheme of an experiment or the optimal algorithm of a calculation. Boltzmann and hopping types of conductivity are compared. The qualitative theory of weak localization is presented and its links with the true localization and metal-insulator transitions. Processes that determine the structure of impurity bands are revealed. The concepts introduced in this book are applied to descriptions of granular metals and quasicrystals, as well as the integer quantum Hall effect, emphasizing their universality.
Christopher G. Small and Jinfang Wang
- Published in print:
- 2003
- Published Online:
- September 2007
- ISBN:
- 9780198506881
- eISBN:
- 9780191709258
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198506881.003.0003
- Subject:
- Mathematics, Probability / Statistics
This chapter surveys a variety of root-finding and hill-climbing algorithms that are useful for solving estimating equations or maximizing artificial likelihoods, starting with a basic technique ...
More
This chapter surveys a variety of root-finding and hill-climbing algorithms that are useful for solving estimating equations or maximizing artificial likelihoods, starting with a basic technique known as the iterative substitution. Methods such as the Newton-Raphson and the quasi-Newton algorithms are motivated as attempts to improve the rate of convergence of the iterative substitution. The contractive mapping theorem, which provides general conditions for the convergence of a multiparameter algorithm, is stated and proved. The EM-algorithm is described in generality and illustrated with examples. Aitken's method for accelerating linear convergence of algorithms is developed, along with a refinement known as Steffensen's method. Other methods discussed in this chapter include the method of false positions, Muller's method, methods particularly suitable for solving polynomial equations (such as the Bernoulli's method, the quotient-difference algorithm, Sturm's method and the QR-algorithm), the Nelder-Mead algorithm, and the method of Jacobi iteration for approximate inversion of matrices.Less
This chapter surveys a variety of root-finding and hill-climbing algorithms that are useful for solving estimating equations or maximizing artificial likelihoods, starting with a basic technique known as the iterative substitution. Methods such as the Newton-Raphson and the quasi-Newton algorithms are motivated as attempts to improve the rate of convergence of the iterative substitution. The contractive mapping theorem, which provides general conditions for the convergence of a multiparameter algorithm, is stated and proved. The EM-algorithm is described in generality and illustrated with examples. Aitken's method for accelerating linear convergence of algorithms is developed, along with a refinement known as Steffensen's method. Other methods discussed in this chapter include the method of false positions, Muller's method, methods particularly suitable for solving polynomial equations (such as the Bernoulli's method, the quotient-difference algorithm, Sturm's method and the QR-algorithm), the Nelder-Mead algorithm, and the method of Jacobi iteration for approximate inversion of matrices.
Mark Newman
- Published in print:
- 2010
- Published Online:
- September 2010
- ISBN:
- 9780199206650
- eISBN:
- 9780191594175
- Item type:
- book
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199206650.001.0001
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
The scientific study of networks, including computer networks, social networks, and biological networks, has received an enormous amount of interest in the last few years. The rise of the Internet ...
More
The scientific study of networks, including computer networks, social networks, and biological networks, has received an enormous amount of interest in the last few years. The rise of the Internet and the wide availability of inexpensive computers have made it possible to gather and analyze network data on a large scale, and the development of a variety of new theoretical tools has allowed us to extract new knowledge from many different kinds of networks. The study of networks is broadly interdisciplinary and important developments have occurred in many fields, including mathematics, physics, computer and information sciences, biology, and the social sciences. This book brings together the most important breakthroughs in each of these fields and presents them in a coherent fashion, highlighting the strong interconnections between work in different areas. Subjects covered include the measurement and structure of networks in many branches of science, methods for analyzing network data, including methods developed in physics, statistics, and sociology, the fundamentals of graph theory, computer algorithms, and spectral methods, mathematical models of networks, including random graph models and generative models, and theories of dynamical processes taking place on networks.Less
The scientific study of networks, including computer networks, social networks, and biological networks, has received an enormous amount of interest in the last few years. The rise of the Internet and the wide availability of inexpensive computers have made it possible to gather and analyze network data on a large scale, and the development of a variety of new theoretical tools has allowed us to extract new knowledge from many different kinds of networks. The study of networks is broadly interdisciplinary and important developments have occurred in many fields, including mathematics, physics, computer and information sciences, biology, and the social sciences. This book brings together the most important breakthroughs in each of these fields and presents them in a coherent fashion, highlighting the strong interconnections between work in different areas. Subjects covered include the measurement and structure of networks in many branches of science, methods for analyzing network data, including methods developed in physics, statistics, and sociology, the fundamentals of graph theory, computer algorithms, and spectral methods, mathematical models of networks, including random graph models and generative models, and theories of dynamical processes taking place on networks.
M. Vidyasagar
- Published in print:
- 2014
- Published Online:
- October 2017
- ISBN:
- 9780691133157
- eISBN:
- 9781400850518
- Item type:
- book
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691133157.001.0001
- Subject:
- Mathematics, Probability / Statistics
This book explores important aspects of Markov and hidden Markov processes and the applications of these ideas to various problems in computational biology. It starts from first principles, so that ...
More
This book explores important aspects of Markov and hidden Markov processes and the applications of these ideas to various problems in computational biology. It starts from first principles, so that no previous knowledge of probability is necessary. However, the work is rigorous and mathematical, making it useful to engineers and mathematicians, even those not interested in biological applications. A range of exercises is provided, including drills to familiarize the reader with concepts and more advanced problems that require deep thinking about the theory. Biological applications are taken from post-genomic biology, especially genomics and proteomics. The topics examined include standard material such as the Perron–Frobenius theorem, transient and recurrent states, hitting probabilities and hitting times, maximum likelihood estimation, the Viterbi algorithm, and the Baum–Welch algorithm. The book contains discussions of extremely useful topics not usually seen at the basic level, such as ergodicity of Markov processes, Markov Chain Monte Carlo (MCMC), information theory, and large deviation theory for both i.i.d and Markov processes. It also presents state-of-the-art realization theory for hidden Markov models. Among biological applications, it offers an in-depth look at the BLAST (Basic Local Alignment Search Technique) algorithm, including a comprehensive explanation of the underlying theory. Other applications such as profile hidden Markov models are also explored.Less
This book explores important aspects of Markov and hidden Markov processes and the applications of these ideas to various problems in computational biology. It starts from first principles, so that no previous knowledge of probability is necessary. However, the work is rigorous and mathematical, making it useful to engineers and mathematicians, even those not interested in biological applications. A range of exercises is provided, including drills to familiarize the reader with concepts and more advanced problems that require deep thinking about the theory. Biological applications are taken from post-genomic biology, especially genomics and proteomics. The topics examined include standard material such as the Perron–Frobenius theorem, transient and recurrent states, hitting probabilities and hitting times, maximum likelihood estimation, the Viterbi algorithm, and the Baum–Welch algorithm. The book contains discussions of extremely useful topics not usually seen at the basic level, such as ergodicity of Markov processes, Markov Chain Monte Carlo (MCMC), information theory, and large deviation theory for both i.i.d and Markov processes. It also presents state-of-the-art realization theory for hidden Markov models. Among biological applications, it offers an in-depth look at the BLAST (Basic Local Alignment Search Technique) algorithm, including a comprehensive explanation of the underlying theory. Other applications such as profile hidden Markov models are also explored.
