Volume 21, pp. 28-46, 2005.

Obtaining bounds on the two norm of a matrix from the splitting lemma

Doron Chen, John R. Gilbert, and Sivan Toledo

Abstract

The splitting lemma is one of the two main tools of support theory, a framework for bounding the condition number of definite and semidefinite preconditioned linear systems. The splitting lemma allows the analysis of a complicated system to be partitioned into analyses of simpler systems. The other tool is the symmetric-product-support lemma, which provides an explicit spectral bound on a preconditioned matrix.
The symmetric-product-support lemma shows that under suitable conditions on the null spaces of $A$ and $B$, the finite eigenvalues of the pencil $(A,B)$ are bounded by ${\Vert W\Vert }_2^2$, where $U=VW$, $A=U{U}^T$, and $B=V{V}^T$. To apply the lemma, one has to construct a $W$ satisfying these conditions, and to bound its $2$-norm.
In this paper we show that in all its existing applications, the splitting lemma can be viewed as a mechanism to bound ${\Vert W\Vert }_2^2$ for a given $W$. We also show that this bound is sometimes tighter than other easily-computed bounds on ${\Vert W\Vert }_2^2$, such as ${\Vert W\Vert }_F^2$ and ${\Vert W\Vert }_1{\Vert W\Vert }_{\mathrm{\infty }}$. The paper shows that certain regular splittings have useful algebraic and combinatorial interpretations. In particular, we derive six separate algebraic bounds on the $2$-norm of a real matrix; to the best of our knowledge, these bounds are new.

Full Text (PDF) [262 KB], BibTeX

Key words

matrix norm bounds, two-norm, norm bounds for sparse matrices, splitting lemma, support theory, support preconditioning

AMS subject classifications

15A60, 65F10, 65F35, 65F50.