Structured Matrix Days 2016

Invited Speakers

• Francesca Arrigo (Università dell'Insubria)

  Computation of centrality and communicability indices using generalized matrix functions
  Network models are nowadays ubiquitous in the natural, information, social, and engineering sciences.
  It is well known that real-world networks are characterized by some "hidden" structural properties that make them very different from both regular graphs and completely random graphs [4]. Real networks frequently exhibit a highly skewed degree distribution, small diameter, and high clustering coefficient. Moreover, highly optimized undirected networks usually have a large total communicability [3], meaning that they are good at exchanging information.
  In this talk, we describe how to extend the concept of total communicability to the case of directed graphs [1]. We further provide guidelines to efficiently select a small number of modifications to the connections in the network aimed to tune the new indices. We show that one of the most effective techniques is based on the concept of generalized matrix functions [2,5], whose definition is based on replacing the Jordan canonical form of A with its compact singular value decomposition, and evaluating the function at the positive singular values of A, if defined. We describe several computational approaches based on variants of Golub--Kahan bidiagonalization algorithm to compute or estimate bilinear forms involving generalized matrix functions. Extensive numerical studies are presented to assess the effectiveness of the proposed methods.
  References:
  [1] F. Arrigo and M. Benzi, Edge modification criteria for enhancing the communicability of digraphs, SIAM J. Matrix Anal. Appl., 37(1) (2016), pp. 443--468.
  [2] F. Arrigo, M. Benzi, and C. Fenu, Computation of generalized matrix functions, SIAM J. Matrix Anal. Appl. 2016 (in press).
  [3] M. Benzi and C. Klymko, Total communicability as a centrality measure, J. Complex Networks, 1(2) (2013), pp. 124--149.
  [4] E. Estrada, The Structure of Complex Networks. Theory and Applications, Oxford University Press, 2012.
  [5] J. B. Hawkins and A. Ben--Israel, On generalized matrix functions, Linear and Multilinear Algebra, 1 (1973), pp. 163--171.

• Robert Luce (EPF Lausanne)

  Pathways to the Toeplitz matrix exponential
  An important structural feature of Toeplitz matrices is that they have low rank representations as solutions of certain matrix Stein or Sylvester equations. Using these low rank properties we present techniques for the computation of the full matrix exponential of a Toeplitz matrix in quadratic complexity, i.e., with run time and storage proportional to the output. An interesting application for our algorithm is the solution of an PIDE arising from option pricing of an asset in Merton's jump diffusion model.

• Clément Pernet (Université Grenoble-Alpes, LIP - ENS Lyon)

  Improved generators for quasiseparable matrices
  The class of quasiseparable matrices is defined by a pair of bounds, called the quasiseparable orders, on the ranks of the sub-matrices entirely located in their strictly lower and upper triangular parts. These arise naturally in applications, as e.g. the inverse of band matrices, and are widely used for they admit structured representations allowing to compute with them in time linear in the dimension. We show, in this paper, the connection between the notion of quasiseparability and the rank profile matrix invariant, presented in [Dumas et al. ISSAC'15]. This allows us to propose an algorithm computing the quasiseparable orders (l,u) in time O(n^2s^(w-2)) where s=max(l,u) and w is the exponent of matrix multiplication. We then present two new structured representations, a binary tree of PLUQ decompositions, and the Bruhat generator using respectively O(ns log (n/s)) and O(ns) field elements instead of O(ns^2) for the classical generator. We present algorithms computing these representations in time O(n^2s^(w-2). These representations allow a matrix-vector product in time linear in the size of their representation. Lastly we show how to multiply two such structured matrices in time O(n^2s^(w-2)).

• Leonardo Robol (KU Leuven)

  A framework for structured linearizations of matrix polynomials in various bases
  We present a framework for the construction of linearizations for scalar and matrix polynomials based on dual bases which, in the case of orthogonal polynomials, can be described by the associated recurrence relations. The framework provides an extension of the classical linearization theory for polynomials expressed in non-monomial bases and allows to represent polynomials expressed in product families, that is as a linear combination of elements of the form $\phi_i(\x) \psi_j(\x)$, where $\{ \phi_i(\x) \}$ and $\{ \psi_j(\x) \}$ can either be polynomial bases or polynomial families which satisfy some mild assumptions. We show that this general construction can be used for many different purposes. Among them, we show how to linearize sums of polynomials and rational functions expressed in different bases. As an example, this allows to look for intersections of functions interpolated on different nodes without converting them to the same basis. We then provide some constructions for structured linearizations for $\star$-even and $\star$-palindromic matrix polynomials. The extensions of these constructions to $\star$-odd and $\star$-antipalindromic of odd degree is discussed and follows immediately from the previous results.
  Joint work with Raf Vandebril and Paul Van Dooren.