Matrix Iters K¬‚ops Residual Error

F2DA 112 2736 0.46E-04 0.68E-04

F3D 78 8772 0.52E-04 0.61E-03

ORS 252 7107 0.38E-01 0.19E-03

¤ ¤A 7 §¡¤

¥

A test run of TFQMR with no preconditioning.

See Example 6.1 for the meaning of the column headers in the table. The number of

steps is slightly higher than that of BICGSTAB. Comparing with BCG, we note that each

step of BCG requires two matrix-by-vector products compared with one for TFQMR and

BICGSTAB. Thus, using the number of matrix-by-vector products as a criterion, BCG is

more expensive than TFQMR in all cases, as is shown in the “Iters” columns. If the num-

ber of steps is used as a criterion, then BCG is just slightly better for Problems 1 and 2. A

comparison is not possible for Problem 3, since the number of matrix-by-vector products

required for convergence exceeds the limit of 300. In general, the number of steps required

for convergence is similar for BICGSTAB and TFQMR. A comparison with the methods

seen in the previous chapter indicates that in many cases, GMRES will be faster if the

problem is well conditioned, resulting in a moderate number of steps required to converge.

If many steps (say, in the hundreds) are required, then BICGSTAB and TFQMR may per-

form better. If memory is not an issue, GMRES or DQGMRES, with a large number of

directions, is often the most reliable choice. The issue then is one of trading ribustness for

µ£ „ ¢

|5¥ „yq¢| ¢ £ ¥§

5| j C§¦£¥

5

¨

¢£

£ ¡

§ "–© ¡"

§

1B

I

memory usage. In general, a sound strategy is to focus on ¬nding a good preconditioner

rather than the best accelerator.

vcE—“˜lf¢ ™

—™ ™

1 Consider the following modi¬cation of the Lanczos algorithm, Algorithm 7.1. We replace line 6

by #

f # i # £ ¥ #£

¦

¥X v¢ ¥

¨£

§

v

#£ ¦

where the scalars are arbitrary. Lines 5 and 7 through 10 remain the same but line 4 in which

#

is computed must be changed.

¢#C

Show how to modify line 4 to ensure that the vector is orthogonal against the vectors

v

£¥ 5 CB0B

, for .

AAA

` #£ ¦

¨

£C

Prove that the vectors ™s and the matrix do not depend on the choice of the ™s.

¢

# £

…

¦

•” 5

Consider the simplest possible choice, namely, for all . What are the advantages

and potential dif¬culties with this choice?

2 Assume that the Lanczos algorithm does not break down before step , i.e., that it is possible

¢¢ ¦

£¢ C 0BB v C £¢

to generate . Show that and are both of full rank.

¢ AAA ¢

v v v

3 Develop a modi¬ed version of the non-Hermitian Lanczos algorithm that produces a sequence 2£C2 2£ ¥2

# §

£ ¥£C £C 5

of vectors such that each is orthogonal to every with and

¥

for all . What does the projected problem become?

4 Develop a version of the non-Hermitian Lanczos algorithm that produces a sequence of vectors

£ ¥£C

which satisfy

¢

¡ ¦

9# #£

¥ £ G3

C

¨

but such that the matrix is Hermitian tridiagonal. What does the projected problem become

¢

in this situation?

w 3 # !

¢#G 5 w 3

9 9

5 Using the notation of Section 7.1.2 prove that is orthogonal to the poly-

# #

5 ¢ G

nomials , assuming that . Show that if is orthogonalized against

! BBB0 # ! v !

AAA t ¦

E5

, the result would be orthogonal to all polynomials of degree . Derive a

t ! B0BB ! v !

AAA ¦

general Look-Ahead non-Hermitian Lanczos procedure based on this observation.

¦

I

H HI

¢ C BACB0 v C ¢ V V

6 Consider the matrices and obtained from the Lanczos ¢ ¥ BBABB v ¥

AA A A ¢

biorthogonalization algorithm. (a) What are the matrix representations of the (oblique) projector

¢ ¢ ¢

C q3 9 X q3 9 X q3 9

onto orthogonal to the subspace , and the projector onto ¥ ¥

v

¢ ¢ ¢

v v

¢ C q3

9

orthogonally to the subspace ? (b) Express a general condition for the existence ofv

¢

£ ¤

an oblique projector onto , orthogonal to . (c) How can this condition be interpreted using

the Lanczos vectors and the Lanczos algorithm?

#

7 Show a three-term recurrence satis¬ed by the residual vectors of the BCG algorithm. Include !

the ¬rst two iterates to start the recurrence. Similarly, establish a three-term recurrence for the

#

conjugate direction vectors in BCG. !

y £ w ¢ ¡y ¡|

|5 | §| ¢£

£