Department of Mathematics
University of Pisa

 Numerical Analysis  and Computational Mathematics

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 Toeplitz-like 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 2-nd Annual ACM Symposium on Parallel Algorithms and Architectures, Crete, 1990, 220-223.
• D.A. Bini, V. Pan, Parallel complexity of tridiagonal symmetric eigenvalue problem, Proc. 2-nd Ann. ACM-SIAM Symp.  on Discrete Algorithms, 384-393, 1990.
• D.A. Bini, L. Gemignani, V. Pan,Improved parallel computations with matrices and polynomials, Proc. 18-th Intern. Symposium on Automata, Languages and Programming, Lectures Notes in Computer Science, 510, 520-531, Springer  1991.
• D.A. Bini, V. Pan, On the evaluation of the eigenvalues of a banded Toeplitz block matrix, J. of Complexity, 7, 408-424, 1991.
• D.A. Bini, F. Di Benedetto, An observation on certain spectral properties of Toeplitz matrices, Calcolo 28, 37-43, 1991.
• D.A. Bini, V. Pan, Practical improvement of the divide-and-conquer eigenvalue algorithms, Computing 48, 109-123, 1992.
• D.A. Bini, P. Favati, On a Matrix algebra related to the Hartley transform, SIAM J. Matrix Analysis Appl., 14,2, 500-507, 1993.
• D.A. Bini, V. Pan, Improved parallel computations with Toeplitz-like and Hankel-like matrices, Linear Algebra Appl., 188,189, 3--29, 1993.
• D.A. Bini, E. Bozzo, Fast discrete transform by means of eigenpolynomials, Computers & Mathematics (with Applications), 26,9, 35--52, 1993.
• D.A. Bini, L. Gemignani, Iteration schemes for the divide-and-conquer eigenvalue solver, Numer. Math. 67, 403--425, 1994.
• 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, Exploiting the Toeplitz structure in certain queueing problems. Calcolo, 33:289--305, 1996.
• D.A. Bini, F. Di Benedetto, Toeplitz matrices: structures, algorithms and applications. Calcolo, 33: 1--10, 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:1-16, 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.
• 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) 119-123.
• L. Gemignani , Solving Hankel Systems over the Integers, J. Symbolic Computation 18 (1994) 403-425.
• L. Gemignani , Schur Complements of Bezoutians with Applications to the Inversion of Block Hankel and Toeplitz Matrices , Linear Algebra Appl. 253 (1997) 39-59.
• L. Gemignani , A Fast Algorithm for Generalized Hankel Matrices Arising in Finite Moment Problems , Linear Algebra Appl. 267 (1997) 41-52.
• 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, TR-97/08, Computer Science Department, University of Pisa, (1997). To appear in Linear Algebra Appl.
• D. A. Bini, L. Gemignani, Fast Fraction-Free Triangularization of Bezoutians with Applications to Sub-Resultant Chain Computation, TR-97/15,Computer Science Department, University of Pisa, (1997). To appear in Linear Algebra Appl.
• L. Gemignani , Fast QR Factorization of Low-Rank Changes of Vandermonde-like Matrices. To appear on CALCOLO.

 

Conferences:

Cortona 2000: "Structured Matrices: Analysis, Algorithms and Applications"