D. A. Bini, G. Latouche, and B. Meini
- Published in print:
- 2005
- Published Online:
- September 2007
- ISBN:
- 9780198527688
- eISBN:
- 9780191713286
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198527688.003.0002
- Subject:
- Mathematics, Numerical Analysis
This chapter describes structural and computational properties which are the basis of the design and analysis of fast algorithms for the numerical solution of structured Markov chains. Toeplitz ...
More
This chapter describes structural and computational properties which are the basis of the design and analysis of fast algorithms for the numerical solution of structured Markov chains. Toeplitz matrices, circulant and z-circulant matrices with their block analogs are introduced together with the fast algorithms for their manipulation. The concept of discrete Fourier transform is recalled with the FFT algorithm for its computation. Attention is given to the concept of displacement operator and of displacement rank needed to design efficient algorithms for a wide class of matrices related to Toeplitz matrices.Less
This chapter describes structural and computational properties which are the basis of the design and analysis of fast algorithms for the numerical solution of structured Markov chains. Toeplitz matrices, circulant and z-circulant matrices with their block analogs are introduced together with the fast algorithms for their manipulation. The concept of discrete Fourier transform is recalled with the FFT algorithm for its computation. Attention is given to the concept of displacement operator and of displacement rank needed to design efficient algorithms for a wide class of matrices related to Toeplitz matrices.
D. A. Bini, G. Latouche, and B. Meini
- Published in print:
- 2005
- Published Online:
- September 2007
- ISBN:
- 9780198527688
- eISBN:
- 9780191713286
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198527688.003.0003
- Subject:
- Mathematics, Numerical Analysis
This chapter is concerned with infinite block Toeplitz matrices, their relationships with matrix power series and matrix Laurent power series, and the fundamental problem of solving matrix equations ...
More
This chapter is concerned with infinite block Toeplitz matrices, their relationships with matrix power series and matrix Laurent power series, and the fundamental problem of solving matrix equations and computing canonical factorizations. It introduces the concept of a Wiener algebra and provides a natural theoretical framework where the convergence properties of algorithms for solving Markov chains can easily be proved. Furthermore, the notion of canonical factorization provides a powerful tool for solving infinite linear systems, such as the fundamental system involving the stationary probability distribution of structured Markov chains.Less
This chapter is concerned with infinite block Toeplitz matrices, their relationships with matrix power series and matrix Laurent power series, and the fundamental problem of solving matrix equations and computing canonical factorizations. It introduces the concept of a Wiener algebra and provides a natural theoretical framework where the convergence properties of algorithms for solving Markov chains can easily be proved. Furthermore, the notion of canonical factorization provides a powerful tool for solving infinite linear systems, such as the fundamental system involving the stationary probability distribution of structured Markov chains.
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.
Moody T. Chu and Gene H. Golub
- Published in print:
- 2005
- Published Online:
- September 2007
- ISBN:
- 9780198566649
- eISBN:
- 9780191718021
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198566649.003.0004
- Subject:
- Mathematics, Applied Mathematics
The feasibility conditions for a physical system often mandate specific structural stipulations on the inverse problems. This chapter focuses on eight selected structures: Jacobi matrices, Toeplitz ...
More
The feasibility conditions for a physical system often mandate specific structural stipulations on the inverse problems. This chapter focuses on eight selected structures: Jacobi matrices, Toeplitz matrices, nonnegative matrices, stochastic matrices, unitary matrices, matrices with prescribed entries, matrices with prescribed singular values, and matrices with prescribed singular values and eigenvalues.Less
The feasibility conditions for a physical system often mandate specific structural stipulations on the inverse problems. This chapter focuses on eight selected structures: Jacobi matrices, Toeplitz matrices, nonnegative matrices, stochastic matrices, unitary matrices, matrices with prescribed entries, matrices with prescribed singular values, and matrices with prescribed singular values and eigenvalues.
Moody T. Chu and Gene H. Golub
- Published in print:
- 2005
- Published Online:
- September 2007
- ISBN:
- 9780198566649
- eISBN:
- 9780191718021
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198566649.003.0005
- Subject:
- Mathematics, Applied Mathematics
In practice, it is often the case that only partial information on eigenvalues and eigenvectors is available. In many cases, just a few eigenpairs can determine much of the desirable reconstruction. ...
More
In practice, it is often the case that only partial information on eigenvalues and eigenvectors is available. In many cases, just a few eigenpairs can determine much of the desirable reconstruction. This chapter illustrates this point by concentrating on the Toeplitz structure and the self-adjoint quadratic pencils. The possibility of model updating or tuning applications is discussed.Less
In practice, it is often the case that only partial information on eigenvalues and eigenvectors is available. In many cases, just a few eigenpairs can determine much of the desirable reconstruction. This chapter illustrates this point by concentrating on the Toeplitz structure and the self-adjoint quadratic pencils. The possibility of model updating or tuning applications is discussed.
Mihály Bakonyi and Hugo J. Woerdeman
- Published in print:
- 2011
- Published Online:
- October 2017
- ISBN:
- 9780691128894
- eISBN:
- 9781400840595
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691128894.003.0003
- Subject:
- Mathematics, Computational Mathematics / Optimization
This chapter shows how five closely related problems become vastly different when one considers the multivariable case. In a similar way, various natural sums of Hermitian squares problems that one ...
More
This chapter shows how five closely related problems become vastly different when one considers the multivariable case. In a similar way, various natural sums of Hermitian squares problems that one may consider in the multivariable case all come down to the classical factorization problem in one variable as discussed in Section 1.1. The discussions cover positive Carathéodory interpolation on the polydisk; inverses of multivariable Toeplitz matrices and Christoel–Darboux formulas; two-variable moment problem for Bernstein–Szeg ő measures; Fejéer–Riesz factorization and sums of Hermitian squares; completion problems for positive semidefinite functions on amenable groups; moment problems on free groups, noncommutative factorization; two-variable Hamburger moment problem; and Bochner's theorem and an application to autoregressive stochastic processes. Exercises and notes are provided at the end of the chapter.Less
This chapter shows how five closely related problems become vastly different when one considers the multivariable case. In a similar way, various natural sums of Hermitian squares problems that one may consider in the multivariable case all come down to the classical factorization problem in one variable as discussed in Section 1.1. The discussions cover positive Carathéodory interpolation on the polydisk; inverses of multivariable Toeplitz matrices and Christoel–Darboux formulas; two-variable moment problem for Bernstein–Szeg ő measures; Fejéer–Riesz factorization and sums of Hermitian squares; completion problems for positive semidefinite functions on amenable groups; moment problems on free groups, noncommutative factorization; two-variable Hamburger moment problem; and Bochner's theorem and an application to autoregressive stochastic processes. Exercises and notes are provided at the end of the chapter.
Marek A. Kowalski, Krzystof A. Sikorski, and Frank Stenger
- Published in print:
- 1995
- Published Online:
- November 2020
- ISBN:
- 9780195080599
- eISBN:
- 9780197560402
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/oso/9780195080599.003.0006
- Subject:
- Computer Science, Mathematical Theory of Computation
Sine methods are a new family of self-contained methods of approximation, which have several advantages over classical methods of approximation in the case of the ...
More
Sine methods are a new family of self-contained methods of approximation, which have several advantages over classical methods of approximation in the case of the presence of end-point singularities, in the case when we have a semi-infinite or infinite interval of approximation, or in the case of the presence of a boundary layer situation.
Less
Sine methods are a new family of self-contained methods of approximation, which have several advantages over classical methods of approximation in the case of the presence of end-point singularities, in the case when we have a semi-infinite or infinite interval of approximation, or in the case of the presence of a boundary layer situation.