Francis\'s Algorithm - Mathematics - Washington State University

Francis’s Algorithm David S. Watkins Department of Mathematics Washington State University

Purdue University, November 8, 2013

David S. Watkins

Francis’s Algorithm

The Problem

Eigenvalue Problem:

Av = λv

David S. Watkins

Francis’s Algorithm

The Problem

Eigenvalue Problem:

Av = λv

Lots of applications

David S. Watkins

Francis’s Algorithm

The Problem

Eigenvalue Problem:

Av = λv

Lots of applications How to solve?

David S. Watkins

Francis’s Algorithm

The Problem

Eigenvalue Problem:

Av = λv

Lots of applications How to solve? lambda = eig(A)

David S. Watkins

Francis’s Algorithm

The Problem

Eigenvalue Problem:

Av = λv

Lots of applications How to solve? lambda = eig(A) How does eig do it?

David S. Watkins

Francis’s Algorithm

The Problem

Eigenvalue Problem:

Av = λv

Lots of applications How to solve? lambda = eig(A) How does eig do it? Francis’s algorithm,

David S. Watkins

Francis’s Algorithm

The Problem

Eigenvalue Problem:

Av = λv

Lots of applications How to solve? lambda = eig(A) How does eig do it? Francis’s algorithm, aka

David S. Watkins

Francis’s Algorithm

The Problem

Eigenvalue Problem:

Av = λv

Lots of applications How to solve? lambda = eig(A) How does eig do it? Francis’s algorithm, aka the implicitly shifted QR algorithm

David S. Watkins

Francis’s Algorithm

The Problem

Eigenvalue Problem:

Av = λv

Lots of applications How to solve? lambda = eig(A) How does eig do it? Francis’s algorithm, aka the implicitly shifted QR algorithm 50 years!

David S. Watkins

Francis’s Algorithm

The Problem

Eigenvalue Problem:

Av = λv

Lots of applications How to solve? lambda = eig(A) How does eig do it? Francis’s algorithm, aka the implicitly shifted QR algorithm 50 years! Top Ten of the century (Dongarra and Sullivan)

David S. Watkins

Francis’s Algorithm

John Francis

David S. Watkins

Francis’s Algorithm

Who is John Francis?

David S. Watkins

Francis’s Algorithm

Who is John Francis?

born near London in 1934

David S. Watkins

Francis’s Algorithm

Who is John Francis?

born near London in 1934 employed in late 50’s, Pegasus computer

David S. Watkins

Francis’s Algorithm

Who is John Francis?

born near London in 1934 employed in late 50’s, Pegasus computer linear algebra, eigenvalue routines

David S. Watkins

Francis’s Algorithm

Who is John Francis?

born near London in 1934 employed in late 50’s, Pegasus computer linear algebra, eigenvalue routines primitive computer

David S. Watkins

Francis’s Algorithm

Who is John Francis?

born near London in 1934 employed in late 50’s, Pegasus computer linear algebra, eigenvalue routines primitive computer no software

David S. Watkins

Francis’s Algorithm

Who is John Francis?

born near London in 1934 employed in late 50’s, Pegasus computer linear algebra, eigenvalue routines primitive computer no software experimented with a variety of methods

David S. Watkins

Francis’s Algorithm

Who is John Francis?

born near London in 1934 employed in late 50’s, Pegasus computer linear algebra, eigenvalue routines primitive computer no software experimented with a variety of methods invented his algorithm

David S. Watkins

Francis’s Algorithm

Who is John Francis?

born near London in 1934 employed in late 50’s, Pegasus computer linear algebra, eigenvalue routines primitive computer no software experimented with a variety of methods invented his algorithm moved on to other things (“disappeared”)

David S. Watkins

Francis’s Algorithm

Today’s Talk

David S. Watkins

Francis’s Algorithm

Today’s Talk

What is Francis’s algorithm and how should we understand it?

David S. Watkins

Francis’s Algorithm

Today’s Talk

What is Francis’s algorithm and how should we understand it? Reference: DSW, Francis’s Algorithm, Amer. Math. Monthly, 118 (2011), pp. 387–403.

David S. Watkins

Francis’s Algorithm

Today’s Talk

What is Francis’s algorithm and how should we understand it? Reference: DSW, Francis’s Algorithm, Amer. Math. Monthly, 118 (2011), pp. 387–403. Why am I still talking about this?

David S. Watkins

Francis’s Algorithm

Some History

David S. Watkins

Francis’s Algorithm

Some History

When did it all begin?

David S. Watkins

Francis’s Algorithm

Some History

When did it all begin? It’s hard to say.

David S. Watkins

Francis’s Algorithm

Some History

When did it all begin? It’s hard to say. polynomial root finding

David S. Watkins

Francis’s Algorithm

Some History

When did it all begin? It’s hard to say. polynomial root finding Babylonians

David S. Watkins

Francis’s Algorithm

Eduard Stiefel

Eduard Stiefel (1909-1978) David S. Watkins

