Department of Mathematics
University of Pisa

 Numerical Analysis  and Computational Mathematics

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/1-type and G/M1-type 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, 30395--420, 1993.
• D.A. Bini, B. Meini, On cyclic reduction applied to a class of Toeplitz-like matrices arising in queueing problems. In W. J. Stewart, editor, Computations with Markov Chains, pages 21--38. 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:906--926, 1996.
• D.A. Bini, B. Meini, Exploiting the Toeplitz structure in certain queueing problems. Calcolo, 33:289--305, 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:127--151, 1997.
• B. Meini, An improved  FFT-based version of Ramaswami's formula. Comm. Statist. Stochastic Models, 13:223-238, 1997.
• D.A. Bini, B. Meini, Improved cyclic reduction for solving queueing problems.  Numerical Algorithms, 15:57--74, 1997.
• B. Meini, New convergence results on functional iteration techniques for the numerical solution of M/G/1 type Markov chains. Numerische Mathematik, 78:39--58, 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: 479-496, 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:1-16, 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:653-667, 1998.
• D.A. Bini, B. Meini, Using displacement structure for solving Non-Skip-Free 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 17-37.
• 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 44-54.
• P. Favati,  B. Meini, Relaxed functional iteration techniques for the numerical solution of M/G/1 type Markov chains. BIT Numerical Mathematics, 38:510-526, 1998.
• B. Meini, Solving QBD problems: the cyclic reduction algorithm versus the invariant subspace method. Advances in Performance Analysis, 1:215-225, 1998.
• P. Favati, B. Meini, On functional iteration methods for solving nonlinear matrix equations arising in queueing problems, IMA Journal of Numerical Analysis, 19:39-49, 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.

Conferences:

Third International Conference on Matrix Analytic Methods, Leuven, July 2000.

Related Links
Matrix Analytic Home Page