Federico Poloni

Federico Poloni, Timo Reis

We introduce a numerical method for the numerical solution of the so-called Lur'e matrix equations that arise in balancing-related model reduction and linear-quadratic infinite time horizon optimal control. Based on the fact that the set of solutions can be characterized in terms of deflating subspaces of even matrix pencils, an iterative scheme is derived that converges linearly to the maximal solution.

Nigel Bean, Giang T. Nguyen, Federico Poloni

Fluid queues are mathematical models frequently used in stochastic modelling. Their stationary distributions involve a key matrix recording the conditional probabilities of returning to an initial level from above, often known in the literature as the matrix $Ψ$. Here, we present a probabilistic interpretation of the family of algorithms known as \emph{doubling}, which are currently the most effective algorithms for computing the return probability matrix $Ψ$. To this end, we first revisit the links described in \cite{ram99, soares02} between fluid queues and Quasi-Birth-Death processes; in particular, we give new probabilistic interpretations for these connections. We generalize this framework to give a probabilistic meaning for the initial step of doubling algorithms, and include also an interpretation for the iterative step of these algorithms. Our work is the first probabilistic interpretation available for doubling algorithms.

Federico Poloni

The aim of this paper is twofold. First, we introduce a new class of linearizations, based on the generalization of a construction used in polynomial algebra to find the zeros of a system of (scalar) polynomial equations. We show that one specific linearization in this class, which is constructed naturally from the QR factorization of the matrix obtained by stacking the coefficients of $A(x)$, has good conditioning and stability properties. Moreover, while analyzing this class, we introduce a general technique to derive new linearizations from existing ones. This technique generalizes some ad-hoc arguments used in dealing with the existing linearization classes, and can hopefully be used to derive a simpler and more general theory of linearizations. This technique relates linearizations to \emph{pencil arithmetic}, a technique used in solving matrix equations that allows to extend some algebraic operations from matrix to matrix pencils.

G. A. Di Luna, P. Flocchini, S. Gan Chaudhuri et al.

Consider a finite set of identical computational entities that can move freely in the Euclidean plane operating in Look-Compute-Move cycles. Let p(t) denote the location of entity p at time t; entity p can see entity q at time t if at that time no other entity lies in the line segment p(t)q(t). We consider the basic problem called Mutual Visibility: starting from arbitrary distinct locations, within finite time the entities must reach, without collisions, a configuration where they all see each other. This problem must be solved by each entity autonomously executing the same algorithm. We study this problem in the "luminous robots" model; in this generalization of the standard model of oblivious robots, each entity, called "robot", has an externally visible persistent light which can assume colors from a fixed set. The case where the number of colors is c=1 corresponds to the classical model without lights. In this paper we investigate under what conditions luminous robots can solve Mutual Visibility without collisions and at what cost (i.e., with how many colors). We establish a spectrum of results, depending on the power of the adversary, on the number c of colors, and on the a-priori knowledge the robots have about the system. Among such results, we prove that Mutual Visibility can always be solved without collisions in SSynch with c=2 colors and in ASynch with c=3 colors. If an adversary can interrupt and stop a robot moving to its computed destination, Mutual Visibility is still always solvable without collisions in SSynch with c=3 colors, and, if the robots agree on the direction of one axis, also in ASynch. All the results are obtained constructively by means of novel protocols. As a byproduct of our solutions, we provide the first obstructed-visibility solutions to two classical problems for oblivious robots: Collision-less Convergence to a point and Circle Formation.

Federico Poloni

In this paper, we analyze the process of "assembling" new matrix geometric means from existing ones, through function composition or limit processes. We show that for n=4 a new matrix mean exists which is simpler to compute than the existing ones. Moreover, we show that for n>4 the existing proving strategies cannot provide a mean computationally simpler than the existing ones.

Dario A. Bini, Federico Poloni

We review some known inclusion results for the roots of a polynomial, and adapt them to a conjecture recently presented by S. A. Vavasis. In particular, we provide strict upper and lower bounds to the distance of the closest root of a polynomial p(z) from a given root of p'(z).