Search

We present some accelerated variants of fixed point iterations for computing the minimal non-negative solution of the unilateral matrix equation associated with an M/G/1-type Markov chain. These variants derive from certain staircase regular splittings of the block Hessenberg M-matrix associated with the Markov chain. By exploiting the staircase profile, we introduce a two-step fixed point iteration. The iteration can be further accelerated by computing a weighted average between the approximations obtained at two consecutive steps. The convergence of the basic two-step fixed point iteration and of its relaxed modification is proved. Our theoretical analysis, along with several numerical experiments, shows that the proposed variants generally outperform the classical iterations.

We consider the problem of computing the minimal non-negative solution $G$ of the nonlinear matrix equation $X=\sum _{i=-1}^\infty A_iX^{i+1}$ where $A_i$, for $i\geqslant -1$, are non-negative square matrices such that $\sum _{i=-1}^\infty A_i$ is stochastic. This equation is fundamental in the analysis of M/G/1-type Markov chains, since the matrix $G$ provides probabilistic measures of interest. A new family of fixed point iterations for the numerical computation of $G$, which includes the classical iterations, is introduced. A detailed convergence analysis proves that the iterations in the new class converge faster than the classical iterations. Numerical experiments confirm the effectiveness of our extension.

In discrete time, $\ell$-blocks of red lights are separated by $\ell$-blocks of green lights. Cars arrive at random. \ We seek the distribution of maximum line length of idle cars, and justify conjectured probabilistic asymptotics algebraically for $2\leq\ell\leq3$ and numerically for $\ell\geq4$.

A new measure $c(e)$ of the centrality of an edge $e$ in an undirected graph $G$ is introduced. It is based on the variation of the Kemeny constant of the graph after removing the edge $e$. The new measure is designed in such a way that the Braess paradox is avoided. A numerical method for computing $c(e)$ is introduced and a regularization technique is designed in order to deal with cut-edges and disconnected graphs. Numerical experiments performed on synthetic tests and on real road networks show that this measure is particularly effective in revealing bottleneck roads whose removal would greatly reduce the connectivity of the network.

A Markov modulated Brownian motion (MMBM) is a substantial generalization of the classical Brownian motion and is obtained by allowing the Brownian parameters to be modulated by an underlying Marko...

We identify a relationship between the solutions of a nonsymmetric algebraic$$T$$T-Riccati equation ($$T$$T-NARE) and the deflating subspaces of a palindromic matrix pencil, obtained by arranging the coefficients of the$$T$$T-NARE. The interplay between$$T$$T-NAREs and palindromic pencils allows one to derive both theoretical properties of the solutions of the equation, and new methods for its numerical solution. In particular, we propose methods based on the (palindromic) QZ algorithm and the doubling algorithm, whose effectiveness is demonstrated by several numerical tests.

Let $a(z)=\sum_{i\in\mathbb Z}a_iz^i$ be a complex valued function defined for $|z|=1$, such that $\sum_{i\in\mathbb Z}|ia_i

We consider the problem of solving a rational matrix equation arising in the solution of G-networks. We propose and analyze two numerical methods: a fixed point iteration and the Newton–Raphson method. The fixed point iteration is shown to be globally convergent with linear convergence rate, while the Newton method is shown to have a local convergence, with quadratic convergence rate. Numerical experiments show the effectiveness of the proposed methods.

Quadratic matrix equations of the kind $A_1X^2+A_0X+A_{-1}=X$ are encountered in the analysis of Quasi--Birth-Death stochastic processes where the solution of interest is the minimal nonnegative solution $G$. In many queueing models, described by random walks in the quarter plane, the coefficients $A_1,A_0,A_{-1}$ are infinite tridiagonal matrices with an almost Toeplitz structure. Here, we analyze some fixed point iterations, including Newton's iteration, for the computation of $G$ and introduce effective algorithms and acceleration strategies which fully exploit the Toeplitz structure of the matrix coefficients and of the current approximation. Moreover, we provide a structured perturbation analysis for the solution $G$. The results of some numerical experiments which demonstrate the effectiveness of our approach are reported.

The treatment of two-dimensional random walks in the quarter plane leads to Markov processes which involve semi-infinite matrices having Toeplitz or block Toeplitz structure plus a low-rank correction. Finding the steady state probability distribution of the process requires to perform operations involving these structured matrices. We propose an extension of the framework of [5] which allows to deal with more general situations such as processes involving restart events. This is motivated by the need for modeling processes that can incur in unexpected failures like computer system reboots. Algebraically, this gives rise to corrections with infinite support that cannot be treated using the tools currently available in the literature. We present a theoretical analysis of an enriched Banach algebra that, combined with appropriate algorithms, enables the numerical treatment of these problems. The results are applied to the solution of bidimensional Quasi-Birth-Death processes with infinitely many phases which model random walks in the quarter plane, relying on the matrix analytic approach. This methodology reduces the problem to solving a quadratic matrix equation with coefficients of infinite size. We provide conditions on the transition probabilities which ensure that the solution of interest of the matrix equation belongs to the enriched algebra. The reliability of our approach is confirmed by extensive numerical experimentation on some case studies.

