1 January 2013 in SIAM Journal on Matrix Analysis and Applications
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$ ...
18 May 2017 in BIT Numerical Mathematics
1 January 2013 in SIAM Journal on Scientific Computing
Large-scale networks arise in many applications. It is often of interest to be able to identify the most important nodes of a network or to ascertain the ease of traveling between nodes. These and related quantities can be determined by evaluating expressions of the form $\mathbf{u}^Tf(A)\mathbf{w}$, where $A$ is the adjacency matrix that represents the graph of the network, $f$ is a nonlinear function, such as the exponential function, and $\mathbf{u}$ and $\mathbf{w}$ are vectors, for instance, axis vectors. This paper describes a novel technique for determining upper and lower bounds for expressions $\mathbf{u}^Tf(A)\mathbf{w}$ when $A$ is symmetric and bounds for many vectors $\mathbf{u}$ and $\mathbf{w}$ are desired. The bounds are computed by first evaluating a low-rank approximation of $A$, which is used to determine rough bounds for the desired quantities for all nodes. These rough bounds indicate for which vectors $\mathbf{u}$ and $\mathbf{w}$ more accurate bounds should be computed with the aid ...
9 February 2016 in Numerical Linear Algebra with Applications
1 December 2014 in Inverse Problems
1 January 2016 in SIAM Journal on Matrix Analysis and Applications
We develop numerical algorithms for the efficient evaluation of quantities associated with generalized matrix functions [J. B. Hawkins and A. Ben-Israel, Linear Multilinear Algebra, 1 (1973), pp. 163--171]. Our algorithms are based on Gaussian quadrature and Golub--Kahan bidiagonalization. Block variants are also investigated. Numerical experiments are performed to illustrate the effectiveness and efficiency of our techniques in computing generalized matrix functions arising in the analysis of networks.