Solving nonlinear matrix equations arising in tree-like stochastic processes.
The authors consider the problem of computing a nonsingular matrix \(X\) which solves the nonlinear matrix equation \[ X+ \sum_{1\leq i\leq d} A_i X^{-1} D_i= C,\tag{1} \] where \(C\), \(A_i\), \(D_i\in \mathbb{R}^{m\times m}\), \(i= 1,\dots, d\), are given matrices. It is assumed that 1) \(C= B-I\), and \(B\) is sub-stochastic; 2) \(A\) and \(D\) have nonnegative entries; 3) the matrices \(I+ C+ D+ A_1+\cdots + A_d\), \(I= 1,\dots,d\) are stochastic. This problem arises in the analyses of certain discrete-time bivariate Markov processes called tree-like processes. The computation of the stationary distribution of the Markov process can be reduced to solving (1). In this paper efficient algorithms for solving (1) are derived. First the rapidity of the natural fixed point iteration is anlyzed using the Perron-Frobenius theory of nonnegative matrices. Then two new improved methods are introduced. The first one consists in generating a sequence of approximations obtained by solving at each step quadratic matrix equations. The second method is based on Newton's scheme and is quadratically convergent. To compare the three methods under consideration these methods are tested on a service problem.
- On the numerical solution of a nonlinear matrix equation in Markov chains
- Nonlinear matrix equations and structured linear algebra
- Nonlinear Matrix Equations in Applied Probability—Solution Techniques and Open Problems
- Newton's iteration for non-linear equations in Markov chains
- Equilibrium analysis of skip free markov chains: nonlinear matrix equations
- A generalization of the matrix M/G/l paradigm for Markov chains with a tree structure
- A logarithmic reduction algorithm for quasi-birth-death processes
- Calculating the equilibrium distribution in level dependent quasi-birth-and-death processes
- scientific article; zbMATH DE number 3736680 (Why is no real title available?)
- scientific article; zbMATH DE number 3215568 (Why is no real title available?)
- scientific article; zbMATH DE number 3381785 (Why is no real title available?)
- scientific article; zbMATH DE number 967331 (Why is no real title available?)
- Improved cyclic reduction for solving queueing problems
- Introduction to Matrix Analytic Methods in Stochastic Modeling
- Matrix product-form solutions for Markov chains with a tree structure
- New convergence results on functional iteration techniques for the numerical solution of M/G/1 type Markov chains
- Newton's iteration for non-linear equations in Markov chains
- On the Solution of a Nonlinear Matrix Equation Arising in Queueing Problems
- Solution of the Sylvester matrix equation AXB T + CXD T = E
- STABILITY AND PERFORMANCE OF STACK ALGORITHMS FOR RANDOM ACCESS COMMUNICATION MODELED AS A TREE STRUCTURED QBD MARKOV CHAIN
- The \(MMAP[K]/PH[K]/1\) queues with a last-come-first-served preemptive service discipline
- The quasi-birth-death type markov chain with a tree structure
- On the link between Markovian trees and tree-structured Markov chains
- On the numerical solution of a nonlinear matrix equation in Markov chains
- On preemptive-repeat LIFO queues
- Quadratic vector equations
- Solving two generalized nonlinear matrix equations
- Fitting correlated arrival and service times and related queueing performance
- Some iterative methods for the largest positive definite solution to a class of nonlinear matrix equation
- Throughput and delay analysis of an opportunistic tree algorithm
- The \(M/G/1\)-type Markov chain with restricted transitions and its application to queues with batch arrivals
- Matrix structures in queuing models
- Solving nonlinear matrix equation in credit risk by using iterative methods
- Nonlinear Matrix Equations in Applied Probability—Solution Techniques and Open Problems
- Tree Structured QBD Markov Chains and Tree‐Like QBD Processes
- Convergence analysis of some iterative methods for a nonlinear matrix equation
- A polynomial time algorithm for computing extinction probabilities of multitype branching processes
- Richardson method and totally nonnegative linear systems
- On the Hermitian positive defnite solution of the nonlinear matrix equation \(X + A^*X ^{-1} A + B^*X ^{-1} B = I\)
- Nonlinear matrix equations and structured linear algebra
- Analyzing priority queues with 3 classes using tree-like processes
- QBD Markov chains on binomial-like trees and its application to multilevel feedback queues
- On the Hermitian positive definite solution of the nonlinear matrix equation
This page was built for publication: Solving nonlinear matrix equations arising in tree-like stochastic processes.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1874657)
