Donatelli, Marco and Serra Capizzano, Stefano:
Multigrid Methods for (Multilevel) Structured Matrices Associated with a Symbol and Related Application
Bollettino dell'Unione Matematica Italiana Serie 9 6 (2013), fasc. n.2, p. 319-347, (English)
pdf (557 Kb), djvu (333 Kb). | MR 3112982 | Zbl 1280.65033
Sunto
When dealing with large linear systems with a prescribed structure, two key ingredients are important for designing fast solvers: the first is the computational analysis of the structure which is usually inherited from an underlying infinite dimensional problem, the second is the spectral analysis which is often deeply related to a compact symbol, again depending on the infinite dimensional problem of which the linear system is a given approximation. When considering the computational view-point, the first ingredient is useful for designing fast matrix-vector multiplication algorithms, while the second ingredient is essential for designing fast iterative solvers (multigrid, preconditioned Krylov etc.), whose convergence speed is optimal in the Axelsson, Neytcheva sense, i.e., the number of iterations for reaching a preassigned accuracy can be bounded by a pure constant independent of the matrix-size. In this review paper we consider in some details the specific case of multigrid-type techniques for Toeplitz related structures, by emphasizing the role of the structure and of the compact spectral symbol. A sketch of several extensions to other (hidden) structures as those appearing in the numerical approximation of partial differential equations and integral equations is given and critically discussed.
Referenze Bibliografiche
[2]
A. ARICÒ -
M. DONATELLI -
S. SERRA CAPIZZANO,
V-cycle optimal convergence for certain (multilevel) structured linear system,
SIAM J. Matrix Anal. Appl.,
26, 1 (
2004), 186-214. |
fulltext (doi) |
MR 2112856 |
Zbl 1105.65322[3]
G. AXELSSON -
M. NEYTCHEVA,
The algebraic multilevel iteration methods - theory and applications,
Proceedings of the 2nd. Int Coll. on Numerical Analysis,
D. Bainov Ed.,
VSP 1994, Bulgaria, August 1993. |
MR 1455926 |
Zbl 0845.65012[5]
D. BINI -
M. CAPOVANI,
Spectral and computational properties of band simmetric Toeplitz matrices,
Linear Algebra Appl.,
52/53 (
1983), 99-125. |
fulltext (doi) |
MR 709346 |
Zbl 0549.15005[7]
J. H. BRAMBLE,
Multigrid methods, volume
294 of
Pitman Research Notes in Mathematics Series.
Longman Scientific & Technical, Harlow,
1993. |
MR 1247694 |
Zbl 0786.65094[8]
R. H. CHAN -
T. F. CHAN -
W. L. WANG,
Multigrid for differential-convolution problems arising in image processing,
Proc. Workshop on Scientific Computing,
G. Golub,
S.H. Lui,
F. Luk,
R. Plemmons Eds,
Springer (
1999), 58-72. |
MR 1729650 |
Zbl 0922.65097[9]
R. H. CHAN -
Q. CHANG -
H. SUN,
Multigrid method for ill-conditioned symmetric Toeplitz systems,
SIAM J. Sci. Comp.,
19, 2 (
1998), 516-529. |
fulltext (doi) |
MR 1618824 |
Zbl 0916.65029[11] R. H. CHAN - M. DONATELLI - S. SERRA CAPIZZANO - C. TABLINO POSSIO, Application of multigrid techniques to image restoration problems,, in Proc. SPIE, 46th Annual Meeting, F. Luk Ed, SPIE, 4791 (2002), 210-221.
[12]
R. H. CHAN -
S. SERRA CAPIZZANO -
C. TABLINO POSSIO,
Two-Grid methods for banded linear systems from DCT III algebra,
Numer. Linear Algebra Appl.,
12, 2/3 (
2005), 241-249. |
fulltext (doi) |
MR 2125635 |
Zbl 1164.65341[14]
L. CHENG -
H. WANG -
Z. ZHANG,
The solution of ill-conditioned symmetric Toeplitz systems via two-grid and wavelet methods,
Comput. Math. Appl.,
46 (
2003), 793-804. |
fulltext (doi) |
MR 2020438 |
Zbl 1051.65030[15] M. DONATELLI, A Multigrid method for restoration and regularization of images with Dirichlet boundary conditions, in Proc. SPIE, 48th Annual Meeting, F. Luk Ed, SPIE, 5205 (2004), 380-389.
[17]
M. DONATELLI,
An algebraic generalization of local Fourier analysis for grid transfer operators in multigrid based on Toeplitz matrices,
Numer. Linear Algebra Appl.,
17 (
2010), 179-197. |
fulltext (doi) |
MR 2650207 |
Zbl 1240.65353[18]
M. DONATELLI,
An iterative multigrid regularization method for Toeplitz discrete ill-posed problems,
Numer. Math. Theor. Meth. Appl.,
5 (
2012), 43-61. |
MR 2872586 |
Zbl 1265.65074[20]
M. DONATELLI -
S. SERRA CAPIZZANO,
Filter factor analysis of an iterative multilevel regularizing method,
Electron. Trans. Numer. Anal.,
29 (
2007/2008), 163-177. |
fulltext EuDML |
MR 2494953 |
Zbl 1171.65369[21]
M. DONATELLI -
S. SERRA CAPIZZANO -
D. SESANA,
Multigrid methods for Toeplitz linear systems with different size reduction,
BIT,
52, 2 (
2012), 305-327. |
fulltext (doi) |
MR 2931352 |
Zbl 1251.65047[22]
M. I. ESPAÑ OL -
M. E. KILMER,
Multilevel Approach For Signal Restoration Problems With Toeplitz Matrices,
SIAM J. Sci. Comput.,
32, 1 (
2010), 299-319. |
fulltext (doi) |
MR 2599779 |
Zbl 1228.65060[24]
G. FIORENTINO -
S. SERRA CAPIZZANO,
Multigrid methods for symmetric positive definite block Toeplitz matrices with nonnegative generating functions,
SIAM J. Sci. Comp.,
17, 4 (
1996), 1068-1081. |
fulltext (doi) |
MR 1404861 |
Zbl 0858.65039[26]
P. C. HANSEN -
J. NAGY -
D. P. O'LEARY,
Deblurring Images: Matrices, Spectra, and Filtering,
SIAM, Philadelphia, PA,
2006. |
fulltext (doi) |
MR 2271138[28]
E. HEINZ -
M. HANKE -
A. NEUBAUER,
Regularization of inverse problems,
Mathematics and its Applications,
Kluwer Academic Publishers,
1996. |
MR 1408680 |
Zbl 0859.65054[32]
N. KALOUPTSIDIS -
G. CARAYANNIS -
D. MANOLAKIS Fast algorithms for block Toeplitz matrices with Toeplitz entries,
Signal Process.,
6 (
1984), 77-81. |
MR 754759[33]
S. MORIGI -
L. REICHEL -
F. SGALLARI -
A. SHYSHKOV,
Cascadic multiresolution methods for image deblurring,
SIAM J. Imaging Sci.,
1 (
2008), 51-74. |
fulltext (doi) |
MR 2475825 |
Zbl 1144.65092[34]
J. W. RUGE -
K. STÜBEN,
Algebraic Multigrid, in
Frontiers in Applied Mathemathics: Multigrid Methods,
S. McCormick Ed.
SIAM, Philadelphia (PA) (
1987), 73-130. |
fulltext (doi) |
MR 972752[36]
S. SERRA CAPIZZANO,
Convergence analysis of two-grid methods for elliptic Toeplitz and PDEs Matrix-sequences,
Numer. Math.,
92, 3 (
2002), 433-465. |
fulltext (doi) |
MR 1930386 |
Zbl 1013.65026[37]
S. SERRA CAPIZZANO,
Generalized Locally Toeplitz sequences: spectral analysis and applications to discretized Partial Differential Equations,
Linear Algebra Appl.,
366, 1 (
2003), 371-402. |
fulltext (doi) |
MR 1987730 |
Zbl 1028.65109[38]
S. SERRA CAPIZZANO,
A note on anti-reflective boundary conditions and fast deblurring models,
SIAM J. Sci. Comput.,
25, 4 (
2004), 1307-1325. |
fulltext (doi) |
MR 2045058 |
Zbl 1062.65152[41]
S. SERRA CAPIZZANO -
E. TYRTYSHNIKOV,
Any circulant-like preconditioner for multilevel matrices is not superlinear,
SIAM J. Matrix Anal. Appl.,
21, 2 (
1999), 431-439. |
fulltext (doi) |
MR 1718339 |
Zbl 0952.65037[42]
C. TABLINO POSSIO,
V-cycle optimal convergence for DCT-III matrices, Numerical methods for structured matrices and applications,
Oper. Theory Adv. Appl.,
199 (
2010), 377-396. |
fulltext (doi) |
MR 2656837 |
Zbl 1203.65228[44]
U. TROTTENBERG -
C. W. OOSTERLEE -
A. SCHÜLLER,
Multigrid,
Academic Press,
2001. |
MR 1807961[46]
E. TYRTYSHNIKOV,
A unifying approach to some old and new theorems on pre-condictioning and clustering,
Linear Algebra Appl.,
232 (
1996), 1-43. |
fulltext (doi) |
MR 1366576 |
Zbl 0841.15006