×

Spectral analysis of coupled PDEs and of their Schur complements via generalized locally Toeplitz sequences in 2D. (English) Zbl 1439.65138

Summary: We consider large linear systems of algebraic equations arising from the Finite Element approximation of coupled partial differential equations. As case study we focus on the linear elasticity equations, formulated as a saddle point problem to allow for modelling of purely incompressible materials. To analyse the properties of the arising matrices we use the notion of the so-called spectral symbol in the Generalized Locally Toeplitz (GLT) setting. The fruitful idea behind GLT is that it allows to associate a function, a symbol, with instances of a broad class of structured matrices. The symbol describes the spectrum of the corresponding matrix, easing in this way its analysis and guiding the construction of efficient approximations of the matrix to be used as preconditioners or solvers in a multigrid context. We derive the GLT symbol of the sequence of matrices \(\{A_n \}\) approximating the elasticity equations. Further, exploiting the property that the GLT class defines an algebra of matrix sequences and the fact that the Schur complements are obtained via elementary algebraic operation on the blocks of \(A_n\), we derive the symbols \(f^{\mathcal{S}}\) of the associated sequences of Schur complements \(\{S_n \}\). As a consequence of the GLT theory, the eigenvalues of \(S_n\) for large \(n\) are described by a sampling of \(f^{\mathcal{S}}\) on a uniform grid of its domain of definition. We extend the existing GLT technique with novel elements, related to block-matrices and Schur complement matrices, and illustrate the theoretical findings with numerical tests.

MSC:

65N22 Numerical solution of discretized equations for boundary value problems involving PDEs
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
65F10 Iterative numerical methods for linear systems
Full Text: DOI

References:

