Approximations of matrix-valued functions of the form WT f(A)W, where A ∈Rm×m is symmetric, W ∈ Rm×k, with m large and k ≪ 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 ∈ Rm×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 WT f(A)V , where A ∈ Rm×m may be nonsymmetric, and the matrices V, W ∈ Rm×k satisfy VT W = Ik also are 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.

Block Gauss and anti-Gauss quadrature with application to networks

FENU, CATERINA;RODRIGUEZ, GIUSEPPE
2013-01-01

Abstract

Approximations of matrix-valued functions of the form WT f(A)W, where A ∈Rm×m is symmetric, W ∈ Rm×k, with m large and k ≪ 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 ∈ Rm×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 WT f(A)V , where A ∈ Rm×m may be nonsymmetric, and the matrices V, W ∈ Rm×k satisfy VT W = Ik also are 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.
2013
Gauss quadrature; Anti-Gauss quadrature; Block Lanczos algorithm; Nonsymmetric block Lanczos algorithm; Adjacency matrix; Network analysis; Graph
File in questo prodotto:
File Dimensione Formato  
antigauss13.pdf

Solo gestori archivio

Tipologia: versione editoriale
Dimensione 329.31 kB
Formato Adobe PDF
329.31 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11584/99909
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 43
  • ???jsp.display-item.citation.isi??? 41
social impact