Francis’s Algorithm

Eduard Stiefel

David S. Watkins

Francis’s Algorithm

Eduard Stiefel

conjugate gradient method (with Hestenes)

David S. Watkins

Francis’s Algorithm

Eduard Stiefel

conjugate gradient method (with Hestenes) Professor at ETH (1948)

David S. Watkins

Francis’s Algorithm

Eduard Stiefel

conjugate gradient method (with Hestenes) Professor at ETH (1948) founded Institute for Applied Mathematics (1948)

David S. Watkins

Francis’s Algorithm

Eduard Stiefel

conjugate gradient method (with Hestenes) Professor at ETH (1948) founded Institute for Applied Mathematics (1948) rented Zuse Z4 computer

David S. Watkins

Francis’s Algorithm

Eduard Stiefel

conjugate gradient method (with Hestenes) Professor at ETH (1948) founded Institute for Applied Mathematics (1948) rented Zuse Z4 computer hired a very talented assistant

David S. Watkins

Francis’s Algorithm

Heinz Rutishauser

Heinz Rutishauser (1918-1970) David S. Watkins

Francis’s Algorithm

Heinz Rutishauser

David S. Watkins

Francis’s Algorithm

Heinz Rutishauser

Ph.D. at ETH 1948 (complex analysis)

David S. Watkins

Francis’s Algorithm

Heinz Rutishauser

Ph.D. at ETH 1948 (complex analysis) went to work for Stiefel

David S. Watkins

Francis’s Algorithm

Heinz Rutishauser

Ph.D. at ETH 1948 (complex analysis) went to work for Stiefel early computing work on Zuse Z4 1950–

David S. Watkins

Francis’s Algorithm

Heinz Rutishauser

Ph.D. at ETH 1948 (complex analysis) went to work for Stiefel early computing work on Zuse Z4 1950– Problem from Stiefel:

David S. Watkins

Francis’s Algorithm

Heinz Rutishauser

Ph.D. at ETH 1948 (complex analysis) went to work for Stiefel early computing work on Zuse Z4 1950– Problem from Stiefel: Given Schwarz constants sk = y T Ak x, k = 1, 2, 3, . . . ,

David S. Watkins

Francis’s Algorithm

Heinz Rutishauser

Ph.D. at ETH 1948 (complex analysis) went to work for Stiefel early computing work on Zuse Z4 1950– Problem from Stiefel: Given Schwarz constants sk = y T Ak x, k = 1, 2, 3, . . . ,

find the eigenvalues of A.

David S. Watkins

Francis’s Algorithm

Heinz Rutishauser

Ph.D. at ETH 1948 (complex analysis) went to work for Stiefel early computing work on Zuse Z4 1950– Problem from Stiefel: Given Schwarz constants sk = y T Ak x, k = 1, 2, 3, . . . ,

find the eigenvalues of A. quotient-difference (q-d) algorithm

David S. Watkins

Francis’s Algorithm

Heinz Rutishauser

Ph.D. at ETH 1948 (complex analysis) went to work for Stiefel early computing work on Zuse Z4 1950– Problem from Stiefel: Given Schwarz constants sk = y T Ak x, k = 1, 2, 3, . . . ,

find the eigenvalues of A. quotient-difference (q-d) algorithm flexible, various formulations

David S. Watkins

Francis’s Algorithm

Heinz Rutishauser

David S. Watkins

Francis’s Algorithm

Heinz Rutishauser

q-d led to LR: Ak = Lk Rk ,

David S. Watkins

Rk Lk = Ak+1

Francis’s Algorithm

Heinz Rutishauser

q-d led to LR: Ak = Lk Rk ,

Rk Lk = Ak+1

with shifts to accelerate convergence: Ak − µk I = Lk Rk ,

David S. Watkins

Rk Lk + µk I = Ak+1

Francis’s Algorithm

Heinz Rutishauser

q-d led to LR: Ak = Lk Rk ,

Rk Lk = Ak+1

with shifts to accelerate convergence: Ak − µk I = Lk Rk ,

Rk Lk + µk I = Ak+1

NBS publication 1958

David S. Watkins

Francis’s Algorithm

John Francis

David S. Watkins

Francis’s Algorithm

John Francis

experiments in late 50’s

David S. Watkins

Francis’s Algorithm

John Francis

experiments in late 50’s influenced by Rutishauser

David S. Watkins

Francis’s Algorithm

John Francis

experiments in late 50’s influenced by Rutishauser and Wilkinson

David S. Watkins

Francis’s Algorithm

James H Wilkinson

James H Wilkinson (1919-1986) David S. Watkins

Francis’s Algorithm

John Francis

experiments in late 50’s influenced by Rutishauser and Wilkinson

David S. Watkins

Francis’s Algorithm

John Francis

experiments in late 50’s influenced by Rutishauser and Wilkinson QR algorithm: Ak − µk I = Qk Rk ,

David S. Watkins

Rk Qk + µk I = Ak+1

Francis’s Algorithm

