Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 
 

 

Spectral analysis and spectral symbol of matrices in isogeometric collocation methods


Authors: Marco Donatelli, Carlo Garoni, Carla Manni, Stefano Serra-Capizzano and Hendrik Speleers
Journal: Math. Comp. 85 (2016), 1639-1680
MSC (2010): Primary 15A18, 15B05, 41A15, 15A69, 65N35
DOI: https://doi.org/10.1090/mcom/3027
Published electronically: October 15, 2015
MathSciNet review: 3471103
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We consider a linear full elliptic second order partial differential equation in a $ d$-dimensional domain, $ d\ge 1$, approximated by isogeometric collocation methods based on uniform (tensor-product) B-splines of degrees $ \boldsymbol {p}:=(p_1,\ldots ,p_d)$, $ p_j\ge 2$, $ j=1,\ldots ,d$. We give a construction of the inherently non-symmetric matrices arising from this approximation technique and we perform an analysis of their spectral properties. In particular, we find and study the associated (spectral) symbol, that is, the function describing their asymptotic spectral distribution (in the Weyl sense) when the matrix-size tends to infinity or, equivalently, the fineness parameters tend to zero. The symbol is a non-negative function with a unique zero of order two at $ \boldsymbol {\theta }=\mathbf {0}$ (where $ \boldsymbol {\theta }:=(\theta _1,\ldots ,\theta _d)$ are the Fourier variables), but with infinitely many `numerical zeros' for large $ \Vert\boldsymbol {p}\Vert _\infty $. Indeed, the symbol converges exponentially to zero with respect to $ p_j$ at all the points $ \boldsymbol {\theta }$ such that $ \theta _j=\pi $. In other words, if $ p_j$ is large, all the points $ \boldsymbol {\theta }$ with $ \theta _j=\pi $ behave numerically like a zero of the symbol. The presence of the zero of order two at $ \boldsymbol {\theta }=\mathbf {0}$ is expected because it is intrinsic in any local approximation method, such as finite differences and finite elements, of second order differential operators. However, the `numerical zeros' lead to the surprising fact that, for large $ \Vert\boldsymbol {p}\Vert _\infty $, there is a subspace of high frequencies where the collocation matrices are ill-conditioned. This non-canonical feature is responsible for the slowdown, with respect to $ \boldsymbol {p}$, of standard iterative methods. On the other hand, this knowledge and the knowledge of other properties of the symbol can be exploited to construct iterative solvers with convergence properties independent of the fineness parameters and of the degrees $ \boldsymbol {p}$.


