# Research topics

This page contains a quick description of the research topics and fields of expertise of the group members. A more technical view can be obtained by looking at conference presentations in the members' home pages.

## 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 of this kind of numerical tools 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 to approximate 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 rootfinding 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. Polynomial of degree $2^{21}$ and $2^{22}$ can be solved in a few days and in few weeks, respectively. Mandelbrot polynomials have zeros which coincide with the cycles of given length in the Mandelbrot iteration. These zeros are severely ill-conditioned. For more information we refer to the home page of MPSolve and to the Wikipedia page on MPSolve.

A variation of this approach based on the use of
**secular equations** and a particular class of semiseparable companion
matrices has been studied and implemented in the package. The final
algorithm, called **secsolve**, has proved to be very effective and
particulary fast on bad conditioned polynomials.

There is an ongoing effort to generalize these strategies to the matrix
case, i.e., to find the generalized eigenvalues and eigenvectors of a
**matrix polynomial** $P(x) = \sum_{i = 0}^n P_i x^i$ with $P_i \in
\mathbb{C}^{m \times m}$. This is a very active research area since many
engingeering problems are related to these kind of equations and there
are **no totally reliable methods** available for the cases where the degree
is greater than 1.

*Involved people:*D.A. Bini, G. Fiorentino, L. Robol*Collaborations:*Dhagash Mehta (University of Notre Dame, Indiana USA)

### Numerical method for differential problems with ordinary and fractional derivatives

Initial and boundary value problems
for **ordinary and fractional ODEs** are analyzed with the aim of
designing new and more effective algorithms for their numerical
solution. Direct and inverse eigenvalue problems for the **Sturm-Liouville type operators** are investigated both in the regular and in the singular case.

*Involved people:*L. Aceto, P. Ghelardoni, C. Magherini*Collaborators:*L. Brugnano (Firenze), F. Iavernaro (Bari), M. Marletta (Cardiff), P. Novati (Padova), E. Weinmueller (Vienna)

### 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** which
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 share 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 low rank. This property has been investigated in 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 sructure**. 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.

*Involved people:*D.A. Bini, R. Bevilacqua, G. Del Corso, L. Gemignani, F. Poloni, L. Robol.*Collaborations:*Paola Boito (Limoges), Yuli Eidelman and Israel Gohberg (Tel Aviv), Vanni Noferini (Manchester), V. Pan (New York), Meisam Sharify (Manchester), Francoise Tisseur (Manchester), Raf Vandebril (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 with the analysis of **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
equations. 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 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 nonnegativity**, **symmetry** 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** modelling in applied probability, and **time series** estimaton 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.

*Involved people:*D.A. Bini, B. Meini, S. Massei, F. Poloni.*Collaborations:*Sophie Hautphenne (Melbourne), C.-H. Guo (Regina), B. Iannazzo (Perugia), Guy Latouche (Bruxelles), V. Mehrmann (Berlin), G.T. Nguyen (Adelaide), V. Ramaswami (AT&T Labs, New York), G. Sbrana (Rouen), C. Schroeder (Berlin), T. Reis (Hamburg).

### 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+\dots+X_n)$ is not always the best choice from this point of view.

The concept of **geometric mean** of a set of positive number 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 exist 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 the 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, faster and more **reliable algorithms** for their computation.

*Involved people:*D.A. Bini, B. Iannazzo, B. Meini, F. Poloni.*Collaborations:*B. Jeuris (Leuven), R. Vandebril (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 on **complex analysis**,
numerical analysis, and **structured matrix computations**.

*Involved people:*D.A. Bini, S. Massei, B. Meini, F. Poloni, S. Steffè.*Collaborations:*P. Favati (CNR Pisa), C. H. Foh (Surrey), G. Latouche (Bruxelles), V. Ramaswami (AT&T Labs, New York), B. Van Houdt (Antwerp), M. Zukerman (Hong Kong)

### Analysis of complex networks

In this research direction, we aim to apply **complex network analysis** to the assessment of the **quality of research** including individuals, institutions, and journals, together with models for **patent evaluation**.

*Involved people:*D. Bini, G. Del Corso, F. Romani.*Collaborations:*M. Shaffer (Tucson).*Patent Pending:*n. 61/494,821, filed 6/8/2011, US Patent Office.*Patent Pending:*n.,61/933,812, filed 1/20/2014, US Patent Office.

### 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 is investigated in the case of **op-amp**.
**Distributional methods** for the analysis of continuous-time and time-invariant linear systems are considered.

*Involved people:*M. Ciampa.*Collaborations:*M. Franciosi, M. Poletti.