Spectral analysis and spectral symbol of matrices in isogeometric collocation methods
HTML articles powered by AMS MathViewer
- by Marco Donatelli, Carlo Garoni, Carla Manni, Stefano Serra-Capizzano and Hendrik Speleers PDF
- Math. Comp. 85 (2016), 1639-1680 Request permission
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 $\|\boldsymbol {p}\|_\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 $\|\boldsymbol {p}\|_\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
- 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. MR 2112856, DOI 10.1137/S0895479803421987
- 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, DOI 10.1142/S0218202510004878
- Bernhard Beckermann and Arno B. J. Kuijlaars, Superlinear convergence of conjugate gradients, SIAM J. Numer. Anal. 39 (2001), no. 1, 300–329. MR 1860727, DOI 10.1137/S0036142999363188
- 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. MR 2300295, DOI 10.1137/05063533X
- Rajendra Bhatia, Matrix analysis, Graduate Texts in Mathematics, vol. 169, Springer-Verlag, New York, 1997. MR 1477662, DOI 10.1007/978-1-4612-0653-8
- D. Bini, M. Capovani, O. Menchi. Metodi Numerici per l’Algebra Lineare. Zanichelli (1988).
- Carl de Boor, A practical guide to splines, Revised edition, Applied Mathematical Sciences, vol. 27, Springer-Verlag, New York, 2001. MR 1900298
- Albrecht Böttcher and Bernd Silbermann, Introduction to large truncated Toeplitz matrices, Universitext, Springer-Verlag, New York, 1999. MR 1724795, DOI 10.1007/978-1-4612-1426-7
- Charles K. Chui, An introduction to wavelets, Wavelet Analysis and its Applications, vol. 1, Academic Press, Inc., Boston, MA, 1992. MR 1150048
- J. A. Cottrell, T. J. R. Hughes, Y. Bazilevs. Isogeometric Analysis: Toward Integration of CAD and FEA. John Wiley & Sons (2009).
- 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, DOI 10.1016/j.cma.2014.06.001
- 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, DOI 10.1016/j.cma.2014.11.036
- 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.
- 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.
- 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, DOI 10.1007/s00211-013-0600-2
- 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, DOI 10.1007/s00020-014-2157-6
- 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, DOI 10.1016/j.jat.2006.05.002
- 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, DOI 10.1016/j.cma.2008.12.004
- 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, DOI 10.1137/S0036142995285034
- Arno B. J. Kuijlaars, Convergence analysis of Krylov subspace iterations with methods from potential theory, SIAM Rev. 48 (2006), no. 1, 3–40. MR 2219308, DOI 10.1137/S0036144504445376
- 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, DOI 10.1006/jath.2001.3617
- 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, DOI 10.1016/j.cma.2013.07.017
- Stefano Serra, On the extreme eigenvalues of Hermitian (block) Toeplitz matrices, Linear Algebra Appl. 270 (1998), 109–129. MR 1484077
- 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, DOI 10.1007/s002110050400
- 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, DOI 10.1016/S0024-3795(00)00311-6
- 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, DOI 10.1016/S0024-3795(02)00504-9
- Stefano Serra-Capizzano, The GLT class as a generalized Fourier analysis and applications, Linear Algebra Appl. 419 (2006), no. 1, 180–233. MR 2263117, DOI 10.1016/j.laa.2006.04.012
- Stefano Serra Capizzano and Cristina Tablino Possio, Analysis of preconditioning strategies for collocation linear systems, Linear Algebra Appl. 369 (2003), 41–75. MR 1988478, DOI 10.1016/S0024-3795(02)00719-X
- Weiwei Sun, Spectral analysis of Hermite cubic spline collocation systems, SIAM J. Numer. Anal. 36 (1999), no. 6, 1962–1975. MR 1712216, DOI 10.1137/S0036142997322722
- P. Tilli, Locally Toeplitz sequences: spectral properties and applications, Linear Algebra Appl. 278 (1998), no. 1-3, 91–120. MR 1637331, DOI 10.1016/S0024-3795(97)10079-9
Additional Information
- Marco Donatelli
- Affiliation: Department of Science and High Technology, University of Insubria, Via Valleggio 11, 22100 Como, Italy
- MR Author ID: 751539
- Email: marco.donatelli@uninsubria.it
- Carlo Garoni
- Affiliation: Department of Science and High Technology, University of Insubria, Via Valleggio 11, 22100 Como, Italy
- MR Author ID: 1021672
- Email: carlo.garoni@uninsubria.it
- Carla Manni
- Affiliation: Department of Mathematics, University of Rome ‘Tor Vergata’, Via della Ricerca Scientifica, 00133 Rome, Italy
- MR Author ID: 119310
- 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
- MR Author ID: 332436
- 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
- MR Author ID: 778374
- Email: speleers@mat.uniroma2.it, hendrik.speleers@cs.kuleuven.be
- 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.
- © Copyright 2015 American Mathematical Society
- Journal: Math. Comp. 85 (2016), 1639-1680
- MSC (2010): Primary 15A18, 15B05, 41A15, 15A69, 65N35
- DOI: https://doi.org/10.1090/mcom/3027
- MathSciNet review: 3471103