Hierarchical Matrices (eBook)

A Means to Efficiently Solve Elliptic Boundary Value Problems

Mario Bebendorf (Autor)

eBook Download: PDF

2008 | 2008
XVI, 296 Seiten
Springer Berlin (Verlag)
978-3-540-77147-0 (ISBN)

Infos

Hierarchical matrices are an efficient framework for large-scale fully populated matrices arising, e.g., from the finite element discretization of solution operators of elliptic boundary value problems. In addition to storing such matrices, approximations of the usual matrix operations can be computed with logarithmic-linear complexity, which can be exploited to setup approximate preconditioners in an efficient and convenient way. Besides the algorithmic aspects of hierarchical matrices, the main aim of this book is to present their theoretical background.

The book contains the existing approximation theory for elliptic problems including partial differential operators with nonsmooth coefficients. Furthermore, it presents in full detail the adaptive cross approximation method for the efficient treatment of integral operators with non-local kernel functions. The theory is supported by many numerical experiments from real applications.

Inhalt

Preface 6
Acknowledgements 7
Contents 8
Acronyms 11
Introduction 13
Chapter 1 Low-Rank Matrices and Matrix Partitioning 20
1.1 Low-Rank Matrices 20
1.1.1 Efficient Representation 21
1.1.2 Adding and Multiplying Low-Rank Matrices 23
1.1.3 Approximation by Low-Rank Matrices 24
1.1.4 Singular Value Decomposition of Low-Rank Matrices 26
1.1.5 Approximate Addition of Low-Rank Matrices 27
1.1.6 Agglomerating Low-Rank Blocks 29
1.2 Structured Low-Rank Matrices 30
1.3 Admissible Partitions 32
1.3.1 Tensor vs. Hierarchical Partitions 36
1.4 Cluster Trees 40
1.4.1 Construction of Cluster Trees 44
1.4.2 Example: An Easily Analyzed Partition 52
1.5 Block Cluster Trees 54
Chapter 2 Hierarchical Matrices 59
2.1 The Set of Hierarchical Matrices 60
2.2 Matrix-Vector Multiplication 62
2.3 Parallel Matrix-Vector Multiplication 63
2.3.1 Parallelization for Usual Matrices 64
2.3.2 Non-Uniform Block Distributions 65
2.3.3 Numerical Experiments 70
2.4 Blockwise and Global Norms 73
2.5 Adding H -Matrices 75
2.5.1 Preserving Positivity 76
2.6 Coarsening H -Matrices 79
2.7 Multiplying H -Matrices 84
2.7.1 Product Block Cluster Tree 84
2.7.2 Preserving the Original Block Structure 87
2.7.3 Rounded Multiplication 89
2.7.4 Multiplication of Hierarchical and Semi-Separable Matrices 90
2.8 Hierarchical Inversion 93
2.9 Computing the H -Matrix LU Decomposition 95
2.10 Hierarchical QR Decomposition 97
2.11 H 2-Matrices and Fast Multipole Methods 100
2.12 Using Hierarchical Matrices for Preconditioning 102
Chapter 3 Approximation of Discrete Integral Operators 109
3.1 Boundary Integral Formulations 114
3.2 Asymptotic Smoothness of Kernel Functions 119
3.2.1 The Biharmonic Equation 124
3.3 Approximation by Degenerate Kernels 126
3.3.1 Degenerate Kernels through Taylor Expansion 131
3.3.2 Degenerate Kernels through Interpolation 133
3.3.3 Another Kind of Approximation 138
3.3.4 Matrix Approximation Error 144
3.4 Adaptive Cross Approximation (ACA) 149
3.4.1 The Algorithm 150
3.4.2 Error Analysis 152
3.4.3 The Right Choice of Rows 158
3.4.4 Overall Complexity 162
3.4.5 Numerical Experiments 163
3.4.6 Parallelization of ACA 173
3.5 A Recompression Technique for ACA (RACA) 179
3.5.1 Approximation Using Chebyshev Polynomials 182
3.5.2 Evaluation of the Approximation 183
3.5.3 Least Squares Approximation 185
3.5.4 Numerical Results 188
3.6 Preconditioning with Low-Accuracy Approximations 190
3.6.1 Dirichlet Problem 193
3.6.2 Neumann Problem 194
3.6.3 Mixed Boundary Value Problems 197
Chapter 4 Application to Finite Element Discretizations 203
4.1 Approximating FE Matrix Inverses 209
4.1.1 Inverses of Banded Matrices 210
4.1.2 Approximating the Inverse Mass Matrix 214
4.1.3 An Algebraic Approach to the Approximation of the Inverse 216
4.1.4 Degenerate Approximation of the Green’s Function 219
4.1.5 Approximation of Discrete Operators 228
4.1.6 Numerical Experiments 232
4.2 Schur Complements 239
4.3 Hierarchical LU Decomposition 242
4.3.1 Approximating Schur Complements Hierarchically 244
4.3.2 Constructing the Factors LH and UH 246
4.4 Numerical Experiments with the H -Matrix LU Factorization 248
4.4.1 Two-Dimensional Diffusion 249
4.4.2 Convection-Diffusion Problems 254
4.4.3 Three-Dimensional Diffusion 255
4.5 Nested Dissection LU Factorization 258
4.5.1 Matrix Partitioning 259
4.5.2 Approximation of the Factors of the LU Decomposition 260
4.5.3 Numerical Results 263
4.5.4 Parallel Approximate LU Factorization 263
4.6 Solving Nonlinear Problems with Broyden Updates 267
4.6.1 Broyden Updates 270
4.6.2 An Update Method for the LU Decomposition 271
4.6.3 The Influence of Truncation Errors 274
4.6.4 Numerical Experiments 275
References 278
Appendix 289
Index 296

Produkt-Details

• Erscheint lt. Verlag: 25.6.2008
• Reihe/Serie: Lecture Notes in Computational Science and Engineering
• Reihe/Serie: Lecture Notes in Computational Science and Engineering
• Zusatzinfo: XVI, 296 p.
• Verlagsort: Berlin
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Mathematik ► Statistik
• Themenwelt: Mathematik / Informatik ► Mathematik ► Wahrscheinlichkeit / Kombinatorik
• Themenwelt: Technik
• Schlagworte: Approximation • Approximation Theory • Boundary value problem • efficient algorithms in science and engineering • Numerical analysis • partial differential equation • Partial differential equations • Scientific Computing
• ISBN-10: 3-540-77147-6 / 3540771476
• ISBN-13: 978-3-540-77147-0 / 9783540771470