University of Insubria
Department of Science and High Technology
Ph.D. in Mathematics of Computation: Models, Structures, Algorithms and Applications
Structured Matrices coming from PDE Approximation Theory:
Spectral Analysis, Spectral Symbol and Design of Fast Iterative Solvers
Supervisor: Prof. Stefano Serra-Capizzano
Ph.D. Thesis of Carlo Garoni
Academic Year 2013/2014
I dedicate my Ph.D. thesis to my wonderful supervisor Stefano
Contents
Introduction 5
1 Notation, definitions and mathematical background 9
1.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.1.1 Multi-index notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2 Preliminaries on Linear Algebra and Matrix Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2.1 Tensor products and direct sums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.2.2 Hadamard product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.3 Spectral distribution, spectral symbol, clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.4 Toeplitz matrices and related topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.4.1 Multilevel block Toeplitz matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.4.2 Multilevel block circulant matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.4.3 GLT sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2 Some new tools for computing spectral distributions 34 2.1 Tools for determining the spectral distribution of Hermitian matrix-sequences and applications . . . . . 34
2.1.1 An a.c.s.-based proof of the Szegö theorem on the spectral distribution of Toeplitz matrices . . . . 38
2.2 Tools for determining the spectral distribution of non-Hermitian perturbations of Hermitian matrix- sequences and applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.2.1 Main results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.2.2 Some applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3 Spectral analysis and spectral symbol ofQp Lagrangian FEM stiffness matrices 48 3.1 Galerkin method and Qp Lagrangian FEM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.2 Construction of theQp Lagrangian FEM stiffness matrices A( p)n . . . . . . . . . . . . . . . . . . . . . . . . 53
3.2.1 Construction of K(p)n , Mn(p) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.3 Properties offp(θ) and hp(θ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.4 Spectral analysis and spectral symbol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.4.1 Estimates for the eigenvalues, localization of the spectrum and conditioning of A( p)n . . . . . . . . 61
3.4.2 Spectral distribution and symbol of the normalized sequence {nd−2A( p)n }n . . . . . . . . . . . . . . . 67
3.4.3 Exponential scattering and ill-conditioning of the symbol . . . . . . . . . . . . . . . . . . . . . . . . 69
3.4.4 Clustering of the normalized sequence {nd−2A( p)n }n . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4 Spectral analysis and spectral symbol of Galerkin B-spline IgA stiffness matrices 72 4.1 Problem setting and Galerkin B-spline IgA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.2 Cardinal B-splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.2.1 Properties of cardinal B-splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.2.2 Fourier transform of cardinal B-splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.3 Construction of the Galerkin B-spline IgA stiffness matrices A[ p]n . . . . . . . . . . . . . . . . . . . . . . . 79
4.3.1 Construction of K[p]n , Hn[p], Mn[p] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
4.4 Properties of fp(θ) and hp(θ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
4.5 Spectral analysis and spectral symbol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
4.5.1 Estimates for the eigenvalues, localization of the spectrum and conditioning of A[ p]n . . . . . . . . 86
4.5.2 Spectral distribution and symbol of the normalized sequence {nd−2A[ p]n }n . . . . . . . . . . . . . . . 92
4.5.3 The linear case p=1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
4.5.4 The quadratic case p=2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.5.5 The bilinear case p1 = p2=1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4.5.6 The biquadratic case p1= p2=2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
5 Spectral distribution and spectral symbol of B-spline IgA collocation matrices 105 5.1 B-spline IgA Collocation Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
5.2 Construction of the B-spline IgA collocation matrices A[ p]n . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
5.2.1 Construction of K[p]n , Hn[p], Mn[p] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
5.3 Properties of fp(θ), gp(θ), hp(θ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
5.4 Spectral distribution and spectral symbol of the normalized sequences {n12A[ p]n }n and {n12A[ p]G,n}n . . . . . . 120
5.4.1 Properties of the spectral symbol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
6 Fast iterative solvers for Galerkin B-spline IgA linear systems 130 6.1 How to use the symbol? A basic guide to the user . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
6.1.1 Counting the eigenvalues belonging to a given interval . . . . . . . . . . . . . . . . . . . . . . . . . 132
6.1.2 Eigenvectors vs. frequencies in a perturbed Toeplitz setting . . . . . . . . . . . . . . . . . . . . . . . 132
6.2 Iterative solvers and the multi-iterative approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
6.2.1 Unity makes strength: the multi-iterative approach . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
6.2.2 Two-grid and multigrid methods in a multi-iterative perspective . . . . . . . . . . . . . . . . . . . . 135
6.2.3 Multi-iterative solvers vs. spectral distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
6.2.4 Choice of the projector in our two-grid and multigrid methods . . . . . . . . . . . . . . . . . . . . 137
6.2.5 PCG with p-independent convergence rate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
6.3 Two-grid algorithms and their performances: 1D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
6.3.1 Classical two-grid methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
6.3.2 Multi-iterative two-grid method with PCG as smoother . . . . . . . . . . . . . . . . . . . . . . . . . 144
6.4 Two-grid algorithms and their performances: 2D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
6.4.1 Classical two-grid methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
6.4.2 Multi-iterative two-grid method with PCG as smoother . . . . . . . . . . . . . . . . . . . . . . . . . 147
6.5 Two-grid algorithms and their performances: 3D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
6.6 Multigrid: V-cycle and W-cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
6.6.1 1D case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
6.6.2 2D case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
6.6.3 3D case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
6.7 Further insights: fast multi-iterative solver for Galerkin B-spline IgA stiffness matrices associated with full elliptic problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
7 Fast iterative solvers for B-spline IgA collocation linear systems 156 7.1 Optimal and robust PGMRES for the general IgA collocation matrix A[ p]G,n . . . . . . . . . . . . . . . . . . 158
7.2 Optimal and robust multi-iterative multigrid solver for the PL-matrix A[ p]n . . . . . . . . . . . . . . . . . . 162
7.2.1 Two-grid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
7.2.2 Multigrid: V-cycle and W-cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
Conclusion 168
Bibliography 170
Acknowledgments 174
Introduction
Partial Differential Equations (PDE) are extensively used in Physics, Engineering and Applied Sciences in order to model real-world problems. A closed form for the analytical solution of such PDE is normally not available and, even in the few cases in which it is available, it often reduces to a non-informative representation formula, completely useless from a practical viewpoint (think for example to the solution of the heat equation ...). It is therefore of fundamental importance to approximate the solution u of a PDE by means of some numerical method.
Despite the differences that allow one to distinguish among the various numerical methods, the principle on which all of them are based is essentially the same: they first discretize the continuous PDE by introducing a mesh, related to some discretization parameter n, and then they compute the corresponding numerical solution un, which will converge in some topology to the solution u of the PDE when n → ∞, i.e., when the mesh is progressively refined.
Now, if the considered PDE and the chosen numerical method are both linear, the actual computation of the numerical solution un reduces to solving a certain linear system Anun = fn whose size dn increases with n and tends to infinity when n → ∞. Hence, what we actually have is not just a single linear system, but a whole sequence of linear systems with increasing dimensions. Furthermore, what is often verified in practice is that, when n → ∞, the sequence of discretization matrices An enjoys an asymptotic spectral distribution, which is somehow related to the spectrum of the differential operator L associated with the PDE. More in detail, it often happens that, for a large set of test functions F (usually, for all continuous functions F with bounded support), the following limit relation holds:
n→∞lim 1 dn
dn
X
j=1
F(λj(An))= 1 md(D)
Z
D
Ps
i=1F(λi(f(x)))
s dx, (1)
where λj(An), j = 1, . . . , dn, are the eigenvalues of An, md is the Lebesgue measure in Rd, and λi(f(x)), i = 1, . . . , s, are the eigenvalues of a certain matrix-valued function
f : D ⊆ Rd → Cs×s. (2)
In this situation, f is called the spectral symbol (or simply the symbol) of the sequence of matrices An, and it provides a ‘compact’ description of the asymptotic spectral distribution of An; see Remark 1.2 below.
The identification and the study of the symbol f are, of course, two interesting issues in themselves, because they provide a quite accurate information about the asymptotic global behavior of the eigenvalues of An. In particular, an often successful guesstimate for the spectral condition number κ(An), at least in the case where An is Hermitian positive definite, can be obtained by analyzing the eigenvalue functions λmin(f(x)) and λmax(f(x)) (especially, the number and the orders of the zeros of λmin(f(x)), if any). Moreover, the number s, indentifying the space Cs×s in which the symbol f takes values, coincides with the number of
‘branches’ that compose the asymptotic spectrum of An; refer again to Remark 1.2 for details and see [32]
for recent findings, concerning the number of spectral branches that characterize the large discretization matrices associated with Galerkin-type approximations of the Laplacian eigenvalue problem −∆u = λu.
At this point, we should say that the knowledge of the symbol f and of its properties is not only interesting in itself, but can also be used for practical purposes. In particular, the symbol can be used either to perform a convergence analysis and predict the behavior of preconditioned Krylov and multigrid methods applied to An, or to design effective preconditioners and multigrid solvers for the associated linear systems.
The reason is clear: the convergence properties of preconditioned Krylov and multigrid methods strongly depend on the spectral features of the matrix to which they are applied. Hence, the spectral information provided by the symbol f can be conveniently used for designing fast solvers of this kind and/or analyzing their convergence properties. In this respect, we recall that recent estimates of the superlinear convergence of the Conjugate Gradient (CG) method are strictly related to the asymptotic spectral distribution of the matrices to which the CG method is applied; see [5].
The purpose of this thesis is to present some specific examples in which the above philosophical discussion comes to life. As our model PDE, we consider classical second-order elliptic differential equations; see (3.1), (4.1) and (5.1) below. Concerning the numerical methods that we employ for their solution, we make three choices: the classicalQpLagrangian Finite Element Method (FEM), the Galerkin Isogeometric Analysis (IgA) based on B-splines, and the IgA Collocation Method based on B-splines. The first method is a classical approximation technique and, consequently, there is not much to say about it: we just refer the reader to the wide literature on the subject (see, e.g., [47, 48, 49, 18, 55]). As for the second two methods, they will be described in Chapters 4 and 5, respectively. However, we anticipate here that both of them are based on the IgA paradigm, whose goal is to improve the connection between numerical simulation of PDE and Computer Aided Design (CAD) systems, the latter being widely employed in Engineering. In its original formulation, the main idea in IgA is to use directly the geometry provided by CAD systems and to approximate the unknown solutions of differential equations by the same type of functions. Tensor-product B-splines and their rational extension, the so-called NURBS, are the dominant technology in CAD systems used in Engineering, and thus also in IgA. The reader is referred to [33, Section 1.2] for a quick overview of the IgA paradigm and to [41, 19] for a detailed introduction to this fascinating subject, which has been developed by T. J. R. Hughes and his research team since 2005 and is now emerging on the international scene.
Despite the specific features of the three mentioned numerical methods, all of them, as well as our elliptic PDE, are linear. As a consequence, the actual computation of the numerical solution un reduces to solving a linear system Anun =fn whose sizedn tends to infinity when the discretization parameter n → ∞. Therefore, we are precisely in the framework described at the beginning, and we may be interested in computing the symbol f characterizing the asymptotic spectrum of the matrices An in the sense (1). This will be done, for the three numerical methods under investigation, in Chapters 3–5, where we will also study the properties of the symbol. After this, in Chapters 6–7, the properties of the symbol will be used in order to design fast iterative solvers for the discretization matrices An associated with the two numerical methods based on IgA (the Galerkin IgA and the IgA Collocation Method). The design of fast iterative solvers for the discretization matrices An associated with the Lagrangian FEM approximation is an harder task, due to the ‘bad’ features of the related symbol, and so it will be the subject of future research.
We now describe in more details the content of Chapters 3–7, which form the core of this thesis.
Nonetheless, Chapters 1–2 are also important. Indeed, Chapter 1 provides the fundamental background that is necessary for understanding the subsequent chapters, while Chapter 2 presents new tools for computing spectral distributions, some of which are used in Chapter 3.
• In Chapter 3, we shall see that the symbolf of the QpLagrangian FEM stiffness matrices approximating the elliptic PDE (3.1) is a (Hermitian) matrix-valued function of the form (2) with s= N(p) := Qdi=1pi, where pi is the polynomial approximation degree in the direction xi; see Section 3.1 for more details.
In particular, this means that the (asymptotic) spectrum of the Lagrangian FEM stiffness matrices is split into N( p) spectral branches (cf. Remark 1.2). We will also study the properties of the symbol f,
