Numerical Analysis

The group of Numerical Analysis covers research topics from Numerical Linear Algebra, such as low-rank approximation of matrices and tensors, the numerical solution of matrix equations, the computation of matrix functions, polynomial root-finding, and the theory of circuits. Details on these topics can be found below.
The group works in close collaboration with the Numerical Analysis group at the Department of Computer Science of the University of Pisa (G. Del Corso, L. Gemignani, F. Poloni), and at Scuola Normale Superiore (M. Benzi).

The group runs a Seminar Series: further information can be found at this link.

Research Topics

Low-rank Approximation and Structured Matrices

This research area deal with the problem of efficiently finding low-rank factorization of matrices $A$ in the form $$A \approx UV^T,$$ where $U,V$ are tall and skinny matrices. In most cases of interest, one assumes to either be able to evaluate $X \mapsto AX$ and $Y \mapsto A^T Y$ or to sample selected entries of $A$ at a reduced cost. Several strategies may be adopted for retrieving matrices $U,V$ such as randomized linear algebra methods, or cross-approximation techniques.

A natural evolution of this idea is to consider structured matrices, which are – in general – not low-rank, but may have low-rank blocks, or obtained as low-rank perturbations of particularly structured matrices. The aim is to represent such matrices using $\mathcal O(n)$ or even $O(1)$ storage and perform operations with a similar complexity (up to logarithmic factors in the dimension).

In particular, the following structures are considered:

  • Rank-structured matrices: Matrices with off-diagonal blocks of low-rank (HODLR), which may be efficiently representable using hierarchically structured bases (HSS).
  • Low-rank perturbations of Toeplitz matrices: matrices with this structure form an algebra, which has important applications in the study of queues and Markov chains. See also the section on the numerical solution of Markov chains below. Matrices in this class can often be represented with a storage that is independent of the dimensions, enabling the numerical study of infinite and semi-infinite matrices.

For matrices in this form, efficient arithmetic operations are available. MATLAB toolboxes for handling such matrices are available (see hm-toolbox for rank-structured matrices and cqt-toolbox for quasi-Toeplitz ones).

Members
Dario Andrea Bini
dario.bini@unipi.it
Stefano Massei
stefano.massei@unipi.it
Beatrice Meini
beatrice.meini@unipi.it
Leonardo Robol
leonardo.robol@unipi.it
Collaborators
Bruno Iannazzo (Università degli Studi di Perugia)
Daniel Kressner (École Polytechnique Fédérale de Lausanne (EPFL))
Numerical Methods for Polynomial Root-Finding

This research area concerns the design, analysis, and implementation of numerical algorithms for the guaranteed approximation of the roots of a polynomial up to any number of digits. The motivation for this kind of numerical tool comes mainly from computer algebra systems where the symbolic treatment of polynomial systems leads to solving polynomials with very large degrees and with huge coefficients (exact or approximate). Other motivations come from problems in combinatorics, problems in dynamics of holomorphic functions, and problems in celestial mechanics.

Various numerical methods and tools are available to solve this problem and a huge literature exists. Among the classical choices, there are matrix methods, like the QR iteration applied to companion matrices, and functional iteration techniques (often based on the Newton method). In the latter class, an important method is Aberth’s iteration, a global version of the Newton iteration, that allows approximating all the roots of $p(x)$ simultaneously.

In the year 2000, we have produced the package MPSolve in the framework of the European project FRISCO. This package has been improved recently and is the fastest available software for polynomial root-finding available so far. Just to give an example, the software can solve the Mandelbrot polynomials of degree $2^{20}$ in a few hours over a dual Xeon server. Polynomials of degree $2^{21}$ and $2^{22}$ can be solved in a few days and in a few weeks, respectively. Mandelbrot polynomials have zeros that coincide with the cycles of a given length in the Mandelbrot iteration. These zeros are severely ill-conditioned.

Members
Dario Andrea Bini
dario.bini@unipi.it
Giuseppe Fiorentino
giuseppe.fiorentino@unipi.it
Leonardo Robol
leonardo.robol@unipi.it
Collaborators
Matrix Polynomials, Companion Linearizations, and Quasiseparable Matrices

