Block Gauss and Anti-Gauss Quadrature with Application to Networks
- 1 January 2013
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 34 (4), 1655-1684
- https://doi.org/10.1137/120886261
Abstract
Approximations of matrix-valued functions of the form $W^Tf(A)W$, where $A \in {\mathbb R}^{m\times m}$ is symmetric, $W\in{\mathbb R}^{m\times k}$, with $m$ large and $ k\ll m$, has orthonormal columns, and $f$ is a function, can be computed by applying a few steps of the symmetric block Lanczos method to $A$ with initial block-vector $W\in{\mathbb R}^{m\times k}$. Golub and Meurant have shown that the approximants obtained in this manner may be considered block Gauss quadrature rules associated with a matrix-valued measure. This paper generalizes anti-Gauss quadrature rules, introduced by Laurie for real-valued measures, to matrix-valued measures, and shows that under suitable conditions pairs of block Gauss and block anti-Gauss rules provide upper and lower bounds for the entries of the desired matrix-valued function. Extensions to matrix-valued functions of the form $W^Tf(A)V$, where $A\in{\mathbb R}^{m\times m}$ may be nonsymmetric, and the matrices $V,W\in{\mathbb R}^{m\times k}$ satisfy $V^TW=I_k$ are also discussed. Approximations of the latter functions are computed by applying a few steps of the nonsymmetric block Lanczos method to $A$ with initial block-vectors $V$ and $W$. We describe applications to the evaluation of functions of a symmetric or nonsymmetric adjacency matrix for a network. Numerical examples illustrate that a combination of block Gauss and anti-Gauss quadrature rules typically provides upper and lower bounds for such problems. We introduce some new quantities that describe properties of nodes in directed or undirected networks, and demonstrate how these and other quantities can be computed inexpensively with the quadrature rules of the present paper.
Keywords
This publication has 29 references indexed in Scilit:
- Ranking hubs and authorities using matrix functionsLinear Algebra and its Applications, 2012
- Fast Matrix Computations for Pairwise and Columnwise Commute Times and Katz ScoresInternet Mathematics, 2012
- A generalized global Arnoldi method for ill-posed matrix equationsJournal of Computational and Applied Mathematics, 2011
- Quadrature rule-based bounds for functions of adjacency matricesLinear Algebra and its Applications, 2010
- Rational extrapolation for the PageRank vectorMathematics of Computation, 2008
- Community detection in complex networks using extremal optimizationPhysical Review E, 2005
- New look-ahead Lanczos-type algorithms for linear systemsNumerische Mathematik, 1999
- ABLE: An Adaptive Block Lanczos Method for Non-Hermitian Eigenvalue ProblemsSIAM Journal on Matrix Analysis and Applications, 1999
- Bounds for the Entries of Matrix Functions with Applications to PreconditioningBIT Numerical Mathematics, 1999
- Some large-scale matrix computation problemsJournal of Computational and Applied Mathematics, 1996