John Francis

experiments in late 50’s influenced by Rutishauser and Wilkinson QR algorithm: Ak − µk I = Qk Rk ,

Rk Qk + µk I = Ak+1

Kublanovskaya too!

David S. Watkins

Francis’s Algorithm

Vera Kublanovskaya

Vera Kublanovskaya (1920-2012) David S. Watkins

Francis’s Algorithm

John Francis

experiments in late 50’s influenced by Rutishauser and Wilkinson QR algorithm: Ak − µk I = Qk Rk ,

Rk Qk + µk I = Ak+1

Kublanovskaya too!

David S. Watkins

Francis’s Algorithm

John Francis

experiments in late 50’s influenced by Rutishauser and Wilkinson QR algorithm: Ak − µk I = Qk Rk ,

Rk Qk + µk I = Ak+1

Kublanovskaya too! . . . but this is not “Francis’s Algorithm”

David S. Watkins

Francis’s Algorithm

Francis’s Algorithm

David S. Watkins

Francis’s Algorithm

Francis’s Algorithm

Second paper of Francis

David S. Watkins

Francis’s Algorithm

Francis’s Algorithm

Second paper of Francis real matrices

David S. Watkins

Francis’s Algorithm

Francis’s Algorithm

Second paper of Francis real matrices with complex pairs of eigenvalues

David S. Watkins

Francis’s Algorithm

Francis’s Algorithm

Second paper of Francis real matrices with complex pairs of eigenvalues complex shifts

David S. Watkins

Francis’s Algorithm

Francis’s Algorithm

Second paper of Francis real matrices with complex pairs of eigenvalues complex shifts want to stay in real arithmetic

David S. Watkins

Francis’s Algorithm

Francis’s Algorithm

Second paper of Francis real matrices with complex pairs of eigenvalues complex shifts want to stay in real arithmetic two steps at once

David S. Watkins

Francis’s Algorithm

Francis’s Algorithm

Second paper of Francis real matrices with complex pairs of eigenvalues complex shifts want to stay in real arithmetic two steps at once double-shift QR algorithm

David S. Watkins

Francis’s Algorithm

Francis’s Algorithm

Second paper of Francis real matrices with complex pairs of eigenvalues complex shifts want to stay in real arithmetic two steps at once double-shift QR algorithm radically different from basic QR

David S. Watkins

Francis’s Algorithm

Francis’s Algorithm

Second paper of Francis real matrices with complex pairs of eigenvalues complex shifts want to stay in real arithmetic two steps at once double-shift QR algorithm radically different from basic QR Usual justification: Francis’s implicit-Q theorem

David S. Watkins

Francis’s Algorithm

Francis’s Algorithm

David S. Watkins

Francis’s Algorithm

Francis’s Algorithm

upper Hessenberg form

David S. Watkins

Francis’s Algorithm

Francis’s Algorithm

upper Hessenberg form pick some shifts ρ1 , . . . , ρm

David S. Watkins

(m = 1, 2, 4, 6)

Francis’s Algorithm

Francis’s Algorithm

upper Hessenberg form pick some shifts ρ1 , . . . , ρm

(m = 1, 2, 4, 6)

p(A) = (A − ρ1 I ) · · · (A − ρm I )

David S. Watkins

Francis’s Algorithm

Francis’s Algorithm

upper Hessenberg form pick some shifts ρ1 , . . . , ρm

(m = 1, 2, 4, 6)

p(A) = (A − ρ1 I ) · · · (A − ρm I )

David S. Watkins

expensive!

Francis’s Algorithm

Francis’s Algorithm

upper Hessenberg form pick some shifts ρ1 , . . . , ρm

(m = 1, 2, 4, 6)

p(A) = (A − ρ1 I ) · · · (A − ρm I )

expensive!

compute p(A)e1

David S. Watkins

Francis’s Algorithm

Francis’s Algorithm

upper Hessenberg form pick some shifts ρ1 , . . . , ρm

(m = 1, 2, 4, 6)

p(A) = (A − ρ1 I ) · · · (A − ρm I ) compute p(A)e1

expensive!

cheap!

David S. Watkins

Francis’s Algorithm

Francis’s Algorithm

upper Hessenberg form pick some shifts ρ1 , . . . , ρm

(m = 1, 2, 4, 6)

p(A) = (A − ρ1 I ) · · · (A − ρm I ) compute p(A)e1

expensive!

cheap!

Build unitary Q0 with q1 = αp(A)e1 .

David S. Watkins

Francis’s Algorithm

Francis’s Algorithm

upper Hessenberg form pick some shifts ρ1 , . . . , ρm

(m = 1, 2, 4, 6)

p(A) = (A − ρ1 I ) · · · (A − ρm I ) compute p(A)e1

expensive!

cheap!

Build unitary Q0 with q1 = αp(A)e1 . Perform similarity transform A → Q0−1 AQ0 .

David S. Watkins

Francis’s Algorithm

Francis’s Algorithm