Denote by $\mathcal{W}_1$ the set of complex valued functions of the form $a(z)=\sum_{i=-\infty}^{+\infty}a_iz^i$ which are continuous on the unit circle, and such that $\sum_{i=-\infty}^{+\infty}|ia_i

Given a square matrix A, Brauer’s theorem [Duke Math. J. 19 (1952), 75–91] shows how to modify one single eigenvalue of A via a rank-one perturbation, without changing any of the remaining eigenvalues. We reformulate Brauer’s theorem in functional form and provide extensions to matrix polynomials and to matrix Laurent series A(z) together with generalizations to shifting a set of eigenvalues. We provide conditions under which the modified function \( \tilde{A}(z) \) has a canonical factorization \( \tilde{A}(z)=\tilde{U}(z)\tilde{L}(z^{-1}) \) and we provide explicit expressions of the factors \( \tilde{U}(z) \) and \( \tilde{L}(z) \). Similar conditions and expressions are given for the factorization of \( \tilde{A}(z^{-1}) \). Some applications are discussed.

In their 1960 book on finite Markov chains, Kemeny and Snell established that a certain sum is invariant. The value of this sum has become known as {\it Kemeny's constant}. Various proofs have been given over time, some more technical than others. We give here a very simple physical justification, which extends without a hitch to continuous-time Markov chains on a finite state space. For Markov chains with denumerably infinite state space, the constant may be infinite and even if it is finite, there is no guarantee that the physical argument will hold. We show that the physical interpretation does go through for the special case of a birth-and-death process with a finite value of Kemeny's constant. Keywords: Kemeny's constant; discrete-time Markov chains; continuous-time Markov chains; passage times; deviation matrix.

We revisit the shift technique applied to Quasi-Birth and Death (QBD) processes He et al. (2001) [13] in functional form by bringing the attention to the existence and properties of canonical factorizations. To this regard, we prove new results concerning the solutions of the quadratic matrix equations associated with the QBD. These results find applications to the solution of the Poisson equation for QBDs.

Let $a(z)=\sum_{i\in\mathbb Z}a_iz^i$ be a complex valued continuous function, defined for $|z|=1$, such that $\sum_{i=-\infty}^{+\infty}|ia_i

We consider the Poisson equation $(I-P)\boldsymbol{u}=\boldsymbol{g}$, where $P$ is the transition matrix of a Quasi-Birth-and-Death (QBD) process with infinitely many levels, $\bm g$ is a given infinite dimensional vector and $\bm u$ is the unknown. Our main result is to provide the general solution of this equation. To this purpose we use the block tridiagonal and block Toeplitz structure of the matrix $P$ to obtain a set of matrix difference equations, which are solved by constructing suitable resolvent triples.

We consider the multilinear pagerank problem studied in [Gleich, Lim and Yu, Multilinear Pagerank, 2015], which is a system of quadratic equations with stochasticity and nonnegativity constraints. We use the theory of quadratic vector equations to prove several properties of its solutions and suggest new numerical algorithms. In particular, we prove the existence of a certain minimal solution, which does not always coincide with the stochastic one that is required by the problem. We use an interpretation of the solution as a Perron eigenvector to devise new fixed-point algorithms for its computation, and pair them with a homotopy continuation strategy. The resulting numerical method is more reliable than the existing alternatives, being able to solve a larger number of problems.

The cyclic reduction algorithm is specialized to palindromic matrix polynomials and a complete analysis of applicability and convergence is provided. The resulting iteration is then related to other algorithms as the evaluation/interpolation at the roots of unity of a certain Laurent matrix polynomial, the trapezoidal rule for a certain integral and an algorithm based on the finite sections of a tridiagonal block Toeplitz matrix.

The Erlangian approximation of Markovian fluid queues leads to the problem of computing the matrix exponential of a subgenerator having a block-triangular, block-Toeplitz structure. To this end, we propose some algorithms which exploit the Toeplitz structure and the properties of generators. Such algorithms allow us to compute the exponential of very large matrices, which would otherwise be untreatable with standard methods. We also prove interesting decay properties of the exponential of a generator having a block-triangular, block-Toeplitz structure.

Summary Matrix equations of the kind A1X2+A0X+A−1=X, where both the matrix coefficients and the unknown are semi-infinite matrices belonging to a Banach algebra, are considered. These equations, where coefficients are quasi-Toeplitz matrices, are encountered in certain quasi-birth–death processes as the tandem Jackson queue or in any other processes that can be modeled as a reflecting random walk in the quarter plane. We provide a numerical framework for approximating the minimal nonnegative solution of these equations that relies on semi-infinite quasi-Toeplitz matrix arithmetic. In particular, we show that the algorithm of cyclic reduction can be effectively applied and can approximate the infinite-dimensional solutions with quadratic convergence at a cost that is comparable to that of the finite case. This way, we may compute a finite approximation of the sought solution and of the invariant probability measure of the associated quasi-birth–death process, within a given accuracy. Numerical experiments, performed on a collection of benchmarks, confirm the theoretical analysis.