An $m \times m$ matrix polynomial $A(x)$ is a polynomial in the variable $x$ whose coefficients are matrices. Matrix polynomials are encountered in many applications; an important computational problem is to compute the values of $x$ such that $\det(A(x)) = 0$. This problem, which is related to the analysis of eigenfrequencies of complex dynamical systems, is customarily reduced to solving a generalized linear eigenvalue problem of the kind $Hv = \lambda Kv$ where the $nm \times nm$ pencil $H -\lambda K$ provides a linearization of $A(x)$.

Here, the research concerns the design and analysis of linearizations that have nice computational properties and keep the condition number of the eigenvalues as small as possible. The literature in this area is very rich with many theoretical and computational results.

One nice feature is that the known linearization shares the quasiseparable property. That is, for any, $\lambda$ the submatrices of $H – \lambda K$ which are contained in the upper or in the lower triangular part of the matrix have a low rank. This property has been investigated in a different context and is exploitable to a certain extent for designing highly efficient algorithms.

In this research, we aim both to determine new and more effective linearizations and to design efficient algorithms for solving the linear pencil by relying on the quasiseparable structure. We also aim to combine analytic techniques, like the Aberth iteration, and matrix techniques to improve the efficiency of solution algorithms. Other related researches concern the localization of the eigenvalues of matrix polynomials.

Members
Dario Andrea Bini
dario.bini@unipi.it
Paola Boito
paola.boito@unipi.it
Leonardo Robol
leonardo.robol@unipi.it
Collaborators
Gianna M. Del Corso (Università di Pisa)
Yuli Eidelman (Tel Aviv University)
Luca Gemignani (Università di Pisa)
Israel Gohberg (Tel Aviv University)
Vanni Noferini (Aalto University)
Victor Y. Pan (Lehman College - CUNY)
Federico Giovanni Poloni (Università di Pisa)
federico.poloni@unipi.it
Meisam Sharify (Isfahan University of Technology)
Françoise Tisseur (University of Manchester)
Raf Vandebril (Katholieke Universiteit Leuven)
Matrix Equations and Matrix Functions

Many problems from the real world and from Scientific Computing are modeled by matrix equations or by matrix functions. For instance, the celebrated algebraic Riccati equation which in the continuous-time models takes the form $XBX+AX+XD+C=0$, is related to the analysis of the stability of dynamical systems. Here, $A,B,C,D$ are given matrices of compatible sizes and $X$ is the unknown matrix. Quadratic equations like $AX^2+BX+C=0$ model damped vibration problems as well as stochastic models encountered in the analysis of queues. In the case of queues of the M/G/1 type the equations take the form $\sum_{i={-1}}^\infty A_i X^{i+1} = 0$ where a matrix analytic function over a suitable domain is involved.

The goal of the research in this area is to develop tools for designing fast and effective algorithms to solve this kind of equation. These equations, as well as similar ones, can be recast as generalized eigenvalue problems; for instance, the latter is related to finding $\lambda\in\mathbb C$ and $x\in \mathbb{C}^n$ such that $(\lambda^2 P+\lambda Q+R)x=0$ (quadratic eigenvalue problem). The techniques needed to combine the ones used for general nonlinear equations (multivariate Newton methods, fixed-point iterations) and eigenvalue problems (Schur decompositions, orthogonal reductions, rational approximations).

Matrix structures (such as entrywise nonnegativitysymmetry, and symplecticity) play a crucial role in all of this; they are needed for defining the solutions of these equations in the first place, and to ensure feasibility, accuracy, and computational efficiency of the numerical algorithms.

Applications of these equations include control and system theory, queuing theory and structured Markov chain modeling in applied probability, and time series estimation in statistics. It is useful to interface directly with researchers working in these application fields: the different points of view provide useful insight, and the algorithms can be better tailored to the needs of the practitioners.