upper Hessenberg form pick some shifts ρ1 , . . . , ρm

(m = 1, 2, 4, 6)

p(A) = (A − ρ1 I ) · · · (A − ρm I ) compute p(A)e1

expensive!

cheap!

Build unitary Q0 with q1 = αp(A)e1 . Perform similarity transform A → Q0−1 AQ0 . Hessenberg form is disturbed.

David S. Watkins

Francis’s Algorithm

An Upper Hessenberg Matrix

@ @ @ @ @ @ @ @ @ @ @ @ @

David S. Watkins

Francis’s Algorithm

After the Transformation (Q0−1 AQ0 )

@ @ @ @ @ @ @ @ @ @

David S. Watkins

Francis’s Algorithm

After the Transformation (Q0−1 AQ0 )

@ @ @ @ @ @ @ @ @ @

Now return the matrix to Hessenberg form.

David S. Watkins

Francis’s Algorithm

Chasing the Bulge

@ @ @ @

@ @ @ @ @ @ @

David S. Watkins

Francis’s Algorithm

Chasing the Bulge

@ @ @ @ @ @ @

@ @ @

David S. Watkins

Francis’s Algorithm

Done

@ @ @ @ @ @ @ @ @ @ @ @ @

David S. Watkins

Francis’s Algorithm

Done

@ @ @ @ @ @ @ @ @ @ @ @ @

The Francis iteration is complete!

David S. Watkins

Francis’s Algorithm

Summary of Francis Iteration

David S. Watkins

Francis’s Algorithm

Summary of Francis Iteration

Pick some shifts.

David S. Watkins

Francis’s Algorithm

Summary of Francis Iteration

Pick some shifts. Compute p(A)e1 .

(p determined by shifts)

David S. Watkins

Francis’s Algorithm

Summary of Francis Iteration

Pick some shifts. Compute p(A)e1 .

(p determined by shifts)

Build Q0 with first column q1 = αp(A)e1 .

David S. Watkins

Francis’s Algorithm

Summary of Francis Iteration

Pick some shifts. Compute p(A)e1 .

(p determined by shifts)

Build Q0 with first column q1 = αp(A)e1 . Make a bulge.

(A → Q0−1 AQ0 )

David S. Watkins

Francis’s Algorithm

Summary of Francis Iteration

Pick some shifts. Compute p(A)e1 .

(p determined by shifts)

Build Q0 with first column q1 = αp(A)e1 . Make a bulge. Chase the bulge.

(A → Q0−1 AQ0 ) (return to Hessenberg form)

David S. Watkins

Francis’s Algorithm

Summary of Francis Iteration

Pick some shifts. Compute p(A)e1 .

(p determined by shifts)

Build Q0 with first column q1 = αp(A)e1 . Make a bulge. Chase the bulge. ˆ = Q −1 AQ A

(A → Q0−1 AQ0 ) (return to Hessenberg form)

David S. Watkins

Francis’s Algorithm

Quicker Summary

David S. Watkins

Francis’s Algorithm

Quicker Summary

Make a bulge.

David S. Watkins

Francis’s Algorithm

Quicker Summary

Make a bulge. Chase it.

David S. Watkins

Francis’s Algorithm

Remarks

David S. Watkins

Francis’s Algorithm

Remarks

This is pretty simple.

David S. Watkins

Francis’s Algorithm

Remarks

This is pretty simple. no QR decomposition in sight!

David S. Watkins

Francis’s Algorithm

Remarks

This is pretty simple. no QR decomposition in sight! Why call it the QR algorithm?

David S. Watkins

Francis’s Algorithm

Remarks

This is pretty simple. no QR decomposition in sight! Why call it the QR algorithm? Confusion!

David S. Watkins

Francis’s Algorithm

Remarks

This is pretty simple. no QR decomposition in sight! Why call it the QR algorithm? Confusion! Can we think of another name?

David S. Watkins

Francis’s Algorithm

Remarks

This is pretty simple. no QR decomposition in sight! Why call it the QR algorithm? Confusion! Can we think of another name? I’m calling it Francis’s Algorithm.

David S. Watkins

Francis’s Algorithm

Remarks

This is pretty simple. no QR decomposition in sight! Why call it the QR algorithm? Confusion! Can we think of another name? I’m calling it Francis’s Algorithm. This is not a radical move.

David S. Watkins

Francis’s Algorithm

Question

David S. Watkins

Francis’s Algorithm

Question

How should we view Francis’s algorithm?

David S. Watkins

Francis’s Algorithm

Question

How should we view Francis’s algorithm? Do we have to start with the basic QR algorithm?

David S. Watkins

Francis’s Algorithm

Question

How should we view Francis’s algorithm? Do we have to start with the basic QR algorithm? Couldn’t we just as well introduce Francis’s algorithm directly?

David S. Watkins

Francis’s Algorithm

Question

How should we view Francis’s algorithm? Do we have to start with the basic QR algorithm? Couldn’t we just as well introduce Francis’s algorithm directly? . . . bypassing the basic QR algorithm entirely?

