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.
Željko Ivezi, Andrew J. Connolly, Jacob T. VanderPlas, Alexander Gray, Željko Ivezi, Andrew J. Connolly, Jacob T. VanderPlas, and Alexander Gray
- Published in print:
- 2014
- Published Online:
- October 2017
- ISBN:
- 9780691151687
- eISBN:
- 9781400848911
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691151687.003.0002
- Subject:
- Physics, Particle Physics / Astrophysics / Cosmology
This chapter describes basic concepts and tools for tractably performing the computations described in the rest of this book. The need for fast algorithms for such analysis subroutines is becoming ...
More
This chapter describes basic concepts and tools for tractably performing the computations described in the rest of this book. The need for fast algorithms for such analysis subroutines is becoming increasingly important as modern data sets are approaching billions of objects. With such data sets, even analysis operations whose computational cost is linearly proportional to the size of the data set present challenges, particularly since statistical analyses are inherently interactive processes, requiring that computations complete within some reasonable human attention span. For more sophisticated machine learning algorithms, the often worse-than-linear runtimes of straightforward implementations become quickly unbearable. The chapter looks at some techniques that can reduce such runtimes in a rigorous manner that does not sacrifice the accuracy of the analysis through unprincipled approximations. This is far more important than simply speeding up calculations: in practice, computational performance and statistical performance can be intimately linked. The ability of a researcher, within his or her effective time budget, to try more powerful models or to search parameter settings for each model in question, leads directly to better fits and predictions.Less
This chapter describes basic concepts and tools for tractably performing the computations described in the rest of this book. The need for fast algorithms for such analysis subroutines is becoming increasingly important as modern data sets are approaching billions of objects. With such data sets, even analysis operations whose computational cost is linearly proportional to the size of the data set present challenges, particularly since statistical analyses are inherently interactive processes, requiring that computations complete within some reasonable human attention span. For more sophisticated machine learning algorithms, the often worse-than-linear runtimes of straightforward implementations become quickly unbearable. The chapter looks at some techniques that can reduce such runtimes in a rigorous manner that does not sacrifice the accuracy of the analysis through unprincipled approximations. This is far more important than simply speeding up calculations: in practice, computational performance and statistical performance can be intimately linked. The ability of a researcher, within his or her effective time budget, to try more powerful models or to search parameter settings for each model in question, leads directly to better fits and predictions.
Vlatko Vedral
- Published in print:
- 2006
- Published Online:
- January 2010
- ISBN:
- 9780199215706
- eISBN:
- 9780191706783
- Item type:
- book
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199215706.001.0001
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
In addition to treating quantum communication, entanglement, error correction, and algorithms in great depth, this book also addresses a number of interesting miscellaneous topics, such as Maxwell's ...
More
In addition to treating quantum communication, entanglement, error correction, and algorithms in great depth, this book also addresses a number of interesting miscellaneous topics, such as Maxwell's demon, Landauer's erasure, the Bekenstein bound, and Caratheodory's treatment of the second law of thermodynamics. All mathematical derivations are based on clear physical pictures which make even the most involved results — such as the Holevo bound — look comprehensible and transparent. Quantum information is a fascinating topic precisely because it shows that the laws of information processing are actually dependent on the laws of physics. However, it is also very interesting to see that information theory has something to teach us about physics. Both of these directions are discussed throughout the book. Other topics covered in the book are quantum mechanics, measures of quantum entanglement, general conditions of quantum error correction, pure state entanglement and Pauli matrices, pure states and Bell's inequalities, and computational complexity of quantum algorithms.Less
In addition to treating quantum communication, entanglement, error correction, and algorithms in great depth, this book also addresses a number of interesting miscellaneous topics, such as Maxwell's demon, Landauer's erasure, the Bekenstein bound, and Caratheodory's treatment of the second law of thermodynamics. All mathematical derivations are based on clear physical pictures which make even the most involved results — such as the Holevo bound — look comprehensible and transparent. Quantum information is a fascinating topic precisely because it shows that the laws of information processing are actually dependent on the laws of physics. However, it is also very interesting to see that information theory has something to teach us about physics. Both of these directions are discussed throughout the book. Other topics covered in the book are quantum mechanics, measures of quantum entanglement, general conditions of quantum error correction, pure state entanglement and Pauli matrices, pure states and Bell's inequalities, and computational complexity of quantum algorithms.
George Em Karniadakis and Spencer J. Sherwin
- Published in print:
- 2005
- Published Online:
- September 2007
- ISBN:
- 9780198528692
- eISBN:
- 9780191713491
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198528692.003.0008
- Subject:
- Mathematics, Numerical Analysis
This chapter presents different ways of formulating the incompressible Navier-Stokes equations based on primitive variables, that is, velocity and pressure, as well as velocity-vorticity algorithms. ...
More
This chapter presents different ways of formulating the incompressible Navier-Stokes equations based on primitive variables, that is, velocity and pressure, as well as velocity-vorticity algorithms. It considers both coupled, splitting, and least-squares formulations for primitive variables. Both the Uzawa coupled algorithm and a new substructured solver are discussed. The discussion on primitive variables time-splitting includes recent theoretical advances in the pressure-correction and velocity correction schemes as well as the rotational formulation of the pressure boundary condition. The final section is devoted to nonlinear terms; it includes a discussion of spatial and temporal discretization with focus on the semi-Lagrangian method for the incompressible Navier-Stokes equations.Less
This chapter presents different ways of formulating the incompressible Navier-Stokes equations based on primitive variables, that is, velocity and pressure, as well as velocity-vorticity algorithms. It considers both coupled, splitting, and least-squares formulations for primitive variables. Both the Uzawa coupled algorithm and a new substructured solver are discussed. The discussion on primitive variables time-splitting includes recent theoretical advances in the pressure-correction and velocity correction schemes as well as the rotational formulation of the pressure boundary condition. The final section is devoted to nonlinear terms; it includes a discussion of spatial and temporal discretization with focus on the semi-Lagrangian method for the incompressible Navier-Stokes equations.
N. Thompson Hobbs and Mevin B. Hooten
- Published in print:
- 2015
- Published Online:
- October 2017
- ISBN:
- 9780691159287
- eISBN:
- 9781400866557
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691159287.003.0007
- Subject:
- Biology, Ecology
This chapter explains how to implement Bayesian analyses using the Markov chain Monte Carlo (MCMC) algorithm, a set of methods for Bayesian analysis made popular by the seminal paper of Gelfand and ...
More
This chapter explains how to implement Bayesian analyses using the Markov chain Monte Carlo (MCMC) algorithm, a set of methods for Bayesian analysis made popular by the seminal paper of Gelfand and Smith (1990). It begins with an explanation of MCMC with a heuristic, high-level treatment of the algorithm, describing its operation in simple terms with a minimum of formalism. In this first part, the chapter explains the algorithm so that all readers can gain an intuitive understanding of how to find the posterior distribution by sampling from it. Next, the chapter offers a somewhat more formal treatment of how MCMC is implemented mathematically. Finally, this chapter discusses implementation of Bayesian models via two routes—by using software and by writing one's own algorithm.Less
This chapter explains how to implement Bayesian analyses using the Markov chain Monte Carlo (MCMC) algorithm, a set of methods for Bayesian analysis made popular by the seminal paper of Gelfand and Smith (1990). It begins with an explanation of MCMC with a heuristic, high-level treatment of the algorithm, describing its operation in simple terms with a minimum of formalism. In this first part, the chapter explains the algorithm so that all readers can gain an intuitive understanding of how to find the posterior distribution by sampling from it. Next, the chapter offers a somewhat more formal treatment of how MCMC is implemented mathematically. Finally, this chapter discusses implementation of Bayesian models via two routes—by using software and by writing one's own algorithm.
Iwo Bialynicki-Birula and Iwona Bialynicka-Birula
- Published in print:
- 2004
- Published Online:
- January 2010
- ISBN:
- 9780198531005
- eISBN:
- 9780191713033
- Item type:
- book
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198531005.001.0001
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
This book covers a wide range of subjects concerning the use of computer modeling to solve a diverse set of problems. The book covers some advanced topics (cellular automata, Shannon measure of ...
More
This book covers a wide range of subjects concerning the use of computer modeling to solve a diverse set of problems. The book covers some advanced topics (cellular automata, Shannon measure of information content, dynamical systems, deterministic chaos, fractals, statistical linguistics, game theory, neural networks, genetic algorithms, Turing machines, and artificial intelligence). These advanced subjects are explained in terms of well known simple concepts such as the Game of Life, probability and statistics, Galton's board, Shannon's formula, game of twenty questions, game theory, and a format similar to a television quiz. Twenty-five programs written specifically for the book greatly enhance its pedagogical value and the enjoyment of learning. These can be found at http://www.modelingreality.net/.Less
This book covers a wide range of subjects concerning the use of computer modeling to solve a diverse set of problems. The book covers some advanced topics (cellular automata, Shannon measure of information content, dynamical systems, deterministic chaos, fractals, statistical linguistics, game theory, neural networks, genetic algorithms, Turing machines, and artificial intelligence). These advanced subjects are explained in terms of well known simple concepts such as the Game of Life, probability and statistics, Galton's board, Shannon's formula, game of twenty questions, game theory, and a format similar to a television quiz. Twenty-five programs written specifically for the book greatly enhance its pedagogical value and the enjoyment of learning. These can be found at http://www.modelingreality.net/.
Rafal Goebel, Ricardo G. Sanfelice, and Andrew R. Teel
- Published in print:
- 2012
- Published Online:
- October 2017
- ISBN:
- 9780691153896
- eISBN:
- 9781400842636
- Item type:
- book
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691153896.001.0001
- Subject:
- Mathematics, Applied Mathematics
Hybrid dynamical systems exhibit continuous and instantaneous changes, having features of continuous-time and discrete-time dynamical systems. Filled with a wealth of examples to illustrate concepts, ...
More
Hybrid dynamical systems exhibit continuous and instantaneous changes, having features of continuous-time and discrete-time dynamical systems. Filled with a wealth of examples to illustrate concepts, this book presents a complete theory of robust asymptotic stability for hybrid dynamical systems that is applicable to the design of hybrid control algorithms—algorithms that feature logic, timers, or combinations of digital and analog components. With the tools of modern mathematical analysis, this book unifies and generalizes earlier developments in continuous-time and discrete-time nonlinear systems. It presents hybrid system versions of the necessary and sufficient Lyapunov conditions for asymptotic stability, invariance principles, and approximation techniques, and examines the robustness of asymptotic stability, motivated by the goal of designing robust hybrid control algorithms. This self-contained and classroom-tested book requires standard background in mathematical analysis and differential equations or nonlinear systems. It will interest graduate students in engineering as well as students and researchers in control, computer science, and mathematics.Less
Hybrid dynamical systems exhibit continuous and instantaneous changes, having features of continuous-time and discrete-time dynamical systems. Filled with a wealth of examples to illustrate concepts, this book presents a complete theory of robust asymptotic stability for hybrid dynamical systems that is applicable to the design of hybrid control algorithms—algorithms that feature logic, timers, or combinations of digital and analog components. With the tools of modern mathematical analysis, this book unifies and generalizes earlier developments in continuous-time and discrete-time nonlinear systems. It presents hybrid system versions of the necessary and sufficient Lyapunov conditions for asymptotic stability, invariance principles, and approximation techniques, and examines the robustness of asymptotic stability, motivated by the goal of designing robust hybrid control algorithms. This self-contained and classroom-tested book requires standard background in mathematical analysis and differential equations or nonlinear systems. It will interest graduate students in engineering as well as students and researchers in control, computer science, and mathematics.
Mark Wilson
- Published in print:
- 2006
- Published Online:
- January 2007
- ISBN:
- 9780199269259
- eISBN:
- 9780191710155
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199269259.003.0004
- Subject:
- Philosophy, Philosophy of Language
Because classical demands on conceptual understanding are quite strong and can prove potentially inhibiting within a scientific context, various philosopher/scientists in the late 19th century ...
More
Because classical demands on conceptual understanding are quite strong and can prove potentially inhibiting within a scientific context, various philosopher/scientists in the late 19th century proposed that certain predicates could be provided with an alternative form of ‘meaning’ through distributed normativity, i.e., through implicit definition within a syntactic web of interconnection. Applied mathematics, however, warns that such globally unified webs often do not provide optimal descriptive platforms. On the basis of these considerations, it is argued that the ‘facades’ of Chapter 6 often represent better ‘linguistic engineering’ solutions to certain descriptive problems.Less
Because classical demands on conceptual understanding are quite strong and can prove potentially inhibiting within a scientific context, various philosopher/scientists in the late 19th century proposed that certain predicates could be provided with an alternative form of ‘meaning’ through distributed normativity, i.e., through implicit definition within a syntactic web of interconnection. Applied mathematics, however, warns that such globally unified webs often do not provide optimal descriptive platforms. On the basis of these considerations, it is argued that the ‘facades’ of Chapter 6 often represent better ‘linguistic engineering’ solutions to certain descriptive problems.
Vlatko Vedral
- Published in print:
- 2006
- Published Online:
- January 2010
- ISBN:
- 9780199215706
- eISBN:
- 9780191706783
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199215706.003.0014
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
This book has discussed the foundations of quantum information science as well as the relationship between physics and information theory in general. It has considered the quantum equivalents of the ...
More
This book has discussed the foundations of quantum information science as well as the relationship between physics and information theory in general. It has considered the quantum equivalents of the Shannon coding and channel capacity theorems. The von Neumann entropy plays a role analogous to the Shannon entropy, and the Holevo bound is the analogue of Shannon's mutual information used to quantify the capacity of a classical channel. Quantum systems can process information more efficiently than classical systems in a number of different ways. Quantum teleportation and quantum dense coding can be performed using quantum entanglement. Entanglement is an excess of correlations that can exist in quantum physics and is impossible to reproduce classically (with what is termed “separable” states). The book has also demonstrated how to discriminate entangled from separable states using entanglement witnesses, as well as how to quantify entanglement, and looked at quantum computation and quantum algorithms.Less
This book has discussed the foundations of quantum information science as well as the relationship between physics and information theory in general. It has considered the quantum equivalents of the Shannon coding and channel capacity theorems. The von Neumann entropy plays a role analogous to the Shannon entropy, and the Holevo bound is the analogue of Shannon's mutual information used to quantify the capacity of a classical channel. Quantum systems can process information more efficiently than classical systems in a number of different ways. Quantum teleportation and quantum dense coding can be performed using quantum entanglement. Entanglement is an excess of correlations that can exist in quantum physics and is impossible to reproduce classically (with what is termed “separable” states). The book has also demonstrated how to discriminate entangled from separable states using entanglement witnesses, as well as how to quantify entanglement, and looked at quantum computation and quantum algorithms.
M. Vidyasagar
- Published in print:
- 2014
- Published Online:
- October 2017
- ISBN:
- 9780691133157
- eISBN:
- 9781400850518
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691133157.003.0006
- Subject:
- Mathematics, Probability / Statistics
This chapter considers the basic properties of hidden Markov processes (HMPs) or hidden Markov models (HMMs), a special type of stochastic process. It begins with a discussion of three distinct types ...
More
This chapter considers the basic properties of hidden Markov processes (HMPs) or hidden Markov models (HMMs), a special type of stochastic process. It begins with a discussion of three distinct types of HMMs and shows that they are all equivalent from the standpoint of their expressive power or modeling ability: Type 1 hidden Markov model, or a HMM of the deterministic function of a Markov chain type; hidden Markov model of Type 2, or a HMM of the random function of a Markov chain type; and hidden Markov model of Type 3, or a HMM of the joint Markov process type. The chapter also examines various issues related to the computation of likelihoods in a HMM before concluding with an overview of the Viterbi algorithm and the Baum–Welch algorithm.Less
This chapter considers the basic properties of hidden Markov processes (HMPs) or hidden Markov models (HMMs), a special type of stochastic process. It begins with a discussion of three distinct types of HMMs and shows that they are all equivalent from the standpoint of their expressive power or modeling ability: Type 1 hidden Markov model, or a HMM of the deterministic function of a Markov chain type; hidden Markov model of Type 2, or a HMM of the random function of a Markov chain type; and hidden Markov model of Type 3, or a HMM of the joint Markov process type. The chapter also examines various issues related to the computation of likelihoods in a HMM before concluding with an overview of the Viterbi algorithm and the Baum–Welch algorithm.
M. Vidyasagar
- Published in print:
- 2014
- Published Online:
- October 2017
- ISBN:
- 9780691133157
- eISBN:
- 9781400850518
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691133157.003.0008
- Subject:
- Mathematics, Probability / Statistics
This chapter considers some applications of Markov processes and hidden Markov processes to computational biology. It introduces three important problems, namely: sequence alignment, the gene-finding ...
More
This chapter considers some applications of Markov processes and hidden Markov processes to computational biology. It introduces three important problems, namely: sequence alignment, the gene-finding problem, and protein classification. After providing an overview of some relevant aspects of biology, the chapter examines the problem of optimal gapped alignment between two sequences. This is a way to detect similarity between two sequences over a common alphabet, such as the four-symbol alphabet of nucleotides, or the 20-symbol alphabet of amino acids. The chapter proceeds by discussing some widely used algorithms for finding genes from DNA sequences (genomes), including the GLIMMER algorithm and the GENSCAN algorithm. Finally, it describes a special type of hidden Markov model termed profile hidden Markov model, which is commonly used to classify proteins into a small number of groups.Less
This chapter considers some applications of Markov processes and hidden Markov processes to computational biology. It introduces three important problems, namely: sequence alignment, the gene-finding problem, and protein classification. After providing an overview of some relevant aspects of biology, the chapter examines the problem of optimal gapped alignment between two sequences. This is a way to detect similarity between two sequences over a common alphabet, such as the four-symbol alphabet of nucleotides, or the 20-symbol alphabet of amino acids. The chapter proceeds by discussing some widely used algorithms for finding genes from DNA sequences (genomes), including the GLIMMER algorithm and the GENSCAN algorithm. Finally, it describes a special type of hidden Markov model termed profile hidden Markov model, which is commonly used to classify proteins into a small number of groups.
