Shifted extended global Lanczos processes for trace estimation with application to network analysis

Authors / Editors

Research Areas

No matching items found.

Publication Details

Output type: Journal article

UM6P affiliated Publication?: Yes

Author list: Bentbib, A. H.; El Ghomari, M.; Jbilou, K.; Reichel, L.

Publisher: Springer (part of Springer Nature): Springer Open Choice Hybrid Journals

Publication year: 2021

Journal: Calcolo (0008-0624)

Volume number: 58

Issue number: 1

ISSN: 0008-0624

eISSN: 1126-5434

Languages: English (EN-GB)

View in Web of Science | View on publisher site | View citing articles in Web of Science


The need to estimate upper and lower bounds for matrix functions of the form trace(W-T f (A)V), where the matrix A. Rnxn is large and sparse, V, W is an element of R-nxs are block vectors with 1 <= s << n columns, and f is a function arises in many applications, including network analysis and machine learning. This paper describes the shifted extended global symmetric and nonsymmetric Lanczos processes and how they can be applied to approximate the trace. These processes compute approximations in the union of Krylov subspaces determined by positive powers of A and negative powers of A - sigma I-n, where the shift sigma is a user-chosen parameter. When A is nonsymmetric, transposes of these powers also are used. When A is symmetric and W = V, we describe how error bounds or estimates of bounds for the trace can be computed by pairs of Gauss and Gauss-Radau quadrature rules, or by pairs of Gauss and anti-Gauss quadrature rules. These Gauss-type quadrature rules are defined by recursion coefficients for the shifted extended global Lanczos processes. Gauss and anti-Gauss quadrature rules also can be applied to give estimates of error bounds for the trace when A is nonsymmetric and W not equal V. Applications to the computation of the Estrada index for networks and to the nuclear norm of a large matrix are presented. Computed examples show the shifted extended symmetric and nonsymmetric Lanczos processes to produce accurate approximations in fewer steps than the standard symmetric and nonsymmetric global Lanczos processes, respectively.


No matching items found.


No matching items found.

Last updated on 2021-08-05 at 23:19