David S. Watkins

Francis’s Algorithm

Question

How should we view Francis’s algorithm? Do we have to start with the basic QR algorithm? Couldn’t we just as well introduce Francis’s algorithm directly? . . . bypassing the basic QR algorithm entirely? . . . and the answer is:

David S. Watkins

Francis’s Algorithm

Question

How should we view Francis’s algorithm? Do we have to start with the basic QR algorithm? Couldn’t we just as well introduce Francis’s algorithm directly? . . . bypassing the basic QR algorithm entirely? . . . and the answer is: Why not?

David S. Watkins

Francis’s Algorithm

Question

How should we view Francis’s algorithm? Do we have to start with the basic QR algorithm? Couldn’t we just as well introduce Francis’s algorithm directly? . . . bypassing the basic QR algorithm entirely? . . . and the answer is: Why not? This simplifies the presentation.

David S. Watkins

Francis’s Algorithm

Question

How should we view Francis’s algorithm? Do we have to start with the basic QR algorithm? Couldn’t we just as well introduce Francis’s algorithm directly? . . . bypassing the basic QR algorithm entirely? . . . and the answer is: Why not? This simplifies the presentation. I’m putting my money where my mouth is.

David S. Watkins

Francis’s Algorithm

David S. Watkins

Francis’s Algorithm

I’m putting my money where my mouth is . . .

David S. Watkins

Francis’s Algorithm

I’m putting my money where my mouth is . . . . . . and saving one entire section!

David S. Watkins

Francis’s Algorithm

Pedagogical Pathway

David S. Watkins

Francis’s Algorithm

Pedagogical Pathway

reduction to Hessenberg form

David S. Watkins

Francis’s Algorithm

Pedagogical Pathway

reduction to Hessenberg form Francis’s algorithm

David S. Watkins

Francis’s Algorithm

Pedagogical Pathway

reduction to Hessenberg form Francis’s algorithm Try it out!

David S. Watkins

Francis’s Algorithm

Pedagogical Pathway

reduction to Hessenberg form Francis’s algorithm Try it out! It works great!

David S. Watkins

Francis’s Algorithm

Pedagogical Pathway

reduction to Hessenberg form Francis’s algorithm Try it out! It works great! Why does it work?

David S. Watkins

Francis’s Algorithm

Ingredients of Francis’s Algorithm

David S. Watkins

Francis’s Algorithm

Ingredients of Francis’s Algorithm

subspace iteration

(power method)

David S. Watkins

Francis’s Algorithm

Ingredients of Francis’s Algorithm

subspace iteration

(power method)

subspace iteration with changes of coordinate system

David S. Watkins

Francis’s Algorithm

Ingredients of Francis’s Algorithm

subspace iteration

(power method)

subspace iteration with changes of coordinate system Krylov subspaces

David S. Watkins

Francis’s Algorithm

Ingredients of Francis’s Algorithm

subspace iteration

(power method)

subspace iteration with changes of coordinate system Krylov subspaces (instead of the implicit-Q theorem)

David S. Watkins

Francis’s Algorithm

Ingredients of Francis’s Algorithm

subspace iteration

(power method)

subspace iteration with changes of coordinate system Krylov subspaces (instead of the implicit-Q theorem) Krylov subspaces and subspace iteration

David S. Watkins

Francis’s Algorithm

Ingredients of Francis’s Algorithm

subspace iteration

(power method)

subspace iteration with changes of coordinate system Krylov subspaces (instead of the implicit-Q theorem) Krylov subspaces and subspace iteration Krylov subspaces and Hessenberg form

David S. Watkins

Francis’s Algorithm

Power Method, Subspace Iteration

David S. Watkins

Francis’s Algorithm

Power Method, Subspace Iteration

v , Av , A2 v , A3 v , . . .

David S. Watkins

Francis’s Algorithm

Power Method, Subspace Iteration

v , Av , A2 v , A3 v , . . . convergence rate | λ2 /λ1 |

David S. Watkins

Francis’s Algorithm

Power Method, Subspace Iteration

v , Av , A2 v , A3 v , . . . convergence rate | λ2 /λ1 | S, AS, A2 S, A3 S, . . .

David S. Watkins

Francis’s Algorithm

Power Method, Subspace Iteration

v , Av , A2 v , A3 v , . . . convergence rate | λ2 /λ1 | S, AS, A2 S, A3 S, . . . subspaces of dimension j

David S. Watkins

Francis’s Algorithm

Power Method, Subspace Iteration

v , Av , A2 v , A3 v , . . . convergence rate | λ2 /λ1 | S, AS, A2 S, A3 S, . . . subspaces of dimension j

David S. Watkins

(| λj+1 /λj |)

Francis’s Algorithm

Power Method, Subspace Iteration

v , Av , A2 v , A3 v , . . . convergence rate | λ2 /λ1 | S, AS, A2 S, A3 S, . . . subspaces of dimension j

(| λj+1 /λj |)

