Database Reference
In-Depth Information
Example 6.3
For a shop with 9 products (
n ¼
9) and using 3 partitions (
β ¼
3)
with 2, 4, and 3 products, respectively, the matrix
P
has the following structure:
2
3
aa
bb
0
0
4
5
2
3
cccc
dddd
eeee
f
4
5
0
0
P ¼
:
■
f
f
f
2
3
ggg
hhh
i
4
5
0
0
i
i
Obviously, the first assumption is realistic, since, in a typical shop, most
transitions take place within product categories, provided that the latter have been
chosen sensibly. The second assumption, however, is violated in most practical
situations.
An alternative approach with favorable convergence properties in more general
situations is
iterative aggregation-disaggregation (IAD).
This method is obtained
by replacing the Richardson sweep by a so-called additive algebraic Schwarz
sweep. Having its origins in the field of partial differential equations, the latter is
a domain decomposition-based procedure which can also be applied to systems of
linear equations of the form (
6.4
). In this context, one speaks of
algebraic Schwarz
methods
. We shall now provide a brief outline of the algebraic Schwarz sweep
(details may be found in [Pap10]).
For each set in the partition, we restrict the residual and the corresponding
matrix coefficients to the indices therein and add the solution of the thus obtained
system to the corresponding entries of the current iterate. It may easily be verified
that the algebraic Schwarz sweep yields the exact solution in case of a block-
diagonal system. Due to continuity, we may conclude that - if applied in an
iterative fashion - the method exhibits swift convergence if the system is almost
block-diagonal.
From a practical point of view, this complies with the above-described situa-
tion where the major part of the state transitions takes place within the sets of the
partition. Hence, we may expect the method to exhibit rapid convergence in a
larger class of practical situations even without a coarse grid correction. Sadly
enough, practical experience in [Pap10] reveal that even in cases where the
second condition of the above is not satisfied, the aggregation method with a
Richardson step outperforms the IAD method with respect to computation time,
although the number of iterations is larger by 1 up to 2 orders of magnitude. This
is due to the fairly greater computational intensity of the algebraic Schwarz
sweep, which requires the solution of a multitude of smaller systems of linear
equations, whereas the Richardson step consists of only one matrix-vector
multiplication.
