Numerical Analysis
and Computational Mathematics
Structured Matrices and Toeplitz
Computations
The research in this field concerns the analysis
of structured matrices under different point of views. The main goal is
to investigate properties related to structures that can be used for the
design of efficient algorithm for the solution of different related problems.
Numerical computation of eigenvalues of large matrices and solution of
linear systems with dense structured or sparse matrices are the main problems
that we consider. Among the main investigated structures we are interested
to Toeplitz and Toeplitzlike matrices, Hankel and Bezout matrices, or
more generally to classes of matrices associated with a displacement operator.
Collaborations:
F. Di Benedetto, E. Bozzo, V. Pan, S. Serra,
P. Tilli, E. Tyrtyshnikov
Papers:

D.A. Bini, F. Di Benedetto, Solving the generalized eigenvalue problem
for rational Toeplitz matrices,
SIAM J. Matrix Anal. Appl. 11,
1990.

D.A. Bini, F. Di Benedetto, A new preconditioner for the parallel solution
of positive definite Toeplitz systems, Proceedings of 2nd Annual ACM
Symposium on Parallel Algorithms and Architectures, Crete, 1990, 220223.

D.A. Bini, V. Pan, Parallel complexity of tridiagonal symmetric eigenvalue
problem, Proc. 2nd Ann. ACMSIAM Symp. on Discrete Algorithms,
384393, 1990.

D.A. Bini, L. Gemignani, V. Pan,Improved parallel computations with matrices
and polynomials, Proc. 18th Intern. Symposium on Automata, Languages
and Programming, Lectures Notes in Computer Science, 510, 520531,
Springer 1991.

D.A. Bini, V. Pan, On the evaluation of the eigenvalues of a banded Toeplitz
block matrix, J. of Complexity, 7, 408424, 1991.

D.A. Bini, F. Di Benedetto, An observation on certain spectral properties
of Toeplitz matrices, Calcolo
28, 3743, 1991.

D.A. Bini, V. Pan, Practical improvement of the divideandconquer eigenvalue
algorithms,
Computing
48, 109123, 1992.

D.A. Bini, P. Favati, On a Matrix algebra related to the Hartley transform,
SIAM J. Matrix Analysis Appl., 14,2, 500507, 1993.

D.A. Bini, V. Pan, Improved parallel computations with Toeplitzlike and
Hankellike matrices,
Linear Algebra Appl., 188,189, 329,
1993.

D.A. Bini, E. Bozzo, Fast discrete transform by means of eigenpolynomials,
Computers & Mathematics (with Applications), 26,9, 3552,
1993.

D.A. Bini, L. Gemignani, Iteration schemes for the divideandconquer eigenvalue
solver, Numer. Math. 67, 403425, 1994.

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,
Exploiting the Toeplitz
structure in certain queueing problems. Calcolo, 33:289305,
1996.

D.A. Bini, F. Di Benedetto, Toeplitz matrices: structures, algorithms and
applications. Calcolo,
33: 110, 1996.

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.

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.

D.A. Bini, B. Meini,
Effective methods for solving
banded Toeplitz systems, to appear in SIAM J. Matrix
Anal. Appl..

D.A. Bini, L. Gemignani, B. Meini,
Factorization
of analytic functions by means of Koenig's theorem and Toeplitz computations,
Technical report, Dipartimento di Informatica, Universita' di Pisa, 1998.

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.

D.A. Bini, M. Del Corso, G. Manzini, L. Margara, Inversion of Circulant
Matrices over $\Z_m$, 25th International Colloquium on
Automata Languages and Programming (ICALP '98), to appear in Mathematics
of Computations.

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.

D.A. Bini, B. Meini, Solving block banded block Toeplitz systems with banded
Toeplitz blocks, Proceedings SPIE Conference, Denver, 1999.

L. Gemignani , Fast Inversion of Hankel and Toeplitz Matrices , Information
Processing Letters 41 (1992) 119123.

L. Gemignani , Solving Hankel Systems over the Integers, J. Symbolic Computation
18 (1994) 403425.

L. Gemignani , Schur Complements of Bezoutians with Applications to the
Inversion of Block Hankel and Toeplitz Matrices , Linear Algebra Appl.
253 (1997) 3959.

L. Gemignani , A Fast Algorithm for Generalized Hankel Matrices Arising
in Finite Moment Problems , Linear Algebra Appl. 267 (1997) 4152.

L. Gemignani, A Hybrid Approach to the Computation of the Inertia of a
Parametric Family of Bezoutians with Applications to some stability problems
for bivariate polynomials, TR97/08, Computer Science Department, University
of Pisa, (1997). To appear in Linear Algebra Appl.

D. A. Bini, L. Gemignani, Fast FractionFree Triangularization of Bezoutians
with Applications to SubResultant Chain Computation, TR97/15,Computer
Science Department, University of Pisa, (1997). To appear in Linear Algebra
Appl.

L. Gemignani , Fast QR Factorization of LowRank Changes of Vandermondelike
Matrices. To appear on CALCOLO.
Software:
Cyclic reduction for banded Toeplitz
matrices
Cyclic reduction for banded
symmetric Toeplitz matrices
Conferences:
Cortona 2000: "Structured Matrices: Analysis, Algorithms and Applications"