# Preconditioning block Toeplitz matrices.

1. Introduction. We consider ill-conditioned symmetric positive definite (spd) block Toeplitz (BT) matrices of the form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.1)

with small general k x k matrices [A.sub.j], j = 1 - n, ..., n - 1, k fixed and independent of n. Mainly, we are interested in the case k = 2, because for this case we can display already all the problems and techniques that are different from the scalar case with k = 1.

Furthermore, we assume that the family of BT matrices [B.sub.n] = [B.sub.n] (F), n = 1, 2, 3, ..., is related to a generating k x k matrix function

F(x) = [([f.sub.j,m](x)).sup.k.sub.j,m=1] = ... + [A.sub.l] exp(-ix) + [A.sub.0] + [A.sub.-1] exp(ix) + ... that may be [L.sup.l], [L.sup.2], [L.sup.[infinity]], or continuous and 2[pi] periodic in the interval [-[pi], [pi], which is equivalent to write that every [f.sub.j,m],(x), j, k = 1, ..., k, is [L.sup.1], [L.sup.2], [L.sup.[infinity]], or continuous and 2[pi]-periodic in [-[pi], [pi]] as standard scalar-valued functions.

By a simple permutation we can transform the matrix [B.sub.n] into the k x k block form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.2)

with n x n Toeplitz matrices [T.sub.j,m] = [T.sup.(n).sub.j,m], j,m = 1, ..., k, related to the same generating matrix function F(x). Then, each [f.sub.j,m] (x) is the scalar generating function to [T.sup.(n).sub.j,m].

Note, that in contrast to multilevel Toeplitz matrices we consider in (1.1) blocks [A.sub.j] of fixed size that will be in general of non-Toeplitz structure. Hence, the analysis derived for the multilevel case based on trigonometric polynomials [8, 9, 15] cannot be applied in this BT case. In fact such negative results as in [8, 9, 15] do not hold in the block case; see [10, 12] for related positive results concerning strong clustering with block circulant preconditioners and spectral equivalence with band block Toeplitz preconditioners, respectively. So, the BT case is quite different from the scalar case and the multilevel case.

Block Toeplitz matrices are closely related to Schur complements in Toeplitz matrices, e.g., Toeplitz Schur complement [T.sub.1] - [T.sub.2] * [T.sup.1.sub.4] * [T.sub.3] to BT matrix [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. So, fork = 2 3 the given block equations can be reduced to solving Toeplitz matrices and Schur complement systems of Toeplitz matrices. In the following we will derive theoretical and numerical results on block Toeplitz systems and also on Toeplitz Schur complements. Note, that also the Toeplitz normal equations are a special case of a Schur complement, and therefore are related to block Toeplitz systems.

For a well-conditioned spd Toeplitz matrix [T.sub.n] related to a continuous generating function f(x) there exist various preconditioning techniques that ensure fast convergence of the preconditioned conjugate gradient (pcg) method; see [2, 7] and the references therein. Fast Transform preconditioners based on circulant matrices or other classes of matrix algebras lead to a preconditioned system with clustered eigenvalues for [C.sup.-1.sub.n][T.sup.n]. Here the computation of the preconditioner and each step in the pcg algorithm take O(n log(n)) operations based on fast algorithms for the trigonometric transforms. Hence, if the linear system can be solved in a bounded number of iterations--independent of n--then the whole procedure takes O(n log(n)) operations [2, 7]. This case occurs if the symbol is strictly positive or if it is nonnegative and polynomial.

Another important class of preconditioners for ill-conditioned matrices is based on banded Toeplitz matrices. If the scalar generating function f (x) has only zeros of even order then we can define a trigonometric polynomial p that has the same zeros of the same order as f. Then, p is related to a band Toeplitz matrix. Furthermore, the preconditioned system [P.sup.-1.sub.n] [T.sub.n] is well-conditioned with eigenvalues contained in an interval given by the range of f(x)/p(x); this again leads to fast convergence of the pcg method [3, 10]. In [12] the author considers also band preconditioners with bandwidth up to log(n) by choosing, e.g., the partial Fourier polynomial [F.sub.n](x) for the given Fourier expansion of F(x). For well-conditioned matrices this approach leads to clustered spectrum of the preconditioned system. For ill-conditioned matrices with singular F(x) the banded approximation given by Fn (x) may be indefinite and therefore in [11, 12] a generalization of the approach in [10] is considered in order to deal with the ill-conditioned case; see Theorems 3.1, 3.6, and sections 4.1, 4.2 in [11] and sections 3 and 4 in [12]. Here, we introduce a different banded approximation that can deal with singular F(x) also allowing a broader bandwidth.

Aim of this paper is to generalize the positive preconditioning results for circulant and band preconditioners for Block Toeplitz matrices, e.g., [6, 11, 12, 13, 14], and to derive further results on the eigenvalue distribution and clustering of preconditioned block Toeplitz systems and Toeplitz Schur complements (like the normal equations). This also leads to some negative results on the eigenvalue clustering of preconditioned BT matrices. The paper is organized as follows. In section 2 some results are presented concerning BT, Hankel Matrices and Schur complements of BT matrices. In section 3 some spectral and convergence properties are presented and proved for pcg method applied on BT systems and for preconditioning Toeplitz Schur complements. General propositions for constructing efficient prconditioners for BT systems and Schur complements are given in section 4. In section 5 numerical examples are presented showing the validity of the theory. Finally, concluding remarks are given in section 6.

2. Toeplitz, Block Toeplitz and multilevel Toeplitz matrices. In this section we present some useful known results that are necessary to obtain the main results in the following sections.

THEOREM 2.1 (Spectrum of preconditioned BT system, Theorem 4.1 in [6], see also [11, 12]). Let [T.sub.n] (G) and [T.sub.n] (F) be two sequences of matrices generated by Lebesgue integrable Hermitian k x k-matrix-valued functions F and G defined on Q = [-[pi], [pi]], where G is positive definite for almost every x [member of] Q, that is, the Lebesgue measure of Q\[Q.sub.+] is zero with [Q.sub.+] := {x [member of] Q : G(x) spd}. Then all the eigenvalues of [T.sup.-.sub.n] (G)[T.sub.n](F) lie in the (not necessarily bounded) interval [r, R], where

r = sup{y [member of] R : [[lambda].sub.min]([G.sup.-1]F) > y for almost every x [member of] [Q.sub.+]} R = inf{y [member of] R : [[lambda].sub.min]([G.sup.-1]F) < y for almost every x [member of] [Q.sub.+]}

THEOREM 2.2 (Product of Toeplitz matrices [19]). If f, g [member of] [L.sup.[infinity]], then [T.sub.n](fg) - [T.sub.n](f)*[T.sub.n](g) = [P.sub.n] * H(f) * H([bar.g]) * [P.sub.n] + [Q.sub.n] * H([bar.f]) * H(g) * [Q.sub.n] with [P.sub.n] ([x.sub.1], ...) = ([x.sub.1], ..., [x.sub.n]) and [Q.sub.n] ([x.sub.1], ...) = ([x.sub.n], ..., [x.sub.1]) are matrices picking out the first n entries of an infinite vector, and the infinite Hankel matrix

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

COROLLARY 2.3 (Product of band Toeplitz and Toeplitz matrix). For a real trigonometric polynomial p(x) and g [member of] [L.sup.[infinity]] it holds

[T.sub.n](pg) = [T.sub.n](p)[T.sub.n](g) + [R.sub.1]

and

[T.sup.-1.sub.n](p)[T.sub.n](pg) = [T.sub.n](g) + [R.sub.2]

with [R.sub.j], j = 1, 2, matrices of low rank that depends only on p(x) and not on the dimension n.

COROLLARY 2.4 (Product of band BT matrix and BT matrix). For a real trigonometric matrix polynomial P(x) and G [member of] [L.sup.[infinity]] with k x k blocks it holds

[T.sub.n](PG) = [T.sub.n](P)[T.sub.n](G) + [R.sub.1]

and

[T.sup.-1.sub.n](P)[T.sub.n](PG)=[T.sub.n](G) + [R.sub.2]

with [R.sub.j], j = 1, 2, matrices of low rank.

THEOREM 2.5 (Spectrum of Hilbert matrix [18, 7]). Let [H.sub.n] be the n x n Hilbert matrix to H(f) with [t.sub.j] = 1/j, j = 1, 2, .... Then for any 0 < [epsilon] < [pi], the number of eigenvalues of [H.sub.n] with absolute values exceeding [epsilon] is given by

2/[pi] log n * [sech.sup.-1] [epsilon]/[pi] * (1 + o(n)).

Hence for every cluster of eigenvalues around zero with small radius E the number of outliers is growing like log(n). This behavior is denoted as weakly clustered because the number of outliers is allowed to grow like o(n).

THEOREM 2.6 (Negative results for multilevel Toeplitz matrices [8, 9, 15]). For ill-conditioned positive definite multilevel Toeplitz matrices there exist examples where for every positive definite multilevel circulant preconditioner there holds:

1. If the spectrum of the preconditioned matrix is bounded ([[lambda].sub.max] [less than or equal to] [alpha] < [infinity], [alpha] independent of n), then [[lambda].sub.min] [right arrow] [infinity] and [beta](n) eigenvalues tend to zero, with [beta](n) tending to infinity when n tends to infinity.

2. If the spectrum of the preconditioned matrix is bounded from below ([[lambda].sub.min] [greater than or equal to] [beta] > 0, [beta] independent of n), then [[lambda].sub.max] [right arrow] [infinity] and [beta](n) eigenvalues tend to infinity, with [beta](n) [right arrow] [infinity] for n [right arrow] [infinity].

Now, let us turn to Schur complements related to BT matrices for k = 2. The close relationship between BT matrices and Schur complements is displayed by the equations

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2.1)

