Multigrid Methods for (Multilevel) Structured Matrices Associated with a Symbol and Related Application

Marco Donatelli; Stefano Serra Capizzano

Bollettino dell'Unione Matematica Italiana (2013)

  • Volume: 6, Issue: 2, page 319-347
  • ISSN: 0392-4041

Abstract

top
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.

How to cite

top

Donatelli, Marco, and Serra Capizzano, Stefano. "Multigrid Methods for (Multilevel) Structured Matrices Associated with a Symbol and Related Application." Bollettino dell'Unione Matematica Italiana 6.2 (2013): 319-347. <http://eudml.org/doc/294022>.

@article{Donatelli2013,
abstract = {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.},
author = {Donatelli, Marco, Serra Capizzano, Stefano},
journal = {Bollettino dell'Unione Matematica Italiana},
language = {eng},
month = {6},
number = {2},
pages = {319-347},
publisher = {Unione Matematica Italiana},
title = {Multigrid Methods for (Multilevel) Structured Matrices Associated with a Symbol and Related Application},
url = {http://eudml.org/doc/294022},
volume = {6},
year = {2013},
}

TY - JOUR
AU - Donatelli, Marco
AU - Serra Capizzano, Stefano
TI - Multigrid Methods for (Multilevel) Structured Matrices Associated with a Symbol and Related Application
JO - Bollettino dell'Unione Matematica Italiana
DA - 2013/6//
PB - Unione Matematica Italiana
VL - 6
IS - 2
SP - 319
EP - 347
AB - 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.
LA - eng
UR - http://eudml.org/doc/294022
ER -

References

top
  1. ARICÒ, A. - DONATELLI, M., A V-cycle Multigrid for multilevel matrix algebras: proof of optimality, Numer. Math., 105, 4 (2007), 511-547. Zbl1114.65033MR2276759DOI10.1007/s00211-006-0049-7
  2. ARICÒ, A. - DONATELLI, M. - SERRA CAPIZZANO, S., V-cycle optimal convergence for certain (multilevel) structured linear system, SIAM J. Matrix Anal. Appl., 26, 1 (2004), 186-214. Zbl1105.65322MR2112856DOI10.1137/S0895479803421987
  3. AXELSSON, G. - NEYTCHEVA, M., The algebraic multilevel iteration methods - theory and applications, Proceedings of the 2nd. Int Coll. on Numerical Analysis, D. Bainov Ed., VSP1994, Bulgaria, August 1993. Zbl0845.65012MR1455926
  4. BECKERMANN, B. - SERRA CAPIZZANO, S., On the asymptotic spectrum of Finite Elements matrices, SIAM J. Numer. Anal., 45, 2 (2007), 746-769. Zbl1140.65080MR2300295DOI10.1137/05063533X
  5. BINI, D. - CAPOVANI, M., Spectral and computational properties of band simmetric Toeplitz matrices, Linear Algebra Appl., 52/53 (1983), 99-125. Zbl0549.15005MR709346DOI10.1016/0024-3795(83)80009-3
  6. BINI, D. - FAVATI, P., On a matrix algebra related to the discrete Hartley transform, SIAM J. Matrix Anal. Appl., 14, 2 (1993), 500-507. Zbl0773.65029MR1211803DOI10.1137/0614035
  7. BRAMBLE, J. H., Multigrid methods, volume 294 of Pitman Research Notes in Mathematics Series. Longman Scientific & Technical, Harlow, 1993. Zbl0786.65094MR1247694
  8. CHAN, R. H. - CHAN, T. F. - WANG, W. L., 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. Zbl0922.65097MR1729650
  9. CHAN, R. H. - CHANG, Q. - SUN, H., Multigrid method for ill-conditioned symmetric Toeplitz systems, SIAM J. Sci. Comp., 19, 2 (1998), 516-529. Zbl0916.65029MR1618824DOI10.1137/S1064827595293831
  10. CHAN, R. H. - NG, M., Conjugate gradient methods for Toeplitz systems, SIAM Rev., 38 (1996), 427-482. Zbl0863.65013MR1409592DOI10.1137/S0036144594276474
  11. CHAN, R. H. - DONATELLI, M. - SERRA CAPIZZANO, S. - TABLINO POSSIO, C., Application of multigrid techniques to image restoration problems,, in Proc. SPIE, 46th Annual Meeting, F. Luk Ed, SPIE, 4791 (2002), 210-221. 
  12. CHAN, R. H. - SERRA CAPIZZANO, S. - TABLINO POSSIO, C., Two-Grid methods for banded linear systems from DCT III algebra, Numer. Linear Algebra Appl., 12, 2/3 (2005), 241-249. Zbl1164.65341MR2125635DOI10.1002/nla.399
  13. CHANG, Q. - JIN, X. - SUN, H., Convergence of the multigrid method for ill-conditioned block toeplitz systems, BIT, 41, 1 (2001), 179-190. Zbl0991.65033MR1829668DOI10.1023/A:1021978020255
  14. CHENG, L. - WANG, H. - ZHANG, Z., The solution of ill-conditioned symmetric Toeplitz systems via two-grid and wavelet methods, Comput. Math. Appl., 46 (2003), 793-804. Zbl1051.65030MR2020438DOI10.1016/S0898-1221(03)90142-8
  15. DONATELLI, M., 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. 
  16. DONATELLI, M., A Multigrid method for image restoration with Tikhonov regularization., Numer. Linear Algebra Appl., 12 (2005), 715-729. Zbl1164.68445MR2172672DOI10.1002/nla.446
  17. DONATELLI, M., 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. Zbl1240.65353MR2650207DOI10.1002/nla.704
  18. DONATELLI, M., An iterative multigrid regularization method for Toeplitz discrete ill-posed problems, Numer. Math. Theor. Meth. Appl., 5 (2012), 43-61. Zbl1265.65074MR2872586
  19. DONATELLI, M. - SERRA CAPIZZANO, S., On the regularizing power of multigrid-type algorithms, SIAM J. Sci. Comput., 27, 6 (2006), 2053-2076. Zbl1103.65043MR2211439DOI10.1137/040605023
  20. DONATELLI, M. - SERRA CAPIZZANO, S., Filter factor analysis of an iterative multilevel regularizing method, Electron. Trans. Numer. Anal., 29 (2007/2008), 163-177. Zbl1171.65369MR2494953
  21. DONATELLI, M. - SERRA CAPIZZANO, S. - SESANA, D., Multigrid methods for Toeplitz linear systems with different size reduction, BIT, 52, 2 (2012), 305-327. Zbl1251.65047MR2931352DOI10.1007/s10543-011-0356-y
  22. ESPAÑ OL, M. I. - KILMER, M. E., Multilevel Approach For Signal Restoration Problems With Toeplitz Matrices, SIAM J. Sci. Comput., 32, 1 (2010), 299-319. Zbl1228.65060MR2599779DOI10.1137/080715780
  23. FIORENTINO, G. - SERRA CAPIZZANO, S., Multigrid methods for Toeplitz matrices, Calcolo, 28 (1991), 283-305. Zbl0778.65021MR1219617DOI10.1007/BF02575816
  24. FIORENTINO, G. - SERRA CAPIZZANO, S., Multigrid methods for symmetric positive definite block Toeplitz matrices with nonnegative generating functions, SIAM J. Sci. Comp., 17, 4 (1996), 1068-1081. Zbl0858.65039MR1404861DOI10.1137/S1064827594271512
  25. FISCHER, R. HUCKLE, T., Multigrid methods for anisotropic BTTB systems, Linear Algebra Appl.417 (2006), 314-334. Zbl1101.65034MR2250314DOI10.1016/j.laa.2006.02.032
  26. HANSEN, P. C. - NAGY, J. - O'LEARY, D. P., Deblurring Images: Matrices, Spectra, and Filtering, SIAM, Philadelphia, PA, 2006. MR2271138DOI10.1137/1.9780898718874
  27. HEMKER, P. W., On the order of prolongations and restrictions in multigrid procedures, J. Comput. Appl. Math., 32 (1990), 423-429. Zbl0717.65098MR1090888DOI10.1016/0377-0427(90)90047-4
  28. HEINZ, E. - HANKE, M. - NEUBAUER, A., Regularization of inverse problems, Mathematics and its Applications, Kluwer Academic Publishers, 1996. Zbl0859.65054MR1408680
  29. HUCKLE, T., Compact Fourier analysis for designing multigrid methods, SIAM J. Sci. Comput.31 (2008), 644-666. Zbl1186.65037MR2460793DOI10.1137/070702564
  30. HUCKLE, T. - STAUDACHER, J., Multigrid preconditioning and Toeplitz matrices, Electr. Trans. Numer. Anal., 13 (2002), 81-105. Zbl1065.65063MR1961200
  31. HUCKLE, T. - STAUDACHER, J., Multigrid methods for block Toeplitz matrices with small size blocks, BIT, 46 (2006), 61-83, Zbl1103.65035MR2214848DOI10.1007/s10543-006-0047-2
  32. KALOUPTSIDIS, N. - CARAYANNIS, G. - MANOLAKIS, D.Fast algorithms for block Toeplitz matrices with Toeplitz entries, Signal Process., 6 (1984), 77-81. MR754759
  33. MORIGI, S. - REICHEL, L. - SGALLARI, F. - SHYSHKOV, A., Cascadic multiresolution methods for image deblurring, SIAM J. Imaging Sci., 1 (2008), 51-74. Zbl1144.65092MR2475825DOI10.1137/070694065
  34. RUGE, J. W. - STÜBEN, K., Algebraic Multigrid, in Frontiers in Applied Mathemathics: Multigrid Methods, S. McCormick Ed. SIAM, Philadelphia (PA) (1987), 73-130. MR972752DOI10.1137/1.9781611971057
  35. SERRA CAPIZZANO, S., Preconditioning strategies for asymptotically ill-conditioned block Toeplitz systems, BIT, 34, 4 (1994), 579-594. Zbl0823.65030MR1430910DOI10.1007/BF01934269
  36. SERRA CAPIZZANO, S., Convergence analysis of two-grid methods for elliptic Toeplitz and PDEs Matrix-sequences, Numer. Math., 92, 3 (2002), 433-465. Zbl1013.65026MR1930386DOI10.1007/s002110100331
  37. SERRA CAPIZZANO, S., Generalized Locally Toeplitz sequences: spectral analysis and applications to discretized Partial Differential Equations, Linear Algebra Appl., 366, 1 (2003), 371-402. Zbl1028.65109MR1987730DOI10.1016/S0024-3795(02)00504-9
  38. SERRA CAPIZZANO, S., A note on anti-reflective boundary conditions and fast deblurring models, SIAM J. Sci. Comput., 25, 4 (2004), 1307-1325. Zbl1062.65152MR2045058DOI10.1137/S1064827502410244
  39. SERRA CAPIZZANO, S., The GLT class as a Generalized Fourier Analysis and applications, Linear Algebra Appl., 419, 1 (2006), 180-233. Zbl1109.65032MR2263117DOI10.1016/j.laa.2006.04.012
  40. SERRA CAPIZZANO, S. - TABLINO POSSIO, C., Multigrid Methods for Multilevel Circulant Matrices, SIAM J. Sci. Comp., 26, 1 (2005), 55-85. Zbl1079.65033MR2114334DOI10.1137/S1064827501388509
  41. SERRA CAPIZZANO, S. - TYRTYSHNIKOV, E., Any circulant-like preconditioner for multilevel matrices is not superlinear, SIAM J. Matrix Anal. Appl., 21, 2 (1999), 431-439. Zbl0952.65037MR1718339DOI10.1137/S0895479897331941
  42. TABLINO POSSIO, C., V-cycle optimal convergence for DCT-III matrices, Numerical methods for structured matrices and applications, Oper. Theory Adv. Appl., 199 (2010), 377-396. Zbl1203.65228MR2656837DOI10.1007/978-3-7643-8996-3_17
  43. TILLI, P., Locally Toeplitz matrices: spectral theory and applications, Linear Algebra Appl., 278 (1998), 91-120. Zbl0934.15009MR1637331DOI10.1016/S0024-3795(97)10079-9
  44. TROTTENBERG, U. - OOSTERLEE, C. W. - SCHÜLLER, A., Multigrid, Academic Press, 2001. MR1807961
  45. TYRTYSHNIKOV, E., Circulant precondictioners with unbounded inverse, Linear Algebra Appl., 216 (1995), 1-23. Zbl0821.65013MR1319972DOI10.1016/0024-3795(93)00092-E
  46. TYRTYSHNIKOV, E., A unifying approach to some old and new theorems on pre-condictioning and clustering, Linear Algebra Appl., 232 (1996), 1-43. Zbl0841.15006MR1366576DOI10.1016/0024-3795(94)00025-5
  47. VARGA, R. S., Matrix Iterative Analysis, Prentice Hall, Englewood Cliffs, 1962. Zbl0133.08602MR158502
  48. VOGEL, C. R., Computational Methods for Inverse Problems, SIAM, Philadelphia, PA, 2002. Zbl1008.65103MR1928831DOI10.1137/1.9780898717570
  49. XU, J., Iterative methods by space decomposition and subspace correction, SIAM Rev., 34, 4 (1992), 581-613. Zbl0788.65037MR1193013DOI10.1137/1034116
  50. YAVNEH, I., Coarse-grid correction for nonelliptic and singular perturbation problems, SIAM J. Sci. Comp., 19, 5 (1998), 1682-1699. Zbl0918.65076MR1618757DOI10.1137/S1064827596310998

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.