Paper VIII: Krylov methods and packet preconditioning

7 Krylov methods and packet preconditioning

On this page · Permalink · Source line 1092

Definition 7.1: Krylov space

For a linear operator \(A\), a vector \(v\), and a positive integer \(m\), define

\[ {\mathcal K}_m(A,v) = \operatorname{span} \{v,Av,\ldots,A^{m-1}v\}. \]

Permalink · Source line 1094 · Claim record · Lean coverage · Code · Worked examples

Proposition 7.2: Invariant packet Krylov decomposition

Assume

\[ [A,P_\alpha]=0 \]

for every packet. If

\[ v=\sum_\alpha v_\alpha, \qquad v_\alpha=P_\alpha v, \]

then

\[ A^jv = \sum_\alpha A_\alpha^jv_\alpha \]

for every \(j\geq0\), where

\[ A_\alpha=P_\alpha AP_\alpha. \]

Hence

\[ {\mathcal K}_m(A,v) \subseteq \bigoplus_\alpha {\mathcal K}_m(A_\alpha,v_\alpha). \]

Read proof · Visual guide: Invariant does not mean independently addressable · Read statement and proof side by side · Permalink · Source line 1104 · Claim record · Lean coverage · Code · Worked examples

Proof of Proposition 7.2

Commutation gives

\[ A^jP_\alpha=P_\alpha A^j. \]

Apply this identity to each packet component of \(v\).

Back to statement · Read statement and proof side by side · Permalink · Source line 1134 · Claim record · Lean coverage · Code · Worked examples

Theorem 7.3: Approximate packet Krylov bound

Write

\[ A=D+K, \]

where \(D\) is packet diagonal. For every positive integer \(j\),

\[ \boxed{ {\left\lVert A^j-D^j\right\rVert} \leq jM^{j-1}{\left\lVert K\right\rVert}, } \]

where

\[ M=\max\{{\left\lVert A\right\rVert},{\left\lVert D\right\rVert}\}. \]

Consequently,

\[ {\operatorname{dist}}(A^jv,\bigoplus_\alpha{\mathcal K}_{j+1}(D_\alpha,v_\alpha)) \leq jM^{j-1}{\left\lVert K\right\rVert}{\left\lVert v\right\rVert}. \]

Read proof · Visual guide: Invariant does not mean independently addressable · Read statement and proof side by side · Permalink · Source line 1142 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem 7.3

Use the telescoping identity

\[ A^j-D^j = \sum_{k=0}^{j-1} A^{j-1-k}KD^k. \]

Each term has norm at most \(M^{j-1}{\left\lVert K\right\rVert}\). The vector \(D^jv\) lies in the direct sum of local Krylov spaces.

Back to statement · Read statement and proof side by side · Permalink · Source line 1167 · Claim record · Lean coverage · Code · Worked examples

Theorem 7.4: Block Jacobi condition bound

Let

\[ A=D+K \]

act on a nonempty finite coordinate space and be Hermitian positive definite with positive definite block diagonal part \(D\). Here \(D^{-1/2}\) is the actual inverse of the positive square root of \(D\). Suppose

\[ E=D^{-1/2}KD^{-1/2} \]

is Hermitian and

\[ {\left\lVert E\right\rVert}_2\leq\eta<1. \]

Then

\[ \boxed{ {\operatorname{cond}}_2(D^{-1/2}AD^{-1/2}) \leq \frac{1+\eta}{1-\eta}. } \]

Read proof · Visual guide: Measure coupling after normalization · Read statement and proof side by side · Permalink · Source line 1178 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem 7.4

For every unit vector \(x\),

\[ {\left\lvert x^*Ex\right\rvert}\leq\eta. \]

The Rayleigh quotient of \(I+E\) lies in \([1-\eta,1+\eta]\). The quotient of the extreme eigenvalue bounds gives the result.

Back to statement · Read statement and proof side by side · Permalink · Source line 1201 · Claim record · Lean coverage · Code · Worked examples

Standard fact 7.5: Preconditioned conjugate gradient convergence

Let \(A\) and \(M\) be Hermitian positive definite on a nonempty finite coordinate space, and set

\[ \kappa = {\operatorname{cond}}_2(M^{-1/2}AM^{-1/2}). \]

In exact arithmetic, the energy norm error of preconditioned conjugate gradient satisfies

\[ {\left\lVert x_m-x_*\right\rVert}_A \leq 2 \left( \frac{\sqrt\kappa-1}{\sqrt\kappa+1} \right)^m {\left\lVert x_0-x_*\right\rVert}_A. \]

Visual guide: Measure coupling after normalization · Permalink · Source line 1209 · Claim record · Lean coverage · Code · Worked examples

This standard estimate is discussed in [Saad2003]. Combining it with Theorem 7.4 yields an explicit iteration certificate when the normalized cross packet coupling is small.

Permalink · Source line 1228

The block diagonal packet operator serves as a reusable local preconditioner in a weakly coupled positive system.

Corollary 7.6: Certified packet preconditioning

Under the hypotheses of Theorem 7.4, the convergence factor in Standard fact 7.5 is bounded by the value obtained from

\[ \kappa = \frac{1+\eta}{1-\eta}. \]

Read proof · Visual guide: Measure coupling after normalization · Read statement and proof side by side · Permalink · Source line 1237 · Claim record · Lean coverage · Code · Worked examples

Proof of Corollary 7.6

Insert the condition bound from Theorem 7.4 into the monotone convergence factor in Standard fact 7.5.

Back to statement · Read statement and proof side by side · Permalink · Source line 1246 · Claim record · Lean coverage · Code · Worked examples

Read and explore

Proofs and implementation

About this work

Other resources