Substitute p(A) for A

David S. Watkins

Francis’s Algorithm

Power Method, Subspace Iteration

v , Av , A2 v , A3 v , . . . convergence rate | λ2 /λ1 | S, AS, A2 S, A3 S, . . . (| λj+1 /λj |)

subspaces of dimension j Substitute p(A) for A

(shifts, multiple steps)

David S. Watkins

Francis’s Algorithm

Power Method, Subspace Iteration

v , Av , A2 v , A3 v , . . . convergence rate | λ2 /λ1 | S, AS, A2 S, A3 S, . . . (| λj+1 /λj |)

subspaces of dimension j Substitute p(A) for A S, p(A)S,

p(A)2 S,

(shifts, multiple steps)

p(A)3 S,

David S. Watkins

...

Francis’s Algorithm

Power Method, Subspace Iteration

v , Av , A2 v , A3 v , . . . convergence rate | λ2 /λ1 | S, AS, A2 S, A3 S, . . . (| λj+1 /λj |)

subspaces of dimension j Substitute p(A) for A S, p(A)S,

p(A)2 S,

(shifts, multiple steps)

p(A)3 S,

...

convergence rate | p(λj+1 )/p(λj ) |

David S. Watkins

Francis’s Algorithm

Subspace Iteration with changes of coordinate system

David S. Watkins

Francis’s Algorithm

Subspace Iteration with changes of coordinate system

take S = span{e1 , . . . , ej }

David S. Watkins

Francis’s Algorithm

Subspace Iteration with changes of coordinate system

take S = span{e1 , . . . , ej } p(A)S = span{p(A)e1 , . . . , p(A)ej } = span{q1 , . . . , qj } (orthonormal)

David S. Watkins

Francis’s Algorithm

Subspace Iteration with changes of coordinate system

take S = span{e1 , . . . , ej } p(A)S = span{p(A)e1 , . . . , p(A)ej } = span{q1 , . . . , qj } (orthonormal) build unitary Q = [q1 · · · qj · · · ]

David S. Watkins

Francis’s Algorithm

Subspace Iteration with changes of coordinate system

take S = span{e1 , . . . , ej } p(A)S = span{p(A)e1 , . . . , p(A)ej } = span{q1 , . . . , qj } (orthonormal) build unitary Q = [q1 · · · qj · · · ] ˆ = Q −1 AQ change coordinate system: A

David S. Watkins

Francis’s Algorithm

Subspace Iteration with changes of coordinate system

take S = span{e1 , . . . , ej } p(A)S = span{p(A)e1 , . . . , p(A)ej } = span{q1 , . . . , qj } (orthonormal) build unitary Q = [q1 · · · qj · · · ] ˆ = Q −1 AQ change coordinate system: A qk → Q −1 qk = Q ∗ qk = ek

David S. Watkins

Francis’s Algorithm

Subspace Iteration with changes of coordinate system

take S = span{e1 , . . . , ej } p(A)S = span{p(A)e1 , . . . , p(A)ej } = span{q1 , . . . , qj } (orthonormal) build unitary Q = [q1 · · · qj · · · ] ˆ = Q −1 AQ change coordinate system: A qk → Q −1 qk = Q ∗ qk = ek span{q1 , . . . , qj } → span{e1 , . . . , ej }

David S. Watkins

Francis’s Algorithm

Subspace Iteration with changes of coordinate system

take S = span{e1 , . . . , ej } p(A)S = span{p(A)e1 , . . . , p(A)ej } = span{q1 , . . . , qj } (orthonormal) build unitary Q = [q1 · · · qj · · · ] ˆ = Q −1 AQ change coordinate system: A qk → Q −1 qk = Q ∗ qk = ek span{q1 , . . . , qj } → span{e1 , . . . , ej } ready for next iteration

David S. Watkins

Francis’s Algorithm

This version of subspace iteration . . .

David S. Watkins

Francis’s Algorithm

This version of subspace iteration . . . . . . holds the subspace fixed

David S. Watkins

Francis’s Algorithm

This version of subspace iteration . . . . . . holds the subspace fixed while the matrix changes.

David S. Watkins

Francis’s Algorithm

This version of subspace iteration . . . . . . holds the subspace fixed while the matrix changes. . . . moving toward a matrix under which span{e1 , . . . , ej } is invariant.

David S. Watkins

Francis’s Algorithm

This version of subspace iteration . . . . . . holds the subspace fixed while the matrix changes. . . . moving toward a matrix under which span{e1 , . . . , ej } is invariant.   A11 A12 A→ 0 A22

(A11 is j × j.)

David S. Watkins

Francis’s Algorithm

Application to Francis’s Iteration (first pass)

David S. Watkins

Francis’s Algorithm

Application to Francis’s Iteration (first pass)

ˆ = Q −1 AQ A

where

David S. Watkins

q1 = αp(A)e1 .

Francis’s Algorithm

Application to Francis’s Iteration (first pass)

ˆ = Q −1 AQ A

