Numerical Analysis
and Computational Mathematics
Numerical Methods for Markov Chains
The research in this field concerns the design
and analysis of numerical methods for solving Markov chains. Particular
attention is devoted to structures arising from the modeling of problems
in queueing theory. The main problems investigated are related to the solution
of M/G/1type and G/M1type Markov chains, QBD problems, PH/PH/1 queues.
Efficiency of the algorithms in terms of their complexity and stability
is pursued.
Collaborations:
S.
Chakravarthy, P. Favati, U. Krieger, G. Latouche, V. Ramaswami, N.
Rhee
Papers:

D.A. Bini, B. Meini, Solving certain queueing problems modelled by Toeplitz
matrices. Calcolo,
30395420, 1993.

D.A. Bini, B. Meini, On cyclic reduction
applied to a class of Toeplitzlike matrices arising in queueing problems.
In W. J. Stewart, editor, Computations with Markov Chains, pages
2138. Kluwer Academic Publisher, Boston, 1995.

D.A. Bini, B. Meini, On the solution
of a nonlinear matrix equation arising in queueing problems. SIAM
J. Matrix Anal. Appl. 17:906926, 1996.

D.A. Bini, B. Meini, Exploiting
the Toeplitz structure in certain queueing problems. Calcolo,
33:289305, 1996.

G. Anastasi, L. Lenzini, B. Meini, Performance evaluation of a worst case
model of the MetaRing MAC protocol with global fairness. Performance
Evaluation, 29:127151, 1997.

B. Meini, An improved FFTbased
version of Ramaswami's formula. Comm. Statist. Stochastic Models,
13:223238, 1997.

D.A. Bini, B. Meini, Improved cyclic
reduction for solving queueing problems. Numerical Algorithms,
15:5774, 1997.

B. Meini, New convergence results on
functional iteration techniques for the numerical solution of M/G/1 type
Markov chains.
Numerische Mathematik, 78:3958, 1997.

D.A. Bini, B. Meini, Fast algorithms for structured problems with applications
to Markov chains and queueing models, in Fast Reliable Methods
for Matrices with Structure, T. Kailath and A. Sayed Editors,
SIAM Volumes, to appear.

B. Meini, Solving M/G/1 type Markov chains:
recent advances and applications. Comm. Statist. Stochastic Models,
14:
479496, 1998.

D.A. Bini, B. Meini, Inverting block
Toeplitz matrices in block Hessenberg form by means of displacement operators:
application to queueing problems.Linear Algebra Appl., 272:116,
1998.

L Lenzini, B. Meini, E. Mingozzi, An efficient numerical method for
performance analysis of contention MAC protocols: a case study (PRMA++).
IEEE
Journal on Selected Areas in Communications, 16:653667, 1998.

D.A. Bini, B. Meini, Using displacement
structure for solving NonSkipFree M/G/1 type Markov chains. In Advances
in Matrix Analytic Methods for Stochastic Models  Proceedings of the
2nd international conference on matrix analytic methods}, A. Alfa and S.
Chakravarthy Eds., 1998, Notable Publications Inc, NJ, pages 1737.

P. Favati, B. Meini, On functional
iteration methods for solving M/G/1 type Markov chains. In Advances
in Matrix Analytic Methods for Stochastic Models  Proceedings of the
2nd international conference on matrix analytic methods, A. Alfa and S.
Chakravarthy Eds., 1998, Notable Publications Inc, NJ, pages 4454.

P. Favati, B. Meini, Relaxed
functional iteration techniques for the numerical solution of M/G/1 type
Markov chains.
BIT Numerical Mathematics, 38:510526, 1998.

B. Meini, Solving QBD problems: the
cyclic reduction algorithm versus the invariant subspace method. Advances
in Performance Analysis, 1:215225, 1998.

P. Favati, B. Meini, On functional
iteration methods for solving nonlinear matrix equations arising in queueing
problems,
IMA Journal of Numerical Analysis, 19:3949, 1999.

D.A. Bini, S. Chakravarthy, B. Meini, A
New Algorithm for the Design of Capacity Service Units, in Proceedings
of the Third international Conference on the Numerical Solution of Markov
Chains, Saragoza, Spain, sept. 1999.

P. Favati, B. Meini, Solving certain
queueing problems by means of regular splittings, to appear in
Appl. Math, Letters.

B. Meini, Fast algorithms for the numerical solution of structured
Markov chains, PhD Thesis, Dottorato di Ricerca in Matematica, Universita'
di Pisa, 1998. <dvi> <postscript>

D.A. Bini, S. Chakravarthy, B. Meini, Control of the BMAP/PH/1/K queue
with group services, submitted for publication, 1999.

D. A. Bini, B. Meini, V. Ramaswami, Analyzing M/G/1 paradigms through
QBDs: the role of the block structure in computing the matrix G, submitted
for publication, 1999.
Software:
Cyclic Reduction for QBD problems.
Pointwise Cyclic Reduction for
M/G/1 Matrices.
Doubling Method for M/G/1 Matrices
Nonskipfree M/G/1 Matrices
PH/PH/1/N Queues
Conferences:
Third International Conference
on Matrix Analytic Methods, Leuven, July 2000.
Related Links
Matrix Analytic
Home Page