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 $\left\Vert W\right\Vert _{2}^{2}$, where $U=VW$, $A=UU^{T}$, and $B=VV^{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 $\left\Vert W\right\Vert _{2}^{2}$ for a given $W$. We also show that this bound is sometimes tighter than other easily-computed bounds on $\left\Vert W\right\Vert _{2}^{2}$, such as $\left\Vert W\right\Vert _{F}^{2}$ and $\left\Vert W\right\Vert _{1}\left\Vert W\right\Vert _{\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.

< Back