Numerical Linear Algebra with Applications

Items from 1 to 12 out of 12 results

article

On the solution of a quadratic vector equation arising in Markovian Binary Trees

Dario A. Bini, Beatrice Meini, Federico Poloni

Numerical Linear Algebra with Applications > 18 > 6 > 981 - 991

We present some advances, both from a theoretical and a computational point of view, on a quadratic vector equation (QVE) arising in Markovian Binary Trees. Concerning the theoretical advances, some irreducibility assumptions are relaxed, and the minimality of the solution of the QVE is expressed in terms of properties of the Jacobian of a suitable function. From the computational point of view, we...

article

Restricted additive Schwarz methods for Markov chains

Michele Benzi, Verena Kuhlemann

Numerical Linear Algebra with Applications > 18 > 6 > 1011 - 1029

The restricted additive Schwarz method is adapted to the problem of computing the stationary probability distribution vector of large, sparse, and irreducible stochastic matrices. Inexact and two‐level variants are also considered as well as acceleration by Krylov subspace methods. The convergence properties are analyzed, and extensive numerical experiments aimed at assessing the effect of varying...

article

Fast multilevel methods for Markov chains

Hans De Sterck, Killian Miller, Eran Treister, Irad Yavneh

Numerical Linear Algebra with Applications > 18 > 6 > 961 - 980

This paper describes multilevel methods for the calculation of the stationary probability vector of large, sparse, irreducible Markov chains. In particular, several recently proposed significant improvements to the multilevel aggregation method of Horton and Leutenegger are described and compared. Furthermore, we propose a very simple improvement of that method using an over‐correction mechanism....

article

Bounding the equilibrium distribution of Markov population models

Tuǧrul Dayar, Holger Hermanns, David Spieler, Verena Wolf

Numerical Linear Algebra with Applications > 18 > 6 > 931 - 946

We propose a bounding technique for the equilibrium probability distribution of continuous‐time Markov chains with population structure and infinite state space. We use Lyapunov functions to determine a finite set of states that contains most of the equilibrium probability mass. Then we apply a refinement scheme based on stochastic complementation to derive lower and upper bounds on the equilibrium...

article

Perturbation analysis of continuous‐time absorbing Markov chains

Hal Caswell

Numerical Linear Algebra with Applications > 18 > 6 > 901 - 917

The behavior of Markov chains depends on the transition intensities or probabilities; in applications, these transitions are often written as functions of parameters. In this paper, matrix calculus is used to provide the sensitivities and elasticities of the behavior of continuous time‐absorbing Markov chains to arbitrary parameters, which could include the transition intensities themselves or parameters...

article

A Markov‐modulated fluid flow queueing model under D‐policy

Jung Woo Baek, Ho Woo Lee, Se Won Lee, Soohan Ahn

Numerical Linear Algebra with Applications > 18 > 6 > 993 - 1010

We consider a Markov‐modulated fluid flow queueing model under D‐policy. As soon as the fluid level reaches zero, the server becomes idle. During the idle period, fluid arrives from outside according to an underlying continuous time Markov chain (UMC) and the idle server does not process the fluid. We consider two increase patterns of fluid during the idle period: vertical increase (Type‐V) and linear...

article

Physiology and pathology of iterative aggregation–disaggregation methods

I. Pultarová, I. Marek

Numerical Linear Algebra with Applications > 18 > 6 > 1051 - 1065

We found characteristics that can help us predict the convergence or divergence of iterative aggregation–disaggregation methods. We provided two results for spectral radii of asymptotic error propagation matrices: (i) the spectral radius is bounded by unity for symmetric Markov chains and (ii) the spectral radius can be arbitrarily large for a certain class of sparse Markov chains. Surprisingly, permuting...

article

Numerical Solution of Markov Chains

Michele Benzi

Numerical Linear Algebra with Applications > 18 > 6 > 897 - 900

This special issue contains a selection of papers from the Sixth International Workshop on the Numerical Solution of Markov Chains, held in Williamsburg, Virginia on September 16–17, 2010. The papers cover a broad range of topics including perturbation theory for absorbing chains, bounding techniques, steady‐state and transient solution methods, multilevel algorithms, preconditioning, and applications...

article

Revisiting the matrix‐free solution of Markov regenerative processes

Elvio Gilberto Amparore, Susanna Donatelli

Numerical Linear Algebra with Applications > 18 > 6 > 1067 - 1083