where

q1 = αp(A)e1 .

power method

David S. Watkins

Francis’s Algorithm

Application to Francis’s Iteration (first pass)

ˆ = Q −1 AQ A

where

q1 = αp(A)e1 .

power method + change of coordinates

David S. Watkins

Francis’s Algorithm

Application to Francis’s Iteration (first pass)

ˆ = Q −1 AQ A

where

q1 = αp(A)e1 .

power method + change of coordinates q1 → Q −1 q1 = e1

David S. Watkins

Francis’s Algorithm

Application to Francis’s Iteration (first pass)

ˆ = Q −1 AQ A

where

q1 = αp(A)e1 .

power method + change of coordinates q1 → Q −1 q1 = e1 case j = 1 of subspace iteration with a change of coordinate system

David S. Watkins

Francis’s Algorithm

Application to Francis’s Iteration (first pass)

ˆ = Q −1 AQ A

where

q1 = αp(A)e1 .

power method + change of coordinates q1 → Q −1 q1 = e1 case j = 1 of subspace iteration with a change of coordinate system . . . but this is just a small part of the story.

David S. Watkins

Francis’s Algorithm

Krylov Subspaces and Subspace Iteration

David S. Watkins

Francis’s Algorithm

Krylov Subspaces and Subspace Iteration

 Def: Kj (A, q) = span q, Aq, A2 q, . . . , Aj−1 q

David S. Watkins

Francis’s Algorithm

Krylov Subspaces and Subspace Iteration

 Def: Kj (A, q) = span q, Aq, A2 q, . . . , Aj−1 q j = 1, 2, 3, . . . (nested subspaces)

David S. Watkins

Francis’s Algorithm

Krylov Subspaces and Subspace Iteration

 Def: Kj (A, q) = span q, Aq, A2 q, . . . , Aj−1 q j = 1, 2, 3, . . . (nested subspaces) Kj (A, q) are “determined by q”.

David S. Watkins

Francis’s Algorithm

Krylov Subspaces and Subspace Iteration

 Def: Kj (A, q) = span q, Aq, A2 q, . . . , Aj−1 q j = 1, 2, 3, . . . (nested subspaces) Kj (A, q) are “determined by q”. p(A)Kj (A, q) = Kj (A, p(A)q)

David S. Watkins

Francis’s Algorithm

Krylov Subspaces and Subspace Iteration

 Def: Kj (A, q) = span q, Aq, A2 q, . . . , Aj−1 q j = 1, 2, 3, . . . (nested subspaces) Kj (A, q) are “determined by q”. p(A)Kj (A, q) = Kj (A, p(A)q) . . . because p(A)A = Ap(A)

David S. Watkins

Francis’s Algorithm

Krylov Subspaces and Subspace Iteration

 Def: Kj (A, q) = span q, Aq, A2 q, . . . , Aj−1 q j = 1, 2, 3, . . . (nested subspaces) Kj (A, q) are “determined by q”. p(A)Kj (A, q) = Kj (A, p(A)q) . . . because p(A)A = Ap(A) Conclusion: Power method induces nested subspace iterations on Krylov subspaces.

David S. Watkins

Francis’s Algorithm

power method:

q → p(A)k q

David S. Watkins

Francis’s Algorithm

power method:

q → p(A)k q

nested subspace iterations: p(A)k Kj (A, q) = Kj (A, p(A)k q) j = 1, 2, 3, . . .

David S. Watkins

Francis’s Algorithm

power method:

q → p(A)k q

nested subspace iterations: p(A)k Kj (A, q) = Kj (A, p(A)k q) j = 1, 2, 3, . . .

convergence rates: | p(λj+1 )/p(λj ) |,

David S. Watkins

j = 1, 2, 3, . . . , n − 1

Francis’s Algorithm

Krylov Subspaces and Hessenberg matrices . . .

David S. Watkins

Francis’s Algorithm

Krylov Subspaces and Hessenberg matrices . . .

. . . go hand in hand.

David S. Watkins

Francis’s Algorithm

Krylov Subspaces and Hessenberg matrices . . .

. . . go hand in hand. A properly upper Hessenberg =⇒ Kj (A, e1 ) = span{e1 , . . . , ej }.

David S. Watkins

Francis’s Algorithm

Krylov Subspaces and Hessenberg matrices . . .

. . . go hand in hand. A properly upper Hessenberg =⇒ Kj (A, e1 ) = span{e1 , . . . , ej }.

More generally . . .

David S. Watkins

Francis’s Algorithm

Krylov-Hessenberg Relationship

David S. Watkins

Francis’s Algorithm

Krylov-Hessenberg Relationship

ˆ = Q −1 AQ, If A

David S. Watkins

Francis’s Algorithm

Krylov-Hessenberg Relationship

ˆ = Q −1 AQ, If A ˆ is properly upper Hessenberg, and A

David S. Watkins

Francis’s Algorithm

Krylov-Hessenberg Relationship