with [S.sub.1] = [T.sub.1] - [T.sub.2][T.sup.-1.sub.3] [T.sup.H.sub.2] and [S.sub.3] = [T.sub.3] - [T.sup.H.sub.2][T.sup.-1.sub.1][T.sub.2]. Hence, an efficient preconditioner for a BT matrix directly leads to an efficient preconditioner for both Schur complements [S.sub.l] and [S.sub.3]. On the other side an efficient preconditioner for one of the Schur complements directly leads to an efficient preconditioner for the whole BT matrix.

3. BT matrices and Toeplitz Schur Complements. First we present some useful results on the location of eigenvalues of Schur complements of Toeplitz matrices. These results are based on the connection between Schur complements and block matrices.

THEOREM 3.1 (Preconditioned normal equations). Consider the family of Toeplitz matrices [T.sub.n](f), n = 1, 2, ... with generating function f, real Lebesgue integrable. Then it holds

[T.sub.n] ([f.sup.2]) [greater than or equal to] [T.sub.n] [(f).sup.2].

Proof. We consider the BT matrix [B.sub.n] to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

This matrix F is rank-1 symmetric positive semidefinite with eigenvalues [lambda] = 0 and [lambda] = 1 + f[(x).sup.2]. The generating function is positive semidefinite, therefore the BT matrix [B.sub.n] is also positive semidefinite. Hence, both Schur complements are positive semidefinite and therefore [T.sub.n] ([f.sup.2]) - [T.sup.n.sub.2](f) [greater than or equal to] 0 and [I.sub.n] - [T.sub.n](f) [T.sup.-1.sub.n]([f.sup.2])[T.sub.n](f) [greater than or equal to] 0 (for [T.sub.n]([f.sup.2]) nonsingular).

Note that if F(x) [greater than or equal to] 0 is symmetric positive semidefinite, [B.sub.n](F) may be even positive definite, depending on f, e.g., f(x) = [x.sup.2]. Theorem 3.1 can be also shown for general Toeplitz matrices: [T.sub.n]([[absolute value of f].sup.2]) [greater than or equal to] [T.sup.H.sub.2](f)[T.sub.n](f).

LEMMA 3.2. Consider b, g Lebesgue integrable and g(x) nonnegative with [absolute value of b(x)].sup.2]/g(x) < [infinity] for all x, and [T.sub.n](g) and [T.sub.n]([[absolute value of b].sup.2]/g) nonsingular. Then it holds