Members
Dario Andrea Bini
dario.bini@unipi.it
Fabio Durastante
fabio.durastante@unipi.it
Stefano Massei
stefano.massei@unipi.it
Beatrice Meini
beatrice.meini@unipi.it
Collaborators
Chun-Hua Guo (University of Regina)
Sophie Hautphenne (University of Melbourne)
Bruno Iannazzo (Università degli Studi di Perugia)
Guy Latouche (Université libre de Bruxelles)
Volker Mehrmann (Technische Universität Berlin)
Giang Nguyen (The University of Adelaide)
Federico Giovanni Poloni (Università di Pisa)
federico.poloni@unipi.it
Vaidyanathan Ramaswami (AT&T Labs)
Timo Reis (Universität Hamburg)
Giacomo Sbrana (NEOMA Business School)
Matrix Geometric Means

In several applications, different sets of measurements produce different symmetric positive-definite matrices as a result; a natural problem is finding the most plausible correct value for the desired matrix. This corresponds to a form of averaging. The plain arithmetic mean $\frac{1}{n} (X_1 + X_2 + \ldots + X_n)$ is not always the best choice from this point of view.

The concept of the geometric mean of a set of positive numbers can be extended to the case of a set of positive definite matrices. However, this extension is not so trivial and, while for the case of two matrices there is a unique definition, in the case of several matrices there exists an infinite number of valid definitions.

The most general setting under which to study this problem is the one of Riemannian geometry: one gives a Riemannian scalar product on the manifold of symmetric positive-definite matrices and studies the point which minimizes the sum of squared distances from the given matrices (Cartan mean). This gives rise to a mean which is compatible in some sense with matrix inversions, much like the geometric mean in the scalar case.

In addition to the theoretical aspects, practical computation of these means is an interesting problem, a special case of optimization on manifolds. The classical multivariate methods from optimization need to be adapted to work on a generic manifold; one needs to consider the role of its tangent space and construct suitable maps to and from it.

This kind of mean is of great importance in applications, especially in engineering and in problems of radar detection.

Our goal is to provide a better understanding of the different concepts involved in this research, new definitions of mean which are better suited for the applicative models, and faster and more reliable algorithms for their computation.

Members
Dario Andrea Bini
dario.bini@unipi.it
Beatrice Meini
beatrice.meini@unipi.it
Collaborators
Bruno Iannazzo (Università degli Studi di Perugia)
Ben Jeuris (Katholieke Universiteit Leuven)
Federico Giovanni Poloni (Università di Pisa)
federico.poloni@unipi.it
Raf Vandebril (Katholieke Universiteit Leuven)
Numerical Solution of Markov Chains

Many problems from the applications are modeled by Markov chains. Very often the set of the states is huge or even infinite. In these cases, customary techniques are not suited to solve this kind of problems.

The goal of this research area is the design and analysis of effective solution algorithms for infinite Markov chains, with special attention to the ones coming from queuing models. This goal is reached by developing theoretical tools relying on complex analysis, numerical analysis, and structured matrix computations.

Members
Dario Andrea Bini
dario.bini@unipi.it
Stefano Massei
stefano.massei@unipi.it
Beatrice Meini
beatrice.meini@unipi.it
Collaborators
Paola Favati (CNR - Pisa)
Chuan H. Foh (University of Surrey)
Guy Latouche (Université libre de Bruxelles)
Federico Giovanni Poloni (Università di Pisa)
federico.poloni@unipi.it
Vaidyanathan Ramaswami (AT&T Labs)
Benny Van Houdt (University of Antwerp)
Moshe Zukerman (City University of Hong Kong)
Theory of Circuits

The aim is to analyze the dynamic behavior of linear networks containing models which depend polynomially on a set of parameters. The existence and uniqueness of the solution of such networks are investigated in the case of op-ampDistributional methods for the analysis of continuous-time and time-invariant linear systems are considered.

Members
Maurizio Ciampa
maurizio.ciampa@unipi.it
Marco Franciosi
marco.franciosi@unipi.it
Collaborators

People