ˆ = Q −1 AQ, If A ˆ is properly upper Hessenberg, and A then for j = 1, 2, 3, . . . ,

David S. Watkins

Francis’s Algorithm

Krylov-Hessenberg Relationship

ˆ = Q −1 AQ, If A ˆ is properly upper Hessenberg, and A then for j = 1, 2, 3, . . . , span{q1 , . . . , qj } = Kj (A, q1 ).

David S. Watkins

Francis’s Algorithm

Application to Francis’s Iteration

David S. Watkins

Francis’s Algorithm

Application to Francis’s Iteration

ˆ = Q −1 AQ A

where

David S. Watkins

q1 = αp(A)e1 .

Francis’s Algorithm

Application to Francis’s Iteration

ˆ = Q −1 AQ A

where

q1 = αp(A)e1 .

power method with a change of coordinate system.

David S. Watkins

Francis’s Algorithm

Application to Francis’s Iteration

ˆ = Q −1 AQ A

where

q1 = αp(A)e1 .

power method with a change of coordinate system. Moreover ...

David S. Watkins

Francis’s Algorithm

Application to Francis’s Iteration

ˆ = Q −1 AQ A

where

q1 = αp(A)e1 .

power method with a change of coordinate system. Moreover ... p(A)Kj (A, e1 ) = Kj (A, p(A)e1 )

David S. Watkins

Francis’s Algorithm

Application to Francis’s Iteration

ˆ = Q −1 AQ A

where

q1 = αp(A)e1 .

power method with a change of coordinate system. Moreover ... p(A)Kj (A, e1 ) = Kj (A, p(A)e1 ) i.e. p(A)span{e1 , . . . , ej } = span{q1 , . . . , qj }

David S. Watkins

Francis’s Algorithm

Application to Francis’s Iteration

ˆ = Q −1 AQ A

where

q1 = αp(A)e1 .

power method with a change of coordinate system. Moreover ... p(A)Kj (A, e1 ) = Kj (A, p(A)e1 ) i.e. p(A)span{e1 , . . . , ej } = span{q1 , . . . , qj } subspace iteration with a change of coordinate system

David S. Watkins

Francis’s Algorithm

Application to Francis’s Iteration

ˆ = Q −1 AQ A

where

q1 = αp(A)e1 .

power method with a change of coordinate system. Moreover ... p(A)Kj (A, e1 ) = Kj (A, p(A)e1 ) i.e. p(A)span{e1 , . . . , ej } = span{q1 , . . . , qj } subspace iteration with a change of coordinate system for j = 1, 2, 3, . . . , n − 1

David S. Watkins

Francis’s Algorithm

Application to Francis’s Iteration

ˆ = Q −1 AQ A

where

q1 = αp(A)e1 .

power method with a change of coordinate system. Moreover ... p(A)Kj (A, e1 ) = Kj (A, p(A)e1 ) i.e. p(A)span{e1 , . . . , ej } = span{q1 , . . . , qj } subspace iteration with a change of coordinate system for j = 1, 2, 3, . . . , n − 1 | p(λj+1 )/p(λj ) |

j = 1, 2, 3, . . . , n − 1

David S. Watkins

Francis’s Algorithm

Details

David S. Watkins

Francis’s Algorithm

Details

choice of shifts

David S. Watkins

Francis’s Algorithm

Details

choice of shifts We change the shifts at each step.

David S. Watkins

Francis’s Algorithm

Details

choice of shifts We change the shifts at each step. ⇒ quadratic or cubic convergence

David S. Watkins

Francis’s Algorithm

Details

choice of shifts We change the shifts at each step. ⇒ quadratic or cubic convergence Watkins (2007, 2010)

David S. Watkins

Francis’s Algorithm

Where is John Francis?

David S. Watkins

Francis’s Algorithm

Where is John Francis?

question asked frequently by Gene Golub

David S. Watkins

Francis’s Algorithm

Where is John Francis?

question asked frequently by Gene Golub inquiries by Golub and Frank Uhlig

David S. Watkins

Francis’s Algorithm

Where is John Francis?

question asked frequently by Gene Golub inquiries by Golub and Frank Uhlig Francis is alive and well, retired in the South of England.

David S. Watkins

Francis’s Algorithm

Where is John Francis?

question asked frequently by Gene Golub inquiries by Golub and Frank Uhlig Francis is alive and well, retired in the South of England. was unaware of the impact of his algorithm

David S. Watkins

Francis’s Algorithm

Where is John Francis?

question asked frequently by Gene Golub inquiries by Golub and Frank Uhlig Francis is alive and well, retired in the South of England. was unaware of the impact of his algorithm appearance at the Biennial Numerical Analysis Conference in Glasgow in June of 2009

David S. Watkins

Francis’s Algorithm

John Francis speaking in Glasgow

David S. Watkins

Francis’s Algorithm

A Portion of the Audience

David S. Watkins

Francis’s Algorithm

Afterwards

Photos courtesy of Frank Uhlig David S. Watkins

Francis’s Algorithm