Look-Ahead Procedures for Lanczos-Type Product Methods Based on Three-Term Lanczos Recurrences.
Lanczos-type product methods for the solution of large sparse non-Hermitian linear systems either square the Lanczos process or combine it with a local minimization of the residual. They inherit from the underlying Lanczos process the danger of breakdown. For various Lanczos-type product methods that are based on the Lanczos three-term recurrence, look-ahead versions are presented which avoid such breakdowns or near-breakdowns at the cost of a small computational overhead. Different look-ahead strategies are discussed and their efficiency is demonstrated by several numerical examples.
Introduction
. Lanczos-type product methods (LTPMs) like (Bi)CGS [42],
BiCGStab [44], BiCGStab2 [22], and BiCGStab(') [38], [41] are among the most
efficient methods for solving large systems of linear equations
sparse system matrix A 2 C
N \ThetaN . Compared to the biconjugate gradient
method they have the advantage of converging roughly twice as fast and of
not requiring a routine for applying the adjoint system matrix A H to a vector. Nev-
ertheless, they inherit from BiCG the short recurrence formulas for generating the
approximations x k and the corresponding residuals r k := b \Gamma Ax k .
As for BiCG, where the convergence can be smoothed by applying the quasi-
minimal residual (QMR) method [16] or the local minimum residual process (MR
smoothing) [37], [47], product methods can be combined with the same techniques
[14], [47] to avoid the likely "erratic" convergence behavior [11], [36]; the benefit of
these smoothing techniques is disputed, however.
A well-known problem of all methods that make implicit use of the Lanczos polynomials
generated by a non-Hermitian matrix is the danger of breakdown. Although
exact breakdowns are very rare in practice, it has been observed that near-breakdowns
can slow down or even prevent convergence [15]. Look-ahead techniques for the Lanczos
process [15], [21], [23], [34], [35], [43] allow us to avoid this problem when we
use variants of the BiCG method with or without the mentioned smoothing tech-
niques. However, the general look-ahead procedures that have so far been proposed
for (Bi)CGS or other LTPMs are either limited to exact breakdowns [8], [9] or are
based on different look-ahead recursions: in fact, the look-ahead steps proposed by
Brezinski and Redivo Zaglia [5] to avoid near-breakdowns in CGS and those in [6],
which are applicable to all LTPMs, are based on the so-called BSMRZ algorithm,
which is itself based on a generalization of coupled recurrences (different from those
of the standard BiOMin and BiODir versions of the BiCG method) for implementing
the Lanczos method. For a theoretical comparison of the two approaches we refer to
[25, x 19]. Recently, a number of further "look-ahead-like" algorithms for Lanczos-
type solvers have been proposed by Ayachour [1], Brezinski et al. [7], Graves-Morris
Applied Mathematics, ETH Zurich, ETH-Zentrum HG, CH-8092 Zurich, Switzerland
(mhg@sam.math.ethz.ch). Formerly at the Swiss Center for Scientific Computing (CSCS/SCSC).
y German Aerospace Research Establishment (DLR), German Remote Sensing Data Center
(DFD), D-82234 Oberpfaffenhofen, Germany (kjr@dfd.dlr.de). Formerly also at CSCS/SCSC.
[19], and Ziegler [48]. Their discussion is beyond the scope of this paper, but it seems
that [1, 7, 48] are restricted to exact breakdowns.
In this paper, we start from the approach in [15] and [23, x 9] and derive an
alternative look-ahead procedure for LTPM algorithms that make use of the Lanczos
three-term recurrences. Compared to the standard coupled two-term recurrences they
have the advantage of being simpler to handle with regard to look-ahead, since they
are only affected by one type of breakdown. In contrast to the first version of this work
[26], we also capitalize upon an enhancement for the look-ahead Lanczos algorithm
pointed out by Hochbruck recently (see [28], [25]), which is here adapted to LTPMs.
Other improvements help to further reduce the overhead and stabilize the process.
Starting with an initial approximation x 0 and a corresponding initial residual
steps a basis of the 2n-dimensional Krylov space
in such a way that the even indexed basis vectors are of the form
where ae n is the nth Lanczos polynomial (see below) and  n is another suitably chosen
polynomial of exact degree n. In the algorithms we discuss, these vectors will be either
the residual of the nth approximation xn or a scalar multiple of it. By allowing them
to be multiples of the residuals, that is, by considering so-called unnormalized [20]
or inconsistent [25] Krylov space solvers, we avoid the occurrence of pivot (or ghost)
breakdowns. (For the various types of breakdowns and their connection to the block
structure of the Pad'e table see [20, 24, 30, 31]. In the setting of [5, 6], they have been
addressed particularly in [4].)
More generally, we define a doubly indexed sequence of product vectors w l
n by
The aim is to find in the (n 1)th step of an LTPM an improved approximation
xn+1 by computing a new product vector w n+1
n+1 from previously determined ones in a
stable way. To visualize the progression of an algorithm and the recurrences it uses
we arrange the product vectors w l
n in a w-table 1 . Its n-axis points downwards and
its l-axis to the right. We describe then how an algorithm moves in this table from
the upper left corner downwards to the right.
This paper is organized as follows. In Section 2 we review the look-ahead Lanczos
process. Versions based on the Lanczos three-term recurrences of various LTPMs are
introduced in Section 3. In Section 4 we present for these LTPMs look-ahead procedures
and analyze their computational overhead, and in Section 5 several look-ahead
strategies are discussed. Our preferred way of applying the look-ahead procedures
to obtain the solution of a linear system is presented in Section 6. In Section 7 the
efficiency of the proposed algorithms is demonstrated by numerical examples, and in
Section 8 we draw some conclusions.
2. The Look-Ahead Lanczos Process. The primary aim of the Lanczos process
[32] is the construction of a pair of biorthogonal bases for two nested sequences of
Krylov spaces. Given A 2 C
N \ThetaN and a pair of starting vectors, (ey
Biorthogonalization (BiO) Algorithm generates a pair of finite sequences, fey n g
1 The w-table is different from the scheme introduced by Sleijpen and Fokkema [38] for
BiCGstab(').
fyng
n=0 , of left and right Lanczos vectors, such that
e
and
ae
or, equivalently,
Here, h\Delta; \Deltai denotes the inner product in C
N , which we choose to be linear in the second
argument, and ? indicates the corresponding orthogonality.
The sequence of pairs of Lanczos vectors can be constructed by the three-term
recursions
with coefficients ff n and fi n that are determined from the orthogonality condition
(2.2) and nonvanishing scale factors fl n that can be chosen arbitrarily. Choosing
would allow us to consider the right Lanczos vectors yn as residuals
and to update the iterates xn particularly simply. But this choice also introduces the
possibility of a breakdown due to ff n Therefore, we suggest in Section 6 a
different way of defining iterates.
From (2.4) it follows directly that the Lanczos vectors can be written in the form
e yn=ae n
where ae n denotes the n-th Lanczos polynomial. Since we aim here at LTPMs, we
consider for the Krylov spaces e
Kn more general basis vectors of the form
e
with arbitrary, but suitably chosen polynomials  n of exact degree n and e z 0 := e y 0 . In
general, e z n+1 ? Kn+1 will no longer hold, but e
Kn+1 ? yn+1 can still be attained by
enforcing e
z means choosing the coefficients ff n and
in (2.4) in the following way: if n ? 0 we need
but since hez
When Similarly, from the orthogonality condition hez
we obtain
Equations (2.7)-(2.9) and the first recurrence of (2.4) specify what one might call the
one-sided Lanczos process, formulated in [36] to derive LTPMs.
Clearly, this recursive process terminates with y or it breaks
down with ffi
The look-ahead Lanczos process [23, x 9], [15]
overcomes such a breakdown if curable, i.e., if for some k, hez  ; A k y  i 6= 0. However,
its role is not restricted to treating such exact breakdowns with ffi
0: it allows us
to continue the biorthogonalization process whenever for stability reasons we choose
to enforce the orthogonality condition (2.2) only partially for a couple of steps. We
will come back later to the conditions that make us start such a look-ahead phase.
In the look-ahead Lanczos process the price we have to pay is that the Gramian
matrix D := (hez m ; yn i) becomes block-lower triangular instead of triangular (as in
the generic one-sided Lanczos algorithm) or diagonal (as in the generic two-sided
Lanczos algorithm). In other words, we replace the conditions e
by
e
and
nonsingular
is the subsequence of indices of (well-condi-
tioned) regular Lanczos vectors yn j
; for the other indices the vectors are called inner
vectors. Likewise, we refer to n as a regular index if while n is
called an inner index otherwise. Note that there is considerable freedom in choosing
the subsequence fn j g J
example, we might request that the smallest singular
value oe min (D j ) is sufficiently large.
The sequence fyn g is determined by the condition e
hence it does not depend directly on the sequence fez n g but only on the spaces e
that are spanned by the first n j elements of fez n g. On the other hand, the smallest
singular value of each D j depends on the basis chosen, a fact that one should take
into account. Forming the blocks
\Theta

\Theta
e
z

we can express relation (2.10) as
e
ae
The look-ahead step size is in the following denoted by h j := n
In the look-ahead case the Lanczos vectors fyng can be generated by the recursion
[23, x 9], [15]:
\Theta

denotes the not yet fully completed j-block if
is an inner index, while b
regular, that is, if . The
coefficient vector fi n is determined by the condition
thus,
e
The coefficient vector ff n can be chosen arbitrarily if n+1 is an inner index. Obviously,
the choice ff yields the cheapest recursion, but we may gain numerical stability
by choosing ff n 6= 0. On the other hand, if results from
the condition
that is
e
Recently, it was pointed out by Hochbruck [28] that the recursion (2.13) can
be simplified since the contribution of the older block Y j \Gamma1 can be represented by
multiples of a single auxiliary vector y 0
. This is due to the fact (noticed in [23])
that the matrix made up of the coefficient vectors fi n j
is of
rank one; see also [25, x 19]. This simplification has also been capitalized upon in
the look-ahead Hankel solver of Freund and Zha [17], which is closely related to the
look-ahead Lanczos algorithm.
In particular, due to (2.10) or (2.12) we have
Therefore, (2.14) simplifies to
e
Introducing the auxiliary vector
we have
e z H
so that the recurrence (2.13) becomes
and (2.15) changes to
e
(2.
3. Lanczos-Type Product Methods (LTPMs). LTPMs are based on two
ideas. The first one is to derive for a certain sequence of product vectors w l+1
recursion formulas that involve only previously computed product vectors, so that
there is no need of explicitly computing the vectors e z l and yn . By multiplying the
three-term recursion (2.4) for the right Lanczos vectors yn with  l (A) we obtain
Aw l
This recursion can be applied to move forward in the vertical direction in the w-table.
To obtain a formula for proceeding in the horizontal direction, the recursion for the
chosen polynomials  l (i) is capitalized upon in an analogous way.
The second basic idea is to rewrite the inner products that appear in the Lanczos
process in terms of product vectors:
For the coefficients ff n and fi n of (2.8) and (2.9) this results in
LTPMs still have short recurrence formulas if the polynomials  l have a short
one. In addition, they have two advantages over BiCG: first, multiplications with
the adjoint system matrix A H are avoided; second, for an appropriate choice of the
polynomials  l (i) smaller new residuals r l := w l
(A)y l can be expected because of
a further reduction of y l by the operator  l (A). Different choices of the polynomials
l (i) lead to different LTPMs. In the following we briefly review some possible choices
for these polynomials. We start with the general class where they satisfy a three-term
recursion. Since then both the 'left' polynomials  l and the `right' polynomials ae n
fulfill a three-term recursion, we say that this is the class of (3; 3)-type LTPMs.
In the following we briefly review some possible choices for these polynomials.
For a more detailed discussion and a pseudocode for the resulting algorithms we refer
to [36].
3.1. LTPMs based on a three-term recursion for f l g: BiOxCheb and
BiOxMR2. Assume the polynomials  l (i) are generated by a three-term recursion
of the form [22]
l. Note that, by induction,  l
has exact degree l and  l l. Hence, the polynomials qualify as residual
polynomials of a Krylov space method.
Multiplying yn by  l+1 (A) from the left and applying (3.3) yields the horizontal
recurrence
By applying (3.1) and (3.4) the following loop produces a new product vector w n+1
from previously calculated ones, namely w l
1), and the product Aw
also evaluated before. At the end of the loop, besides
n+1 , which will be needed in the next run through the
loop, are available.
Loop 3.1. (General (3; 3)-type LTPM)
1. Compute
n and determine fi n and ff n .
2. Use (3.1) to compute w
n+1 .
3. Compute
n+1 and determine  n and jn .
4. Use (3.4) to compute w n+1
n and w n+1
n+1 .
Next we discuss two ways of choosing the polynomials  l , that is, of specifying
the recurrence coefficients  l and j l .
One possibility is to combine the Lanczos process with the Chebyshev method
[13], [45] by choosing  l as a suitably shifted and scaled Chebyshev polynomial. This
combination was suggested in [3, 22, 44]. Let us call the resulting (3; 3)-type LTPM
BiOxCheb. It is well known that these polynomials satisfy a recurrence of the form
(3.3). After acquiring some information about the spectrum of the matrix A, for
example, by performing a few iterations with another Krylov space method, one can
determine the recursion for the scaled and shifted Chebyshev polynomials that correspond
to an ellipse surrounding the estimated spectrum [33]. However, the necessity
to provide spectral information is often seen as a drawback of this method.
Another idea is to use the coefficients  l and j l of (3.3) for locally minimizing
the norm of the new residual w l+1
l+1 . This idea is borrowed from the BiCGStab and
methods [44], [22] reviewed below:  l and j l are determined by solving
the two-dimensional minimization problem
min
Introducing the N \Theta 2 matrix B l+1 :=
\Theta
(w l

we can write (3.5)
as the least-squares problem
min
Therefore,  l and j l can be computed as the solution of the normal equations
l
In view of the two-dimensional local residual norm minimization performed at
every step (except the first one) we call this the BiOxMR2 method 2 . A version based
on coupled two-term Lanczos recurrences of this method was introduced by the first
author in a talk in Oberwolfach (April 1994). Independently it was as well proposed by
Cao [10] and by Zhang [46], whose Technical Report is dated April 1993. Zhang also
considered two-term formulas for  l and presented very favorable numerical results.
2 The letter 'x' in the name BiOxMR2 reflects the fact that the residual polynomials of this method
are the products of the Lanczos polynomials generated by the BiO process with polynomials obtained
from a successive two-dimensional minimization of the residual (MR2). Similarly, BiOxCheb means
a combination of the BiO process with a Chebyshev process.
3.2. LTPMs based on a two-term recursion for f l g: BiOStab. In Van
der Vorst's BiCGStab [44] the polynomials  l (i) are built up successively as products
of polynomials of degree 1:
Inserting here for i the system matrix A and multiplying by yn from the right yields
The coefficient  l is determined by minimizing the norm of w l+1
that is by solving the one-dimensional minimization problem
min 2C
which leads to
hAw l
hAw l
Recurrences (3.1) and (3.8) can be used to compute a new product vector w n+1
from w n
n and w n
as described in Loop 3.1 with
is calculated from (3.10). However, since (3.8) is only a two-term recurrence, there is
no need now to compute w
n+1 in substep 2 of the loop.
We call this algorithm BiOStab since it is a version of BiCGStab that is based on
the three-term recurrences of the Lanczos biorthogonalization process 3 .
3.3. BiOStab2. BiOStab2 is the version of BiCGStab2 [22] based on the three-term
Lanczos recurrences. The polynomials  l (i) satisfy the recursions
l is even;
l is odd:
Here  l may be obtained by solving the one-dimensional minimization problem (3.9),
so  l is given by (3.10). However, if j l j is small, this choice is dangerous since the
vector component needed to enlarge the Krylov space becomes negligible [38]. Then
some other value of  l should be chosen. Except for roundoff, the choice has no
effect on later steps, because  l and j l are determined by solving the two-dimensional
minimization problem (3.5).
Multiplying yn by  l+1 (A) and applying (3.11) leads to
ae
l is even
Aw l
l is odd:
3.1 applies with  is even, while  n and jn are chosen
as indicated above if n is odd. If n is even, there is no need to compute w
n+1 in
substep 2 of the loop.
3 Eijkhout [12] also proposed such a variant of BiCGStab; however, his way of computing the
Lanczos coefficients is much too complicated.
3.4. BiO-Squared (BiOS). BiOS is obtained by "squaring" the three-term
Lanczos process: among the basis vectors generated are those Krylov space vectors
that correspond to the squared Lanczos polynomials. By complementing BiOS with
a recursion for Galerkin iterates we will obtain BiOResS, a (3; 3)-type version of
Sonneveld's (2; 2)-type conjugate gradient squared (CGS ) method [42]. The method
fits into the framework of LTPMs if we identify
l
The vectors e
yn are then exactly the left Lanczos
vectors so that now yn ? e
Kn as well as e z n ? Kn is fulfilled. Thus, the coefficient ff n
in (3.2) simplifies to
and the w-table becomes symmetric since
Consequently, we have in analogy to (3.1)
Aw l
These two recursions lead to the following loop:
Loop 3.2. (BiOS)
1. Compute
n and determine fi n and ff n .
2. Use (3.1) to compute w
n+1 .
3. Compute
n+1 .
4. Use (3.16) to compute w n+1
n+1 .
Note that we exploit in substep 2 the symmetry of the w-table: the product vector
which is needed for the calculation of w n
n+1 by (3.1), is equal to w
n and need
not be stored. We also point out that (3.16) is not of the form (3.4); in particular,
the coefficients of w
n and w l
n need not sum up to 1.
4. Look-Ahead Procedures for LTPMs. Look-ahead steps in an LTPM serve
to stabilize the Lanczos process, the vertical movement in the w-table. Except for
BiOS, the recursion formulas for the horizontal movement remain the same. The
vertical movement is now in general based on the recurrence formula (2.21) for the
Lanczos vectors, but we need to replace these vectors by product vectors w l
We introduce the blocks of product vectors
c
l
\Theta

\Theta

and the auxiliary product vector w 0 l
defined by
Again c
l
is a regular index, while c W l
denotes the not yet
completed jth block if n+ 1 is an inner index. Now, multiplying (2.21) by  l (A) from
the left, we obtain
Aw l
As in Section 3, the coefficient vectors fi 0
n and, in the regular case, ff n can be
expressed in terms of the product vectors by rewriting all inner products in such a
way that the part  l
z l on the left side is transferred to the right side of the
inner product. For the diagonal blocks D j of the Gramian this yields
\Theta
and fi 0
n of (2.18) becomes
Likewise, ff n of (2.22) turns into
For advancing in the horizontal direction of the w-table we will still use (3.4), (3.8),
the combination (3.12), or (3.16). Substituting Aw
n in (4.4) according to these
formulas and letting
i be the (n n)-element of D (4.4) simplifies to
We remark that by using (4.6) instead of hez
we avoid to compute and
store the complete
block. Now only few elements of this block are needed, see

Figure

4.1 below. In this figure we display those entries w l
n and products Aw l
n in the
w-table that are needed to compute by (4.2) a new vector w l
n+1 marked by ' '.
inner case
d d d
d d d v 0
. V
A
regular case
d d d
d d d ff 0 ff
. D D V D
. D D V D
A
A
A
A
Fig. 4.1. Entries in the w-table needed for the construction of a new inner or regular vector
marked by ' ' by recurrence formula (4.2). Here, `v 0 ' indicates entries needed for w 0 l
those
for c
l
, 'd' those for those additionally required for D j . Moreover, 'ff 0 ' marks auxiliary
vectors
in the formula (4.5) for ff n , and 'A' stands for a matrix-vector
product (MV) with A in this formula. One such product also appears explicitly in (4.2).
Note that the horizontal recursions are valid for the auxiliary product vectors
example, (3.4) and (4.1) imply
while (3.8) and (4.1) provide
Thus, the auxiliary vector can be updated in the horizontal direction at the cost of
one matrix-vector product (MV) per step.
Combining the recursions for the vertical movement with those for the horizontal
movement leads to the look-ahead version of an LTPM. (Actually, we will also need
to compute approximations to the solution A \Gamma1 b of the linear system; but we defer
this till section 6). Because of the additional vectors involved in the above recurrence
formulas, it seems that such a look-ahead LTPM requires much more computational
work and storage than its unstable, standard version. However, the number of look-ahead
steps as well as the size of their blocks is small in practice, so that the overhead
is moderate. Moreover, we describe in the following for various choices of polynomials
how MVs that are needed can be computed indirectly by applying the recurrence
formulas. In the same way also the values of inner products can be obtained indirectly
at nearly no cost.
4.1. Look-ahead LTPMs based on a three-term recursion for f l g: LA-
BiOxCheb and LA-BiOxMR2. For methods incorporating a horizontal three-term
recurrence, such as BiOxCheb and BiOxMR2, applying the above principles for
look-ahead LTPMs leads to the general Loop 4.1. Note that the first four substeps are
identical in both cases. We will see in Section 5 that the decision between a regular
and an inner loop is made during substep 5.
In

Figure

4.2 we display the action of this loop in the w-table, but now we use a
different format than before, which, on the one hand specifies what has been known
before the current sweep through the loop and what is being computed in this sweep.
In particular, the following symbols and indicators are used:
ffl 'V' indicates that the corresponding product vector is already known;
ffl 'A' as `denominator' indicates that the product of the vector represented by
'V' with the matrix A was needed;
ffl a solid box around a 'fraction' means that this product by A required (or
requires) an MV;
ffl no box around a 'fraction' means that this product can be obtained by applying
a recurrence formula;
ffl a number as entry specifies in which substep of the current sweep this entry
is calculated;
ffl a prime indicates that the vector is an auxiliary one, as defined in (4.1)
(these vectors are displayed in the last row of the corresponding block of the
indicates that the product of the vector represented by
with the matrix A was needed;
ffl double primes will indicate that the vector is an auxiliary one of the type
defined in (4.11) used in LA-BiCGS (these vectors are displayed in the lower
right corner of the corresponding block of the w-table);
ffl 'S' will indicate that the vector or the MV is obtained for free due to the
symmetry of the w-table of LA-BiCGS.
Loop 4.1. (Look-ahead for (3; 3)-type LTPM.) Let  := min fn
Inner Loop: (n
1. Compute
n .
2. If n ? use (4.2) to compute
indirectly Aw n
.
3. If n
n .
4. If n  n j +3, use (3.4) to compute
indirectly Aw +1
n .
5. Use (4.2) to compute w n
n+1 .
6. Compute
n+1 and n ; jn .
7. Use (3.4) to compute w n+1
n+1 .
8. Compute
use (4.7) to
compute w 0 n+1
Regular Loop: (n
1. Compute
n .
2. If n ? use (4.2) to compute
indirectly Aw n
.
3. If n
n .
4. If n  n j +3, use (3.4) to compute
indirectly Aw +1
n .
5. Use (4.2) to compute w n
n+1 and
n+1 .
6. Compute
n+1 and n ; jn .
7. Use (3.4) to compute w n+1
n+1 .
8. Compute
according
to definition (4.1).
Inner Loop
A
A
A
A
A
A
Regular Loop
A
A
A
A
A
Inner Loop
A
A
A
A
A
A
A
A
A
A
A
A
Regular Loop
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
Fig. 4.2. Action of Loop 4.1 (Look-ahead for (3; 3)-type LTPM) in the w-table. For blocks of
different sizes an inner step (at left) and the following regular step (at right) are shown.
In the first two w-tables of Figure 4.2 we display what happens in a first inner
step (at left) and in a regular step (at right) that follows directly a regular step (so
that 1). In the second pair of w-tables of Figure 4.2 we consider an inner and a
regular step in case of a large block size. Note that the substeps 2-4 of the loop do
not appear in the first pair, and that substep 4 would still not be active in the regular
loop at the end of a look-ahead step of length h
active.
For such a look-ahead step of length h j , the cost in terms of MVs is 4h
MVs if h j ? 1. In fact, in the first substep of the h inner and the one regular
loops h j MVs are consumed; another h are needed in substep 3, further
in substep 6, and the remaining h are used in substep 6 of the
inner loops. If no look-ahead is needed, that is if h are required,
both in our procedure and in the standard one that does not allow for look-ahead.
Hence, in a step of length 2, we have 25% overhead, in a step of length 3 there is 50%
overhead, and for even longer steps, which are very rare in practice, the overhead
grows gradually towards 100%.
4.2. Look-ahead for BiOStab and BiOStab2. Since the horizontal recurrence
(3.8) for BiOStab is only a two-term one, there is no need to compute elements
of the second subdiagonal of the w-table as long as we are not in a look-ahead step.
In case of a look-ahead step, this remains true for those of these elements that lie in
a subdiagonal block, but, of course, not for those in a diagonal block. For Loop 4.1
this means that  simplifies to  := n j and that in substep 5 of a regular loop there
is no need to compute w
. All the other changes refer to equation numbers or the
coefficients  n and jn . In summary, we obtain Loop 4.2. Again the first four substeps
are the same in both cases, and the choice between them will be made in substep 5.
In

Figure

4.3 we display for this loop the two sections of w-tables that correspond to
the second pair in Figure 4.2.
Since those product vectors from Loop 4.1 that are no longer needed in Loop 4.2
were found without an extra MV before, the overhead in terms of MVs remains the
same here.
Look-ahead for BiOStab2 could be defined along the same lines, by alternating
between steps of Loop 4.1 and Loop 4.2. At this point it also becomes clear how to
obtain a look-ahead version of BiOStab('), an algorithm analogous to BiCGStab(')
of Sleijpen and Fokkema [38], but based on the three-term Lanczos process instead of
coupled two-term BiCG formulas.
4.3. Look-ahead (bi)conjugate gradient squared: LA-BiOS. For BiOS,
which will be the underlying process for our BiOResS version of BiCGS, the horizontal
recurrence (3.4) has to be substituted by the Lanczos recurrence given in (3.16), which
may need to be replaced by the look-ahead formula that is analogous to (4.2) with
l and n exchanged and with suitably defined auxiliary vectors and blocks of vectors.
But since the w-table is symmetric, we can build it up by vertical recursions only and
reflections at the diagonal.
We only formulate the recursion for w 0 l
as a horizontal one that replaces (4.7):
where now
\Theta

Recurrence (4.9) follows from the horizontal Lanczos look-ahead recurrences for computing
derived from (2.13) instead of (2.21), which can be gathered
Loop 4.2. (Look-ahead for BiOStab.)
Inner Loop: (n
1. Compute
n .
2. If n ? use (4.2) to compute
indirectly Aw n
.
3. If n
n .
4. If n  n j +3, use (3.8) to compute
indirectly Aw n j +1
n .
5. Use (4.2) to compute w n
n+1 .
6. Compute
n+1 and n .
7. Use (3.8) to compute w n+1
n+1 .
8. Compute
use (4.8) to
compute w 0 n+1
Regular Loop: (n
1. Compute
n .
2. If n ? use (4.2) to compute
indirectly Aw n
.
3. If n
n .
4. If n  n j +3, use (3.8) to compute
indirectly Aw n j +1
n .
5. Use (4.2) to compute w n
n+1 .
6. Compute
n+1 and n .
7. Use (3.8) to compute w n+1
n+1 .
8. Compute
according
to definition (4.1).
Inner Loop
A
A
A
A
A
A
A
A
A
A
A
Regular Loop
A
A
A
A
A
A
A
A
A
A
A
A
A
A
Fig. 4.3. Action of Loop 4.2 (Look-ahead for BiOStab) in the w-table. An inner step (at left)
and the following regular step (at right) are shown.
into one recurrence for these columns of W l+1
post-multiplied by
as in (4.1).
Again, (4.9) can be simplified: if we define for block and the needed values
of j the auxiliary vector
and for each l with n k  l ! n k+1 the same coefficient fi 0
l := ffi nk
l nk \Gamma1 as in (4.6),
then in view of (2.17) and (4.6),
Loop 4.3. (Look-ahead for BiOS.)
Inner Loop: (n
1. Compute
n .
2. If n  n j +2, use (4.2) to compute
indirectly Aw n
n\Gamma2 .
3. Use (4.2) to compute w n
n+1 .
4. Compute
n+1 and Aw 0 n
5. Use (4.13) to compute w 0 n+1
6. Use (4.2) to compute w n+1
n+1 .
Regular Loop: (n
1. Compute
n .
2. If n  n j +2, use (4.2) to compute
indirectly Aw n
n\Gamma2 .
3. Use (4.2) to compute w n
n+1 .
4. Compute
n+1 and Aw 0 n
5. Use (4.13) to compute w 0 n+1
6. Use definition (4.1) to compute
j and use definition
(4.11) to compute w 00 j
.
7. Use (4.2) to compute w n+1
n+1 .
8. Use definition (4.1) to compute
.
Inner Loop
A
A
A
A
A
A
A
A
VS
Regular Loop
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
Fig. 4.4. Action of Loop 4.3 (Look-ahead for BiOS) in the w-table. An inner loop (at the top)
and the following regular loop (at the bottom) are shown.
Consequently, (4.9) simplifies to
l
A step of the resulting LA-BiOS algorithm is summarized as Loop 4.3.
Here, the decision between a regular and an inner loop is made in substep 3 (which
corresponds to substep 5 in Loops 4.1 and 4.2). Now even the first five substeps of
the two versions of the loop are identical. In Figure 4.4 we display for LA-BiOS the
same pair of loops as we did in Figure 4.3 LA-BiOStab.
For a look-ahead step of length h j , the cost in terms of MVs is now 3h j MVs if
while it is only 3h As the standard, non-look-
ahead algorithm requires 2 MVs per step, this means that the overhead is at most
50%. Here, in the first substep of the h inner and the one regular loop h j MVs
are consumed, and another 2h j MVs are needed in substep 4.
4.4. Overhead for Look-Ahead. In this subsection we further discuss the
overhead of the look-ahead process in terms of MVs, inner products (IPs) and the
necessary storage of N-vectors.
First we note that all IPs required in the look-ahead algorithms have the fixed
initial vector e z 0 as their first argument. Therefore, if the second argument of an IP
was computed by a recurrence formula, then also the IP of this vector with e z 0 can be
computed indirectly by applying the same recurrence formula. Thus, only IPs of the
n i, for which Aw l
n is computed directly, need to be computed explicitly.
This means that in all algorithms the number of required IPs is equal to the number
of required MVs. We must admit, however, that such recursively computed inner
products, as well as the recursively computed matrix-vector products, may be the
source of additional roundoff, which may cause instability.
Actually, for understanding how to compute all the inner products needed, the
reader may want to introduce a ffi-table and a oe-table with entries ffi l
and oe l
Our loops and figures about generating the w-
table then hold as well for these two tables. Note that the ffi-table just contains the
transposed of the matrix D.

Table
Cost and overhead of look-ahead LTPMs when constructing a look-ahead step of length h j ? 1.
The construction of iterates is not yet included. By further capitalizing upon storage locations that
become available during a look-ahead step, the storage overhead could be reduced by roughly 50 %.
method total cost cost overhead storage overhead
(MVs, IPs) (MVs, IPs) relativ (N-vectors)
In terms of MVs, the cost of a look-ahead step of length h j ? 1 has been specified
in the previous subsection. By subtracting the cost for h j non-look-ahead steps, that
is 2h j MVs, we obtain the overhead summarized in Table 4.1. We stress that when
our algorithm has no overhead except for the necessary test of regularity,
which, if it fails, would reveal an upcoming instability and initiate a look-ahead step.
The table lists additionally the overhead in storage of N-vectors in a straightforward
implementation that is not optimized with respect to memory usage.
For comparison, we cite from page 60 of [5] or page 180 of [6] that the CGS look-ahead
procedure of Brezinski and Redivo Zaglia requires 6h
(the typical case) and 5h j +n (which means that a relatively
large look-ahead step is needed in one of the first few iterations). Therefore, compared
to our numbers, the overhead in terms of MVs is about four times (if h j is large, but
five times (if h larger than in our LA-BiOS (assuming as the basis
a standard CGS implementation requiring 2MVs per ordinary iteration). However,
we also note that, according to the above numbers, for a step without look-ahead
1), the methods of [5] and [6] need 3MVs instead of 2MVs.
5. Look-Ahead Strategies. In this section we address the delicate issue of
when to perform a look-ahead step, which means in an LTPM to decide whether the
new vertical index n+1 is a regular index or an inner index, i.e., whether the required
product vectors w l
n+1 in the (n 1)th row of the w-table should be computed as
regular or as inner vectors. Therefore, the look-ahead procedure in LTPMs serves
to stabilize the underlying Lanczos method, the vertical movement of the product
method in the w-table. Consequently, the criterion, when to carry out a look-ahead
step in an LTPM can be based on the criterion given in [15] for the Lanczos algorithm.
However, since the Lanczos vectors e yn and yn are not computed explicitly in a product
method, we need to rewrite the conditions of this criterion in terms of the product
vectors w l
. Let us first motivate these conditions.
In the case of an exact breakdown, where
e
z n 6= 0; yn 6= 0, a division by zero would occur in the next Lanczos step. The first
task of the look-ahead process is to circumvent these exact breakdowns without the
necessity of restarting the Lanczos process and loosing its superlinear convergence.
In finite precision arithmetic, exact breakdowns are very unlikely. However, near
breakdowns, where jffi
very small, may occur and cause large relative roundoff errors
in the Lanczos coefficients ff n and fi n given by (3.2). To be more precise, we recall
that the relative roundoff error in the computation of the inner product ffi
is bounded by [18, p. 64]
" denotes the roundoff unit. Thus, a small value of jffi
leads in finite precision
arithmetic to a big relative roundoff error in the computation of the inner product
n , which also causes a perturbation of the Lanczos coefficients ff n and fi n , since they
depend on ffi
respectively. The second task of the look-ahead process is
therefore, to avoid a convergence deterioration due to perturbed Lanczos coefficients.
Of course, similar roundoff effects may come up in the numerators of the formulas
(3.2) for ff n and fi n , but large relative errors in those will only be harmful if the
denominators are small too.
We would like to point out that in an LTPM the inner products ffi
n can be enlarged
to a certain extent by an appropriate adaptive choice of the polynomials  n [39, 40],
as long as h
example, considering the BiOStab case, where
we obtain, since hez
Thus, minimizing the relative roundoff error in the calculation of ffi
n is equivalent
to choosing n\Gamma1 such that it minimizes
to  OR
n i, which corresponds to the use of orthogonal
residual polynomials of degree 1 instead of minimal residual polynomials of degree 1
in the recursive definition of  l (i). Therefore, minimizing the relative roundoff error in
the inner product ffi
conflicts often with the objective of avoiding large intermediate
residuals in order to prevent the recursive residual to drift apart from the true residual
[40]. Performing a look-ahead step is then the only possible remedy.
We need now to find a criterion for deciding when a look-ahead step should be
performed so that both the above objectives can be attained. In view of the recursion
(4.2) for the product vectors in the case of look-ahead, it follows that a block can
be closed and a new product vector can be computed as regular vector only if the
diagonal blocks D j \Gamma1 and D j of the Gramian are numerically nonsingular. Thus, the
first condition that needs to be fulfilled in order to compute a new product vector
n+1 as regular vector (n
oe min (D j )  ";
where oe min (D j ) denotes the minimal singular value of the block D j . Note that this
does not mean that D j is well conditioned; it just guarantees numerical nonsingu-
larity. In practice, (5.1) can be replaced by some other condition that implies this
nonsingularity, for example by one implemented in a linear solver used for computing
in (2.19) and ff n in (2.22).
Freund et al. [15] use a second condition to guarantee that the Krylov space is
stably extended in the next Lanczos step in the sense that the basis of Lanczos vectors
is sufficiently well conditioned. In terms of product vectors, this second condition
amounts to computing, for any l, the new product vector w l
n+1 as regular vector if in
addition to (5.1) the following conditions for the coefficients ff n and fi n are fulfilled:
Here k\Deltak 1 denotes the ' 1 -norm and n(A) is an estimate for kAk which is updated
dynamically to ensure that the blocks W n
j do not become larger than a user specified
maximal size [15]. The motivation for (5.2) was to ensure that in the new regular
vector
(obtained from (4.2) with c
since n+ is regular) the component in
the new direction Aw n
n is sufficiently large, which will be the case if
n and tol 2 is a chosen tolerance.
Compared to (5.2), condition (5.3) costs additional two inner products and the
calculation of w t , which only in the regular case can be reused for the computation
of the new product vector w n
n+1 . Since we have
we could replace (5.3) by the less expensive condition
However, in an LTPM it is not possible to normalize all product vectors w l
(see
Section 6); so C is not equal to 1. Moreover, (5.5) is less strict than (5.3) and (5.2).
Since a look-ahead step is more expensive than regular steps providing the same
increase of the Krylov space dimension, a tight look-ahead criterion can save overall
computational cost. Therefore, it is reasonable to spend extra effort for it. For this
reason we favor criterion (5.3).
A drawback of (5.3) is that it does not take the angle between Aw n
n and w t into
account. If C c
should be
chosen larger than in the case where it is nearly 1. This motivates the choice
with suitably chosen constants C depending on the roundoff
unit ". This criterion requires an extra inner product and an appropriate choice for
. For many small problems C worked well, but
for larger problems we observed that C c decays dramatically with the block size.
Therefore, the probability that (5.3) with tol 2 as defined in (5.6) will be fulfilled
decreases with the block length and leads very often (especially in BiOS) to situations
where the maximal user specified block size was reached. Further investigations are
needed to see if this problem can be solved by a better choice of C 1 and C 2 or by
a more appropriate selection for ff n in the inner case, instead of using, as in [15],
2.
6. Obtaining the solution of b. So far we have only introduced various
algorithms for constructing a sequence of product vectors w l
n that provide a basis for
Km . However, our goal is to solve the linear system b. We now describe how
to accomplish this with these algorithms. There are several basic approaches to constructing
approximate solutions of linear systems from a Krylov space basis. Ours is
related to the Galerkin method, but avoids the difficulty that arises when the Galerkin
solution does not exist. (This difficulty causes, for example, the so-called pivot break-down
of the biconjugate gradient method.) Our approach is a natural generalization
of the one that lead to "unnormalized BiORes" introduced in [20] and renamed "in-
consistent BiORes" in [25]. In contrast to the BiOMin, BiODir, and BiORes versions
of the BiCG method, the inconsistent BiORes variant is not endangered by pivot
breakdowns. An alternative would be to construct approximate solutions based on
the quasi-minimal residual (QMR) approach [16]. For a combination of this approach
with LTPMs we refer the reader to [36].
Let the doubly indexed sequence of scalars
ae l
n be given by
ae l
We define a doubly indexed sequence of product iterates x l
n as follows. Starting with
an arbitrary x 0
N , we choose the initial product vector w 0
0 so that
ae 0
Here,
ae 0
1. For product iterates are now
implicitly defined by
ae l
ae l n
ae l n
if
ae l
Of course, x l
n will be constructed only when w l
is. If
ae l
it follows from (6.3) that
x l
ae l
n can be considered as an approximate solution of corresponding
residual is w l
ae l
n . In order to derive recursions for the scalars
ae l
n and the product
iterates x l
n , we introduce the blocks
\Theta
x l

\Theta
x l

\Theta
ae l
ae l

\Theta
ae l
ae l

as well as the auxiliary product iterates x 0l
auxiliary scalars
ae 0l
defined by
x 0l
ae 0l
Again, b
Then, by (6.3), (4.1), and (6.4),
ae 0l
Next, using (4.2) we conclude that
ae l
Aw l
l
Aw l
ae 0l
ae 0l
This shows that
x l
ae l
ae 0l
If we arrange the product iterates x l
n and the scalars
ae l
n in two tables analogous to
the w-table (with the n-axis pointing downwards and the l-axis to the right), these
two recursions can be used to proceed in vertical direction.
To obtain recursions for a horizontal movement, we assume first that the polynomials
are given by the normalized three-term recurrence (3.3). This covers all
algorithms described in this paper except look-ahead BiOS. Using (3.4) and (6.3) we
see that the product iterates satisfy
For the scalars
ae l
n the recursion
ae l+1
ae l
ae
are valid, but since the
polynomials  l are normalized (that is,  l all l), the scalars
ae l
n do not change
with the index l, and we have simply
ae l
ae 0
In look-ahead BiOS only one horizontal movement is explicitly computed per
step, namely in substep 5 of Loop 4.3 based on the recurrence (4.13). If we define in
analogy to (4.10) and (4.11)
\Theta
x 0nk

\Theta
x 0n

\Theta
ae 0n k
ae 0l

\Theta
ae 0n
ae

and
x
ae
recurrences for the auxiliary iterates and the corresponding scalars are given by
l
ae 0l+1
ae
l
Using for the scaling parameter fl n in (4.2) the special choice
n\Gamman
with 1m := [1
also the Lanczos polynomials ae n could be normalized (ae n
1), so that
ae l
However, as we mentioned before, some fl n might
turn out to be zero, which would lead to a so-called pivot breakdown. Moreover, to
avoid overflow or underflow, in the Lanczos process the scaling parameter fl n is often
used to normalize the Lanczos vectors yn . But since the Lanczos vectors yn are not
explicitly computed in an LTPM, we cannot base the choice of fl n here on their norm.
However, independent of the size of the blocks generated by the look-ahead process,
it is always necessary to compute the product vectors w n
n+1 in an LTPM. Therefore,
we chose here fl n to normalize w n
n+1 , that is,
7. Numerical Examples. In this section we demonstrate the practical performance
of our look-ahead versions of LTPMs in numerical examples. The tests are
restricted to BiOStab, BiOxMR2 and BiOS. The look-ahead versions of these LTPMs
are denoted by LABiOStab, LABiOxMR2, and LABiOS, respectively. For all tests
the initial iterate x used, and the iteration is terminated when the norm of
the recursive residual is less than
", the square root of the roundoff unit. The test
programs were written in FORTRAN90/95 and run on workstations with 64-bit IEEE
arithmetic. We start with small, artificially constructed model problems and move
gradually to large real-world problems.
Example 1. The following small test example was proposed by Joubert [29] and
also used by Brezinski and Redivo-Zaglia [6]:
. The Lanczos process, and hence, BiOStab, BiOxMR2,
and BiOS without look-ahead break down at step 2. On the contrary, all look-ahead
versions avoid this breakdown and converge after 4 iterations as shown in our plots
of the true residual norms kb \Gamma Ax l
ae l n
k in

Figure

7.1.
iteration number
true residual LABiOSstab1e-101e+10
iteration number
true residual LABiOxMR21e-101e+10
iteration number
true residual LABiOS
Fig. 7.1. The true residual norm history (i.e. log(kb \Gamma Ax l
ae l n
vs. n) for the linear system
defined in (7.1) solved by different LTPMs with look-ahead.
Example 2. Our second example is taken from [6], Example 5.2: the matrix
of order 400 and the right-hand side imply that the solution is
the Lanczos process, and
thus the LTPMs break down in the first iteration. Our look-ahead versions perform
two inner steps at the first and second iteration. All following iterations are regular
steps. This is a typical behavior: there are only few and short look-ahead steps, and
therefore the resulting mean overhead per iteration is nearly negligible.1e-101e+10
iteration number
true residual
Fig. 7.2. The true residual norm history (i.e. log(kb \Gamma Ax l
ae l n
vs. n) for the linear system
defined in (7.2) solved by different LTPMs with look-ahead.

Table
Indices of regular steps in LTPMs for three problems with a p-cyclic system matrix.
Example LABiOStab LABiOxMR2 LABiOS
In the next set of examples we consider p-cyclic matrices of the form
Hochbruck [27] showed that the computational work for solving a linear system with
a p-cyclic system matrix by QMR with look-ahead can be reduced by approximately
a factor 1=p (compared to a straight-forward implementation using sparse matrix-vector
multiplications with A), if the initial Lanczos vectors have only one nonzero
block conforming to the block structure of A, if the inner vectors are chosen so that
the nonzero structure of is not destroyed, and if the blocks B k are used
for generating only possibly nonzero components of the Krylov space basis. Then it
can be proven that in each cycle of p steps there are at least consecutive exact
breakdowns for p ? 2. But when using directly the system matrix A to generate the
Krylov subspace, we have only in the first cycle of p steps consecutive exact
breakdowns, while in the following cycles these will, in general, no longer persist,
but must be expected to become near-breakdowns. Therefore, such problems provide
good test examples for look-ahead algorithms.
Example 3. In this example we consider a 5-cyclic matrix with
right-hand side
and as initial left Lanczos vector we choose
entries. The convergence history for the different LTPMs
applied to this problem are shown in Figure 7.3, and the indices of the regular steps
are listed in Table 7.1. Those are found exactly where predicted.
Example 4. We move now to a bigger 4-cyclic system matrix with
is a 100 \Theta 100 matrix with random entries. The results for this
problem are shown in Figure 7.4, and the indices of the regular steps are depicted
also in Table 7.1. Again, they occur where predicted.
Example 5. Finally, we consider an 8-cyclic system matrix with B defined as
in Example 4. The convergence history plotted in Figure 7.5 shows oscillations in
the residual norm history of LABiOS, but overall LABiOS needs one iteration step
less than LABiOStab and LABiOxMR2 to fulfill the convergence condition. For
all methods the same look-ahead criterion ((5.3) with tol 2 defined as in (5.6) and
used. Especially for LABiOS the correct choice of the
look-ahead criterion seems to be crucial. While with the above values of C 1 and C 2
the breakdowns occurred only where expected, we discovered for this larger problem
Fig. 7.3. The true residual norm history (i.e. log(kb \Gamma Ax l
ae l n
vs. n) for the linear system
with the 5-cyclic system matrix defined in Example 3 solved by different LTPMs with look-ahead.
Fig. 7.4. The true residual norm history (i.e. log(kb \Gamma Ax l
ae l n
vs. n) for the linear system
with the 4-cyclic system matrix defined in Example 4 solved by different LTPMs with look-ahead.
that in BiOS the maximal user specified block length of 10 was reached very often
for which indicates, that the constructed inner vectors
become more and more linear dependent. Therefore, further investigations are needed
to figure out a better choice for the coefficient vector ff n in the inner case. For
example, following the proposal in [21], Hochbruck used in [27] a Chebyshev iteration
for the generation of the inner vectors instead of ff n
which we adapted from [15].
Example 6. In our last example we take a real world problem from the Harwell-
Fig. 7.5. The true residual norm history (i.e. log(kb \Gamma Ax l
ae l n
vs. n) for the linear system
with the 8-cyclic system matrix defined in Example 5 solved by different LTPMs with look-ahead.
Boeing Sparse Matrix Collection, namely SHERMAN1, a matrix of order 1000 with
3750 nonzero entries. The right-hand side b and the initial left Lanczos vector e
z 0
were generated as different unit vectors with random entries. Without look-ahead,
all LTPMs introduced here break down (BiOStab at step 186, BiOStab2 at step 176,
BiOxMR2 at step 145 and BiOS at step 352). On the contrary, the look-ahead
versions in combination with the look-ahead criterion (5.3) with tol 2 defined as in
converge as shown in Figure 7.6. Due to the real
spectrum of the system matrix A, there is only a slight difference in the convergence
of LABiOStab and LABiOxMR2. It was reported to us that BiCGStab(') with
and no look-ahead can handle this problem in about the same number of MVs as our
BiCGStab with look-ahead.
8. Conclusions. We have proposed look-ahead versions for various Lanczos-
type product methods that make use of the Lanczos three-term recurrences. Since
they are based on the Lanczos look-ahead version of Gutknecht [23] and Freund et al.
[15], they can handle look-ahead steps of any length and avoid steps that are longer
than needed. The algorithms proposed in this work should be easy to understand due
to the introduction of an array of product vectors, symbolically displayed in the w-
table, and the visualization of the progress in this w-table. Furthermore, the w-table
proved to be a useful tool to derive optimal variants, for which the computational
work in terms of MVs is minimized.
A variety of numerical examples demonstrate the practical performance of the
proposed algorithms. However, larger problems indicate that further work should
be directed to finding an improved look-ahead criterion that more reliably avoids
critical perturbations of the Lanczos coefficients by roundoff errors. Moreover, one
should investigate if there is a better way of constructing inner vectors than the choice
adapted from [15]. Alternatives would be to orthogonalize them within each block [2]
or to construct them by Chebyshev iteration [21]; but it is not clear if the additional
cost involved pays off.
Fig. 7.6. The true residual norm history (i.e. log(kb \Gamma Ax l
ae l n
vs. n) for a real-world
problem with the SHERMAN1 matrix from the Harwell-Boeing collection solved by different LTPMs
with look-ahead.
The look-ahead process in an LTPM stabilizes primarily the vertical movement
in the w-table, except in the BiOS algorithm where the w-table is symmetric. For
the horizontal movement it is also important to generate the Krylov space stably,
and both BiOStab2 and BiOxMR2 (in particular when suitably modified) do that
more reliably than BiCGStab, since the two-dimensional steps offer more flexibility.
This has also a lasting positive effect on the roundoff in the vertical movement. To
stabilize the horizontal movement further, a local minimal residual polynomial of
degree '  1 with an adaptive choice of ', as in BiCGStab(') could be used. A
further possibility is to adapt ' to the size h j of the current Lanczos block, which
would mean to perform in each regular step an h j -dimensional local minimization of
the residual. An alternative is to trade in the local residual minimization for a more
stable Krylov space generation whenever the former causes a problem. Yet another
possibility, indicated in Section 4.2, is to combine the Lanczos process with a hybrid
Chebyshev iteration.
It is known that in finite-precision arithmetic BiORes is usually more affected
by roundoff than the standard BiOMin version of BiCG, at least with regard to the
gap between recursively and explicitly computed residuals. Therefore, we are in the
process to extend this work to look-ahead procedures for LTPMs that are based on
coupled two-term recurrences.



--R

Avoiding the look-ahead in the Lanczos method
Nonsymmetric Lanczos and finding orthogonal polynomials associated with indefinite weights
CGM: a whole class of Lanczos-type solvers for linear systems
Breakdowns in the computation of orthogonal poly- nomials


New look-ahead Lanczos-type algorithms for linear systems
Avoiding breakdown in the CGS algorithm
Avoiding breakdown in variants of the BI-CGSTAB algorithm

A quasi-minimal residual variant of the Bi-CGSTAB algorithm for nonsymmetric systems
Working Note 78: Computational variants of the CGS and BiCGstab methods
Numerical determination of fundamental modes
A transpose-free quasi-minimal residual algorithm for non-Hermitian linear systems
An implementation of the look-ahead Lanczos algorithm for non-Hermitian matrices
QMR: a quasi-minimal residual method for non-Hermitian linear systems

Matrix Computations
"look-around Lanczos"
The unsymmetric Lanczos algorithms and their relations to Pad'e approx- imation








Generalized conjugate gradient and Lanczos methods for the solution of non-symmetric systems of linear equations


An iteration method for the solution of the eigenvalue problem of linear differential and integral operators
The Tchebyshev iteration for nonsymmetric linear systems
Reduction to tridiagonal form and minimal realizations


Scientific Computing on Vector Computers
BiCGstab(l) for linear equations involving unsymmetric matrices with complex spectrum
Maintaining convergence properties of BiCGstab methods in finite precision arithmetic

BiCGstab(l) and other hybrid Bi-CG methods

Analysis of the Look Ahead Lanczos Algorithm

Accelerating the Jacobi method for solving simultaneous equations by Chebyshev extrapolation when the eigenvalues of the iteration matrix are complex

Residual smoothing techniques for iterative methods
Generalized biorthogonal bases and tridiagonalisation of matrices
--TR
lanczos-type product methods;look-ahead;sparse linear systems;non-Hermitian matrices;iterative methods