[1] Chan, R. H.; Ng, M. K., Conjugate gradient methods for Toeplitz systems, SIAM Rev., 38, 3, 427-482 (1996) · Zbl 0863.65013
[2] Pestana, J.; Wathen, A. J., A preconditioned minres method for nonsymmetric Toeplitz matrices, SIAM J. Matrix Anal. Appl., 36, 1, 273-288 (2015) · Zbl 1315.65034
[3] Serra, S., A Korovkin-type theory for finite Toeplitz operators via matrix algebras, Numer. Math., 82, 1, 117-142 (1999) · Zbl 0930.65024
[4] Beckermann, B.; Serra Capizzano, S., On the asymptotic spectrum of finite element matrix sequences, SIAM J. Numer. Anal., 45, 2, 746-769 (2007) · Zbl 1140.65080
[5] Serra Capizzano, S., Convergence analysis of two-grid methods for elliptic Toeplitz and PDEs matrix-sequences, Numer. Math., 92, 3, 433-465 (2002) · Zbl 1013.65026
[6] Serra Capizzano, S.; Possio, C. T., Analysis of preconditioning strategies for collocation linear systems, Linear Algebra Appl., 369, 0, 41-75 (2003) · Zbl 1030.65037
[7] Serra Capizzano, S.; Tablino-Possio, C., Multigrid methods for multilevel circulant matrices, SIAM J. Sci. Comput., 26, 1, 55-85 (2004) · Zbl 1079.65033
[8] Donatelli, M.; Garoni, C.; Manni, C.; Serra Capizzano, S.; Speleers, H., Robust and optimal multi-iterative techniques for IgA Galerkin linear systems, Comput. Methods Appl. Mech. Engrg., 284, 230-264 (2015), MR3310285 · Zbl 1425.65136
[9] Donatelli, M.; Garoni, C.; Manni, C.; Serra Capizzano, S.; Speleers, H., Robust and optimal multi-iterative techniques for IgA collocation linear systems, Comput. Methods Appl. Mech. Engrg., 284, 1120-1146 (2015), MR3310320 · Zbl 1425.65196
[10] Di Benedetto, F.; Estatico, C.; Capizzano, S. S., Superoptimal preconditioned conjugate gradient iteration for image deblurring, SIAM J. Sci. Comput., 26, 3, 1012-1035 (2005) · Zbl 1088.65029
[11] Hanke, M.; Nagy, J., Inverse Toeplitz preconditioners for ill-posed problems, Linear Algebra Appl., 284, 1, 137-156 (1998) · Zbl 0935.65037
[12] Tyrtyshnikov, E. E., A unifying approach to some old and new theorems on distribution and clustering, Linear Algebra Appl., 232, 0, 1-43 (1996) · Zbl 0841.15006
[13] Böttcher, A.; Silbermann, B., Introduction to Large Truncated Toeplitz Matrices (1999), Springer Science & Business Media · Zbl 0916.15012
[14] Serra Capizzano, S., Generalized locally Toeplitz sequences: spectral analysis and applications to discretized partial differential equations, Linear Algebra Appl., 366, 0, 371-402 (2003), Special issue on Structured Matrices: Analysis, Algorithms and Applications · Zbl 1028.65109
[15] Rudin, W., Real and Complex Analysis (1974), McGraw-Hill Education · Zbl 0278.26001
[16] Tilli, P., A note on the spectral distribution of Toeplitz matrices, Linear Multilinear Algebra, 45, 2-3, 147-159 (1998) · Zbl 0951.65033
[17] Serra Capizzano, S., The {GLT} class as a generalized Fourier analysis and applications, Linear Algebra Appl., 419, 1, 180-233 (2006) · Zbl 1109.65032
[18] Grenander, U.; Szegö, G., Toeplitz Forms and their Applications (1984), Chelsea: Chelsea New York · Zbl 0611.47018
[19] Bhatia, R., Matrix Analysis, vol. 169 (1997), Springer Science & Business Media
[20] Horn, R. A.; Johnson, C. R., Topics in Matrix Analysis (1991), Cambridge University Press, Cambridge Books Online · Zbl 0729.15001
[21] Strang, G., A proposal for Toeplitz matrix calculations, Stud. Appl. Math., 74, 2, 171-176 (1986) · Zbl 0621.65025
[22] Garoni, C.; Serra Capizzano, S.; Sesana, D., Spectral Analysis and Spectral Symbol of \(d\)-variate \(Q_p\) Lagrangian FEM Stiffness Matrices. Tech. Rep. 2014-021 (2014), Department of Information Technology, Uppsala University, Nov
[23] Tyrtyshnikov, E.; Zamarashkin, N., Spectra of multilevel Toeplitz matrices: Advanced theory via simple matrix relationships, Linear Algebra Appl., 270, 15-27 (1998) · Zbl 0890.15006
[24] Tilli, P., Some results on complex Toeplitz eigenvalues, J. Math. Anal. Appl., 239, 2, 390-401 (1999) · Zbl 0935.15002
[25] Donatelli, M.; Neytcheva, M.; Serra Capizzano, S., Canonical eigenvalue distribution of multilevel block Toeplitz sequences with non-Hermitian symbols, (Arendt, W.; Ball, J. A.; Behrndt, J.; Förster, K.-H.; Mehrmann, V.; Trunk, C., Spectral Theory, Mathematical System Theory, Evolution Equations, Differential and Difference Equations. Spectral Theory, Mathematical System Theory, Evolution Equations, Differential and Difference Equations, Operator Theory: Advances and Applications, vol. 221 (2012), Springer: Springer Basel), 269-291 · Zbl 1261.15011
[26] Donatelli, M.; Garoni, C.; Mazza, M.; Serra Capizzano, S.; Sesana, D., Spectral behavior of preconditioned non-Hermitian multilevel block Toeplitz matrices with matrix-valued symbol, Appl. Math. Comput., 245, 0, 158-173 (2014) · Zbl 1335.15036
[27] Beckermann, B.; Kuijlaars, A. B.J., Superlinear convergence of conjugate gradients, SIAM J. Numer. Anal., 39, 1, 300-329 (2001) · Zbl 0997.65058
[28] Axelsson, O.; Lindskog, G., On the rate of convergence of the preconditioned conjugate gradient method, Numer. Math., 48, 5, 499-523 (1986) · Zbl 0564.65017
[29] van der Sluis, A.; van der Vorst, H., The rate of convergence of conjugate gradients, Numer. Math., 48, 5, 543-560 (1986) · Zbl 0596.65015
[30] Saad, Y., Iterative Methods for Sparse Linear Systems (2003), Siam · Zbl 1002.65042
[31] Donatelli, M.; Dorostkar, A.; Mazza, M.; Neytcheva, M.; Serra Capizzano, S., (A Block Multigrid Strategy for Two-dimensional Coupled PDEs. Tech. Rep. 2016-001. A Block Multigrid Strategy for Two-dimensional Coupled PDEs. Tech. Rep. 2016-001, Numerical Analysis (2016), Uppsala University)
[32] Axelsson, O., Finite difference methods, Encyclopedia Comput. Mech. (2004) · Zbl 1061.65043
[33] Gustafsson, B.; Kreiss, H.; Oliger, J., Time-dependent problems and difference methods, (Pure and Applied Mathematics: A Wiley Series of Texts, Monographs and Tracts (2013), Wiley) · Zbl 1275.65048
[34] Fortin, M.; Brezzi, F., Mixed and Hybrid Finite Element Methods (1991), Springer-Verlag: Springer-Verlag New York · Zbl 0788.73002
[35] Johnson, C., Numerical Solution of Partial Differential Equations by the Finite Element Method (1988), Cambridge University Press
[36] Cottrell, J. A.; Hughes, T. J.; Bazilevs, Y., Isogeometric Analysis: Toward Integration of CAD and FEA (2009), John Wiley & Sons · Zbl 1378.65009
[37] Garoni, C.; Manni, C.; Pelosi, F.; Serra Capizzano, S.; Speleers, H., On the spectrum of stiffness matrices arising from isogeometric analysis, Numer. Math., 127, 4, 751-799 (2014) · Zbl 1298.65172
[38] Serra Capizzano, S.; Possio, C. T., Spectral and structural analysis of high precision finite difference matrices for elliptic operators, Linear Algebra Appl., 293, 85-131 (1999) · Zbl 0940.65113
[39] Donatelli, M.; Garoni, C.; Manni, C.; Serra Capizzano, S.; Speleers, H., Spectral analysis of matrices in collocation methods with B-splines, Math. Comp., 85, 1639-1680 (2016) · Zbl 1335.65096
[40] Tilli, P., Locally Toeplitz sequences: spectral properties and applications, Linear Algebra Appl., 278, 91-120 (1998) · Zbl 0934.15009
[41] Parter, S., On the eigenvalues of certain generalisations of Toeplitz matrices, Arch. Ration. Mech. Anal., 11, 1, 244-257 (1962) · Zbl 0115.28401
[42] Garoni, C.; Serra Capizzano, S.; Sesana, D., Tools for determining the asymptotic spectral distribution of non-Hermitian perturbations of Hermitian matrix-sequences and applications, Integral Equations Operator Theory, 81, 2, 213-225 (2015) · Zbl 1337.47045
[43] Lund, B.; Näslund, J. O., Glacial isostatic adjustment: implications for glacially induced faulting and nuclear waste repositories, (Connor, C. B.; Chapman, N. A.; Connor, L. J., Volcanic and Tectonic Hazard Assessment for Nuclear Facilities (2009), Cambridge University Press), 142-155, Cambridge Books Online
[44] Wu, P., Deformation of an incompressible viscoelastic flat earth with powerlaw creep: a finite element approach, Geophys. J. Int., 108, 1, 35-51 (1992)
[45] Wu, P., Viscoelastic versus viscous deformation and the advection of pre-stress, Geophys. J. Int., 108, 1, 136-142 (1992)
[46] Braess, D., Finite Elements: Theory, Fast Solvers, and Applications in Solid Mechanics (2007), Cambridge University Press · Zbl 1118.65117
[47] Axelsson, O.; Padiy, A., On a robust and scalable linear elasticity solver based on a saddle point formulation, Internat. J. Numer. Methods Engrg., 44, 6, 801-818 (1999) · Zbl 0956.74050
[48] Axelsson, O., Iterative Solution Methods (1996), Cambridge University Press · Zbl 0845.65011
[49] Axelsson, O.; Neytcheva, M., Preconditioning methods for linear systems arising in constrained optimization problems, Numer. Linear Algebra Appl., 10, 1-2, 3-31 (2003) · Zbl 1071.65527
[50] Benzi, M.; Golub, G. H.; Liesen, J., Numerical solution of saddle point problems, Acta Numer., 14, 5, 1-137 (2005) · Zbl 1115.65034
[51] Axelsson, O.; Blaheta, R.; Neytcheva, M., Preconditioning of boundary value problems using elementwise schur complements, SIAM J. Matrix Anal. Appl., 31, 2, 767-789 (2009) · Zbl 1194.65047
[52] Bängtsson, E.; Lund, B., A comparison between two solution techniques to solve the equations of glacially induced deformation of an elastic earth, Internat. J. Numer. Methods Engrg., 75, 4, 479-502 (2008) · Zbl 1195.74110
[53] Dorostkar, A.; Neytcheva, M.; Lund, B., (On Some Block-preconditioners for Saddle Point Systems and their CPU-GPU Performance. Tech. Rep. 2015-003. On Some Block-preconditioners for Saddle Point Systems and their CPU-GPU Performance. Tech. Rep. 2015-003, Geophysics (2015), Uppsala University)
[54] Kraus, J., Additive schur complement approximation and application to multilevel preconditioning, SIAM J. Sci. Comput., 34, 6, A2872-A2895 (2012) · Zbl 1269.65031
[55] Kraus, J., Algebraic multilevel preconditioning of finite element matrices using local schur complements, Numer. Linear Algebra Appl., 13, 1, 49-70 (2006) · Zbl 1174.65398
[56] Neytcheva, M., On element-by-element schur complement approximations, Linear Algebra Appl., 434, 11, 2308-2324 (2011), Special Issue: Devoted to the 2nd {NASC} 08 Conference in Nanjing (NSC) · Zbl 1216.65041
[57] Neytcheva, M.; Bängtsson, E., Preconditioning of nonsymmetric saddle point systems as arising in modelling of viscoelastic problems, Electron. Trans. Numer. Anal., 29, 193-211 (2007/08) · Zbl 1173.74045
[58] Dorostkar, A.; Neytcheva, M.; Serra Capizzano, S., Schur complement matrix and its (elementwise) approximation: A spectral analysis based on glt sequences, (Large-Scale Scientific Computing (2015), Springer), 419-426 · Zbl 1450.65032
[59] Dorostkar, A.; Neytcheva, M.; Serra Capizzano, S., (Spectral Analysis of Coupled PDEs and of their Schur Complements via the Notion of Generalized Locally Toeplitz Sequences. Tech. Rep. 2015-008. Spectral Analysis of Coupled PDEs and of their Schur Complements via the Notion of Generalized Locally Toeplitz Sequences. Tech. Rep. 2015-008, Numerical Analysis (2015), Uppsala University)
[60] Ngondiep, E.; Serra Capizzano, S.; Sesana, D., Spectral features and asymptotic properties for g-circulants and g-Toeplitz sequences, SIAM J. Matrix Anal. Appl., 31, 4, 1663-1687 (2010) · Zbl 1206.15010
[61] Fiorentino, G.; Serra, S., Multigrid methods for symmetric positive definite block Toeplitz matrices with nonnegative generating functions, SIAM J. Sci. Comput., 17, 5, 1068-1081 (1996) · Zbl 0858.65039
[62] Cottrell, J. A.; Reali, A.; Bazilevs, Y.; Hughes, T. J., Isogeometric analysis of structural vibrations, Comput. Methods Appl. Mech. Engrg., 195, 41, 5257-5296 (2006) · Zbl 1119.74024
[63] Del Prete, V.; Benedetto, F. D.; Donatelli, M.; Serra Capizzano, S., Symbol approach in a signal-restoration problem involving block Toeplitz matrices, J. Comput. Appl. Math., 272, 0, 399-416 (2014) · Zbl 1294.15020
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.