# Algebraic Multigrid smoothing property of Kaczmarz's relaxation for general rectangular linear systems.

1. Algebraic Multigrid (AMG)--some historical comments. In the
early 80's the AMG methods have been designed for the solution of
(sparse) linear systems of equations using classical (geometric)
multigrid ideas. The starting point and initial paper on the sub ject
seems to be the 1982 Report [4] by Brandt, McCormick, and Ruge; see the
references from [6]. In the same period of time, at the occasion of the
1983 International MG Conference at Copper Mountain, three other basic
papers were presented; see [5, 16, 19]. Not far from this moment, in
[17] StUben and Ruge developed both theoretical aspects together with
implementation issues of the classical AMG, as we think of it today.
Moreover, although the initial theoretical results and efficient
implementations were concerned with the class of symmetric M-matrices,
recent developments, for which a rigorous convergence and optimality
theory (level independence, dimension independence, etc.) have been
obtained, are related to structured matrices (Toeplitz, circulants,
sine/cosine, transform matrices, Hartley matrices, etc.). These matrices
are characterized by the shift invariance property joint with proper
boundary conditions; see [1, 2, 18] and references therein.

2. The smoothing property--definition and classical results. According to the basic principles of AMG, as described in the papers mentioned before, the smoother (AMG relaxation) is usually fixed among the classical iterative methods (Gauss--Seidel, Jacobi, Kaczmarz etc.). But, in order to design an efficient AMG code the smoothing property of this smoother has to be properly formulated and proved. In this respect, we shall briefly replay in what follows the basic ideas and results from the classical AMG theory. Let B be an n x n symmetric and positive definite matrix (SPD, for short), and c [member of] [R.sup.n] a given vector. By [B.sub.i], [B.sub.ij] we shall denote the i-th row and (i, j)-th element of B. All the vectors that will appear will be column vectors and the superscript T will indicate the transpose. For the purposes of this section we consider the system of linear equations

(2.1) B[x.sup.*] = c,

where [x.sup.*] = [B.sup.-1] c is its unique solution. Let

(2.2) [x.sup.0] [member of] [R.sup.n], [x.sup.k+1] = [Gx.sup.k] + g, k [greater than or] 0,

or componentwise

[x.sup.k+1.sub.i] = [g.sub.i] + [n.summation over (j=1)] [G.sub.ij][x.sup.k.sub.j],

be a (convergent) relaxation scheme for (2.1). Denoting by <*,*>, [parallel]*[parallel] the Euclidean scalar product and norm, respectively, we define the energy norms [[parallel]*[parallel].sub.B] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(2.3) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where

D = diag(B) = diag([B.sub.11], ..., [B.sub.nn]).

REMARK 2.1. This special (diagonal) choice of D is related to the classical approach considered in [17]. But, it can be replaced by any positive definite matrix D (see Remark 2 in [1] and also [2]). This further degree of flexibility could be useful for refining the convergence results.

Let x be a given approximation of [x.sup.*], x the one obtained after one step of the relaxation scheme (2.2) applied to x and e, [bar.e], r the corresponding errors and residual defined by

(2.4) e = x - [x.sup.*], r = Be = Bx - c, [bar.e] = [bar.x] - [x.sup.*].

DEFINITION 2.2. We say that the relaxation scheme (2.2) satisfies the smoothing property (SP, for short) for the system (2.1) if there is a constant a > 0 (independent of the dimension n of B) such that

(2.5) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In what follows we shall present classical results about the SP property for some well-known relaxation schemes of the type (2.2).

Gauss-Seidel. Let [x.sup.0] [member of] [R.sup.n]; for k = 0,1, ... do

(2.6) [x.sup.k+1.sub.i] = 1/[B.sub.ii] [[c.sub.i] - [summation over (j<1)] [B.sub.ij] [x.sup.k+1.sub.j] [summation over (j>1)]- [B.sub.ij][x.sup.k.sub.j]], [for all] i = 1,...,n.

SOR. Let [x.sup.0] [member of] [R.sup.n]; for k = 0,1, ... do

(2.7) [x.sup.k+1.sub.i] = (1 - [omega])[x.sup.k.sub.i] + [omega]/[B.sub.ii] [[c.sub.i] - [summation over (j<1)] [B.sub.ij] [x.sup.k+1.sub.j] [summation over (j>1)]- [B.sub.ij][x.sup.k.sub.j]], [for all]i = 1, ..., n.

Kaczmarz. Let [x.sup.0] [member of] [R.sup.n]; for k = 0,1, ... do

(2.8) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The following result analyzes property (2.5) for the Gauss-Seidel relaxation (for the proof see [7] and [21, Theorem A.3.1, p. 436]).

THEOREM 2.3. Gauss-Seidel relaxation (2.6) for the system (2.1) satisfies (2.5) with [alpha] = [[gamma].sub.0] given by

(2.9) [[gamma].sub.0] = 1/(1+[[gamma].sub.-](B)) (1+[[gamma].sub.+](B))

and

(2.10) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In [11] we extended the above theorem for SOR relaxation (2.7) in the following way:

THEOREM 2.4. The SOR relaxation (2.7) for the system (2.1) satisfies (2.5) with [alpha] = [[delta].syb.0] given by

[[delta].sub.0] = [omega](2 - [omega])/(1 + [[delta].sub.-](B))(1 + [[delta].sub.+](B))

and

(2.11) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

REMARK 2.5. If the matrix B satisfies [B.sub.ii] = [B.sub.jj], [for all]i, j = 1, ..., n (as is the case in some finite differences approximations of boundary value problems or Toeplitz circulant problems), then the constants [[delta].sub.-] (B), [[delta].sub.+] (B) from (2.11) are equal with [[gamma].sub.-] (B), [[gamma].sub.+] (B) from (2.10), respectively. Thus, in this case Theorem 2.4 is an extension of Theorem 2.3 for SOR relaxation.

In order to derive an SP for Kaczmarz relaxation (2.8), we shall consider a general invertible matrix A (not necessarily SPD), b [member of] [R.sup.n] a given vector and the linear system

(2.12) A[x.sup.*] = b,

with [x.sup.*] its unique solution. For a given approximation x of [x.sup.*] from (2.12), let x be the approximation of [x.sup.*] obtained after a Kaczmarz step (2.8) applied to x and e = x - [x.sup.*], e = x - [x.sup.*] and r = Ae the corresponding errors and residual (see (2.4)). The following theorem was first proved in [7]. But, we shall present in what follows another, more detailed proof required for the results described in section 2 of the paper; see also Remark 2.9 below.

THEOREM 2.6. Using the above definitions and notation, Kaczmarz relaxation (2.8) for the system (2.12) satisfies the following smoothing property (of the type (2.5))

(2.13) [[parallel]e[parallel].sup.2] [less than or equal to] [[parallel]e[parallel].sup.2] - [[bar.[gamma]].sub.0] [parallel][[bar.D].sup.1/2]r[parallel].sup.2],

where

(2.14) D = diag(1/[[parallel][A.sub.1][parallel].sup.2], ..., 1/[[parallel][A.sub.n][parallel].sup.2]),

(2.15) [[bar.[gamma]].sub.0] = 1/(1 +[[bar.[gamma]].sub.-](A))(1 + [[bar.[gamma]].sub.+](A))