In this paper, we revisit the steady‐state solution method for Markov Regenerative Processes (MRP) proposed in the work by German. This method solves the embedded Markov chain P of the MRP without storing the matrix P explicitly. We address three issues left open in German's Work: 1) the solution method is restricted to Power method; 2) it has been defined only for ergodic MRPs; and 3) no preconditioning...

article

Iterative component‐wise bounds for the steady‐state distribution of a Markov chain

Ana Bušić, Jean‐Michel Fourneau

Numerical Linear Algebra with Applications > 18 > 6 > 1031 - 1049

We prove new iterative algorithms to provide component‐wise bounds of the steady‐state distribution of an irreducible and aperiodic Markov chain. These bounds are based on simple properties of (max,+) and (min,+) sequences. The bounds are improved at each iteration. Thus, we have a clear trade‐off between tightness of the bounds (some algorithms converge to the true solution) and computation times...

article

Bounding reward measures of Markov models using the Markov decision processes

Peter Buchholz

Numerical Linear Algebra with Applications > 18 > 6 > 919 - 930

For a Markov reward process, where upper and lower bounds for the transition rates and rewards are known, a new approach to bound the expected reward is presented. Based on a previous paper where sharp bounds have been defined for the problem, but only an inefficient and unstable algorithm is proposed, this paper presents algorithms to compute the bounds by interpreting the problem as a Markov Decision...

article

Inexact uniformization and GMRES methods for large Markov chains

Roger B. Sidje

Numerical Linear Algebra with Applications > 18 > 6 > 947 - 960

Inexact algorithms allow certain operations (typically matrix–vector products or certain function evaluations) to be performed inexactly, either out of necessity or deliberately, in view of trading accuracy for speed. We review recent findings that show the impact of the inexact approach in the uniformization and generalized minimal residual (GMRES) methods when computing the transient, stationary,...

Filter options

Number:
6
Volume:
18

Publication date

Set your own date range

Keywords

PRECONDITIONING (3)
BOUNDS (2)
ITERATIVE METHODS (2)
MARKOV CHAIN (2)
MARKOV CHAINS (2)
ABSORBING MARKOV CHAINS (1)
ALGORITHMS (1)
APPLIED PROBABILITY (1)
BRANCHING PROCESS (1)
CONTINUOUS‐TIME MARKOV CHAIN (1)
DEMOGRAPHY (1)
DISEASE PROGRESSION MODELS (1)
D‐POLICY (1)
EQUILIBRIUM PROBABILITY DISTRIBUTION (1)
FILL‐IN AVOIDANCE (1)
FIXED‐POINT ITERATION (1)
FUNDAMENTAL MATRIX (1)
GEOMETRIC BOUNDS (1)
INEXACT GMRES (1)
INEXACT UNIFORMIZATION (1)
ITERATIVE AGGREGATION–DISAGGREGATION METHOD (1)
KRYLOV METHODS (1)
LYAPUNOV FUNCTION (1)
MARKOV CHAINS GMRES (1)
MARKOV DECISION PROCESSES (1)
MARKOV PROCESSES (1)
MARKOV REGENERATIVE PROCESS (1)
MARKOVIAN ARRIVAL PROCESS (1)
MARKOVIAN BINARY TREE (1)
MARKOV‐MODULATED FLUIDFLOW (1)
MATRIX CALCULUS (1)
MATRIX FREE (1)
MMFF (1)
MULTIGRID (1)
MULTILEVEL AGGREGATION (1)
MULTILEVEL ALGORITHMS (1)
NEWTON METHOD (1)
OVER‐CORRECTION (1)
PERRON VECTOR (1)
PERTURBATION ANALYSIS (1)
RELAXED MATRIX–VECTOR PRODUCT (1)
SCHWARZ METHODS (1)
SERVER CONTROLPOLICY (1)
SORTING OF STATES (1)
STATIONARY ANALYSIS (1)
STATIONARY PROBABILITY DISTRIBUTION VECTOR (1)
STATIONARY PROBABILITY VECTOR (1)
STEADY STATE DISTRIBUTION (1)
STOCHASTIC COMPLEMENT (1)
STOCHASTIC MATRIX (1)
more

INFONA - science communication portal

Numerical Linear Algebra with Applications

Add recipient

Sending message cancelled

Are you sure you want to cancel sending this message?

Send message

Filter options

Publication date

Date range setting

Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.

Keywords

Reporting an error / abuse

Sending the report failed

Accessibility options