References [Enhancements On Off] (What's this?)

  • [1] Antonio Aricò, Marco Donatelli, and Stefano Serra-Capizzano, V-cycle optimal convergence for certain (multilevel) structured linear systems, SIAM J. Matrix Anal. Appl. 26 (2004), no. 1, 186-214 (electronic). MR 2112856 (2006a:65049), https://doi.org/10.1137/S0895479803421987
  • [2] F. Auricchio, L. Beirão da Veiga, T. J. R. Hughes, A. Reali, and G. Sangalli, Isogeometric collocation methods, Math. Models Methods Appl. Sci. 20 (2010), no. 11, 2075-2107. MR 2740715 (2011j:65038), https://doi.org/10.1142/S0218202510004878
  • [3] Bernhard Beckermann and Arno B. J. Kuijlaars, Superlinear convergence of conjugate gradients, SIAM J. Numer. Anal. 39 (2001), no. 1, 300-329 (electronic). MR 1860727 (2002f:65040), https://doi.org/10.1137/S0036142999363188
  • [4] Bernhard Beckermann and Stefano Serra-Capizzano, On the asymptotic spectrum of finite element matrix sequences, SIAM J. Numer. Anal. 45 (2007), no. 2, 746-769 (electronic). MR 2300295 (2007m:65103), https://doi.org/10.1137/05063533X
  • [5] Rajendra Bhatia, Matrix Analysis, Graduate Texts in Mathematics, vol. 169, Springer-Verlag, New York, 1997. MR 1477662 (98i:15003)
  • [6] D. Bini, M. Capovani, O. Menchi. Metodi Numerici per l'Algebra Lineare. Zanichelli (1988).
  • [7] Carl de Boor, A Practical Guide to Splines, Revised edition, Applied Mathematical Sciences, vol. 27, Springer-Verlag, New York, 2001. MR 1900298 (2003f:41001)
  • [8] Albrecht Böttcher and Bernd Silbermann, Introduction to Large Truncated Toeplitz Matrices, Universitext, Springer-Verlag, New York, 1999. MR 1724795 (2001b:47043)
  • [9] Charles K. Chui, An Introduction to Wavelets, Wavelet Analysis and its Applications, vol. 1, Academic Press, Inc., Boston, MA, 1992. MR 1150048 (93f:42055)
  • [10] J. A. Cottrell, T. J. R. Hughes, Y. Bazilevs. Isogeometric Analysis: Toward Integration of CAD and FEA. John Wiley & Sons (2009).
  • [11] Marco Donatelli, Carlo Garoni, Carla Manni, Stefano Serra-Capizzano, and Hendrik Speleers, Robust and optimal multi-iterative techniques for IgA Galerkin linear systems, Comput. Methods Appl. Mech. Engrg. 284 (2015), 230-264. MR 3310285, https://doi.org/10.1016/j.cma.2014.06.001
  • [12] Marco Donatelli, Carlo Garoni, Carla Manni, Stefano Serra-Capizzano, and Hendrik Speleers, Robust and optimal multi-iterative techniques for IgA collocation linear systems, Comput. Methods Appl. Mech. Engrg. 284 (2015), 1120-1146. MR 3310320, https://doi.org/10.1016/j.cma.2014.11.036
  • [13] M. Donatelli, C. Garoni, C. Manni, S. Serra-Capizzano, H. Speleers. Symbol-based multigrid methods for Galerkin B-spline isogeometric analysis. Tech. Report TW650 (2014), Dept. Computer Science, KU Leuven.
  • [14] C. Garoni. Structured matrices coming from PDE approximation theory: spectral analysis, spectral symbol and design of fast iterative solvers. Ph.D. Thesis in Mathematics of Computation, University of Insubria, Como, Italy (2014). Available online at http://hdl.handle.net/10277/568.
  • [15] Carlo Garoni, Carla Manni, Francesca Pelosi, Stefano Serra-Capizzano, and Hendrik Speleers, On the spectrum of stiffness matrices arising from isogeometric analysis, Numer. Math. 127 (2014), no. 4, 751-799. MR 3229992, https://doi.org/10.1007/s00211-013-0600-2
  • [16] Carlo Garoni, Stefano Serra-Capizzano, and Debora Sesana, Tools for determining the asymptotic spectral distribution of non-Hermitian perturbations of Hermitian matrix-sequences and applications, Integral Equations Operator Theory 81 (2015), no. 2, 213-225. MR 3299836, https://doi.org/10.1007/s00020-014-2157-6
  • [17] Leonid Golinskii and Stefano Serra-Capizzano, The asymptotic properties of the spectrum of nonsymmetrically perturbed Jacobi matrix sequences, J. Approx. Theory 144 (2007), no. 1, 84-102. MR 2287378 (2007k:47047), https://doi.org/10.1016/j.jat.2006.05.002
  • [18] T. J. R. Hughes, A. Reali, and G. Sangalli, Efficient quadrature for NURBS-based isogeometric analysis, Comput. Methods Appl. Mech. Engrg. 199 (2010), no. 5-8, 301-313. MR 2576763 (2011a:65055), https://doi.org/10.1016/j.cma.2008.12.004
  • [19] Sang Dong Kim and Seymour V. Parter, Preconditioning Chebyshev spectral collocation by finite-difference operators, SIAM J. Numer. Anal. 34 (1997), no. 3, 939-958. MR 1451108 (98f:65116), https://doi.org/10.1137/S0036142995285034
  • [20] Arno B. J. Kuijlaars, Convergence analysis of Krylov subspace iterations with methods from potential theory, SIAM Rev. 48 (2006), no. 1, 3-40 (electronic). MR 2219308 (2007a:65054), https://doi.org/10.1137/S0036144504445376
  • [21] A. B. J. Kuijlaars and S. Serra Capizzano, Asymptotic zero distribution of orthogonal polynomials with discontinuously varying recurrence coefficients, J. Approx. Theory 113 (2001), no. 1, 142-155. MR 1866252 (2002i:42029), https://doi.org/10.1006/jath.2001.3617
  • [22] Dominik Schillinger, John A. Evans, Alessandro Reali, Michael A. Scott, and Thomas J. R. Hughes, Isogeometric collocation: cost comparison with Galerkin methods and extension to adaptive hierarchical NURBS discretizations, Comput. Methods Appl. Mech. Engrg. 267 (2013), 170-232. MR 3127300, https://doi.org/10.1016/j.cma.2013.07.017
  • [23] Stefano Serra, On the extreme eigenvalues of Hermitian (block) Toeplitz matrices, Linear Algebra Appl. 270 (1998), 109-129. MR 1484077 (98k:15034)
  • [24] Stefano Serra, The rate of convergence of Toeplitz based PCG methods for second order nonlinear boundary value problems, Numer. Math. 81 (1999), no. 3, 461-495. MR 1668099 (99m:65202), https://doi.org/10.1007/s002110050400
  • [25] S. Serra Capizzano, Distribution results on the algebra generated by Toeplitz sequences: a finite-dimensional approach, Linear Algebra Appl. 328 (2001), no. 1-3, 121-130. MR 1823514 (2002b:15016), https://doi.org/10.1016/S0024-3795(00)00311-6
  • [26] S. Serra Capizzano, Generalized locally Toeplitz sequences: spectral analysis and applications to discretized partial differential equations, Linear Algebra Appl. 366 (2003), 371-402. Special issue on structured matrices: analysis, algorithms and applications (Cortona, 2000). MR 1987730 (2004d:47062), https://doi.org/10.1016/S0024-3795(02)00504-9
  • [27] Stefano Serra-Capizzano, The GLT class as a generalized Fourier analysis and applications, Linear Algebra Appl. 419 (2006), no. 1, 180-233. MR 2263117 (2008a:15023), https://doi.org/10.1016/j.laa.2006.04.012
  • [28] Stefano Serra Capizzano and Cristina Tablino Possio, Analysis of preconditioning strategies for collocation linear systems, Linear Algebra Appl. 369 (2003), 41-75. MR 1988478 (2004c:65035), https://doi.org/10.1016/S0024-3795(02)00719-X
  • [29] Weiwei Sun, Spectral analysis of Hermite cubic spline collocation systems, SIAM J. Numer. Anal. 36 (1999), no. 6, 1962-1975. MR 1712216 (2000h:65143), https://doi.org/10.1137/S0036142997322722
  • [30] P. Tilli, Locally Toeplitz sequences: spectral properties and applications, Linear Algebra Appl. 278 (1998), no. 1-3, 91-120. MR 1637331 (99g:47057), https://doi.org/10.1016/S0024-3795(97)10079-9

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 15A18, 15B05, 41A15, 15A69, 65N35

Retrieve articles in all journals with MSC (2010): 15A18, 15B05, 41A15, 15A69, 65N35


Additional Information

Marco Donatelli
Affiliation: Department of Science and High Technology, University of Insubria, Via Valleggio 11, 22100 Como, Italy
Email: marco.donatelli@uninsubria.it

Carlo Garoni
Affiliation: Department of Science and High Technology, University of Insubria, Via Valleggio 11, 22100 Como, Italy
Email: carlo.garoni@uninsubria.it

Carla Manni
Affiliation: Department of Mathematics, University of Rome ‘Tor Vergata’, Via della Ricerca Scientifica, 00133 Rome, Italy
Email: manni@mat.uniroma2.it

Stefano Serra-Capizzano
Affiliation: Department of Science and High Technology, University of Insubria, Via Valleggio 11, 22100 Como, Italy; Department of Information Technology, Uppsala University, Box 337, SE-751 05 Uppsala, Sweden
Email: stefano.serrac@uninsubria.it, stefano.serra@it.uu.se

Hendrik Speleers
Affiliation: Department of Mathematics, University of Rome ‘Tor Vergata’, Via della Ricerca Scientifica, 00133 Rome, Italy; Department of Computer Science, University of Leuven, Celestijnenlaan 200A, 3001 Heverlee (Leuven), Belgium
Email: speleers@mat.uniroma2.it, hendrik.speleers@cs.kuleuven.be

DOI: https://doi.org/10.1090/mcom/3027
Keywords: Spectral distribution, symbol, collocation method, B-splines, isogeometric analysis
Received by editor(s): April 21, 2014
Received by editor(s) in revised form: December 6, 2014
Published electronically: October 15, 2015
Additional Notes: This work was partially supported by INdAM-GNCS Gruppo Nazionale per il Calcolo Scientifico, by MIUR - PRIN 2012 N. 2012MTE38N, by the MIUR ‘Futuro in Ricerca 2013’ Programme through the project DREAMS, by the Research Foundation Flanders, and by the Program ‘Becoming the Number One – Sweden (2014)’ of the Knut and Alice Wallenberg Foundation.
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society