and

(2.16) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof. Let [g.sub.i] = [(0,...,1,...,0).sup.T] [member of] [R.sup.n], i = 1, ..., n be the canonical basis. We first observe that, because of the symmetry of B, [Bg.sub.i] = [B.sub.i] the expression (2.6) can be written as follows: [x.sup.0] [member of] [R.sup.n] given; for k = 0,1, ... do

(2.17) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Now, if we write the system (2.12) in the form

(2.18) ([AA.sup.T])y* =b, [x.sup.*] = [A.sup.T] y*,

and we apply to it Gauss-Seidel relaxation (2.17) (B = AA T, c = b) with the initial approximation [y.sup.0], we get

(2.19) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

If we multiply from the left in (2.19) by AT and replace the terms of the form AT [y.sup.k,i] by [x.sup.k,i], we obtain exactly the Kaczmarz step (2.8) applied to the system (2.12). Thus, the Kaczmarz step (2.8) applied to the system (2.12) with an initial approximation of the form [x.sup.0] = [A.sup.T] [y.sup.0], for some [y.sup.0] [member of] [R.sup.n] is equivalent to the Gauss-Seidel step (2.17) applied to the system (2.18), with the initial approximation [y.sup.0] and setting [x.sup.k+1] = [A.sup.T] [y.sup.k+1]. But, because the matrix [AA.sup.T] is SPD, we can apply Theorem 2.3 for the Gauss-Seidel iteration and get (see (2.5) and (2.3))

(2.20) <([AA.sup.T])[bar.f], [bar.f]) [less than or equal to] <([AA.sup.T])f,f) - [[bar.[gamma]].sub.0]<[bar.D][AA.sup.T]f, [AA.sup.T]f)

with [bar.D] from (2.14), [[bar.[gamma]].sub.0] computed as in (2.9)-(2.10) with AAT instead of B, and with f, [bar.f] the corresponding errors with respect to the system (2.18). But, if e, [bar.e] and r are the corresponding errors and residual, respectively for the Kaczmarz relaxation, we have the following relations

e = [A.sup.T]f, [bar.e] = [A.sup.T][bar.f],

which when substituted into (2.20) give us (2.13) with the elements from (2.14)-(2.16) and the proof is complete.

A similar result as in Theorem 2.6 can be proved for the Kaczmarz iteration with relaxation parameter (for short, [omega]-Kaczmarz relaxation), as described below. [omega]-Kaczmarz relaxation. Let [x.sup.0] [member of] [R.sup.n]; for k = 0,1.... do

(2.21) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

THEOREM 2.7. Using the above definitions and notation, the w-Kaczmarz relaxation (2.21) for the system (2.12) satisfies the following smoothing property (of the type (2.5))

(2.22) [[parallel]e[parallel].sup.2] [less than or equal to] [[parallel]e[parallel].sup.2] - [[bar.[delta]].sub.0] [[parallel][[bar.D].sup.1/2]r[parallel].sup.2]

with [bar.D] from (2.14) and

