ILAS2016 — 11–15 July 2016 — KU Leuven, Belgium

20th Conference of the International Linear Algebra Society (ILAS)

20th ILAS Conference

In minisymposium: Matrix Methods in Network Analysis

Mon 12:00–12:30, Room AV 04.17
Efficient computation of complex network metrics by block Gauss quadrature rules
Giuseppe Rodriguez (University of Cagliari)
Joint work with C. Fenu (University of Pisa); L. Reichel (Kent State University); T. Tang (Kent State University)

During the last decade many new indices have been introduced, in order to characterize either the nodes of a complex network or the network itself in its entirety, which can be expressed as functions of the adjacency matrix $A$ associated to the network. While such matrix functions can be defined in terms of the spectral decomposition of $A$, most interesting applications lead to so large adjacency matrices that it is unfeasible to compute their spectral factorization. In these situations, projecting the original matrix in Krylov spaces of suitable dimension may provide an effective approach for analyzing complex networks.

In this talk we will discuss some block algorithms recently introduced in [1,2] which present substantial computational advantages with respect to other approaches. In particular, we will focus on a procedure based on block averaged Gauss quadrature rules, that guarantees a higher accuracy than traditional Gauss rules, leading to a reduction in the number of iterations.

  1. C. Fenu, D. Martin, L. Reichel, and G. Rodriguez. Block Gauss and anti-Gauss quadrature with application to networks. SIAM J. Matrix Anal. Appl., 34(4):1655–1684, 2013.
  2. L. Reichel, G. Rodriguez, and T. Tang. New block quadrature rules for the approximation of matrix functions. Linear Algebra Appl., 2016.