There are various ways to improve the standard nonsymmetric Lanczos algorithm which

we now discuss brie¬‚y. A major concern here is the potential breakdowns or “near break-

downs” in the algorithm. There exist a number of approaches that have been developed to

avoid such breakdowns. Other approaches do not attempt to eliminate the breakdown, but

rather try to deal with it. The pros and cons of these strategies will be discussed after the

various existing scenarios are described.

Algorithm 7.1 will abort in line 7 whenever, T

a± q ®

i

X

¬

u¦ u ¥( ¡Y

’U

W ’U

W

u¦ u¥

This can arise in two different ways. Either one of the two vectors or van-

"U

W "U

W

ishes, or they are both nonzero, but their inner product is zero. The ¬rst case is the “lucky

¬

u¦

breakdown” scenario which has been seen for symmetric matrices. Thus, if then `

Y

W"U

¢¡

© u £§

is invariant and, as was seen in Chapter 5, the approximate solution is exact.

H

C

¥

¬ ¢¡

u¥ ©u §

If then is invariant. However, in this situation nothing can be said

QH

C

Y

W"U §

about the approximate solution for the linear system with . If the algorithm is being used

§ §

to solve a pair of linear systems, one with and a dual system with , then the approxi-

mate solution for the dual system will be exact in this case. The second scenario in which

(7.6) can occur is when neither of the two vectors is zero, but their inner product is zero.

Wilkinson (see [227], p. 389) called this a serious breakdown. Fortunately, there are cures

for this problem which allow the algorithm to continue in most cases. The corresponding

modi¬cations of the algorithm are often put under the denomination Look-Ahead Lanczos

algorithms. There are also rare cases of incurable breakdowns which will not be discussed

here (see references [161] and [206]).

The main idea of Look-Ahead variants of the Lanczos algorithm is that the pair

£ u ¥(£ u¦ u¦ u ¥(

can often be de¬ned even though the pair is not de¬ned. The al-

U

U W"U "U

W

gorithm can be pursued from that iterate as before until a new breakdown is encountered.

£ u ¥(£ u¦ u¦ u ¥(

If the pair cannot be de¬ned then the pair can be tried, and so on.

U

U #U

R R#U

To better explain the idea, it is best to refer to the connection with orthogonal polyno-

mials mentioned earlier for the symmetric case. The relationship can be extended to the

nonsymmetric case by de¬ning the bilinear form on the subspace

TT T ¢

W“ a± q ®

i

¢ ¢( W ¦X X X

§¬ §

¥

(

¡ ¡

W

Unfortunately, this is now an “inde¬nite inner product” in general since can be

¡

( ¡

T

¬

u u¦

zero or even negative. Note that there is a polynomial of degree such that

¡

X "U ¥

Wu

§

u and, in fact, the same polynomial intervenes in the equivalent expression of .

¦

¡

W W"U

µ£ „ ¢

|5¥ „yq¢| ¢ £ ¥§

5| j C§¦£¥

5

¨

£ ¡

§ "–© ¡"

§

1B

I

T

X

¬ §

u u¥ u ¡u

More precisely, there is a scalar such that . Similar to the symmetric ¡ ¡

¦

W"U W

case, the nonsymmetric Lanczos algorithm attempts to compute a sequence of polynomials

that are orthogonal with respect to the inde¬nite inner product de¬ned above. If we de¬ne

the moment matrix