(2.23) [[bar.[delta]].sub.0] = (1 + [[bar.[delta]].sub.-](A))(1+[bar.[delta]+(A)),

(2.24) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof. As in the proof of Theorem 2.6 we first show the equivalence between the [omega]-Kaczmarz and the SOR relaxation (2.7) written in the form (2.17); see also [10].

REMARK 2.8. The Kaczmarz iteration (2.8) or (2.21) is less efficient as smoother than the Gauss-Seidel one (2.6) (see for a detailed discussion Remark 4.7.2, page 128 in [21]). But, inspite of this, it has the advantage of being applicable to a much larger class of systems (than the classical square invertible ones).

REMARK 2.9. We have to observe that in (2.13) and (2.22), for the errors [bar.e] and e we have the Euclidean norm, instead of the energy one from (2.5). Moreover, the proofs of Theorems 2.6 and 2.7 are based on Theorems 2.3 and 2.4, i.e., the matrix B = [AA.sup.T] must be SPD; thus, we cannot expect such a simple and direct extension of Theorems 2.6 and 2.7 to arbitrary noninvertible systems like (2.12), because in such a case, the matrix [AA.sup.T] is no longer SPD. This extension will be proved in the next section of the paper, using a special technique.

3. Smoothing property of Kaczmarz relaxation for arbitrary consistent systems. Let A be an m x n matrix with [A.sub.i] [not equal to] 0, [for all]i = 1, ... m and b [member of] [R.sup.m] such that the system

(3.1) Ax =b

is consistent. We shall denote by S (A;b), N (A), R (A) the solutions set for (3.1), null space and range of A, respectively. For a given vector subspace E [subset] [R.sup.q], [P.sub.E](x) will be the orthogonal projection onto E of an element x [member of] [R.sup.q] and [E.sup.[perpendicular to]] will denote its orthogonal complement. If [x.sub.LS] is the (unique) minimal norm solution of (3.1) it is well known that (see, e.g., [3], [8])

(3.2) [x.sub.LS] [member of] N[(A).sup.[perpendicular to] = R([A.sup.T]), S(A;b) = [x.sub.LS] + N(A).

Thus, for a vector z [member of] [R.sup.n] we shall denote by s(z) the solution vector (see (3.2))

(3.3) s(z) = [P.sub.N(A)] (z) + [x.sub.LS] [member of] S(A; b).

The Kaczmarz relaxation for (3.1) can be written as (see (2.8)): let [x.sup.0] [member of] [R.sup.n] be given; for k = 0,1,2 ... do

(3.4) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The following results are known (see, e.g., [20]).

THEOREM 3.1. For any [x.sup.0] [member of] [R.sup.n], the sequence [([x.sup.k])k[greater than or equal to]0] generated by the algorithm (3.4) has the properties

(3.5) [P.sub.N(A)]([x.sup.k]) = [P.sub.N(A)]([x.sup.0]), [for all]k [greater than or equal to] 0

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let now x [member of] [R.sup.n] be a current approximation of s([x.sup.0]) (generated by (3.4), for k = 0, x = [x.sup.0]) and x the approximation after one step of (3.4) applied to x. Let e, [bar.e], r be the corresponding errors and residual, defined by (according to (3.3) and (3.5))

e = x - s([x.sup.0]), [bar.e] = x-s([x.sup.0]), r = Ae = Ax - [Ax.sub.LS] = Ax - b.

Then, the generalization of Theorem 2.6 is the following.

THEOREM 3.2. Using the above definitions and notation, Kaczmarz relaxation (3.4) for the system (3.1) satisfies the smoothing property (2.13)-(2.16).

Proof. Step 1. According to (3.4), the computation of x from x can be written as

(3.6) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let {[f.sub.1], [f.sub.2], ..., [f.sub.m]} be the canonical basis in [R.sup.m] and [e.sup.i], [r.sup.i] the errors and residuals defined by

(3.7) [e.sup.i] = [x.sup.i] - s([x.sup.0]), [r.sup.i] = [Ae.sup.i], i = 1,...,m.

Then, for i = 1, ... m, we obtain (by also using the equality [A.sub.i] = [A.sup.T] [f.sub.i])

(3.8) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and

(3.9) [r.sup.i] = [Ae.sup.i] = [r.sup.i-1]<[r.sup.i-1,[f.sub.i]>/ [[parallel][A.sub.i][parallel].sup.2] [AA.sub.i].

From (3.8), taking the Euclidean norm and using again the equality [A.sub.i] = [A.sup.T] [f.sub.i] and (3.7) we Obtain

(3.10) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [r.sup.i-1] is the i-th component of the residual vector [r.sup.i-1]. But, because of (3.6) we have [x.sup.0] = x, x = [x.sup.m], then [e.sup.0] = e, [bar.e] = [e.sup.m]. Thus, summing up in (3.10), we get

(3.11) [[parallel][bar.e][parallel].sup.2] = [[parallel]e[parallel].sup.2] - [m.summation over (i=1)] [([r.sup.i- 1.sub.i]).sup.2]/ [[parallel][A.sub.i][parallel].sup.2].

Step 2. Let now r* = [([r.sup.*.sub.1],..., [r.sup.*.sub.m]).sup.T] [member of] [R.sup.m] be the dynamic residual (as called in [7]), defined by

(3.12) [r.sup.*.sub.i] = [r.sup.i-1.sub.i], i = 1, ..., m,

i.e., [r.sup.*.sub.i] is the i-th component of the residual [r.sup.i-1] (that is, the residual before the projection on the i-th equation of (3.6)). From (3.11) and (3.12), we then get

(3.13) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

with [bar.D] from (2.14). On the other hand, from the equation (3.9), we successively obtain

(3.14) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where

(3.15) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Then, from the definition of the matrices [E.sub.i] in (3.15) and (3.12), we get [r.sup.*.sub.1] = [r.sup.0.sub.1] = [r.sub.1] and for i = 2, ..., m,

[r.sup.*.sub.i] = [r.sub.i] - ([B.sub.i1] [r.sup.0.sub.1] + [B.sub.i2][r.sup.1.sub.2] + ... + [B.sub.i,i-1] [r.sup.i-1.sub.i]))

or in matrix form

(3.16) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

or (see also (3.13))

(3.17) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where L is the corresponding strictly lower triangular matrix from (3.16).

Step 3. If C is a square matrix and [[parallel]C[parallel].sub.2], [[parallel]C[parallel].sub.[infinity]] are, respectively its spectral and infinity norm (see, e.g., [3]), we have

(3.18) [[parallel]C[parallel].sup.2.sub.2] = [rho]([C.sup.T]C) [less than or equal to] [[parallel][C.sup.T]C[parallel].sub.[infinity]] [less than or equal to] [[parallel][C.sup.T][parallel].sub.[infinity]] [[parallel]C[parallel].sub.[infinity]].

Using (3.18) and taking the Euclidean norm in (3.17), we obtain

(3.19) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

But, a simple computation gives us

(3.20) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

with [[??].sub.-] (A), [[??].sub.+] (A) from (2.16). Then, using (3.13), (3.19) and (3.20), we get (2.13) and the proof is complete.

A similar result can be proved for [omega]-Kaczmarz relaxation.

THEOREM 3.3. Using the above definitions and notation, the [omega]-Kaczmarz relaxation for the system (3.1) satisfies the smoothing property (2.22)-(2.24).

Proof. The [omega]-Kaczmarz relaxation (2.21) for the system (3.1) can be written as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

As in the proof of Theorem 3.2, we get

[e.sup.i] = [e.sup.i-1] - [omega](2 - [omega]) <[r.sup.i-1], [f.sub.i]>/ [[parallel][A.sub.i][parallel].sup.2] [A.sub.i]

and

[r.sup.i] = [Ae.sup.i] = [r.sup.i-1] - [omega](2 - [omega]) <[r.sup.i-1], [f.sub.i]>/ [[parallel][A.sub.i[parallel].sup.2] [AA.sub.i].

Then we proceed in exactly the same way as in the above mentioned proof.

4. Smoothing property of Kaczmarz Extended relaxation for arbitrary inconsistent systems. Let A and b be as in section 2. Instead of the consistent system (3.1), we shall consider in this section the linear least squares formulation (inconsistent system)

(4.1) [parallel]Ax - b[parallel] = min!,

for which we shall denote by LSS(A; b) and [x.sub.LS] the set of its solutions and the minimal norm one, respectively. Let [b.sub.A], [b.sup.*.sub.A] be defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Then (see, e.g., [3])

(4.2) b = [b.sub.A] + [b.sup.*.sub.A], LSS(A; b) = S(A; [b.sub.A]) = [x.sub.LS] + N(A).

Moreover, (see (3.3)) for any z [member of] [R.sup.n], we have

s(z) = [P.sub.N(A)] (z) +[x.sub.LS] [member of] LSS(A; b) = S(A; [b.sub.A]).

Thus we define (as in section 2) the error and residual by

(4.3) e=e(z)=z-s(z), r = Ae = Az - [b.sub.A].

The Kaczmarz Extended algorithm for (4.1) (KE, for short), introduced in [12] (see also [13]) is the following.

Kaczmarz Extended. Let [x.sup.0] [member of] [R.sup.n], [y.sup.0] = b; for k = 0,1, ... do

(4.4) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where

[[psi].sub.j](y) = y <y, [A.sup.j])/ [[parallel][A.sup.j][parallel].sup.2] [A.sup.j]

and [A.sup.j] [not equal to] 0, j = 1,...,n, are the columns of A. In [14] we proved that the sequence [([x.sup.k]).sub.k[greater than or equal to]0] generated with the above KE algorithm satisfies the relation (3.5). Then, if x = [x.sup.k] (for some k [greater than or equal to] 0) is a current approximation, we shall define the error (see (4.3)) by

e = x - s([x.sup.0]).

Let y = [y.sup.k] be the corresponding element from the first step of (4.4) and [bar.y] = [y.sup.k+1], i.e.,

(4.5) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where (see for details [13])

(4.6) [??](y) = [PHI][P.sub.R(A)] (y) [member of] R(A).

From (4.5) and (4.6), we get that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus (see also (4.2))

(4.7) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Then, if [bar.b] = [b.sup.k+1] (see (4.4)), from (4.5) and (4.7), we obtain

(4.8) [bar.b] = b - [bar.y] = [b.sub.A] - [??],

Where

(4.9) [??] = [??](y)

REMARK 4. 1. Returning to the original notation, from the above equalities (4.7)-(4.9), we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Moreover, in [20] it is proved that [[parallel][??][parallel].sub.2] < 1. Thus

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The extension of Theorem 3.2 to the problem (4.1), for the KE algorithm (4.4) is the following.

THEOREM 4.2. Using the above definitions and notation, the KE relaxation (4.4) for the (inconsistent) problem (4.1) satisfies the following smoothing property

(4.10) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

with [??] and [[??].sub.0] from (2.14)-(2.16).

Proof. Step 1. The third step in (4.4) can be written as (see also (2.8))

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Then, by defining the errors (see also (3.7))

(4.11) [e.sup.i] = [x.sup.i] - s([x.sup.0]), i = 1, ..., m, [bar.e] = [e.sup.m],

we get

(4.12) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

From (4.12) we obtain (by also using the relation [A.sub.i] = [A.sup.T] [f.sub.i])

(4.13) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Then by summing in (4.13), using (4.11) and the notation from section 2, we get

(4.14) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Step 2. From (4.12) we obtain (see again the notation in section 2)

ri = [Ae.sup.i] = [Ae.sup.i-1] - [r.sup.i-1.sub.i]/[[parallel][A.sub.i][parallel].sup.2] [AA.sub.i] - [[??].sub.i]/[[parallel]{S.sub.i][parallel].sup.2] [AA.sub.i] = ri-1 - [BE.sub.i][r.sup.i-1] - [BE.sub.i][??],i = 1, ..., m,

thus

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Using the equality (see section 2)

r* = [([r.sub.1],[r.sup.1.sub.2],...,[r.sup.m-1.sub.m]).sup.T],

we obtain

(4.15) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Writing (4.15) in matrix form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

with L from (3.16), we get

(4.16) r* = r - Lr* - L[??].

From (4.16) we obtain as in section 2

(4.17) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Where

(4.18) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Using (4.17) and (4.18), it follows that

(4.19) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

From (4.19) and (2.15), we then obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which together with (4.14) gives us (4.10) and the proof is complete.

A similar result can be derived for the Kaczmarz Extended algorithm with Relaxation Parameters (KERP, for short), introduced in [13].

KERP Let [x.sup.0] [member of] [R.sup.n], [y.sup.0] = b; for k = 0,1, ... do

(4.20) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where

[[psi].sub.j] ([alpha]; y) = y - [alpha] <y, [A.sup.j]> [[parallel][A.sup.j][parallel].sup.2] [A.sup.j].

THEOREM 4.3. Using the above definitions and notation, KERP relaxation (4.20) for the (inconsistent) problem (4.1) satisfies the following smoothing property

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

with [??] and [[??].sub.0] from (2.14), (2.23), and [??] (a) = [PHI]([alpha]; y).

Proof. Apply Theorems 4.3 and 2.7 to [omega]-Kaczmarz relaxation.

REMARK 4.4. The result from Theorem 3.2 is not a particular case of Theorem 4.2. Indeed, if b [member of] R(A) for the problem (4.1), we have [b.sup.*.sub.A] = 0. Thus, [bar.y] = [??] [member of] R (A), but we cannot drop the term 2 [[parallel][[??].sup.1/2][??][parallel].sup.2] in (4.10). Thus, in the consistent case Theorems 3.2 and 4.2 provide two smoothing properties for two different algorithms: Kaczmarz and Kaczmarz Extended.

5. Final comments and further developments. In this paper we formulated and proved AMG smoothing properties for the classical Kaczmarz and Kaczmarz Extended algorithms in the general case of arbitrary rectangular systems, either consistent or in least squares formulation. In the consistent case, our result for classical Kaczmarz relaxation (Theorem 3.2) generalizes the well-known result for square invertible matrices (Theorem 2.6). The general character of the matrices involved in the above theory makes extension to AMG to general least squares problems possible. Some steps in this direction have been taken in [15] and [9], but both the theoretical development and experiments are in initial phases.

Acknowledgement. The author thanks the two referees for their comments and suggestions which improved some important parts of the original version of the paper.

* Received October 12, 2006. Accepted for publication July 3, 2007. Published online on July 22, 2008. Recommended by A. Frommer.

REFERENCES

[1] A. ARIC6, M. DONATELLI, AND S. SERRA-CAPIZZANO, V-Cycle optimal convergence for certain (multilevel) structured linear systems, SIAM J. Matrix Anal. Appl., 26 (2004), pp. 186-214.

[2] A. ARIC6 AND M. DONATELLI, V-cycle multigrid for multilevel algebaas: proof of optimality, Numer. Math., 105 (2007), pp. 511-547.

[3] A. BJORCK, Numerical Methods for Least Squares Problems, SIAM, Philadelphia, PA, 1996.

[4] A. BRANDT, S. MCCORMICK, AND J. RUDE, Algebraic multigrid (AMG) for automatic multigrid solution with application to geodetic computations, Technical Report, Institute for Computational Studies, Colorado State University, 1982.

[5] A. BRANDT, Algebraic multigrid theory: the symmetric case (a preliminary version), in Preliminary Proceedings for the International Multigrid Conference (Copper Mountain, Colorado), April, 1983.

[6] A. BRANDT, S. MCCORMICK, AND J. RUDE, Algebraic multigrid (AMG) for sparse matrix equations, in Sparsity and Its Applications, D.J. Evans, ed., Cambridge University Press, Cambridge, 1984.

[7] A. BRANDT, Algebraic multigrid theory: the symmetric case, Appl. Math. Comp., 19 (1986), pp. 23-56.

[8] Y. CENSOR AND A. Z. STAVROS, Parallel Optimization: Theory, Algorithms and Applications, Oxford Univ. Press, New York, 1997.

[9] H. KOSTLER, C. POPA, M. PRUMMER, AND U. RUDE, Towards an algebraic multigrid method for tomographic image reconstruction--improving convergence of ART, Paper 476 in Electronic Proceedings of the European Conference on Computational Fluid Dynamics ECCOMAS CFD 2006, The Netherlands, 2006.

[10] F. NATTERER, The Mathematics of Computerized Tomography, John Wiley and Sons, New York, 1986.

[1l] C. POPA, On smoothing property of the SOR relaxation, Studii si Cercetari Matematice, 41 (1989), pp. 399406.

[12] C. POPA, Least-squares solution of overdetermined inconsistent linear systems using Kaczmarz's relaxation, Internat. J. Comput. Math., 55 (1995), pp. 79-89.

[13] C. POPA, Extensions of block-projections methods with relaxation parameters to inconsistent and rankdefficient least-squares problems, BIT, 38 (1998), pp. 151-176.

[14] C. POPA, Characterization of the solutions set of inconsistent least-squares problems by an extended Kaczmarz algorithm, Korean J. Comp. Appl. Math., 6 (1999), pp. 51-64.

[15] M. PRUMMER, H. KOSTLER, J. HORNEGGER, AND U. RUDE, A full multigrid technique to accelerate an ART scheme for tomographic image reconstruction, in Proceedings of ASIM Conference, September 12-15 2005, SCS Publishing House, Erlangen, Germany, pp. 632-637.

[16] J. RUDE, Algebraic multigrid (AMG) for geodetic survey problems, in Preliminary Proceedings for the International Multigrid Conference (Copper Mountain, Colorado), April, 1983, 24 pages.

[17] J. RUGS AND K. STUBEN, Algebraic Multigrid (AMG), Arbeitspapiere der GMD Bonn 210, GMD, Bonn, Germany, 1986.

[18] S. SERRA-CAPIZZANO, Convergence analysis of two-grid methods for elliptic Toeplitz and PDEs matrixsequences, Numer. Math., 92 (2002), pp. 433-465.

[19] K. STUBEN, Algebraic multigrid (AMG): experiences and comparisons, Appl. Math. Comput. 13 (1983), pp. 419-451.

[20] K. TANABE, Projection method for solving a singular system of linear equations and its applications, Numer. Math., 17 (1971), pp. 203-214.

[21] U. TROTTENBERG, C. OOSTERLEE, AND A. SCHULLER, Multigrid, Academic Press, London, 2001.

[22] D. M. YOUNG, Iterative Solution of Large Linear Systems, Academic Press, New York, 1971.

CONSTANTIN POPA ([dagger])

([dagger]) Faculty of Mathematics and Computer Science, Ovidius University of Constanta, Blvd. Mamaia 124, 900527 Constanta, Romania (cpopa@univ-ovidius.ro).

2. The smoothing property--definition and classical results. According to the basic principles of AMG, as described in the papers mentioned before, the smoother (AMG relaxation) is usually fixed among the classical iterative methods (Gauss--Seidel, Jacobi, Kaczmarz etc.). But, in order to design an efficient AMG code the smoothing property of this smoother has to be properly formulated and proved. In this respect, we shall briefly replay in what follows the basic ideas and results from the classical AMG theory. Let B be an n x n symmetric and positive definite matrix (SPD, for short), and c [member of] [R.sup.n] a given vector. By [B.sub.i], [B.sub.ij] we shall denote the i-th row and (i, j)-th element of B. All the vectors that will appear will be column vectors and the superscript T will indicate the transpose. For the purposes of this section we consider the system of linear equations

(2.1) B[x.sup.*] = c,

where [x.sup.*] = [B.sup.-1] c is its unique solution. Let

(2.2) [x.sup.0] [member of] [R.sup.n], [x.sup.k+1] = [Gx.sup.k] + g, k [greater than or] 0,

or componentwise

[x.sup.k+1.sub.i] = [g.sub.i] + [n.summation over (j=1)] [G.sub.ij][x.sup.k.sub.j],

be a (convergent) relaxation scheme for (2.1). Denoting by <*,*>, [parallel]*[parallel] the Euclidean scalar product and norm, respectively, we define the energy norms [[parallel]*[parallel].sub.B] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(2.3) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where

D = diag(B) = diag([B.sub.11], ..., [B.sub.nn]).

REMARK 2.1. This special (diagonal) choice of D is related to the classical approach considered in [17]. But, it can be replaced by any positive definite matrix D (see Remark 2 in [1] and also [2]). This further degree of flexibility could be useful for refining the convergence results.

Let x be a given approximation of [x.sup.*], x the one obtained after one step of the relaxation scheme (2.2) applied to x and e, [bar.e], r the corresponding errors and residual defined by

(2.4) e = x - [x.sup.*], r = Be = Bx - c, [bar.e] = [bar.x] - [x.sup.*].

DEFINITION 2.2. We say that the relaxation scheme (2.2) satisfies the smoothing property (SP, for short) for the system (2.1) if there is a constant a > 0 (independent of the dimension n of B) such that

(2.5) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In what follows we shall present classical results about the SP property for some well-known relaxation schemes of the type (2.2).

Gauss-Seidel. Let [x.sup.0] [member of] [R.sup.n]; for k = 0,1, ... do

(2.6) [x.sup.k+1.sub.i] = 1/[B.sub.ii] [[c.sub.i] - [summation over (j<1)] [B.sub.ij] [x.sup.k+1.sub.j] [summation over (j>1)]- [B.sub.ij][x.sup.k.sub.j]], [for all] i = 1,...,n.

SOR. Let [x.sup.0] [member of] [R.sup.n]; for k = 0,1, ... do

(2.7) [x.sup.k+1.sub.i] = (1 - [omega])[x.sup.k.sub.i] + [omega]/[B.sub.ii] [[c.sub.i] - [summation over (j<1)] [B.sub.ij] [x.sup.k+1.sub.j] [summation over (j>1)]- [B.sub.ij][x.sup.k.sub.j]], [for all]i = 1, ..., n.

Kaczmarz. Let [x.sup.0] [member of] [R.sup.n]; for k = 0,1, ... do

(2.8) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The following result analyzes property (2.5) for the Gauss-Seidel relaxation (for the proof see [7] and [21, Theorem A.3.1, p. 436]).

THEOREM 2.3. Gauss-Seidel relaxation (2.6) for the system (2.1) satisfies (2.5) with [alpha] = [[gamma].sub.0] given by

(2.9) [[gamma].sub.0] = 1/(1+[[gamma].sub.-](B)) (1+[[gamma].sub.+](B))

and

(2.10) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In [11] we extended the above theorem for SOR relaxation (2.7) in the following way:

THEOREM 2.4. The SOR relaxation (2.7) for the system (2.1) satisfies (2.5) with [alpha] = [[delta].syb.0] given by

[[delta].sub.0] = [omega](2 - [omega])/(1 + [[delta].sub.-](B))(1 + [[delta].sub.+](B))

and

(2.11) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

REMARK 2.5. If the matrix B satisfies [B.sub.ii] = [B.sub.jj], [for all]i, j = 1, ..., n (as is the case in some finite differences approximations of boundary value problems or Toeplitz circulant problems), then the constants [[delta].sub.-] (B), [[delta].sub.+] (B) from (2.11) are equal with [[gamma].sub.-] (B), [[gamma].sub.+] (B) from (2.10), respectively. Thus, in this case Theorem 2.4 is an extension of Theorem 2.3 for SOR relaxation.

In order to derive an SP for Kaczmarz relaxation (2.8), we shall consider a general invertible matrix A (not necessarily SPD), b [member of] [R.sup.n] a given vector and the linear system

(2.12) A[x.sup.*] = b,

with [x.sup.*] its unique solution. For a given approximation x of [x.sup.*] from (2.12), let x be the approximation of [x.sup.*] obtained after a Kaczmarz step (2.8) applied to x and e = x - [x.sup.*], e = x - [x.sup.*] and r = Ae the corresponding errors and residual (see (2.4)). The following theorem was first proved in [7]. But, we shall present in what follows another, more detailed proof required for the results described in section 2 of the paper; see also Remark 2.9 below.

THEOREM 2.6. Using the above definitions and notation, Kaczmarz relaxation (2.8) for the system (2.12) satisfies the following smoothing property (of the type (2.5))

(2.13) [[parallel]e[parallel].sup.2] [less than or equal to] [[parallel]e[parallel].sup.2] - [[bar.[gamma]].sub.0] [parallel][[bar.D].sup.1/2]r[parallel].sup.2],

where

(2.14) D = diag(1/[[parallel][A.sub.1][parallel].sup.2], ..., 1/[[parallel][A.sub.n][parallel].sup.2]),

(2.15) [[bar.[gamma]].sub.0] = 1/(1 +[[bar.[gamma]].sub.-](A))(1 + [[bar.[gamma]].sub.+](A))

and

(2.16) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof. Let [g.sub.i] = [(0,...,1,...,0).sup.T] [member of] [R.sup.n], i = 1, ..., n be the canonical basis. We first observe that, because of the symmetry of B, [Bg.sub.i] = [B.sub.i] the expression (2.6) can be written as follows: [x.sup.0] [member of] [R.sup.n] given; for k = 0,1, ... do

(2.17) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Now, if we write the system (2.12) in the form

(2.18) ([AA.sup.T])y* =b, [x.sup.*] = [A.sup.T] y*,

and we apply to it Gauss-Seidel relaxation (2.17) (B = AA T, c = b) with the initial approximation [y.sup.0], we get

(2.19) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

If we multiply from the left in (2.19) by AT and replace the terms of the form AT [y.sup.k,i] by [x.sup.k,i], we obtain exactly the Kaczmarz step (2.8) applied to the system (2.12). Thus, the Kaczmarz step (2.8) applied to the system (2.12) with an initial approximation of the form [x.sup.0] = [A.sup.T] [y.sup.0], for some [y.sup.0] [member of] [R.sup.n] is equivalent to the Gauss-Seidel step (2.17) applied to the system (2.18), with the initial approximation [y.sup.0] and setting [x.sup.k+1] = [A.sup.T] [y.sup.k+1]. But, because the matrix [AA.sup.T] is SPD, we can apply Theorem 2.3 for the Gauss-Seidel iteration and get (see (2.5) and (2.3))

(2.20) <([AA.sup.T])[bar.f], [bar.f]) [less than or equal to] <([AA.sup.T])f,f) - [[bar.[gamma]].sub.0]<[bar.D][AA.sup.T]f, [AA.sup.T]f)

