Preconditioners for Ill-Conditioned Toeplitz Systems Constructed from Positive Kernels.
In this paper, we are interested in the iterative solution of ill-conditioned Toeplitz systems generated by continuous nonnegative real-valued functions f with a finite number of zeros. We construct new w-circulant preconditioners without explicit knowledge of the generating function f by approximating f by its convolution f * KN with a suitable positive reproducing kernel KN. By the restriction to positive kernels we obtain positive definite preconditioners. Moreover, if f has only zeros of even order $\le 2s$, then we can prove that the property $ \int_{-\pi}^{\pi} t^{2k} K_N (t) \, \mbox{d} t \le C N^{-2k} $ $(k=0,\hspace*{1.5pt}\ldots,s)$ of the kernel is necessary and sufficient to ensure the convergence of the PCG method in a number of iteration steps independent of the dimension N of the system. Our theoretical results were confirmed by numerical tests.
Introduction
In this paper, we are concerned with the iterative solution of sequences of \mildly" ill{
conditioned Toeplitz systems
are positive denite Hermitian Toeplitz matrices generated by a continuous
non{negative function f which has only a nite number of zeros. Often these systems
are obtained by discretization of continuous problems (partial dierential equation, integral
equation with weakly singular kernel) and the dimension N is related to the grid parameter
of the discretization. For further applications see [12] and the references therein.
Iterative solution methods for Toeplitz systems, in particular the conjugate gradient method
(CG{method), have attained much attention during the last years. The reason for this is that
the essential computational eort per iteration step, namely the multiplication of a vector
with the Toeplitz matrix AN , can be reduced to O(N log N) arithmetical operations by fast
Fourier transforms (FFT). However, the number of iteration steps depends on the distribution
of the eigenvalues of AN . If we allow the generating function f to have isolated zeros,
then the condition numbers of the related Toeplitz matrices grow polynomial with N and the
CG{method converges very slow [8, 28, 45]. Therefore, the really task consists in the construction
of suitable preconditioners M N of AN so that the number of iteration steps of the
corresponding preconditioned CG{method (PCG{method) becomes independent of N . Here
it is useful to recall a result of O. Axelsson [1, p. 573] relating the spectrum of the coe-cient
matrix to the number of iteration steps to achieve a prescribed precision:
Theorem 1.1. Let A be a positive denite Hermitian (N; N){matrix which has p and q
isolated large and small eigenvalues, respectively:
Let dxe denote the smallest integer  x. Then the CG{method for the solution of
requires at most
iteration steps to achieve precision  , i.e.
where jjxjj A :=
denotes the numerical solution after n iteration steps.
In literature two kinds of preconditioners were mainly exploited, namely banded Toeplitz
matrices and matrices arising from a matrix algebra AON := f
O 0
where ON denotes a unitary matrix.
For another approach by multigrid methods see for example [23].
Various banded Toeplitz preconditioners were examined [10, 5, 40, 36, 41]. It was proved
that the corresponding PCG{methods converge in a number of iteration steps independent
of N . However, there is the signicant constraint that the cost per iteration of the proposed
procedure should be upper-bounded by O(N log N ). This implies some conditions on the
growth of the bandwidth of the banded Toeplitz preconditioners [41].
The above constraint is trivially fullled if we chose preconditioners from matrix algebras,
where the unitary matrix ON has to allow an e-cient multiplication with a vector in O(N log N)
arithmetical operations. Up to now, the only preconditioners of the matrix algebra class which
ensure the desired convergence of the corresponding PCG{method are the preconditioners proposed
in [31, 25]. Unfortunately, the construction of these preconditioners requires the explicit
knowledge of the generating function f .
Extensive examinations were done with natural and optimal Tau preconditioners [6, 3]. Only
for su-ciently smooth functions, where the necessary smoothness depends on the order of the
zeros of f , the natural Tau preconditioners become positive denite and lead to the desired
location of the eigenvalues of the preconditioned matrices. The optimal Tau preconditioner
is in general a bad choice if f has zeros of order > 2. The reason for this will become clear in
the following sections.
In this paper, we combine our approach in [31] with the approximation of f by its convolution
with a reproducing kernel KN . The kernel approach was given in [15] for positive generating
functions. Interesting tests with B{spline kernels were performed by R. Chan et al. in [14].
The advantage of the kernel approach is that it does not require the explicit knowledge of
the generating function. However, only for our theoretical proofs we need some knowledge
about the location of the zeros of the generating function f . See remarks at the end of this
section. We restrict our attention to positive kernels. This ensures that our preconditioners
are positive denite. Suppose that f has only zeros of even order  2s. Then we prove that
under the \moment condition"
Z
on the kernels KN , the eigenvalues of M 1
N AN are contained in some interval [a; b] (0 < a
b < 1) except for a xed number (independent of N) of eigenvalues falling into [b; 1) so that
PCG converges in O(1) steps.
Note that the above kernel property with su-ciently smooth f the Jackson
result
denotes the modulus of continuity. On the other hand, the classical saturation result
of P. P. Korovkin [29, 21] states that we cannot expect a convergence speed of jjf KN f jj 1
better than N 2 even in the presence of very regular functions f .
This paper is organized as follows: In Section 2, we introduce our w{circulant positive denite
preconditioners. We show how the corresponding PCG{method can be implemented with
only O(N) arithmetical operations per step more than the original CG{method. Section 3
is concerned with the location of the eigenvalues of the preconditioned matrices. We will see
that under some assumptions on the kernel the number of CG{iterations is independent of
N . Special kernels as Jackson kernels and B{spline kernels are considered in Section 5. In
Section 6, we sketch how our ideas can be extended to (real) symmetric Toeplitz matrices with
trigonometric preconditioners and to doubly symmetric block Toeplitz matrices with Toeplitz
blocks. Finally, Section 7 contains numerical results.
After sending our manuscript to SIAM J. Sci. Comput., R. H. Chan informed us that his
group has got similar results as in our preprint. See [16] and for a rened version [17]. The
construction of circulant preconditioners of R. H. Chan et al. is based on Jackson kernels and
the proofs are dierent from ours. In [16], the authors prove convergence of the corresponding
PCG{method in O(log N) iteration steps. By a trick (see [16, Theorem 4.2]), which can also
be applied to our w{circulant preconditioners, the R. H. Chan et al. need no knowledge about
the location of the zeros of f .
2 Preconditioners from kernels
Let C 2 denote the Banach space of 2{periodic real{valued continuous functions with norm
We are interested in the solution of Hermitian Toeplitz systems
a
generated by a non{negative function f 2 C 2 which has only a nite number of zeros. By
[10], the matrices AN (f) are positive denite such that (2.1) can be solved by the CG{method.
Unfortunately, since the generating function f 2 C 2 has zeros, the related Toeplitz matrices
are asymptotically ill{conditioned and the CG{method converges very slow. To accelerate
the convergence of the CG{method, we are looking for suitable preconditioners of AN , where
we do not suppose the explicit knowledge of the generating function f . To reach our aim, we
use reproducing kernels. This method was originally proposed for Toeplitz matrices arising
from positive functions f 2 C 2 in [15].
In [14], R. Chan et al. showed by numerical tests that preconditioners from special kernels
related to B{splines can improve the convergence of the CG{method also if f  0 has zeros
of various order. A theoretical proof of R. Chan's results was open up to now.
In this paper, we restrict our attention to even trigonometric polynomials
KN
c N;k cos
and KN  0; then KN is called a positive (trigonometric) kernel. As main examples of such
kernels we consider generalized Jackson polynomials and B{spline kernels in Section 4. For
denote the convolution of f with KN , i.e.
or equivalently in the Fourier domain
a k (f)c N;k e ikx : (2.5)
We consider so{called reproducing kernels KN (N 2 N) with the property that
lim
kf f N k
for all f 2 C 2 .
We chose grids GN (N 2 N) consisting of equispaced nodes
xN;l
such that f(x N;l 1. Note that the choice of the grids requires
some preliminary information about the location of the zeros of f . By a trick (cf. [16]) this
restriction can be neglected if we accept some more outlyers. We consider matrices of the
with
e 2ijk=N
diag (f(x N;l
Obviously, the matrices M N can be written as
~ a 0 ~ aN 1 e iNwN    ~ a 1 e iNwN
~ a 1 ~
a 0
with
~ a
a k (f) := 1
These are ( e iNwN ){circulant matrices (see [20]). In particular, we obtain circulant matrices
for skew{circulant matrices for
N .
As preconditioners for (2.1), we suggest matrices of the form
with suitable positive reproducing kernels KN . By (2.5), the construction of these preconditioners
requires only the knowledge of the Toeplitz matrices AN . It is not necessary to know
the generating function f explicitly. However, for the theoretical results in this paper, we
must have some information about the location of the zeros of f . Note that by a trick in [16]
this information is also super
uous. Here we point out that the auxiliary nontrivial problem
of nding some crucial analytic properties of the generating function f has been treated and
partially solved in [40].
Moreover, our preconditioners have the following desirable properties:
1. Since f  0 with a nite number of zeros and KN is a positive kernel, it follows by (2.4)
that f N > 0. Thus, the matrices M N (f N ) are positive denite.
2. In the following section, we will prove that under certain conditions on the kernels KN
the eigenvalues of M 1
N AN are bounded from below by a positive constant independent
of N and that the number of isolated eigenvalues of M 1
N AN is independent of N . Then,
by Theorem 1.1, the number of PCG{steps to achieve a xed precision is independent
of N .
3. By construction (2.8), the multiplication of M N with a vector requires only O(N log N)
arithmetical operations by using FFT{techniques. By a technique presented in [26] it is
possible to implement a PCG{method with preconditioner M N which takes only O(N)
instead of O(N log N) arithmetical operations per iteration step more than the original
CG{method with respect to AN .
3 Eigenvalues of M 1
In this section, we prove that under certain assumptions on the kernels KN the eigenvalues
of M 1
N AN are bounded from below by a positive constant independent of N and that the
number of isolated eigenvalues of M 1
N AN is independent of N . For the proof of our main
result, we need some preliminary lemmata.
Lemma 3.1 Let p 2 C 2 be a non{negative function which has only a nite number of zeros.
be a positive function with
Then, for f := ph and any N 2 N, the eigenvalues of A 1
lie in the interval
The proof can be found for example in [5, 10, 31]. A more sophisticated version for f; g 2 L 1
was proved in [38, 37].
Lemma 3.2 Let p be a real{valued non{negative trigonometric polynomial of degree  s.
Let N  2s: Then at most 2s eigenvalues of M N (p) 1 AN (p) dier from 1.
Proof: For arbitrary f 2 C 2 with pointwise convergent Fourier series, we obtain by replacing
by the Fourier series of f at xN;l
~
a
a
a
e 2ilk=N e 2ilj=N
r2Znf0g
a j+rN e iw N k e iw N (j+rN)
e 2ilk=N e 2ilj=N
r2Znf0g
a k+rN e iw
This is well{known as aliasing eect. Then it follows that
where
BN (f) := (b j k (f)) N 1
r2Znf0g
a k+rN (f) e iw
We consider is of degree smaller than s  N
2 , we have that b k
jkj  N 1 s. Consequently, BN (p) is of rank  2s. Now the assertion follows by (3.1).
In the sequel, we restrict our attention to Toeplitz matrices having a non{negative generating
function f 2 C 2 with a zero of even order 2s (s 2 N) at
We use the trigonometric polynomial
s
of degree s which has also a zero of order 2s at
The convergence of our PCG{method is related to the behavior of the grid functions
precisely, for the proof of our main theorem, we need
that fq s;N (x)g N2N is bounded for all x 2 GN from above and below by positive constants
independent of N . This will be the content of the following lemmata.
First, we see that the above property follows immediately for all grid points x 2 GN having
some distance independent of N from the zero of f :
Lemma 3.3 Let GN be dened by (2.7) with wN 6= 0. Let fKN g N2N be a sequence of
positive even reproducing kernels and let q s;N be given by (3.3). Then, for xN 2 GN \ [a; b]
and for every " > 0 there exists N(") such that
for all N  N(").
Proof: Since xN 2 [a; b] (N 2 N) for some a > 0; b < 2, we have that
Further, we obtain by (2.6) that for every " > 0 there exists N(") such that
for all N  N("). By rewriting (3.3) in the form
we obtain the assertion.
By Lemma 3.3, it remains to consider the sequences fq s;N
for N !1 or with xN ! 2 for N !1. Since both cases require the same ideas, we consider
lim
The existence of a lower bound of fq s;N (x N )g N2N does also not require additional properties
of the kernel KN :
Lemma 3.4 Let GN be dened by (2.7) with wN 6= 0. Let fKN g N2N be a sequence of
positive even reproducing kernels and let q s;N be given by (3.3). Then, for xN 2 GN with
lim
there exists a constant  > 0 independent of N such that
q s;N
Proof: By denition of q s;N and p s;N , we have that
and since p s  0 and KN  0, we obtain for xN <  that
Z
xN
The polynomial p s is monotonely increasing on [0; ]. Thus
Z
xN
KN
Since KN is even and fullls (2.3), we get for any sequence xN 2 GN
0 that
xN
It remains to examine if
for any xN 2 GN with lim
Here the \moment property" comes into the play.
Lemma 3.5 Let GN (n 2 N) be dened by (2.7) with
Let fKN g N2N be a sequence of positive even kernels and let q s;N (s  1) be given by (3.3).
Then there exists a constant  < 1 independent of N such that
for all xN 2 GN with lim
only if KN fullls the \moment property"
Z
Note that the restriction (3.4) on the grids GN means that we have for any xN 2 GN that
w=N  xN .
Proof: Since sin 2 x  x 2 for all x 2 R, we obtain by (3.2) that
Similarly, we have for any xed 0  y  =2 that
sin 2 x
and hence
2s
2s
x 2s
Using (3.6), we conclude by KN  0 that
Z
Z
2s
2s
Z
and since KN is even
s
2s
x 2s 2k
Z
Let KN satisfy (3.5). Then
s
2s
By (3.4), we have for any grid sequence xN 2 GN that xN  w=N . Consequently,
By (3.7) this implies that there exists  < 1 independent of N so that q s;N
On the other hand, we see by (3.7) with y := =4 that
Z
2s
x 2s 2k
Z
By denition of GN , there exists a grid sequence fxN g N2N so that xN approaches zero as N 1
1). Assume that KN does not fulll (3.5). Then we obtain for the above sequence
that p s;N while we have by (3.6) that p s
cannot be bounded from above. This completes the proof.
By Lemma 3.3 { Lemma 3.5, we obtain that for grids GN dened by (2.7) and (3.4) and for
even positive reproducing kernels with (3.5) there exist
Now we can prove our main theorem.
Theorem 3.6 Let fAN (f)g N2N be a sequence of Toeplitz matrices generated by a non{
negative function f 2 C 2 which has only a zero of order 2s (s 2 N) at the
grids GN be dened by (2.7) and (3.4). Assume that fKN g N2N is a sequence of even positive
reproducing kernels satisfying (3.5). Finally, let M N (f N ) be dened by (2.10). Then we have:
i) The eigenvalues of M 1
N (f N )AN (f) are bounded from below by a positive constant independent
of N .
ii) For N  2s, at most 2s eigenvalues of M N (f N are not contained in the interval
Here ,  are given by (3.8) and h min ; h max are dened as in Lemma 3.1,
where h := f=p s .
Proof: 1. To show ii), we consider the Rayleigh quotient
By Lemma 3.1, we have that
and thus, since the second factor on the right{hand side of (3.9) is positive
By Lemma 3.2, we know that
with a matrix RN (2s) of rank 2s and consequently
and
Since KN and p s are non{negative, we obtain by (2.4) and by denition of h that
This implies by denition of M N (f N ) that
and further by (3.3), (3.8) and since 0 <    < 1 that
for all u 6= oN . Assume that RN (2s) has s 1 positive eigenvalues. Then, by properties
of the Rayleigh quotient and by Weyl's theorem [24, p. 184] at most s 1 eigenvalues of
are larger than hmax
. Similarly, we obtain by consideration of the left{
hand inequality of (3.10) that at most 2s s 1 eigenvalues of M N (f N are smaller
than h min
hmax .
2. To show i), we rewrite (3.9) as
As in the rst part of the proof, we see that this implies
Consequently, it remains to show that there exists a constant 0 < c < 1 such that
c
By (3.1), this is equivalent to
By the special structure of BN (p s ) and AN (p s ), assertion i) follows as in the proof of Theorem
4.3 in [3]. This completes the proof.
By the following theorem, the \moment property" (3.5) of the kernel is also necessary to
obtain good preconditioners.
Theorem 3.7 Let fAN (f)g N2N be a sequence of Toeplitz matrices generated by a non{
negative function f 2 C 2 which has only a zero of order 2s (s 2 N) at Let the grids
GN be dened by (2.7) and (3.4). Assume that fKN g N2N is a sequence of even positive reproducing
kernels which do not fulll (3.5). Finally, let M N (f N ) be dened by (2.10). Then,
for arbitrary " > 0 and arbitrary c 2 N, there exist N("; c) such that for all N  N("; c) at
least c eigenvalues of M N (f N are contained in (0; ").
The proof follows again the lines of the fundamental paper of F. Di Benedetto [3, Theorem
5.4]. We include the short proof with respect to our background.
Proof: By the proof of Theorem 3.6, we have for all u 6= o that
Hence it remains to show that M N (p s;N has an arbitrary number of eigenvalues
in (0; ") for N su-ciently large. By (3.2) and [32, Theorem 3.1], we have that
diag
2s
I
diag
s
I
j;k=0 is an orthogonal matrix and where stoep a 0
and shank a 0 denote the symmetric Toeplitz matrix and the persymmetric Hankel matrix
with rst row a 0 , respectively. Deleting the rst s 1 and the last s 1 rows and columns of
we obtain AN (p s ). Thus, we have by Courants minimax theorem for the eigenvalues
2s
2s
The later result is due to a technique of D. Bini et al. [7, Proposition 4.2]. Consider AN (p s )
this matrix has positive eigenvalues, while we have for arbitrary " > 0
that
2s

Since KN does not fulll (3.5), we have by Lemma 3.5 that
lim
Thus, for j  c independent of N and for su-ciently large N  N("; c) the values  j (AN (p s )
negative. The eigenvalues of AN (p s are continuous functions
of t. Since the smallest c eigenvalues pass from a positive value for to a negative
value for ") such that AN (p s
zero. This is equivalent to the fact that M N (p s;N has an eigenvalue "
we are done.
The generalization of the above results for generating functions with dierent zeros of even
order
is straightforward (see [18]). By applying the polynomial
Y
instead of p s and following the above lines, we can show that for grids GN of the form (2.7)
with xN;l 6= y m) and for kernels KN fullling (3.5) with
there exist constants 0 <    < 1 such that for all x 2 GN
(p  KN )(x)
4 Jackson polynomials and B{spline kernels
In this section, we consider concrete positive reproducing kernels KN with property (3.5).
The generalized Jackson polynomials of degree  N 1 are dened by
sin(nx=2)
sin x=2
2m
determined by (2.3) [22, p. 203]. It is well{known
[22, p. 204], that the generalized Jackson polynomials J m;N are even positive reproducing
which satisfy property (3.5) for
In particular, J 1;N is the Fejer kernel which is related to the optimal circulant preconditioner
[19, 15]. However, the Fejer kernel does not fulll (3.5) for s  1 such that we cannot expect
a fast convergence of our PCG{method if f has a zero of order  2. Our numerical tests
conrm this result.
By Theorem 3.6, the generalized Jackson polynomials can be used
for the construction of preconditioners. Note that preconditioners related to Jackson kernels
were also suggested in [39]. However, the construction of the Fourier coe-cients of J m;N seems
to be rather complicated. See also [10]. Therefore we prefer the following B{spline kernels.
The \B{spline kernels" were introduced by R. Chan et al. in [14]. The authors showed by
numerical tests that preconditioners from B{spline kernels of certain order seem to be good
candidates for the PCG{method. Applying the results of the previous section, we are able to
show the theoretical reasons for these results, at least for the positive B{spline kernels.
Let  [0;1) denote the characteristic function of [0; 1). The cardinal B{splines Nm (m  1) of
order m are dened by
and their centered version by
Note that Mm is an even function with supp
where
sinc x :=
sin x
Let the B{spline kernels B m;N be dened by [14]
mk
Note that B 1;N again coincides with the Fejer kernel.
For the construction of the preconditioner, it is important, that the Fourier coe-cient c
can be computed in a simple way for example by applying a simplied
version of de Boor's algorithm [9, p. 54].
By (4.1), it is easy to check that B m;N is a dilated, 2{periodized version of (sinc x
sinc
Thus
Moreover, we obtain similar to the generalized Jackson polynomials:
Lemma 4.1 The B{spline kernels B m;N satisfy (3.5) if and only if m  s + 1.
Proof: By (4.2), we obtain that
Z
Z
sinc
dt

sin N
dt
2k  sin u
2m
du
c N 2kZu 2k 2m du  C N 2k
for 1. Thus, for m  s
On the other hand, we have that
Z
Z

sin N
dt
2k  sin u
2m
du
If m  k, then the last integral is not bounded for N !1. Thus, for m  s, the kernel B m;N
does not fulll property (3.5).
By Theorem 3.6, the B{spline kernels preconditioners

5 Generalizations of the preconditioning technique
In this section, we sketch how our preconditioners can be generalized to (real) symmetric
Toeplitz matrices and to doubly symmetric block Toeplitz matrices with Toeplitz blocks. We
will do this in a very short way since both cases do not require new ideas. However, we have
to introduce some notation to understand the numerical tests in Section 7.
Symmetric Toeplitz matrices
First, we suppose in addition to Section 2 that the Toeplitz matrices AN 2 R N;N are symmet-
ric, i.e. the generating function f 2 C 2 is even. Note that in this case, the multiplication of
a vector with AN can be realized using fast trigonometric transforms instead of fast Fourier
transforms (see [32]). In this way, complex arithmetic can be completely avoided in the iterative
solution of (2.1). This is one of the reasons to look for preconditioners of type (2.8),
where the Fourier matrix F N is replaced by trigonometric matrices corresponding to fast
trigonometric transforms. In practice, four discrete sine transforms (DST I { IV) and four
discrete cosine transforms (DCT I { IV) were applied (see [46]). Any of these eight trigonometric
transforms can be realized with O(N log N) arithmetical operations (see for example
[2, 44]). Likewise, we can dene preconditioners with respect to any of these transforms. In
this paper, we restrict our attention to the DST{II and DCT{II, which are determined by the
following transform matrices:
1). Similar to (2.10), (2.8), we
introduce the preconditioners (see [31])
diag
l
diag
l
We recall, that for the construction these preconditioners no explicit knowledge of the generating
function is required. Since f is even, the grids GN are simply chosen as GN := fx N;l :=
l
for the DCT{II and
the DST{II preconditioners, respectively. If f(x N;l then we can prove
Theorem 3.6 with respect to the preconditioners (5.1) in a completely similar way. We have
only to replace the decomposition (3.1) by
for the DCT{II and for the DST{II, respectively. See also [31].
Remark: Let
O 0
denote the matrix algebra with respect to the unitary matrix ON . Then the optimal preconditioner
of AN in AON is dened by
denotes the Frobenius norm. As mentioned in the previous section, the optimal
preconditioner in A FN coincides with our preconditioner (2.10) dened with respect to the
Fejer kernel B 1;N and with in (2.7). It is easy to check (see [33]) that the optimal
preconditioner in AON , where ON 2 fC IV
N g is equal to our preconditioner M N (f N ; ON )
in (5.1) dened with respect to ON and with respect to the Fejer kernel. Unfortunately,
the Fejer kernel preconditioners do not lead to a fast convergence of the PCG{method if the
generating function f of AN has a zero of order 2s  2.
In contrast to these results, the optimal preconditioners in AON with ON dened by the DCT
I { III or by the DST I { III do not coincide with the corresponding Fejer kernel preconditioner
In literature [6, 3], so{called optimal Tau preconditioners were of special
interest. Using our notation, optimal Tau preconditioners are the optimal preconditioners
with respect to the DST{I as unitary transform. The optimal Tau preconditioner realizes a
fast convergence of the PCG{method if the generating function f of AN has only zeros of
order 2s  2 [6].
Block Toeplitz matrices with Toeplitz blocks
Next we are interested in the solution of doubly symmetric block Toeplitz systems with
Toeplitz blocks. The construction of preconditioners with the help of reproducing kernels
was applied to well{conditioned block Toeplitz systems in [27]. Following these lines, we
generalize our univariate construction to ill{conditioned block Toeplitz systems with Toeplitz
blocks. In the next Section we will present good numerical results also for the block case.
However, in general, it is not possible to prove the convergence of PCG in a number of iteration
steps independent of N . Here we refer to [34].
Note that as in the univariate case there exist banded block Toeplitz preconditioners with
banded Toeplitz blocks which ensure a fast convergence of the corresponding PCG{method
[35]. See also [4, 30].
We consider systems of linear equations
where AM;N denotes a positive denite doubly symmetric block Toeplitz matrix with Toeplitz
blocks (BTTB matrix), i.e.
r;s=0 with A r := (a r;j k
and a r;j = a jrj;jjj . We assume that the matrices AM;N are generated by a real{valued 2{
periodic continuous even function in two variables, i.e.
a j;k := 1
Z'(s; ds dt :
Note that the multiplication of a vector with a BTTB matrix requires only O(MN log(MN))
arithmetical operations (see [33]). We dene our so{called \level{2" preconditioners by
N;M
(S II
with
by
r=0 with x kN+j := x
6 Numerical Examples
In this section, we conrm our theoretical results by various numerical examples. The fast
computation of the preconditioners and the PCG{method were implemented in MATLAB,
where the C{programs for the fast trigonometric transforms were included by cmex. The
algorithms were tested on a Sun SPARCstation 20.
As transform length we choose and as right{hand side b of (2.1) the vector consisting of
entries \1". The PCG{method started with the zero vector and stopped if kr (j) k 2 =kr (0) k 2 <
denotes the residual vector after j iterations.
We restrict our attention to preconditioners (2.10) and (5.1) constructed from B{spline kernels
. The following tables show the number of iterations of the corresponding
PCG{method to achieve a xed precision. The rst row of each table contains the exponent
n of the transform length in the univariate case and the block length N in the block
Toeplitz case. The kernels are listed in the rst column and the applied unitary transform in
the second column of each table. Here F w
N := W N F N with W N := diag( e ik=N
wN := =N in (2.7). For comparison, the second row of each table contains the number of
PCG{steps with preconditioner M N (f) dened by (2.8). These preconditioners, which can
be constructed only if the generating function f is known, were examined in [31].
We begin with symmetric ill{conditioned Toeplitz matrices AN (f) arising from the generating
functions
ii) (see [3, 10, 11, 14, 31, 36]): f(x) := x 4
The

Tables

present the number of iteration steps with dierent preconditioners.
As expected, for it is not su-cient to choose a preconditioner based on the Fejer
it is not su-cient to choose a preconditioner based on
the cubic B{spline kernel in order to keep the number of iterations independent
of N .
On the other hand, we have a similar convergence behavior for the dierent unitary transforms.
This is no surprise for F w
N and for S II
N . However, for F N and for C II
N , the corresponding
grids GN contain the zero of f , namely This was excluded in Theorem 3.6. In our
numerical tests it seems to play no rule that a grid point meets the zero of f .
Our next example in Table 3 conrms our theoretical results for the function
with zeros of order 2 at
Finally, let us turn to BTTB matrices AN;N . In our examples, the matrices AN;N are generated
by the functions
iv) (see [4]): '(s;
v) (see [30, 31]): '(s;
vi) (see [30, 31]): '(s;
These matrices are ill{conditioned and the CG{method without preconditioning, with Strang{
type{preconditioning or with optimal trigonometric preconditioning converges very slow (see
[30, 33, 4]). Our preconditioning (5.2) leads to the number of iterations in the Tables 4 { 6.
In [34], we proved that the number of iteration steps of PCG is independent of N in Example
iv) and we explained the convergence behavior of PCG for the other examples. To our
knowledge, there does not exist a faster PCG{method if the generating function ' is unknown
up to now.
Note that by [42, 43] any multilevel preconditioner is not optimal in the sense that a cluster
cannot be proper [45].

Summary

. We suggested new positive denite w{circulant preconditioners for sequences of
Toeplitz systems with polynomial increasing condition numbers. The construction of our preconditioners
is based on the convolution of the generating function with positive reproducing
kernels and, by working in the Fourier domain, does not require the explicit knowledge of the
generating function. As main result we proved that the quality of the preconditioner depends
on a \moment property" of the corresponding kernel which is related to the order of the zeros
of the generating function. This explains, e.g. why optimal circulant preconditioners arising
from convolutions with the Fejer kernels fail to be good preconditioners if the generating
function has zeros of order  2.



--R

Iterative Solution Methods.
Fast polynomial multiplication and convolution related to the discrete cosine transform.
Analysis of preconditioning techniques for ill-conditioned Toeplitz matrices
Preconditioning of block Toeplitz matrices by sine transforms.
preconditioning for Toeplitz matrices.
Capizzano. A unifying approach to abstract matrix algebra preconditioning.
Spectral and computational properties of band symmetric Toeplitz matrices.


Toeplitz preconditioners for Toeplitz systems with nonnegative generating functions.
Toeplitz preconditioners for Hermitian Toeplitz systems.
Conjugate gradient methods of Toeplitz systems.
Sine transform based preconditioners for symmetric Toeplitz systems.
Circulant preconditioners from B-splines
Circulant preconditioners constructed from kernels.
Circulant preconditioners for ill-conditioned Hermitian Toeplitz matrices
The best circulant preconditioners for Hermitian Toeplitz systems.
The best circulant preconditioners for Hermitian Toeplitz systems II: The multiple-zero case
An optimal circulant preconditioner for Toeplitz systems.
Circulant Matrices.
The Approximation of Continuous Functions by Positive Linear Operators.
Constructive Approximation.
Multigrid methods for Toeplitz matrices.
Matrix Analysis.
Iterative methods for ill-conditioned Toeplitz matrices
Iterative methods for Toeplitz-like matrices
A note on construction of circulant preconditioners from kernels.

Linear Operators and Approximation Theory.
Band preconditioners for block-Toeplitz -Toeplitz-block-systems
Preconditioners for ill-conditioned Toeplitz matrices
Optimal trigonometric preconditioners for nonsymmetric Toeplitz systems.
Trigonometric preconditioners for block Toeplitz systems.
Preconditioning of Hermitian block-Toeplitz-Toeplitz-block matrices by level-1 preconditioners
Preconditioning strategies for asymptotically ill-conditioned block Toeplitz systems

An ergodic theorem for classes of preconditiones matrices
On the extreme eigenvalues of Hermitian (block) Toeplitz matrices
Capizzano. Korovkin theorems and linear positive gram matrix algebra approximations of toeplitz matrices.
Capizzano. How to choose the best iterative strategy for symmetric Toeplitz systems
Capizzano. Toeplitz preconditioners constructed from linear approximation pro- cesses
Any circulant-like preconditioner for multi-level matrices is not optimal
How to prove that a preconditioner can not be optimal.
A polynomial approach to fast algorithms for discrete Fourier- cosine and Fourier-sine transforms
Circulant preconditioners with unbounded inverses.
Fast algorithms for the discrete W transform and for the discrete Fourier transform.
--TR

--CTR
D. Noutsos , S. Serra Capizzano , P. Vassalos, Spectral equivalence and matrix algebra preconditioners for multilevel Toeplitz systems: a negative result, Contemporary mathematics: theory and applications, American Mathematical Society, Boston, MA, 2001
D. Noutsos , S. Serra Capizzano , P. Vassalos, Matrix algebra preconditioners for multilevel Toeplitz systems do not insure optimal convergence rate, Theoretical Computer Science, v.315 n.2-3, p.557-579, 6 May 2004
preconditioners;reproducing kernels;ill-conditioned Toeplitz matrices;CG method