Search Results

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.

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.

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.

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.

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.