with [bar.D] from (2.14), [[bar.[gamma]].sub.0] computed as in (2.9)-(2.10) with AAT instead of B, and with f, [bar.f] the corresponding errors with respect to the system (2.18). But, if e, [bar.e] and r are the corresponding errors and residual, respectively for the Kaczmarz relaxation, we have the following relations

e = [A.sup.T]f, [bar.e] = [A.sup.T][bar.f],

which when substituted into (2.20) give us (2.13) with the elements from (2.14)-(2.16) and the proof is complete.

A similar result as in Theorem 2.6 can be proved for the Kaczmarz iteration with relaxation parameter (for short, [omega]-Kaczmarz relaxation), as described below. [omega]-Kaczmarz relaxation. Let [x.sup.0] [member of] [R.sup.n]; for k = 0,1.... do

(2.21) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

THEOREM 2.7. Using the above definitions and notation, the w-Kaczmarz relaxation (2.21) for the system (2.12) satisfies the following smoothing property (of the type (2.5))

(2.22) [[parallel]e[parallel].sup.2] [less than or equal to] [[parallel]e[parallel].sup.2] - [[bar.[delta]].sub.0] [[parallel][[bar.D].sup.1/2]r[parallel].sup.2]

with [bar.D] from (2.14) and

(2.23) [[bar.[delta]].sub.0] = (1 + [[bar.[delta]].sub.-](A))(1+[bar.[delta]+(A)),

(2.24) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof. As in the proof of Theorem 2.6 we first show the equivalence between the [omega]-Kaczmarz and the SOR relaxation (2.7) written in the form (2.17); see also [10].

REMARK 2.8. The Kaczmarz iteration (2.8) or (2.21) is less efficient as smoother than the Gauss-Seidel one (2.6) (see for a detailed discussion Remark 4.7.2, page 128 in [21]). But, inspite of this, it has the advantage of being applicable to a much larger class of systems (than the classical square invertible ones).

REMARK 2.9. We have to observe that in (2.13) and (2.22), for the errors [bar.e] and e we have the Euclidean norm, instead of the energy one from (2.5). Moreover, the proofs of Theorems 2.6 and 2.7 are based on Theorems 2.3 and 2.4, i.e., the matrix B = [AA.sup.T] must be SPD; thus, we cannot expect such a simple and direct extension of Theorems 2.6 and 2.7 to arbitrary noninvertible systems like (2.12), because in such a case, the matrix [AA.sup.T] is no longer SPD. This extension will be proved in the next section of the paper, using a special technique.

3. Smoothing property of Kaczmarz relaxation for arbitrary consistent systems. Let A be an m x n matrix with [A.sub.i] [not equal to] 0, [for all]i = 1, ... m and b [member of] [R.sup.m] such that the system

(3.1) Ax =b

is consistent. We shall denote by S (A;b), N (A), R (A) the solutions set for (3.1), null space and range of A, respectively. For a given vector subspace E [subset] [R.sup.q], [P.sub.E](x) will be the orthogonal projection onto E of an element x [member of] [R.sup.q] and [E.sup.[perpendicular to]] will denote its orthogonal complement. If [x.sub.LS] is the (unique) minimal norm solution of (3.1) it is well known that (see, e.g., [3], [8])

(3.2) [x.sub.LS] [member of] N[(A).sup.[perpendicular to] = R([A.sup.T]), S(A;b) = [x.sub.LS] + N(A).

Thus, for a vector z [member of] [R.sup.n] we shall denote by s(z) the solution vector (see (3.2))

(3.3) s(z) = [P.sub.N(A)] (z) + [x.sub.LS] [member of] S(A; b).

The Kaczmarz relaxation for (3.1) can be written as (see (2.8)): let [x.sup.0] [member of] [R.sup.n] be given; for k = 0,1,2 ... do

(3.4) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The following results are known (see, e.g., [20]).

THEOREM 3.1. For any [x.sup.0] [member of] [R.sup.n], the sequence [([x.sup.k])k[greater than or equal to]0] generated by the algorithm (3.4) has the properties

(3.5) [P.sub.N(A)]([x.sup.k]) = [P.sub.N(A)]([x.sup.0]), [for all]k [greater than or equal to] 0

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let now x [member of] [R.sup.n] be a current approximation of s([x.sup.0]) (generated by (3.4), for k = 0, x = [x.sup.0]) and x the approximation after one step of (3.4) applied to x. Let e, [bar.e], r be the corresponding errors and residual, defined by (according to (3.3) and (3.5))

e = x - s([x.sup.0]), [bar.e] = x-s([x.sup.0]), r = Ae = Ax - [Ax.sub.LS] = Ax - b.

Then, the generalization of Theorem 2.6 is the following.

THEOREM 3.2. Using the above definitions and notation, Kaczmarz relaxation (3.4) for the system (3.1) satisfies the smoothing property (2.13)-(2.16).

Proof. Step 1. According to (3.4), the computation of x from x can be written as

(3.6) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let {[f.sub.1], [f.sub.2], ..., [f.sub.m]} be the canonical basis in [R.sup.m] and [e.sup.i], [r.sup.i] the errors and residuals defined by

(3.7) [e.sup.i] = [x.sup.i] - s([x.sup.0]), [r.sup.i] = [Ae.sup.i], i = 1,...,m.

Then, for i = 1, ... m, we obtain (by also using the equality [A.sub.i] = [A.sup.T] [f.sub.i])

(3.8) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and

(3.9) [r.sup.i] = [Ae.sup.i] = [r.sup.i-1]<[r.sup.i-1,[f.sub.i]>/ [[parallel][A.sub.i][parallel].sup.2] [AA.sub.i].

From (3.8), taking the Euclidean norm and using again the equality [A.sub.i] = [A.sup.T] [f.sub.i] and (3.7) we Obtain

(3.10) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [r.sup.i-1] is the i-th component of the residual vector [r.sup.i-1]. But, because of (3.6) we have [x.sup.0] = x, x = [x.sup.m], then [e.sup.0] = e, [bar.e] = [e.sup.m]. Thus, summing up in (3.10), we get

(3.11) [[parallel][bar.e][parallel].sup.2] = [[parallel]e[parallel].sup.2] - [m.summation over (i=1)] [([r.sup.i- 1.sub.i]).sup.2]/ [[parallel][A.sub.i][parallel].sup.2].

Step 2. Let now r* = [([r.sup.*.sub.1],..., [r.sup.*.sub.m]).sup.T] [member of] [R.sup.m] be the dynamic residual (as called in [7]), defined by

(3.12) [r.sup.*.sub.i] = [r.sup.i-1.sub.i], i = 1, ..., m,

i.e., [r.sup.*.sub.i] is the i-th component of the residual [r.sup.i-1] (that is, the residual before the projection on the i-th equation of (3.6)). From (3.11) and (3.12), we then get

(3.13) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

with [bar.D] from (2.14). On the other hand, from the equation (3.9), we successively obtain

(3.14) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where

(3.15) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Then, from the definition of the matrices [E.sub.i] in (3.15) and (3.12), we get [r.sup.*.sub.1] = [r.sup.0.sub.1] = [r.sub.1] and for i = 2, ..., m,

[r.sup.*.sub.i] = [r.sub.i] - ([B.sub.i1] [r.sup.0.sub.1] + [B.sub.i2][r.sup.1.sub.2] + ... + [B.sub.i,i-1] [r.sup.i-1.sub.i]))

or in matrix form

(3.16) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

or (see also (3.13))

(3.17) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where L is the corresponding strictly lower triangular matrix from (3.16).

Step 3. If C is a square matrix and [[parallel]C[parallel].sub.2], [[parallel]C[parallel].sub.[infinity]] are, respectively its spectral and infinity norm (see, e.g., [3]), we have

(3.18) [[parallel]C[parallel].sup.2.sub.2] = [rho]([C.sup.T]C) [less than or equal to] [[parallel][C.sup.T]C[parallel].sub.[infinity]] [less than or equal to] [[parallel][C.sup.T][parallel].sub.[infinity]] [[parallel]C[parallel].sub.[infinity]].

Using (3.18) and taking the Euclidean norm in (3.17), we obtain

(3.19) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

But, a simple computation gives us

(3.20) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

with [[??].sub.-] (A), [[??].sub.+] (A) from (2.16). Then, using (3.13), (3.19) and (3.20), we get (2.13) and the proof is complete.

A similar result can be proved for [omega]-Kaczmarz relaxation.

THEOREM 3.3. Using the above definitions and notation, the [omega]-Kaczmarz relaxation for the system (3.1) satisfies the smoothing property (2.22)-(2.24).

Proof. The [omega]-Kaczmarz relaxation (2.21) for the system (3.1) can be written as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

As in the proof of Theorem 3.2, we get

[e.sup.i] = [e.sup.i-1] - [omega](2 - [omega]) <[r.sup.i-1], [f.sub.i]>/ [[parallel][A.sub.i][parallel].sup.2] [A.sub.i]

and

[r.sup.i] = [Ae.sup.i] = [r.sup.i-1] - [omega](2 - [omega]) <[r.sup.i-1], [f.sub.i]>/ [[parallel][A.sub.i[parallel].sup.2] [AA.sub.i].

Then we proceed in exactly the same way as in the above mentioned proof.

4. Smoothing property of Kaczmarz Extended relaxation for arbitrary inconsistent systems. Let A and b be as in section 2. Instead of the consistent system (3.1), we shall consider in this section the linear least squares formulation (inconsistent system)

(4.1) [parallel]Ax - b[parallel] = min!,

for which we shall denote by LSS(A; b) and [x.sub.LS] the set of its solutions and the minimal norm one, respectively. Let [b.sub.A], [b.sup.*.sub.A] be defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Then (see, e.g., [3])

(4.2) b = [b.sub.A] + [b.sup.*.sub.A], LSS(A; b) = S(A; [b.sub.A]) = [x.sub.LS] + N(A).

Moreover, (see (3.3)) for any z [member of] [R.sup.n], we have

s(z) = [P.sub.N(A)] (z) +[x.sub.LS] [member of] LSS(A; b) = S(A; [b.sub.A]).

Thus we define (as in section 2) the error and residual by

(4.3) e=e(z)=z-s(z), r = Ae = Az - [b.sub.A].

The Kaczmarz Extended algorithm for (4.1) (KE, for short), introduced in [12] (see also [13]) is the following.

Kaczmarz Extended. Let [x.sup.0] [member of] [R.sup.n], [y.sup.0] = b; for k = 0,1, ... do

(4.4) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where

[[psi].sub.j](y) = y <y, [A.sup.j])/ [[parallel][A.sup.j][parallel].sup.2] [A.sup.j]

and [A.sup.j] [not equal to] 0, j = 1,...,n, are the columns of A. In [14] we proved that the sequence [([x.sup.k]).sub.k[greater than or equal to]0] generated with the above KE algorithm satisfies the relation (3.5). Then, if x = [x.sup.k] (for some k [greater than or equal to] 0) is a current approximation, we shall define the error (see (4.3)) by

e = x - s([x.sup.0]).

Let y = [y.sup.k] be the corresponding element from the first step of (4.4) and [bar.y] = [y.sup.k+1], i.e.,

(4.5) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where (see for details [13])

(4.6) [??](y) = [PHI][P.sub.R(A)] (y) [member of] R(A).

From (4.5) and (4.6), we get that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus (see also (4.2))

(4.7) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Then, if [bar.b] = [b.sup.k+1] (see (4.4)), from (4.5) and (4.7), we obtain

(4.8) [bar.b] = b - [bar.y] = [b.sub.A] - [??],

Where

(4.9) [??] = [??](y)

REMARK 4. 1. Returning to the original notation, from the above equalities (4.7)-(4.9), we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Moreover, in [20] it is proved that [[parallel][??][parallel].sub.2] < 1. Thus

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The extension of Theorem 3.2 to the problem (4.1), for the KE algorithm (4.4) is the following.

THEOREM 4.2. Using the above definitions and notation, the KE relaxation (4.4) for the (inconsistent) problem (4.1) satisfies the following smoothing property

(4.10) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

with [??] and [[??].sub.0] from (2.14)-(2.16).

Proof. Step 1. The third step in (4.4) can be written as (see also (2.8))

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Then, by defining the errors (see also (3.7))

(4.11) [e.sup.i] = [x.sup.i] - s([x.sup.0]), i = 1, ..., m, [bar.e] = [e.sup.m],

we get

(4.12) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

From (4.12) we obtain (by also using the relation [A.sub.i] = [A.sup.T] [f.sub.i])

(4.13) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Then by summing in (4.13), using (4.11) and the notation from section 2, we get

(4.14) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Step 2. From (4.12) we obtain (see again the notation in section 2)

ri = [Ae.sup.i] = [Ae.sup.i-1] - [r.sup.i-1.sub.i]/[[parallel][A.sub.i][parallel].sup.2] [AA.sub.i] - [[??].sub.i]/[[parallel]{S.sub.i][parallel].sup.2] [AA.sub.i] = ri-1 - [BE.sub.i][r.sup.i-1] - [BE.sub.i][??],i = 1, ..., m,

thus

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Using the equality (see section 2)

r* = [([r.sub.1],[r.sup.1.sub.2],...,[r.sup.m-1.sub.m]).sup.T],

we obtain

(4.15) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Writing (4.15) in matrix form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

with L from (3.16), we get

(4.16) r* = r - Lr* - L[??].

From (4.16) we obtain as in section 2

(4.17) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Where

(4.18) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Using (4.17) and (4.18), it follows that

(4.19) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

From (4.19) and (2.15), we then obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which together with (4.14) gives us (4.10) and the proof is complete.

A similar result can be derived for the Kaczmarz Extended algorithm with Relaxation Parameters (KERP, for short), introduced in [13].

KERP Let [x.sup.0] [member of] [R.sup.n], [y.sup.0] = b; for k = 0,1, ... do

(4.20) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where

[[psi].sub.j] ([alpha]; y) = y - [alpha] <y, [A.sup.j]> [[parallel][A.sup.j][parallel].sup.2] [A.sup.j].

THEOREM 4.3. Using the above definitions and notation, KERP relaxation (4.20) for the (inconsistent) problem (4.1) satisfies the following smoothing property

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

with [??] and [[??].sub.0] from (2.14), (2.23), and [??] (a) = [PHI]([alpha]; y).

Proof. Apply Theorems 4.3 and 2.7 to [omega]-Kaczmarz relaxation.

REMARK 4.4. The result from Theorem 3.2 is not a particular case of Theorem 4.2. Indeed, if b [member of] R(A) for the problem (4.1), we have [b.sup.*.sub.A] = 0. Thus, [bar.y] = [??] [member of] R (A), but we cannot drop the term 2 [[parallel][[??].sup.1/2][??][parallel].sup.2] in (4.10). Thus, in the consistent case Theorems 3.2 and 4.2 provide two smoothing properties for two different algorithms: Kaczmarz and Kaczmarz Extended.

5. Final comments and further developments. In this paper we formulated and proved AMG smoothing properties for the classical Kaczmarz and Kaczmarz Extended algorithms in the general case of arbitrary rectangular systems, either consistent or in least squares formulation. In the consistent case, our result for classical Kaczmarz relaxation (Theorem 3.2) generalizes the well-known result for square invertible matrices (Theorem 2.6). The general character of the matrices involved in the above theory makes extension to AMG to general least squares problems possible. Some steps in this direction have been taken in [15] and [9], but both the theoretical development and experiments are in initial phases.

Acknowledgement. The author thanks the two referees for their comments and suggestions which improved some important parts of the original version of the paper.

* Received October 12, 2006. Accepted for publication July 3, 2007. Published online on July 22, 2008. Recommended by A. Frommer.

REFERENCES

[1] A. ARIC6, M. DONATELLI, AND S. SERRA-CAPIZZANO, V-Cycle optimal convergence for certain (multilevel) structured linear systems, SIAM J. Matrix Anal. Appl., 26 (2004), pp. 186-214.

[2] A. ARIC6 AND M. DONATELLI, V-cycle multigrid for multilevel algebaas: proof of optimality, Numer. Math., 105 (2007), pp. 511-547.

[3] A. BJORCK, Numerical Methods for Least Squares Problems, SIAM, Philadelphia, PA, 1996.

[4] A. BRANDT, S. MCCORMICK, AND J. RUDE, Algebraic multigrid (AMG) for automatic multigrid solution with application to geodetic computations, Technical Report, Institute for Computational Studies, Colorado State University, 1982.

[5] A. BRANDT, Algebraic multigrid theory: the symmetric case (a preliminary version), in Preliminary Proceedings for the International Multigrid Conference (Copper Mountain, Colorado), April, 1983.

[6] A. BRANDT, S. MCCORMICK, AND J. RUDE, Algebraic multigrid (AMG) for sparse matrix equations, in Sparsity and Its Applications, D.J. Evans, ed., Cambridge University Press, Cambridge, 1984.

[7] A. BRANDT, Algebraic multigrid theory: the symmetric case, Appl. Math. Comp., 19 (1986), pp. 23-56.

[8] Y. CENSOR AND A. Z. STAVROS, Parallel Optimization: Theory, Algorithms and Applications, Oxford Univ. Press, New York, 1997.

[9] H. KOSTLER, C. POPA, M. PRUMMER, AND U. RUDE, Towards an algebraic multigrid method for tomographic image reconstruction--improving convergence of ART, Paper 476 in Electronic Proceedings of the European Conference on Computational Fluid Dynamics ECCOMAS CFD 2006, The Netherlands, 2006.

[10] F. NATTERER, The Mathematics of Computerized Tomography, John Wiley and Sons, New York, 1986.

[1l] C. POPA, On smoothing property of the SOR relaxation, Studii si Cercetari Matematice, 41 (1989), pp. 399406.

[12] C. POPA, Least-squares solution of overdetermined inconsistent linear systems using Kaczmarz's relaxation, Internat. J. Comput. Math., 55 (1995), pp. 79-89.

[13] C. POPA, Extensions of block-projections methods with relaxation parameters to inconsistent and rankdefficient least-squares problems, BIT, 38 (1998), pp. 151-176.

[14] C. POPA, Characterization of the solutions set of inconsistent least-squares problems by an extended Kaczmarz algorithm, Korean J. Comp. Appl. Math., 6 (1999), pp. 51-64.

[15] M. PRUMMER, H. KOSTLER, J. HORNEGGER, AND U. RUDE, A full multigrid technique to accelerate an ART scheme for tomographic image reconstruction, in Proceedings of ASIM Conference, September 12-15 2005, SCS Publishing House, Erlangen, Germany, pp. 632-637.

[16] J. RUDE, Algebraic multigrid (AMG) for geodetic survey problems, in Preliminary Proceedings for the International Multigrid Conference (Copper Mountain, Colorado), April, 1983, 24 pages.

[17] J. RUGS AND K. STUBEN, Algebraic Multigrid (AMG), Arbeitspapiere der GMD Bonn 210, GMD, Bonn, Germany, 1986.

[18] S. SERRA-CAPIZZANO, Convergence analysis of two-grid methods for elliptic Toeplitz and PDEs matrixsequences, Numer. Math., 92 (2002), pp. 433-465.

[19] K. STUBEN, Algebraic multigrid (AMG): experiences and comparisons, Appl. Math. Comput. 13 (1983), pp. 419-451.

[20] K. TANABE, Projection method for solving a singular system of linear equations and its applications, Numer. Math., 17 (1971), pp. 203-214.

[21] U. TROTTENBERG, C. OOSTERLEE, AND A. SCHULLER, Multigrid, Academic Press, London, 2001.

[22] D. M. YOUNG, Iterative Solution of Large Linear Systems, Academic Press, New York, 1971.

CONSTANTIN POPA ([dagger])

([dagger]) Faculty of Mathematics and Computer Science, Ovidius University of Constanta, Blvd. Mamaia 124, 900527 Constanta, Romania (cpopa@univ-ovidius.ro).

Printer friendly Cite/link Email Feedback | |

Author: | Popa, Constantin |
---|---|

Publication: | Electronic Transactions on Numerical Analysis |

Article Type: | Report |

Geographic Code: | 4EXRO |

Date: | Dec 1, 2007 |

Words: | 4879 |

Previous Article: | On the parameter selection problem in the Newton-ADI iteration for large-scale Riccati equations. |

Next Article: | Filter factor analysis of an iterative multilevel regularizing method. |

Topics: |