Faculty
Name Surname Email Personal Card
Paola Boito paola.boito@unipi.it
Maurizio Ciampa maurizio.ciampa@unipi.it
Fabio Durastante fabio.durastante@unipi.it
Stefano Massei stefano.massei@unipi.it
Beatrice Meini beatrice.meini@unipi.it
Cecilia Pagliantini cecilia.pagliantini@unipi.it
Leonardo Robol leonardo.robol@unipi.it
Affiliate Members
Name Surname Email Personal Card
Dario Andrea Bini dario.bini@unipi.it
Sergio Steffè sergio.steffe@unipi.it
Former Members

there is no data

Postdoctoral Fellows

there is no data

Ph.D. Students at the University of Pisa
Name Surname Email Personal Card
Alberto Bucci alberto.bucci@phd.unipi.it
Ph.D. Students at other institutions
Name Surname Affiliation
Angelo A. Casulli SNS, Pisa

Ph.D. Theses supervised by members of the group

awarded by the University of Pisa
Year Name Surname Title of the Thesis Supervisor(s)
2012 Vanni Noferini Polynomial Eigenproblems: a Root-Finding Approach Luca Gemignani and Dario Andrea Bini
2007 Bruno Iannazzo Numerical Solution of Certain Nonlinear Matrix Equations Dario Andrea Bini
2004 Manuela Bagnasco Il metodo QR per matrici semiseparabili: aspetti teorici e computazionali Dario Andrea Bini
1998 Beatrice Meini Fast Algorithms For The Numerical Solution of Structured Markov Chains Dario Andrea Bini
1997 Giuseppe Fiorentino Tau Matrices and Generating Functions for Solving Toeplitz Systems Dario Andrea Bini
1994 Enrico Bozzo Matrix Algebras and Discrete Transforms Dario Andrea Bini
awarded by another institution
Year Name Surname Title of the Thesis Institution Supervisor(s)
2017 Stefano Massei Exploiting rank structures in the numerical solution of Markov chains and matrix functions SNS, Pisa Dario Andrea Bini
2015 Leonardo Robol Exploiting rank structures for the numerical treatment of matrix polynomials SNS, Pisa Dario Andrea Bini
2010 Federico Giovanni Poloni Algorithms for quadratic matrix and vector equations SNS, Pisa Dario Andrea Bini
2007 Paola Boito Structured Matrix Based Methods for Approximate Polynomial GCD SNS, Pisa Dario Andrea Bini
1995 Stefano Serra Analisi di proprietà spettrali di matrici di Toeplitz ed applicazioni ai metodi di gradiente coniugato precondizionato per certe classi di sistemi lineari strutturati Università degli Studi di Milano (La Statale) Dario Andrea Bini

Grants

Current
Past

Visitors

Prospective

there is no data

Current
First Name Last Name Affiliation Building Floor Office
Ivan Bioli École Polytechnique Fédérale de Lausanne (EPFL) Building A Ground floor 119
Grouped by year
2023
First Name Last Name Affiliation From To
Ivan Bioli École Polytechnique Fédérale de Lausanne (EPFL) Sep 18, 2023 Jan 19, 2024
Alice Cortinovis Stanford University Jun 08, 2023 Jun 10, 2023
Chiara Mauro Universidad Complutense de Madrid Jul 03, 2023 Jul 14, 2023
Aleksey Yordanov Nikolov Technical University of Sofia Feb 04, 2023 Mar 04, 2023
Stoyan Popov Technical University of Sofia Feb 04, 2023 Mar 04, 2023
Raf Vandebril Katholieke Universiteit Leuven Apr 13, 2023 Apr 13, 2023
Lu Xia Eindhoven University of Technology Jul 10, 2023 Jul 21, 2023
2022
First Name Last Name Affiliation From To
Gianluca Ceruti École Polytechnique Fédérale de Lausanne (EPFL) Dec 12, 2022 Dec 17, 2022
Bruno Iannazzo Università degli Studi di Perugia Dec 09, 2022 Dec 12, 2022
Stefano Massei Eindhoven University of Technology Feb 07, 2022 Mar 06, 2022
Mariarosa Mazza Università degli Studi dell’Insubria Nov 28, 2022 Dec 01, 2022
Aaron Melman Santa Clara University Nov 09, 2022 Nov 10, 2022
Back to top