Solving nonlinear matrix equations arising in tree-like stochastic processes.
type: Item
instance of: scholarly article
title: Solving nonlinear matrix equations arising in tree-like stochastic processes.
zbMATH Open document ID: 1044.65034
DOI: 10.1016/S0024-3795(02)00593-1
author: Dario A. Bini
author: Guy Latouche
author: B. Meini
published in: Linear Algebra and its Applications
publication date: 2003-05-25T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 65F30
Mathematics Subject Classification ID: 15A24
Mathematics Subject Classification ID: 65C50
Mathematics Subject Classification ID: 60J05
zbMATH DE Number: 1915797
zbMATH Keywords: matrix equation
zbMATH Keywords: tree-like stochastic processes
zbMATH Keywords: fixed point iteration
zbMATH Keywords: Newton's iteration
zbMATH Keywords: cyclic reduction
zbMATH Keywords: discrete-time bivariate Markov processes
zbMATH Keywords: algorithms
reviewed by: Otu Vaarmann
describes a project that uses: na12
MaRDI profile type: Publication
cites work: On the Solution of a Nonlinear Matrix Equation Arising in Queueing Problems
cites work: Improved cyclic reduction for solving queueing problems
cites work: Calculating the equilibrium distribution in level dependent quasi-birth-and-death processes
cites work: Q5690366
cites work: Solution of the Sylvester matrix equation AXB T + CXD T = E
cites work: The \(MMAP[K]/PH[K]/1\) queues with a last-come-first-served preemptive service discipline
cites work: A logarithmic reduction algorithm for quasi-birth-death processes
cites work: Newton's iteration for non-linear equations in Markov chains
cites work: Introduction to Matrix Analytic Methods in Stochastic Modeling
cites work: New convergence results on functional iteration techniques for the numerical solution of M/G/1 type Markov chains
cites work: Q3923308
cites work: Q5652137
cites work: A generalization of the matrix M/G/l paradigm for Markov chains with a tree structure
cites work: STABILITY AND PERFORMANCE OF STACK ALGORITHMS FOR RANDOM ACCESS COMMUNICATION MODELED AS A TREE STRUCTURED QBD MARKOV CHAIN
cites work: Q5342712
cites work: The quasi-birth-death type markov chain with a tree structure
cites work: Matrix product-form solutions for Markov chains with a tree structure
description: scientific article; zbMATH DE number 1915797