What\'s so great about Krylov subspaces? - Mathematics
October 30, 2017 | Author: Anonymous | Category: N/A
Short Description
subspaces. David S. Watkins. Krylov subspaces and eigenvalue problems focus on eigenvalue problems ......
Description
Krylov subspaces David S. Watkins
What’s so great about Krylov subspaces? David S. Watkins Department of Mathematics Washington State University
Guwahati, 2013
Krylov Subspace Methods are Great Krylov subspaces David S. Watkins
Krylov subspace methods are great. “Everybody” knows this. large, sparse problems linear systems: CG, MINRES, GMRES, . . . eigenvalue problems: Lanczos, Arnoldi, . . .
Krylov Subspace Methods are Great Krylov subspaces David S. Watkins
Krylov subspace methods are great. “Everybody” knows this. large, sparse problems linear systems: CG, MINRES, GMRES, . . . eigenvalue problems: Lanczos, Arnoldi, . . .
Krylov Subspace Methods are Great Krylov subspaces David S. Watkins
Krylov subspace methods are great. “Everybody” knows this. large, sparse problems linear systems: CG, MINRES, GMRES, . . . eigenvalue problems: Lanczos, Arnoldi, . . .
Krylov Subspace Methods are Great Krylov subspaces David S. Watkins
Krylov subspace methods are great. “Everybody” knows this. large, sparse problems linear systems: CG, MINRES, GMRES, . . . eigenvalue problems: Lanczos, Arnoldi, . . .
Krylov Subspace Methods are Great Krylov subspaces David S. Watkins
Krylov subspace methods are great. “Everybody” knows this. large, sparse problems linear systems: CG, MINRES, GMRES, . . . eigenvalue problems: Lanczos, Arnoldi, . . .
Krylov subspaces and eigenvalue problems Krylov subspaces David S. Watkins
focus on eigenvalue problems pedagogy, understanding introduce Krylov subspaces sooner relevant to small, dense problems too proselytizing
Krylov subspaces and eigenvalue problems Krylov subspaces David S. Watkins
focus on eigenvalue problems pedagogy, understanding introduce Krylov subspaces sooner relevant to small, dense problems too proselytizing
Krylov subspaces and eigenvalue problems Krylov subspaces David S. Watkins
focus on eigenvalue problems pedagogy, understanding introduce Krylov subspaces sooner relevant to small, dense problems too proselytizing
Krylov subspaces and eigenvalue problems Krylov subspaces David S. Watkins
focus on eigenvalue problems pedagogy, understanding introduce Krylov subspaces sooner relevant to small, dense problems too proselytizing
Krylov subspaces and eigenvalue problems Krylov subspaces David S. Watkins
focus on eigenvalue problems pedagogy, understanding introduce Krylov subspaces sooner relevant to small, dense problems too proselytizing
Krylov subspaces and eigenvalue problems Krylov subspaces David S. Watkins
focus on eigenvalue problems pedagogy, understanding introduce Krylov subspaces sooner relevant to small, dense problems too proselytizing
Krylov subspaces and eigenvalue problems Krylov subspaces David S. Watkins
reduction to upper Hessenberg form A ∈ Cn×n H = Q −1 AQ,
H upper Hessenberg
Q can be unitary first column, q1 , direction arbitrary O(n3 ) direct method
Krylov subspaces and eigenvalue problems Krylov subspaces David S. Watkins
reduction to upper Hessenberg form A ∈ Cn×n H = Q −1 AQ,
H upper Hessenberg
Q can be unitary first column, q1 , direction arbitrary O(n3 ) direct method
Krylov subspaces and eigenvalue problems Krylov subspaces David S. Watkins
reduction to upper Hessenberg form A ∈ Cn×n H = Q −1 AQ,
H upper Hessenberg
Q can be unitary first column, q1 , direction arbitrary O(n3 ) direct method
Krylov subspaces and eigenvalue problems Krylov subspaces David S. Watkins
reduction to upper Hessenberg form A ∈ Cn×n H = Q −1 AQ,
H upper Hessenberg
Q can be unitary first column, q1 , direction arbitrary O(n3 ) direct method
Krylov subspaces and eigenvalue problems Krylov subspaces David S. Watkins
reduction to upper Hessenberg form A ∈ Cn×n H = Q −1 AQ,
H upper Hessenberg
Q can be unitary first column, q1 , direction arbitrary O(n3 ) direct method
Krylov subspaces and eigenvalue problems Krylov subspaces David S. Watkins
reduction to upper Hessenberg form A ∈ Cn×n H = Q −1 AQ,
H upper Hessenberg
Q can be unitary first column, q1 , direction arbitrary O(n3 ) direct method
Krylov subspaces and eigenvalue problems Krylov subspaces David S. Watkins
H = Q −1 AQ,
H upper Hessenberg
for unitary Q . . . Implicit-Q Theorem: q1 determines Q and H (nearly) uniquely. Krylov subspaces lurking in background Suggestion: Bring them out into the light. Advantages: clearer picture, more general theory
Krylov subspaces and eigenvalue problems Krylov subspaces David S. Watkins
H = Q −1 AQ,
H upper Hessenberg
for unitary Q . . . Implicit-Q Theorem: q1 determines Q and H (nearly) uniquely. Krylov subspaces lurking in background Suggestion: Bring them out into the light. Advantages: clearer picture, more general theory
Krylov subspaces and eigenvalue problems Krylov subspaces David S. Watkins
H = Q −1 AQ,
H upper Hessenberg
for unitary Q . . . Implicit-Q Theorem: q1 determines Q and H (nearly) uniquely. Krylov subspaces lurking in background Suggestion: Bring them out into the light. Advantages: clearer picture, more general theory
Krylov subspaces and eigenvalue problems Krylov subspaces David S. Watkins
H = Q −1 AQ,
H upper Hessenberg
for unitary Q . . . Implicit-Q Theorem: q1 determines Q and H (nearly) uniquely. Krylov subspaces lurking in background Suggestion: Bring them out into the light. Advantages: clearer picture, more general theory
Krylov subspaces and eigenvalue problems Krylov subspaces David S. Watkins
H = Q −1 AQ,
H upper Hessenberg
for unitary Q . . . Implicit-Q Theorem: q1 determines Q and H (nearly) uniquely. Krylov subspaces lurking in background Suggestion: Bring them out into the light. Advantages: clearer picture, more general theory
Krylov subspaces and eigenvalue problems Krylov subspaces David S. Watkins
H = Q −1 AQ,
H upper Hessenberg
for unitary Q . . . Implicit-Q Theorem: q1 determines Q and H (nearly) uniquely. Krylov subspaces lurking in background Suggestion: Bring them out into the light. Advantages: clearer picture, more general theory
Krylov subspaces and eigenvalue problems Krylov subspaces David S. Watkins
H = Q −1 AQ,
H upper Hessenberg
for unitary Q . . . Implicit-Q Theorem: q1 determines Q and H (nearly) uniquely. Krylov subspaces lurking in background Suggestion: Bring them out into the light. Advantages: clearer picture, more general theory
Krylov subspaces and eigenvalue problems Krylov subspaces David S. Watkins
H = Q −1 AQ,
H upper Hessenberg
for unitary Q . . . Implicit-Q Theorem: q1 determines Q and H (nearly) uniquely. Krylov subspaces lurking in background Suggestion: Bring them out into the light. Advantages: clearer picture, more general theory
Krylov subspaces and eigenvalue problems Krylov subspaces David S. Watkins
H = Q −1 AQ,
H upper Hessenberg
for unitary Q . . . Implicit-Q Theorem: q1 determines Q and H (nearly) uniquely. Krylov subspaces lurking in background Suggestion: Bring them out into the light. Advantages: clearer picture, more general theory
Krylov subspaces and eigenvalue problems Krylov subspaces David S. Watkins
Krylov subspace: Kj (A, v ) = span v , Av , A2 v , . . . , Aj−1 v
Theorem: Let A = QHQ −1 , where H is properly upper Hessenberg. Then span{q1 , . . . , qj } = Kj (A, q1 ),
j = 1, . . . , n.
valid even if Q is not unitary (contrast with implicit-Q) no need for implicit-S, implicit-H, implicit-L, . . .
Krylov subspaces and eigenvalue problems Krylov subspaces David S. Watkins
Krylov subspace: Kj (A, v ) = span v , Av , A2 v , . . . , Aj−1 v
Theorem: Let A = QHQ −1 , where H is properly upper Hessenberg. Then span{q1 , . . . , qj } = Kj (A, q1 ),
j = 1, . . . , n.
valid even if Q is not unitary (contrast with implicit-Q) no need for implicit-S, implicit-H, implicit-L, . . .
Krylov subspaces and eigenvalue problems Krylov subspaces David S. Watkins
Krylov subspace: Kj (A, v ) = span v , Av , A2 v , . . . , Aj−1 v
Theorem: Let A = QHQ −1 , where H is properly upper Hessenberg. Then span{q1 , . . . , qj } = Kj (A, q1 ),
j = 1, . . . , n.
valid even if Q is not unitary (contrast with implicit-Q) no need for implicit-S, implicit-H, implicit-L, . . .
Krylov subspaces and eigenvalue problems Krylov subspaces David S. Watkins
Krylov subspace: Kj (A, v ) = span v , Av , A2 v , . . . , Aj−1 v
Theorem: Let A = QHQ −1 , where H is properly upper Hessenberg. Then span{q1 , . . . , qj } = Kj (A, q1 ),
j = 1, . . . , n.
valid even if Q is not unitary (contrast with implicit-Q) no need for implicit-S, implicit-H, implicit-L, . . .
Krylov subspaces and eigenvalue problems Krylov subspaces David S. Watkins
Krylov subspace: Kj (A, v ) = span v , Av , A2 v , . . . , Aj−1 v
Theorem: Let A = QHQ −1 , where H is properly upper Hessenberg. Then span{q1 , . . . , qj } = Kj (A, q1 ),
j = 1, . . . , n.
valid even if Q is not unitary (contrast with implicit-Q) no need for implicit-S, implicit-H, implicit-L, . . .
Need for iteration Krylov subspaces David S. Watkins
Hessenberg form is not the goal. Triangular form is the goal. Hessenberg is as far as we can get with a direct method. (Abel, Galois) need to iterate
Need for iteration Krylov subspaces David S. Watkins
Hessenberg form is not the goal. Triangular form is the goal. Hessenberg is as far as we can get with a direct method. (Abel, Galois) need to iterate
Need for iteration Krylov subspaces David S. Watkins
Hessenberg form is not the goal. Triangular form is the goal. Hessenberg is as far as we can get with a direct method. (Abel, Galois) need to iterate
Need for iteration Krylov subspaces David S. Watkins
Hessenberg form is not the goal. Triangular form is the goal. Hessenberg is as far as we can get with a direct method. (Abel, Galois) need to iterate
Power method, Subspace iteration Krylov subspaces David S. Watkins
v , Av , A2 v , A3 v , . . . convergence rate | λ2 /λ1 | S, AS, A2 S, A3 S, . . . subspaces of dimension j
(| λj+1 /λj |)
Power method, Subspace iteration Krylov subspaces David S. Watkins
v , Av , A2 v , A3 v , . . . convergence rate | λ2 /λ1 | S, AS, A2 S, A3 S, . . . subspaces of dimension j
(| λj+1 /λj |)
Power method, Subspace iteration Krylov subspaces David S. Watkins
v , Av , A2 v , A3 v , . . . convergence rate | λ2 /λ1 | S, AS, A2 S, A3 S, . . . subspaces of dimension j
(| λj+1 /λj |)
Power method, Subspace iteration Krylov subspaces David S. Watkins
v , Av , A2 v , A3 v , . . . convergence rate | λ2 /λ1 | S, AS, A2 S, A3 S, . . . subspaces of dimension j
(| λj+1 /λj |)
Power method, Subspace iteration Krylov subspaces David S. Watkins
v , Av , A2 v , A3 v , . . . convergence rate | λ2 /λ1 | S, AS, A2 S, A3 S, . . . subspaces of dimension j
(| λj+1 /λj |)
Power method, Subspace iteration Krylov subspaces David S. Watkins
v , Av , A2 v , A3 v , . . . convergence rate | λ2 /λ1 | S, AS, A2 S, A3 S, . . . subspaces of dimension j
(| λj+1 /λj |)
Power method, Subspace iteration Krylov subspaces David S. Watkins
for greater flexibility shifts ρ1 , . . . , ρm
(m small)
(explanation deferred) p(A) = (A − ρ1 I ) · · · (A − ρm I ) Substitute p(A) for A S, p(A)S, p(A)2 S, p(A)3 S, . . . convergence rate | p(λj+1 )/p(λj ) |
Power method, Subspace iteration Krylov subspaces David S. Watkins
for greater flexibility shifts ρ1 , . . . , ρm
(m small)
(explanation deferred) p(A) = (A − ρ1 I ) · · · (A − ρm I ) Substitute p(A) for A S, p(A)S, p(A)2 S, p(A)3 S, . . . convergence rate | p(λj+1 )/p(λj ) |
Power method, Subspace iteration Krylov subspaces David S. Watkins
for greater flexibility shifts ρ1 , . . . , ρm
(m small)
(explanation deferred) p(A) = (A − ρ1 I ) · · · (A − ρm I ) Substitute p(A) for A S, p(A)S, p(A)2 S, p(A)3 S, . . . convergence rate | p(λj+1 )/p(λj ) |
Power method, Subspace iteration Krylov subspaces David S. Watkins
for greater flexibility shifts ρ1 , . . . , ρm
(m small)
(explanation deferred) p(A) = (A − ρ1 I ) · · · (A − ρm I ) Substitute p(A) for A S, p(A)S, p(A)2 S, p(A)3 S, . . . convergence rate | p(λj+1 )/p(λj ) |
Power method, Subspace iteration Krylov subspaces David S. Watkins
for greater flexibility shifts ρ1 , . . . , ρm
(m small)
(explanation deferred) p(A) = (A − ρ1 I ) · · · (A − ρm I ) Substitute p(A) for A S, p(A)S, p(A)2 S, p(A)3 S, . . . convergence rate | p(λj+1 )/p(λj ) |
Power method, Subspace iteration Krylov subspaces David S. Watkins
for greater flexibility shifts ρ1 , . . . , ρm
(m small)
(explanation deferred) p(A) = (A − ρ1 I ) · · · (A − ρm I ) Substitute p(A) for A S, p(A)S, p(A)2 S, p(A)3 S, . . . convergence rate | p(λj+1 )/p(λj ) |
Power method, Subspace iteration Krylov subspaces David S. Watkins
for greater flexibility shifts ρ1 , . . . , ρm
(m small)
(explanation deferred) p(A) = (A − ρ1 I ) · · · (A − ρm I ) Substitute p(A) for A S, p(A)S, p(A)2 S, p(A)3 S, . . . convergence rate | p(λj+1 )/p(λj ) |
Subspace Iteration with changes of coordinate system Krylov subspaces David S. Watkins
take S = span{e1 , . . . , ej } p(A)S = span{p(A)e1 , . . . , p(A)ej } = span{q1 , . . . , qj } (orthonormal?) build unitary (or not) Q = [q1 · · · qj · · · ] ˆ = Q −1 AQ change coordinate system: A qk → Q −1 qk = ek span{q1 , . . . , qj } → span{e1 , . . . , ej } ready for next iteration
Subspace Iteration with changes of coordinate system Krylov subspaces David S. Watkins
take S = span{e1 , . . . , ej } p(A)S = span{p(A)e1 , . . . , p(A)ej } = span{q1 , . . . , qj } (orthonormal?) build unitary (or not) Q = [q1 · · · qj · · · ] ˆ = Q −1 AQ change coordinate system: A qk → Q −1 qk = ek span{q1 , . . . , qj } → span{e1 , . . . , ej } ready for next iteration
Subspace Iteration with changes of coordinate system Krylov subspaces David S. Watkins
take S = span{e1 , . . . , ej } p(A)S = span{p(A)e1 , . . . , p(A)ej } = span{q1 , . . . , qj } (orthonormal?) build unitary (or not) Q = [q1 · · · qj · · · ] ˆ = Q −1 AQ change coordinate system: A qk → Q −1 qk = ek span{q1 , . . . , qj } → span{e1 , . . . , ej } ready for next iteration
Subspace Iteration with changes of coordinate system Krylov subspaces David S. Watkins
take S = span{e1 , . . . , ej } p(A)S = span{p(A)e1 , . . . , p(A)ej } = span{q1 , . . . , qj } (orthonormal?) build unitary (or not) Q = [q1 · · · qj · · · ] ˆ = Q −1 AQ change coordinate system: A qk → Q −1 qk = ek span{q1 , . . . , qj } → span{e1 , . . . , ej } ready for next iteration
Subspace Iteration with changes of coordinate system Krylov subspaces David S. Watkins
take S = span{e1 , . . . , ej } p(A)S = span{p(A)e1 , . . . , p(A)ej } = span{q1 , . . . , qj } (orthonormal?) build unitary (or not) Q = [q1 · · · qj · · · ] ˆ = Q −1 AQ change coordinate system: A qk → Q −1 qk = ek span{q1 , . . . , qj } → span{e1 , . . . , ej } ready for next iteration
Subspace Iteration with changes of coordinate system Krylov subspaces David S. Watkins
take S = span{e1 , . . . , ej } p(A)S = span{p(A)e1 , . . . , p(A)ej } = span{q1 , . . . , qj } (orthonormal?) build unitary (or not) Q = [q1 · · · qj · · · ] ˆ = Q −1 AQ change coordinate system: A qk → Q −1 qk = ek span{q1 , . . . , qj } → span{e1 , . . . , ej } ready for next iteration
Subspace Iteration with changes of coordinate system Krylov subspaces David S. Watkins
take S = span{e1 , . . . , ej } p(A)S = span{p(A)e1 , . . . , p(A)ej } = span{q1 , . . . , qj } (orthonormal?) build unitary (or not) Q = [q1 · · · qj · · · ] ˆ = Q −1 AQ change coordinate system: A qk → Q −1 qk = ek span{q1 , . . . , qj } → span{e1 , . . . , ej } ready for next iteration
Subspace Iteration with changes of coordinate system Krylov subspaces David S. Watkins
take S = span{e1 , . . . , ej } p(A)S = span{p(A)e1 , . . . , p(A)ej } = span{q1 , . . . , qj } (orthonormal?) build unitary (or not) Q = [q1 · · · qj · · · ] ˆ = Q −1 AQ change coordinate system: A qk → Q −1 qk = ek span{q1 , . . . , qj } → span{e1 , . . . , ej } ready for next iteration
Subspace Iteration with changes of coordinate system Krylov subspaces David S. Watkins
This version of subspace iteration . . . . . . holds the subspace fixed while the matrix changes. . . . moving toward a matrix under which span{e1 , . . . , ej } is invariant. A→
A11 A12 0 A22
(A11 is j × j.)
Subspace Iteration with changes of coordinate system Krylov subspaces David S. Watkins
This version of subspace iteration . . . . . . holds the subspace fixed while the matrix changes. . . . moving toward a matrix under which span{e1 , . . . , ej } is invariant. A→
A11 A12 0 A22
(A11 is j × j.)
Subspace Iteration with changes of coordinate system Krylov subspaces David S. Watkins
This version of subspace iteration . . . . . . holds the subspace fixed while the matrix changes. . . . moving toward a matrix under which span{e1 , . . . , ej } is invariant. A→
A11 A12 0 A22
(A11 is j × j.)
Subspace Iteration with changes of coordinate system Krylov subspaces David S. Watkins
This version of subspace iteration . . . . . . holds the subspace fixed while the matrix changes. . . . moving toward a matrix under which span{e1 , . . . , ej } is invariant. A→
A11 A12 0 A22
(A11 is j × j.)
Subspace Iteration with changes of coordinate system Krylov subspaces David S. Watkins
This version of subspace iteration . . . . . . holds the subspace fixed while the matrix changes. . . . moving toward a matrix under which span{e1 , . . . , ej } is invariant. A→
A11 A12 0 A22
(A11 is j × j.)
Subspace iteration and Krylov subspaces Krylov subspaces David S. Watkins
single vector q “determines” nested sequence Kj (A, q) = span q, Aq, A2 q, . . . , Aj−1 q , j = 1, . . . , n
step of power method:
q → p(A)q . . .
implies a nested sequence of subspace iterations because ... p(A)Kj (A, q) = Kj (A, p(A)q), since p(A)A = Ap(A)
Subspace iteration and Krylov subspaces Krylov subspaces David S. Watkins
single vector q “determines” nested sequence Kj (A, q) = span q, Aq, A2 q, . . . , Aj−1 q , j = 1, . . . , n
step of power method:
q → p(A)q . . .
implies a nested sequence of subspace iterations because ... p(A)Kj (A, q) = Kj (A, p(A)q), since p(A)A = Ap(A)
Subspace iteration and Krylov subspaces Krylov subspaces David S. Watkins
single vector q “determines” nested sequence Kj (A, q) = span q, Aq, A2 q, . . . , Aj−1 q , j = 1, . . . , n
step of power method:
q → p(A)q . . .
implies a nested sequence of subspace iterations because ... p(A)Kj (A, q) = Kj (A, p(A)q), since p(A)A = Ap(A)
Subspace iteration and Krylov subspaces Krylov subspaces David S. Watkins
single vector q “determines” nested sequence Kj (A, q) = span q, Aq, A2 q, . . . , Aj−1 q , j = 1, . . . , n
step of power method:
q → p(A)q . . .
implies a nested sequence of subspace iterations because ... p(A)Kj (A, q) = Kj (A, p(A)q), since p(A)A = Ap(A)
Subspace iteration and Krylov subspaces Krylov subspaces David S. Watkins
single vector q “determines” nested sequence Kj (A, q) = span q, Aq, A2 q, . . . , Aj−1 q , j = 1, . . . , n
step of power method:
q → p(A)q . . .
implies a nested sequence of subspace iterations because ... p(A)Kj (A, q) = Kj (A, p(A)q), since p(A)A = Ap(A)
Let’s build an algorithm Krylov subspaces David S. Watkins
start with upper Hessenberg A pick shifts ρ1 , ρ2 (m = 2 for illustration) q1 = αp(A)e1 = α(A − ρ1 I )(A − ρ2 I )e1 =
x y z 0 .. . 0
cheap, don’t compute p(A). Q0 = q1 · · · qn , built from q1
Let’s build an algorithm Krylov subspaces David S. Watkins
start with upper Hessenberg A pick shifts ρ1 , ρ2 (m = 2 for illustration) q1 = αp(A)e1 = α(A − ρ1 I )(A − ρ2 I )e1 =
x y z 0 .. . 0
cheap, don’t compute p(A). Q0 = q1 · · · qn , built from q1
Let’s build an algorithm Krylov subspaces David S. Watkins
start with upper Hessenberg A pick shifts ρ1 , ρ2 (m = 2 for illustration) q1 = αp(A)e1 = α(A − ρ1 I )(A − ρ2 I )e1 =
x y z 0 .. . 0
cheap, don’t compute p(A). Q0 = q1 · · · qn , built from q1
Let’s build an algorithm Krylov subspaces David S. Watkins
start with upper Hessenberg A pick shifts ρ1 , ρ2 (m = 2 for illustration) q1 = αp(A)e1 = α(A − ρ1 I )(A − ρ2 I )e1 =
x y z 0 .. . 0
cheap, don’t compute p(A). Q0 = q1 · · · qn , built from q1
Let’s build an algorithm Krylov subspaces David S. Watkins
start with upper Hessenberg A pick shifts ρ1 , ρ2 (m = 2 for illustration) q1 = αp(A)e1 = α(A − ρ1 I )(A − ρ2 I )e1 =
x y z 0 .. . 0
cheap, don’t compute p(A). Q0 = q1 · · · qn , built from q1
Let’s build an algorithm Krylov subspaces David S. Watkins
start with upper Hessenberg A pick shifts ρ1 , ρ2 (m = 2 for illustration) q1 = αp(A)e1 = α(A − ρ1 I )(A − ρ2 I )e1 =
x y z 0 .. . 0
cheap, don’t compute p(A). Q0 = q1 · · · qn , built from q1
Let’s build an algorithm Krylov subspaces David S. Watkins
˜ = Q −1 AQ0 A 0 power method + change of coordinate system now return to Hessenberg form ˆ =Q ˜ −1 A ˜Q ˜ = Q −1 AQ A iteration complete!
Now repeat!
Let’s build an algorithm Krylov subspaces David S. Watkins
˜ = Q −1 AQ0 A 0 power method + change of coordinate system now return to Hessenberg form ˆ =Q ˜ −1 A ˜Q ˜ = Q −1 AQ A iteration complete!
Now repeat!
Let’s build an algorithm Krylov subspaces David S. Watkins
˜ = Q −1 AQ0 A 0 power method + change of coordinate system now return to Hessenberg form ˆ =Q ˜ −1 A ˜Q ˜ = Q −1 AQ A iteration complete!
Now repeat!
Let’s build an algorithm Krylov subspaces David S. Watkins
˜ = Q −1 AQ0 A 0 power method + change of coordinate system now return to Hessenberg form ˆ =Q ˜ −1 A ˜Q ˜ = Q −1 AQ A iteration complete!
Now repeat!
Let’s build an algorithm Krylov subspaces David S. Watkins
˜ = Q −1 AQ0 A 0 power method + change of coordinate system now return to Hessenberg form ˆ =Q ˜ −1 A ˜Q ˜ = Q −1 AQ A iteration complete!
Now repeat!
Let’s build an algorithm Krylov subspaces David S. Watkins
˜ = Q −1 AQ0 A 0 power method + change of coordinate system now return to Hessenberg form ˆ =Q ˜ −1 A ˜Q ˜ = Q −1 AQ A iteration complete!
Now repeat!
What does the algorithm do? Krylov subspaces David S. Watkins
ˆ = Q −1 AQ A q1 = αp(A)e1 ˆ Hessenberg, so A span{q1 , . . . , qj } = Kj (A, q1 ) = p(A)Kj (A, e1 ) = p(A)span{e1 , . . . , ej }
subspace iteration + change of coordinate system: span{q1 , . . . , qj } → span{e1 , . . . , ej }
j = 1, 2, . . . , n − 1
What does the algorithm do? Krylov subspaces David S. Watkins
ˆ = Q −1 AQ A q1 = αp(A)e1 ˆ Hessenberg, so A span{q1 , . . . , qj } = Kj (A, q1 ) = p(A)Kj (A, e1 ) = p(A)span{e1 , . . . , ej }
subspace iteration + change of coordinate system: span{q1 , . . . , qj } → span{e1 , . . . , ej }
j = 1, 2, . . . , n − 1
What does the algorithm do? Krylov subspaces David S. Watkins
ˆ = Q −1 AQ A q1 = αp(A)e1 ˆ Hessenberg, so A span{q1 , . . . , qj } = Kj (A, q1 ) = p(A)Kj (A, e1 ) = p(A)span{e1 , . . . , ej }
subspace iteration + change of coordinate system: span{q1 , . . . , qj } → span{e1 , . . . , ej }
j = 1, 2, . . . , n − 1
What does the algorithm do? Krylov subspaces David S. Watkins
ˆ = Q −1 AQ A q1 = αp(A)e1 ˆ Hessenberg, so A span{q1 , . . . , qj } = Kj (A, q1 ) = p(A)Kj (A, e1 ) = p(A)span{e1 , . . . , ej }
subspace iteration + change of coordinate system: span{q1 , . . . , qj } → span{e1 , . . . , ej }
j = 1, 2, . . . , n − 1
What does the algorithm do? Krylov subspaces David S. Watkins
ˆ = Q −1 AQ A q1 = αp(A)e1 ˆ Hessenberg, so A span{q1 , . . . , qj } = Kj (A, q1 ) = p(A)Kj (A, e1 ) = p(A)span{e1 , . . . , ej }
subspace iteration + change of coordinate system: span{q1 , . . . , qj } → span{e1 , . . . , ej }
j = 1, 2, . . . , n − 1
What does the algorithm do? Krylov subspaces David S. Watkins
ˆ = Q −1 AQ A q1 = αp(A)e1 ˆ Hessenberg, so A span{q1 , . . . , qj } = Kj (A, q1 ) = p(A)Kj (A, e1 ) = p(A)span{e1 , . . . , ej }
subspace iteration + change of coordinate system: span{q1 , . . . , qj } → span{e1 , . . . , ej }
j = 1, 2, . . . , n − 1
What does the algorithm do? Krylov subspaces David S. Watkins
ˆ = Q −1 AQ A q1 = αp(A)e1 ˆ Hessenberg, so A span{q1 , . . . , qj } = Kj (A, q1 ) = p(A)Kj (A, e1 ) = p(A)span{e1 , . . . , ej }
subspace iteration + change of coordinate system: span{q1 , . . . , qj } → span{e1 , . . . , ej }
j = 1, 2, . . . , n − 1
What does the algorithm do? Krylov subspaces David S. Watkins
Convergence rates: | p(λj+1 )/p(λj ) | j = 1, . . . , n − 1
All ratios matter.
What does the algorithm do? Krylov subspaces David S. Watkins
Convergence rates: | p(λj+1 )/p(λj ) | j = 1, . . . , n − 1
All ratios matter.
Implementation Krylov subspaces David S. Watkins
q1 = αp(A)e1 =
x y z 0 .. . 0
(case m = 2)
Implementation Krylov subspaces David S. Watkins
× × × × × × × × ×
× × × × ×
× × × × × ×
× × × × × ×
Implementation Krylov subspaces David S. Watkins
× × × × × × × × × × × × × × ×
× × × × × ×
× × × × × ×
Implementation Krylov subspaces David S. Watkins
× × × ×
× × × ×
× × × ×
× × × × ×
× × × × × ×
× × × × × ×
Implementation Krylov subspaces David S. Watkins
× × × × × × × × × × × ×
× × × × ×
× × × × × ×
× × × × × ×
Implementation Krylov subspaces David S. Watkins
× × × × × × × × × × ×
× × × × × ×
× × × × × ×
× × × × × ×
Implementation Krylov subspaces David S. Watkins
× × × × × × × × ×
× × × × × ×
× × × × × ×
× × × × × ×
Implementation Krylov subspaces David S. Watkins
× × × × × × × × ×
× × × × ×
× × × × × ×
× × × × × ×
Implementation Krylov subspaces David S. Watkins
O(n2 ) work per iteration (cheap!) This is nothing new. John Francis’s algorithm aka implicitly-shifted QR algorithm
Implementation Krylov subspaces David S. Watkins
O(n2 ) work per iteration (cheap!) This is nothing new. John Francis’s algorithm aka implicitly-shifted QR algorithm
Implementation Krylov subspaces David S. Watkins
O(n2 ) work per iteration (cheap!) This is nothing new. John Francis’s algorithm aka implicitly-shifted QR algorithm
Implementation Krylov subspaces David S. Watkins
O(n2 ) work per iteration (cheap!) This is nothing new. John Francis’s algorithm aka implicitly-shifted QR algorithm
Detail: Choice of shifts Krylov subspaces David S. Watkins
shifts? lower right-hand corner new shifts at each step ⇒ quadratic or cubic convergence Watkins (2007, 2010)
Detail: Choice of shifts Krylov subspaces David S. Watkins
shifts? lower right-hand corner new shifts at each step ⇒ quadratic or cubic convergence Watkins (2007, 2010)
Detail: Choice of shifts Krylov subspaces David S. Watkins
shifts? lower right-hand corner new shifts at each step ⇒ quadratic or cubic convergence Watkins (2007, 2010)
Detail: Choice of shifts Krylov subspaces David S. Watkins
shifts? lower right-hand corner new shifts at each step ⇒ quadratic or cubic convergence Watkins (2007, 2010)
Detail: Choice of shifts Krylov subspaces David S. Watkins
shifts? lower right-hand corner new shifts at each step ⇒ quadratic or cubic convergence Watkins (2007, 2010)
Summary Krylov subspaces David S. Watkins
derived Francis’s algorithm made use of Krylov subspaces . . . instead of implicit-Q theorem valid for nonunitary variants
Summary Krylov subspaces David S. Watkins
derived Francis’s algorithm made use of Krylov subspaces . . . instead of implicit-Q theorem valid for nonunitary variants
Summary Krylov subspaces David S. Watkins
derived Francis’s algorithm made use of Krylov subspaces . . . instead of implicit-Q theorem valid for nonunitary variants
Summary Krylov subspaces David S. Watkins
derived Francis’s algorithm made use of Krylov subspaces . . . instead of implicit-Q theorem valid for nonunitary variants
Summary Krylov subspaces David S. Watkins
derived Francis’s algorithm made use of Krylov subspaces . . . instead of implicit-Q theorem valid for nonunitary variants
Summary Krylov subspaces David S. Watkins
no QR decompositions in sight no detour via “explicit” QR algorithm Why call it the QR algorithm? I’m calling it Francis’s algorithm. end of confusion
Summary Krylov subspaces David S. Watkins
no QR decompositions in sight no detour via “explicit” QR algorithm Why call it the QR algorithm? I’m calling it Francis’s algorithm. end of confusion
Summary Krylov subspaces David S. Watkins
no QR decompositions in sight no detour via “explicit” QR algorithm Why call it the QR algorithm? I’m calling it Francis’s algorithm. end of confusion
Summary Krylov subspaces David S. Watkins
no QR decompositions in sight no detour via “explicit” QR algorithm Why call it the QR algorithm? I’m calling it Francis’s algorithm. end of confusion
Summary Krylov subspaces David S. Watkins
no QR decompositions in sight no detour via “explicit” QR algorithm Why call it the QR algorithm? I’m calling it Francis’s algorithm. end of confusion
Advertisement Krylov subspaces David S. Watkins
Publications promoting this point of view: DSW, Francis’s Algorithm, Amer. Math. Monthly (118) 2011, pp. 387–403. DSW, Fundamentals of Matrix Computations, Third Edition, John Wiley and Sons, 2010.
Advertisement Krylov subspaces David S. Watkins
Publications promoting this point of view: DSW, Francis’s Algorithm, Amer. Math. Monthly (118) 2011, pp. 387–403. DSW, Fundamentals of Matrix Computations, Third Edition, John Wiley and Sons, 2010.
Advertisement Krylov subspaces David S. Watkins
Publications promoting this point of view: DSW, Francis’s Algorithm, Amer. Math. Monthly (118) 2011, pp. 387–403. DSW, Fundamentals of Matrix Computations, Third Edition, John Wiley and Sons, 2010.
Thank you for your kind attention Krylov subspaces David S. Watkins
Photo: Frank Uhlig
View more...
Comments
