August 2015

We review and extend the theory of Generalized Locally Toeplitz (GLT) sequences, which goes back to the pioneering work by Tilli on Locally Toeplitz (LT) sequences and was developed by the second author during the last decade. Informally speaking, a GLT sequence

{Ais a sequence of matrices with increasing size, equipped with a Lebesgue-measurable function_{n}}_{n}kappa(the so-called symbol). This function characterizes the asymptotic singular value distribution of{A; in the case where the matrices_{n}}_{n}Aare Hermitian, it also characterizes the asymptotic eigenvalue distribution of_{n}{A. Three fundamental examples of GLT sequences are: (i) the sequence of Toeplitz matrices generated by a function_{n}}_{n}finL; (ii) the sequence of diagonal sampling matrices containing the evaluations of a Riemann-integrable function^{1}aover a uniform grid; (iii) any zero-distributed sequence, i.e., any sequence of matrices possessing an asymptotic singular value distribution characterized by the identically zero function. The symbol of the GLT sequence (i) isf, the symbol of the GLT sequence (ii) isa, and the symbol of any GLT sequence of the form (iii) is 0. The set of GLT sequences is a *-algebra. More precisely, suppose that{Aare GLT sequences with symbols_{n}^{(1)}}_{n},...,{A_{n}^{(r)}}_{n}kappa, and let_{1},...,kappa_{r}Abe a matrix obtained from_{n}=ops(A_{n}^{(1)},...,A_{n}^{(r)})Aby means of certain algebraic operations `ops', such as linear combinations, products, inversions and Hermitian transpositions; then,_{n}^{(1)},...,A_{n}^{(r)}{Ais a GLT sequence with symbol_{n}}_{n}kappa=ops(kappa._{1},...,kappa_{r})As already proved in several contexts, the theory of GLT sequences is a powerful apparatus for computing the asymptotic singular value and eigenvalue distribution of the discretization matrices

Aarising from the numerical approximation of continuous problems, such as integral equations and, especially, partial differential equations. Indeed, when the discretization parameter_{n}ntends to infinity, the discretization matricesAgive rise to a sequence_{n}{A, which often turns out to be a GLT sequence._{n}}_{n}However, in this work we are not concerned with the applicative interest of the theory of GLT sequences, for which we limit to outline some of the numerous applications and to refer the reader to the available literature. On the contrary, we focus on the mathematical foundations. We propose slight (but relevant) modifications of the original definitions, and we introduce for the first time the concept of LT sequences in the multivariate/multilevel setting. With the new definitions, based on the notion of approximating class of sequences, we are able to enlarge the applicability of the theory, by generalizing and/or simplifying a lot of key results. In particular, we remove a technical hypothesis concerning the Riemann-integrability of the so-called `weight functions', which appeared in the statement of many spectral distribution and algebraic results for GLT sequences. Moreover, we provide a formal and detailed proof of the fact that the sequences of matrices mentioned in items (i)-(iii) fall in the class of LT sequences. Several versions of this result were already present in previous papers, but only partial proofs were given.

As a final step, we extend the theory of GLT sequences. We first prove an approximation result, which is particularly useful to show that a given sequence of matrices is a GLT sequence. By using this result, we provide a new and easier proof of the fact that

{Ais a GLT sequence with symbol_{n}^{-1}}_{n}kappawhenever^{-1}{Ais a GLT sequence of invertible matrices with symbol_{n}}_{n}kappaandkappa≠ 0almost everywhere. Finally, using again the approximation result, we prove that{f(Ais a GLT sequence with symbol_{n})}_{n}f(kappa), as long asf:is continuous andR→R{Ais a GLT sequence of Hermitian matrices with symbol_{n}}_{n}kappa. This has important implications, e.g., in proving that the geometric mean of two GLT sequences is still a GLT sequence, with symbol given by the the geometric mean of the symbols.

*Note:* Revised, corrected, updated and extended version of TR 2015-016.

Available as PDF (757 kB, no cover)

Download BibTeX entry.