[T.sub.n]([[absolute value of b].sup.2]/g) [greater than or equal to] [T.sup.-1.sub.n](b)[T.sup.- 1.sub.n](g)[T.sub.n](b)

and

[T.sub.n](g) [greater than or equal to] [T.sub.n](b)[T.sup.-1.sub.n]([[absolute value of b].sup.2]/g) [T.sup.H.sub.n](b).

Proof. Consider the BT matrix [B.sub.n] to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

THEOREM 3.3 (Preconditioned Toeplitz Schur Complement). Let f, g, b Lebesgue integrable and g nonnegative, [[absolute value of b].sup.2]/g < [infinity], and the matrices [T.sub.n](g), [T.sub.n]([[absolute value of b].sup.2]/g), [T.sub.n] (f - [[absolute value of b].sup.2]/g) all nonsingular. Then it holds for the Toeplitz Schur complement relative to the matrix [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The eigenvalues of the Toeplitz preconditioned Toeplitz Schur complement

[T.sub.n][(f - [[absolute value of b].sup.2]/g).sup.-1] [S.sub.n](f, g, b)

are greater or equal 1.

Proof. Direct Corollary of Lemma 3.2.

Note, that for Toeplitz matrices with generating function f(x) equals zero on a whole interval, all matrices [T.sub.n](f) will be singular. Furthermore, if in the scalar case f(x) has only isolated zeros of polynomial order then the smallest eigenvalue tends to zero polynomially depending on the order of the zeros of f. The next theorem displays a basic difference between scalar Toeplitz matrices and BT matrices. To prove this Theorem we need the following Lemma

LEMMA 3.4. If f is a 2[pi] periodic continuous function, then the eigenvalues of [T.sub.n]([f.sup.2]) - [T.sub.n] [(f).sup.2] are clustered at zero and the minimal eigenvalue tends to zero exponentially.

Proof. The related Hankel matrix is a compact operator; see [1]. Therefore, the sum of the eigenvalues of the Hankel matrix is bounded which guarantees the strong clustering, e.g., the infinite Hilbert matrix is a bounded operator [4, 17, 18]. Furthermore, Tyrtyshnikov has shown in [17] that the smallest eigenvalue of the associated Hankel matrix H(f) tends to zero exponentially.

THEOREM 3.5 (Ill-posed BT matrix). There exist examples with generating function F x) [greater than or equal to] 0 but det(F(x)) = 0 such that the related BT matrices [B.sub.n] (F) are spd. For such a [B.sub.n] the condition number may grow exponentially with n, resp. the smallest eigenvalue may tend to zero exponentially.

Proof. As example we consider [B.sub.n](F) to generating function [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then the smallest eigenvalue of [B.sub.n] can be bounded from above by the smallest eigenvalue of the Schur complement [T.sub.n]([f.sup.2]) - [T.sub.n][(f).sup.2] [greater than or equal to] 0 which is exponetially converging to zero following the previous Lemma 3.4. (To see the relationship between the spectrum of a natrix and the spectrum of the Schur complement we can consider the Rayleigh quotient). As special example we can choose f(x) = [x.sup.2]. Then F(x) is singular for all x, but [B.sub.n](F) is still spd in view of Theorem 2.2.

Now we want to analyse the spectrum of different preconditioned BT matrices. The first results show, that well-conditioned BT matrices behave similar to scalar Toeplitz matrices.

THEOREM 3.6 (Well-conditioned BT, Theorems 8.4 and 9.3 in [13]). For well-conditioned spd BT with F(x) 2[pi]-periodic continuous the optimal block circulant preconditioner leads to a strongly clustered spectrum.

THEOREM 3.7. Let f [greater than or equal to] 0 be real 21r-periodic continuous with a finite number of zeros of even order and [T.sub.n]([f.sup.2]) nonsingular. Then the spectrum of [B.sub.n] = [T.sub.n](f) [T.sup.-.sub.1]([f.sup.2])[T.sub.n](f) is strongly clustered around 1.

Proof. We can write f(x) = p(x)h(x) with h(x) [greater than or equal to] m > 0 and trigonometric polynomial p(x). Then [T.sub.n](f) = [T.sub.n](ph) = [T.sub.n](p) * [T.sub.n] (h) + [R.sub.1] = [T.sub.n](h) * [T.sub.n](p) + [R.sub.2] with [R.sub.j] of low rank (Lemma 2.3). In the same way, [T.sub.n][([f.sup.2]).sup.-l] = [T.sup.- 1.sub.n](p)[T.sup.-1.sub.n]([h.sup.2])[T.sup.-1.sub.n](p) + [R.sub.3]. Because [infinity] > M [greater than or equal to] h(x) [greater than or equal to] m > 0, [T.sub.n](h) and [T.sub.n] ([h.sup.2]) are well-conditioned and can be approximated by circulant matrices C such that it holds: For each [epsilon] > 0 there exist matrices [E.sub.5], [E.sub.6], [E.sub.7] and [R.sub.5], [R.sub.6], [R.sub.7] for which [parallel][E.sub.j][[parallel].sub.2] [less than or equal to] [epsilon], j = 5, 6, 7 and [R.sub.j], j = 5, 6, 7 are matrices of low rank (the rank depends on c and not on the dimension n) [2, 7] with

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

THEOREM 3.8 (Well-conditioned Toeplitz Schur complement). For uniformly well-conditioned spd Toeplitz Schur complements [S.sub.n] = [T.sub.n](f) - [T.sup.H.sub.n](b)[T.sup.- 1.sub.n](g)[T.sub.n](b) with real f and g [greater than or equal to] 0 with 0 < [[absolute value of b(x)].sup.2]/g(x) < [infinity], f - [[absolute value of b].sup.2]/g > 0, all 2[pi]-periodic continuous, the Toeplitz preconditioner [P.sub.n] = [T.sub.n] (f(x) - [[absolute value of b(x)].siup.2]/g(x)) leads to a weakly clustered spectrum with eigenvalues uniformly bounded away from 0 and [infinity]. If b(x) is real with zeros of even order the spectrum of the preconditioned Schur complement is strongly clustered around 1.

Proof. All [S.sub.n] and [P.sub.n] are uniformly well-conditioned and the spectrum of [P.sup.-1.sub.n] [S.sub.n] is bounded in an interval [1, M]. With the following Theorem 3.9 this proves the first part of the Theorem. Furthermore, it holds

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

If b(x) has zeros, then g(x) has the same zeros of double order. If b has only zeros of even order then we can write b(x) = p(x)[h.sub.b](x) with a trigonometric polynomial p(x). Further-more, g can be written as g(x) = [p.sup.2](x)[h.sub.g](x) with positive [h.sub.b] > [M.sub.b] > 0 and [h.sub.g] [greater than or equal to] [m.sub.g] > 0. Then, for real b it holds

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

in view of Corollary 2.3. So we have to analyse only the case of well-conditioned [T.sub.n](g) which can be treated like in the previous Theorem by using circulant approximations.

Next we consider ill-conditioned matrices. Here it turns out that for BT matrices the block circulant preconditioner can only ensure a weak clustering but no strong clustering. The proof of the weak clustering is based on the definition of approximating class of matrix sequences:

THEOREM 3.9 (Weak clustering of BC preconditioner for BT matrices, Theorem 3.1 in [16]). For the Hermitian Toeplitz Schur complement of [L.sup.1] functions [S.sub.n](f, g, b) it holds that the spectrum is distributed like the spectrum of the Toeplitz matrix [T.sub.n] (f - [absolute value of [b.sup.2]]/g). Therefore, the eigenvalues of the preconditioned Schur complement are weakly clustered around 1. The same is true for related circulant preconditioners.

THEOREM 3.10 (Counter example with no strong clustering). For the Toeplitz Schur complement there exist examples, e.g., f [member of] [L.sup.2], where the above Toeplitz preconditioner from Theorem 3.9 that leads to a weak clustering, does not lead to a strong clustering.

Proof. Consider the Schur complement [S.sub.n] = ([T.sub.n] (p) + [T.sub.n] ([f.sup.2])) - [T.sub.n][(f).sup.2] with a trigonometric polynomial like p(x) = [(1-cos(x)).sup.m] and function f with coefficients [[tau].sub.j] = 1/j. Note that the sequence [t.sub.j] is in [l.sup.2] and therefore the related Fourier series f is in [L.sup.2]. The Toeplitz preconditioner is given by [T.sub.n](p). Then it holds

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3.1)

