Obtaining bounds on the two norm of a matrix from the splitting lemma.
Doron Chen, John R. Gilbert, Sivan Toledo · 2005
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-productsupport 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 and, the finite eigenvalues of the pencil are bounded by, where, , and. To apply the lemma, one has to construct a satisfying these conditions, and to bound its-norm. In this paper we show that in all its existing applications, the splitting lemma can be viewed as a mechanism to bound for a given. We also show that this bound is sometimes tighter than other easily-computed bounds on, such as! " and. The paper shows that certain regular splittings have useful algebraic and combinatorial interpretations. In particular, we derive six separate algebraic bounds on the-norm of a real matrix; to the best of our knowledge, these bounds are new.