Here, H(f) is the infinite Hilbert matrix. Because of Theorem 2.5 the eigenvalues, and therefore also the singular values are not clustered, and therefore also the eigenvalues of [T.sup.-1.sub.n](p)[S.sub.n] are not clustered around 1 but each cluster leads to O(log(n)) outliers.

THEOREM 3.11 (Counter example for Toeplitz Schur complement preconditioner with unbounded norm). For the Toeplitz Schur complement [S.sub.n] = [A.sub.n] + [T.sub.n]([f.sup.2]) - [T.sub.n](f)[T.sub.n](f) with Toeplitz matrices An there exists an example where the Toeplitz preconditioner that leads to a weak clustering following Theorem 3.9 has unbounded spectrum of the preconditioned system, e.g., for f [member of] [L.sup.2].

Proof. Define the skewcirculant matrix [A.sub.n] = toeplitz(2, -1, 0, ... 0,,1) and f(x) with coefficients [t.sub.j] = [q.sup.j] with related Hankel matrix coefficients [q.sup.j]. (Here we use the MATLAB-notation T = toeplitz(x) to denote the symmetric Toeplitz matrix generated by vector x). With the eigenvectors [u.sub.j] of [A.sub.n], relative to the standard eigendecomposition to [A.sub.n] based on the Fourier matrix, we consider the Rayleigh quotients [u.sup.H.sub.j] [A.sub.n][u.sub.j] and [u.sup.H.sub.j][H.sub.n][u.sub.j]. It can be shown by direct computation that it holds [u.sup.H.sub.j][H.sub.j][u.sub.j] = O(1/n). Therefore, for the eigenvector to small eigenvalues of [A.sub.n] it holds [u.sup.sub.j][A.sup.h][u.sub.j] = O(1/[n.sup.2]), and the Rayleigh quotient of [u.sup.H.sub.j]([A.sub.n] + [H.sub.n])[u.sub.j]/[u.sup.H.sub.j][A.sub.n][u.sub.j] is unbounded.

THEOREM 3.12. For the normal equations [T.sub.n][(f).sup.2] the Toeplitz preconditioner [T.sub.n]([f.sup.2]) from Theorem 3.9 guarantees only a weakly clustered spectrum, e.g., for real f [member of] [L.sup.2].

Proof. Consider f(x) [greater than or equal to] 0 with coefficients [t.sub.j] = 1/j, j = 1, 2, ...; [T.sub.n][(f).sup.2] preconditioned by [T.sub.n]([f.sup.2]) leads to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3.2)

and O(log(n)) outliers in view of Theorem 2.5.

Finally, let us summarize the clustering results on preconditioning multilevel and block Toeplitz matrices by multilevel or block circulant preconditioners:

1. For m-level Toeplitz matrices with equispaced grid, blocksize n, and total size N = [n.sup.m] there may be O([N.sup.(m-1)/m]) = [n.sup.m-1] outliers (this includes also the scalar Toeplitz case with O(1) outliers and the 2-level case with N = [n.sup.2] and O(n) = O([square root of N]) outliers).

2. For a BT matrix of size N = k * n, with fixed k, there may be O(log(N)) = 0(log (n)) outliers in the ill-conditioned case.

So, in the ill-conditioned case for scalar Toeplitz matrices we get strong clustering while for BT and m-level Toeplitz matrices we get only a weak one. Nevertheless, the pcg method for BT systems converges much faster (O(log(N)) outliers) than the one for m-level Toeplitz systems (O([N.sup.(m-1)/m]) outliers).

4. Finding efficient preconditioners for BT matrices and Toeplitz Schur Complements. An important class of preconditioners for scalar and multilevel Toeplitz matrices is given by trigonometric polynomials, resp. band Toeplitz matrices. A polynomial BT matrix is defined as a matrix with generating function whose entries are trigonometric polynomials. Unfortunately, given an ill-conditioned BT matrix it is not obvious whether one can find a spectral equivalent trigonometric polynomial BT matrix. So for the three examples

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4.1)

with small [rho] > 0, the polynomial BT matrix

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4.2)

is spectral equivalent to [F.sub.1] and [F.sub.3], but for [F.sub.2] we cannot find a spectral equivalent polynomial. Note, that [F.sub.1] and [F.sub.2] have the same determinant, trace, and eigenvalues.

In the following, we present a recipe to define a trigonometric polynomial BT matrix for given F(x). For simplicity we assume that F(x) has [x.sub.0] = 0 as only singularity. First, we compute det(F(x)) and assume that at [x.sub.0] = 0 it allows the expansion det(F(x)) = c[x.sup.m] + O([[absolute value of x].sup.m+l]). We split the partial functions [f.sub.ij](x) of F(x) into [f.sub.ij](x) = f[d.sub.ij](x) + f[n.sub.ij](x) with f[d.sub.ij](x) differentiable up to order m and f[n.sub.ij](x) = O([[absolute value of x].sup.m+1]) not necessarily differentiable at [x.sub.0]. Then, we can reduce the partial function f[d.sub.ij](x) to the coefficients [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] that give a contribution to the leading term [x.sup.m] in det(F(x)). In f[d.sub.ij] we can replace the occuring terms [x.sup.r], r = 0, ..., [l.sub.ij] by trigonometric polynomials of the form sin[(x).sup.r] or [(2-2cos(x)).sup.r/2]. In this way we can define a trigonometric polynomial BT matrix where det(P(x)) has the same singularity as det(F(x)). If the resulting polynomial has no other singularity and is positive definite it may lead to a spectral equivalent preconditioner. We can prove the following result.

THEOREM 4.1. Let F(x) be the generating matrix function for an spd ill-conditioned BT matrix with singularity at [x.sub.0] = 0. The determinant of F(x) at [x.sub.0] = 0 is assumed to be of the form det(F(x)) = c[x.sup.m] + O([[absolute value of x].sup.m+l]). Suppose that we have found a trigonometric matrix polynomial P(x) such that all the scalar functions [d.sub.ij](x) in D(x) = F(x) - P(x) are approximated at 0 such that [d.sub.ij](x) = [c.sub.ij][x.sup.m] + O([[absolute value of x].sup.m+1]). Furthermore assume that P(x) is spd and P(x) > O for x [not equal to] 0. Then the spectrum of the preconditioned system [T.sup.- 1.sub.n](P)[T.sub.n](F) is uniformly bounded away from 0 and [infinity].

Proof. Note, that det(P(x)) = det(F(x)) + O([[absolute value of x].sup.m+1]) near 0. The entries of [P.sup.-1](x) * (F(x) - P(x)) are also bounded near [x.sub.0] = 0 because det(P(x)) = c[x.sup.m] + O([[absolute value of x].sup.m+l]). Therefore, the eigenvalues of the preconditioned system [P.sup.-1](x)F(x) are bounded from above. Furthermore, [P.sup.-1](x)F(x) > 0 for all x.

Note that the inverse of F(x) can be written as [F.sup.-1](x) = F[(x).sup.#]/det(F(x)). With this notation the condition in Theorem 4.1 can be formulated in the form that for P(x) all entries of the matrix G := F[(x).sup.#]D(x) have to be of the form [G.sub.ij](x) = [g.sub.j] [x.sup.m] + O([[absolute value of x].sup.m+l]).

Now let us return to the general problem of preconditioning ill-conditioned BT matrices or Toeplitz Schur complements. We are interested in BT matrices where the solution can be reduced to the solution of scalar Toeplitz systems.

THEOREM 4.2 (BT Schur complement I). Given a BT matrix with k = 2. The solution of the BT system can be reduced to solving scalar Toeplitz systems if one of the Schur complements [S.sub.n](g) := [T.sub.n](f) - [T.sup.H.sub.n](b) * [T.sup.-1.sub.n](g) * [T.sub.n](b) or [S.sub.n](f) := [T.sub.n](g) - [T.sub.n](b) * [T.sub.n](f) * [T.sup.H.sub.n](b) is well-conditioned. We call [S.sub.n] (g) and [S.sub.n](f) dual Schur complements.

Proof. This is a direct consequence that via (2.1) we can reduce the BT matrix to scalar Toeplitz matrices and one of the Schur complements. Furthermore, in view of Theorem 3.8 we have efficient preconditinoers for well-conditioned Toeplitz Schur complements.

Note that for ill-conditioned 2 x 2 BT matrix one of the Schur complements may be ill-conditioned and the other may be well-conditioned, e.g., [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

THEOREM 4.3 (BT and Schur complement I1). Given the pair of dual Schur complements [S.sub.n](f) and [S.sub.n](g). Then the solution of [S.sub.n](f) can be reduced to the solution of [S.sub.n](g). Therefore, for ill-conditioned [S.sub.n](f) we can find an efficient preconditioner if [S.sub.n](g) is well-conditioned or if there exists an efficient preconditioner for [S.sub.n](g).

Proof. Again, the result follows from equation (2.1) and Theorem 3.8. One example is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

with trigonometric polynomial p. Then for the Schur complement it holds

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

in view of Corollary 2.3 with [T.sub.n]([p.sup.2]) = [T.sub.n](p)[T.sub.n](p) + R.

THEOREM 4.4. Given a BT matrix with generating matrix function F(x) Lebesgue integrable that admits the factorization

F(x) = L(x) * U(x)

with L(x) a trigonometric matrix polynomial and U(x) a triangular matrix or vice versa. Then the solution of [T.sub.n](F) can be reduced to solving scalar Toeplitz systems and band matrices.

Proof. We consider a BT matrix in the form (1.2). In view of Corollary 2.4 the matrix [T.sub.n](F) can--up to low rank--be transformed in the product of a band matrix and a triangular matrix with Toeplitz matrices on the main diagonal blocks.

One example is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

with real f, b [L.sup.1] functions and the above Schur complement factorization according to (2.1).

THEOREM 4.5. Given a BT matrix with generating matrix function F(x) Lebesgue integrable that admits the factorization

F(x) = U(x) * R(x) * V(x)

with U(x) and V(x) trigonometric matrix polynomials and R(x) a triangular matrix. Then the solution of [T.sub.n](F) can be reduced to solving scalar Toeplitz systems and band matrices.

Proof. We consider a BT matrix in the form (1.2). In view of Corollary 2.4 the matrix [T.sub.n] (F) can--up to low rank--be transformed in the product of a band matrix and a triangular matrix with Toeplitz matrices on the main diagonal blocks.

One example is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

with f and b real [L.sup.1] functions.

5. Numerical Results. First, we present numerical examples related to the Theorems from sections 3 and 4.

EXAMPLE 5.1. Table 5.1 presents an example for Theorem 3.6 with optimal circulant preconditioner for BT matrix to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

with x [member of] [-[pi], [pi]]. The spectrum is clustered and the number of outliers is bounded.

EXAMPLE 5.2. Next we display Theorem 3.7. Table 5.2 shows the number of outliers for a Toeplitz preconditioned Toeplitz normal equations. The function f(x) = [x.sup.2] has zero of even order at 0 and we consider the matrix [N.sub.n] := [T.sub.n]([x.sup.2]) * [T.sup.-1.sub.n]([x.sup.4]) * [T.sub.n]([x.sup.2]) with x [member of] [-[pi],[pi]]. Note, that [N.sub.n] is spectral equivalent to matrix [T.sub.n][([x.sup.2]).sup.2] preconditioned by [T.sub.n]([x.sup.4]).

EXAMPLE 5.3. Table 5.3 presents an example for Theorem 3.8 with strong clustering for the optimal circulant preconditioned well-conditioned dual Toeplitz Schur complements [S.sub.1] = I + [T.sub.n]([absolute value of x]) - [T.sub.n]([absolute value of x]) * [T.sub.n]([absolute value of x])) and [S.sub.2] = I - [T.sub.n]([absolute value of x]) * [T.sup.-1.sub.n](1 + [absolute value of x]) * [T.sub.n]([absolute value of x]) with x [member of] [-[pi], [pi]].

EXAMPLE 5.4. Next we consider the strong clustering described by Theorem 3.8. Table 5.4 deals with the Toeplitz Schur complement 2I + [T.sub.n]([x.sup.2]) - [T.sub.n]([x.sup.2]) * [T.sup.-1.sub.n]([x.sup.4]) * [T.sub.n]([x.sup.2]) preconditioned by [T.sub.n] (1 + [x.sup.2]) with x [member of] [-[pi], [pi]].

EXAMPLE 5.5. Table 5.5 presents an example for Theorem 3.10 with Toeplitz preconditioner for Toeplitz Schur complement [T.sub.n](p) + [T.sub.n]([f.sup.2]) - [T.sup.2.sub.n](f); the preconditioner is given by [T.sub.n](p) with f (x) = [absolute value of x], x [member of] [-[pi], [pi]], and p(x) = 2 - 2 cos(x), resp. p(x) = 6 - 8 cos(x) + 2 cos(2x).

EXAMPLE 5.6. We display Theorem 3.10 by Table 5.6. For the Toeplitz Schur complement [A.sub.n] + [T.sub.n]([f.sup.2]) - [T.sup.2.sub.n](f) we choose the preconditioner [A.sub.n] with f(x) = [absolute value of x] with x [member of] [-[pi], [pi]] and [A.sub.n](p) the skewcirculant matrix given by the polynomial p(x) = 2 - 2 cos(x), resp. p(x) = 6 - 8 cos(x) + 2 cos(2x).

EXAMPLE 5.7. Table 5.7 presents an example for Theorem 4.1 with polynomial BT preconditioner P(x) for the three BT matrices [F.sub.1](x), [F.sub.2](x), and [F.sub.3](x) from (4.1) and (4.2). We see, that P leads to bounded spectrum when applied on [F.sub.l] or [F.sub.3].

EXAMPLE 5.8. We consider the matrix function [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The associated BT matrix generated by F is:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For the solution of the BT system

[B.sub.n](F)x = b

we choose as preconditioner the block band Toeplitz matrix:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The Schur complements of the above BT matrix are

[S.sub.1] = [I.sub.n] - (1/2) * [T.sub.n][(x).sup.H] * [T.sub.n][([x.sup.2]).sup.-1] * [T.sub.n](x),

which is well-conditioned in view of Theorem 3.1 and does not need any preconditioning, and

[S.sub.2] = 2[T.sub.n]([x.sup.2]) - [T.sub.n][(x).sup.H] * [T.sub.n](x),

which is ill-conditioned and needs preconditioning. For this we choose the band Toeplitz preconditioner

[T.sub.n] (2 - 2 cos(x)).

In Table 5.8 we give the number of iterations of the pcg method for various values of n and for using various preconditioners. Thereby, we use the following abbreviations:

BT: cg for block Toeplitz System,

BBT: Block band Toeplitz preconditioning for block Toeplitz System,

CBT: Block circulant preconditioning for block Toeplitz System,

WS: cg for well-conditioned Schur complement,

IS: cg for ill-conditioned Schur complement,

BIS: Band Toeplitz preconditioning ill-conditioned Schur complement, and

CIS: Circulant preconditioning for ill-conditioned Schur complement.

We have to remark that for this example we get only a weak clustering and not a strong clustering for the band Toeplitz preconditioned ill-conditioned Schur complement, since the Hankel matrix related to the function x is similar to the Hilbert matrix (Theorem 3.10). Hence, the number of iterations in the 7th column shows a logarithmic growth.

Since the dual Schur complement is well-conditioned we get a strong clustering for the block band Toeplitz preconditioner applied on the block Toeplitz system (Theorem 4.2). As a consequence, the number of iterations in the 3rd column tends to be constant.

For the circulant preconditioned matrix for the Schur complement as well as for the block circulant preconditioned matrix for the BT system we get only a weak clustering (Theorem 3.9).

Therefore, the number of iterations in the 4th and 8th columns show logarithmic growth.

EXAMPLE 5.9. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. We use as block band Toeplitz preconditioner for the BT system the matrix:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and as band Toeplitz preconditioner for the ill-conditioned Schur complement the matrix:

[T.sub.n][((2 - 2 cos(x)).sup.2]).

In Table 5.9 we give the number of iterations of pcg method as we have done in Table 5.8. The meaning of "*" is that the number of iterations exceeds the dimension of the considered matrix.

We get the same remarks as in the previous example except the band Toeplitz preconditioned ill-conditioned Schur complement. Note, that the Hankel matrix related to the function [x.sup.2] is a compact operator (Theorem 3.4, see also [1]). Consequently, the number of iterations in the 7th column tends to be constant.

EXAMPLE 5.10. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. We use as block band Toeplitz preconditioner for the BT system the matrix:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Both Schur complements are the same Toeplitz matrix: 3/4[T.sub.n]([x.sup.2]), so we use as band Toeplitz preconditioner for the ill-conditioned Schur complement the matrix:

3/4[T.sub.n] (2 - 2 cos(x)).

This example is a special case of Theorem 4.5, so F can be written in the form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Theorem 4.5 is applied, which means that the problem is reduced to solve the scalar Toeplitz system of the matrix [T.sub.n]([x.sup.2]). This system is efficiently solved by band Toeplitz preconditioned method to get superlinear convergence. Since F could be written also as the product:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where the first factor is a diagonal matrix function with roots of even order and the second one is a constant positive definite matrix function, we can use efficiently the block band diagonal Toeplitz preconditioner

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In Table 5.10 we give the associated numbers of iterations for all the methods mentioned above, where the column named by BBDT corresponds to the block band diagonal Toeplitz preconditioner. We get superlinearity in all preconditioned methods which confirms the validity of Theorem 4.5.

It should be mentioned here that the block band diagonal Toeplitz preconditioner for this example could be obtained also by Theorem 3.1 of [12], as an analogous preconditioner has been obtained in the Example 4.2 of the same paper.

6. Conclusions. We have characterized different methods to reduce the solution of BT matrices or Toeplitz Schur complements to the solution of scalar Toeplitz matrices. Furthermore, we have developed different preconditioning methods for block Toeplitz matrices and Toeplitz Schur complement matrices. In ill-conditioned cases we have to reckon with O(log(n)) outliers and growing iteration count with increasing n. Furthermore, we have developed results on the spectrum of preconditioned BT matrices and Toeplitz Schur complements. We have shown that for some cases neither circulant preconditioner nor banded preconditioner lead to an efficient iterative method. In such cases as alternative method the Multigrid approach for BT matrices [5] may be preferable, because these methods can also deal with zeros of uneven order in the generating function.

* Received October 31, 2006. Accepted for publication November 12, 2007. Published online on December 17, 2007. Recommended by M. Hochbruck.

REFERENCES

[1] A. BOTTCHER AND B. SIEBERMANN, Introduction to large truncated Toeplitz matrices, Springer-Verlag, New York, 1998.

[2] R. CHAN AND M. NG, Conjugate gragient methods for Toeplitz systems, SIAM Rev., 38 (1996), pp. 427-482.

[3] R. CHAN, Toeplitz preconditioners for Toeplitz systems with nonnegative generating functions, IMA J. Numer. Anal., 11 (1991), pp. 333-345.

[4] M.-D. CHOI, Tricks or treats with the Hilbert matrix, Amer. Math. Monthly, 90 (1983), pp. 301-312.

[5] T. HECKLE AND J. STAUDACHER, Multigrid methods for block Toeplitz matrices with small size blocks, BIT, 46 (2006), pp. 61-83.

[6] M. MIRANDA AND P. TIEEI, Asymptotic spectra of Hermitian Block Toeplitz matrices and preconditioning results, SIAM J. Matrix Anal. Appl., 21 (2000), pp. 867-881.

[7] M. N G, Iterative Methods for Toeplitz Systems, Oxford University Press, New York, 2004.

[8] D. NOUTSOS, S. SERRA CAPIZZANO, AND P. VASSAEOS, Spectral equivalence and matrix algebra preconditinoers for multilevel Toeplitz systems: a negative result, in Fast algorithms for structured matrices: theory and applications, pp. 313-322, Contemp. Math., 323, AMS, Providence, RI, 2003.

[9] D. NOUTSOS, S. SERRA CAPIZZANO, AND P. VASSAEOS, Matrix algebra preconditioners for multilevel Toeplitz systems do not ensure optimal convergence rate, Theoret. Comput. Sci., 315 (2004), pp. 557-579.

[10] S. SERRA CAPIZZANO, Optimal, quasioptimal and superlinear band-Toeplitz preconditioners for asymptotically ill-conditioned positive definite Toeplitz systems, Math. Comp., 66 (1997), pp. 651-665.

[11] S. SERRA CAPIZZANO, Asymptotic results on the spectra of Block Toeplitz preconditioned matrices, SIAM J. Matrix Anal. Appl., 20 (1998), pp. 31-44.

[12] S. SERRA CA PIZZANO, Spectral and computational analysis of Block Toeplitz matrices having nonnegative definite matrix-valued generating functions, BIT, 39 (1999), pp. 152-175.

[13] S. SERRA CAPIZZANO, A Korovkin-based approximation of multilevel Toeplitz matrices (with rectangular unstructured blocks) via multilevel trigonometric matrix spaces, SIAM J. Num. Anal., 36 (1999), pp.1831-1857.

[14] S. SERRA CAPIZZANO, Approximation of multilevel Toeplitz matrices via multilevel trigonometric matrix spaces and applications to preconditioning, Calcolo, 36 (1999), pp. 187-213.

[15] S. SERRA CAPIZZANO AND E. TYRTYSHNIKOV, Any circulant-like preconditioner for multilevel Matrices is not superlinear, SIAM J. Matrix Anal. Appl., 21 (1999), pp. 431-439.

[16] S. SERRA CAPIZZANO AND P. SUNDQVIST, Stability of the notion of approximating class of sequences and applications, to appear in J. Comp. Appl. Math..

[17] E. TYRTYSHNIKOV, How bad are Hankel matrices?, Num. Math., 67 (1994), pp. 261-269.

[18] H. Widom Hankel matrices, Trans. Amer. Math. Soc., 121 (1966), pp. 1-35.

[19] H. Widom, Asymptotic behavior of block Toeplitz matrices and determinants II, Adv. Math., 21 (1976), pp. 1-29.

THOMAS K. HUCKLE ([dagger]) AND DIMITRIOS NOUTSOS ([double dagger])

([dagger]) Fakultat fur Informatik, Technische Universitat Munchen, Boltzmannstr. 3, D-85748 Garching, Germany (huckle@in.tum.de).

([double dagger]) Department of Mathematics, University of Ioannina, GR-45110, Greece (dnoutsos@uoi.gr). This research was co-funded by the European Union--European Social Fund (ESF) & National Sources, in the framework of the program "Pythagoras I" of the "Operational Program for Education and Initial Vocational Training" of the 3rd Community Support Framework of the Hellenic Ministery of Education.
```TABLE 5.1

Number of eigenvalues of the circulant preconditioned well-conditioned
BT system outside [0.9,1.1].

Size 2*10 2*20 2*40 2*80 2*160 2*320

outliers 9 5 5 5 5 5

TABLE 5.2

Number of eigenvalues of [N.sub.n], outside [0.9,1.001] for Toeplitz
preconditioned Toeplitz normal equations.

Size 10 20 40 80 160 320 640

outliers 2 2 2 2 2 2 2

TABLE 5.3

Number of eigenvalues outside [0.99, 1.01] as example for strong
clustering for well-conditioned Toeplitz Schur complement with
circulant preconditioner

Size 10 20 40 80 160 320 640

outliers [S.sub.1] 3 2 2 2 2 2 2
outliers [S.sub.2] 3 2 2 2 2 2 2

TABLE 5.4

Number of eigenvalues outside [0.9,1.001] as example for strong
clustering for well-conditioned Toeplitz Schur complement with
Toeplitz preconditioner.

Size 10 20 40 80 160 320 640

outliers 2 2 2 2 2 2 2

TABLE 5.5

Number of eigenvalues of outside [0.9, 1.001] as an example for no
strong clustering for Toeplitz preconditioned Toeplitz Schur
complement.

Size 10 20 40 80

outliers toeplitz (2, -1, 0, ...) 2 2 2 2
outliers toeplitz (6, -4,1, 0, ...) 2 2 3 4

Size 160 320 640 1280

outliers toeplitz (2, -1, 0, ...) 3 3 4 4
outliers toeplitz (6, -4,1, 0, ...) 4 6 6 8

TABLE 5.6

Maximum eigenvalue as an example for unboundedness for Toeplitz
preconditioned Toeplitz Schur complement.

Size 10 20 40 80

[[lambda].sub.max] for 3.1 6.0 12.2 25.3
toeplitz (2, -1, 0, ...)
[[lambda].sub.max] for 2.0E1 1.8E2 1.6E3 1.4E4
toeplitz (6, -4,1, 0, ...)

Size 160 320 640 1280

[[lambda].sub.max] for 52.2 106.7 216.5 437.1
toeplitz (2, -1, 0, ...)
[[lambda].sub.max] for 1.1E5 9.2E5 7.5E6 6.0E7
toeplitz (6, -4,1, 0, ...)

TABLE 5.7

Minimum and maximum eigenvalue of the preconditioned spectrum
[T.sup.-1.sub.n] (P) * [T.sub.n], ([F.sub.j]), j = 1, 2, 3.

Size 10 20 40 80

[[lambda[.sub.min], 0.83, 2.4 0.81, 2.6 0.80, 2.7 0.80, 2.9
[[lambda].sub.max]
for [F.sub.1]

[[lambda[.sub.min], 0.1, 9.0 4E-2, 26.9 lE-2, 96.5 4E-3, 4E2
[[lambda].sub.max]
for [F.sub.2]

[[lambda[.sub.min], 0.90, 8.0 0.84, 8.9 0.82, 9.4 0.81, 9.8
[[lambda].sub.max]
for [F.sub.3]

Size 160 320 640

[[lambda[.sub.min], 0.80, 2.9 0.80, 2.9 0.80, 3.0
[[lambda].sub.max]
for [F.sub.1]

[[lambda[.sub.min], lE-3, 1E3 4E-4, 6E3 lE-4, 2E4
[[lambda].sub.max]
for [F.sub.2]

[[lambda[.sub.min], 0.80, 9.9 0.80, 10.1 0.80, 10.1
[[lambda].sub.max]
for [F.sub.3]

TABLE 5.8

Iterations for BT system and for Schur Complements of example 5.8

n BT BBT CBT WS IS BIS CIS

4 8 7 5 2 2 2 2
8 15 10 12 3 4 4 4
16 31 12 14 3 8 8 5
32 64 14 15 3 17 9 5
64 128 14 16 3 39 10 6
128 202 14 16 3 86 11 6
256 350 14 18 3 187 11 6
512 619 13 19 4 395 12 9
1024 1189 13 20 4 819 12 10

TABLE 5.9

Iterations for BT system and for Schur Complements of example 5.9

n BT BBT CBT WS IS BIS CIS

4 4 4 3 2 2 2 2
8 11 7 6 2 4 4 4
16 25 9 9 2 9 8 6
32 * 12 12 2 28 10 8
64 * 16 11 2 * 12 11
128 * 18 15 2 * 13 10
256 * 20 17 2 * 14 14
512 * 20 25 2 * 14 15
1024 * 20 24 2 * 14 24

TABLE 5.10

Iterations for BT system and for Schur Complements of example 5.10

n BT BBT BBDT IS BIS

4 2 2 2 2 2
8 4 4 4 4 4
16 8 7 7 8 7
32 16 9 9 16 9
64 36 10 10 37 10
128 82 10 10 82 10
256 177 10 10 177 10
512 372 11 11 372 11
1024 768 11 11 768 11
```
COPYRIGHT 2007 Institute of Computational Mathematics
No portion of this article can be reproduced without the express written permission from the copyright holder.