Hierarchical Matrices: A Means to Efficiently Solve Elliptic Boundary Value Problems

Front Cover
Springer Science & Business Media, Jun 25, 2008 - Mathematics - 296 pages
0 Reviews

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.

 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

34 Adaptive Cross Approximation ACA
139
341 The Algorithm
140
342 Error Analysis
142
343 The Right Choice of Rows
148
344 Overall Complexity
152
345 Numerical Experiments
153
346 Parallelization of ACA
163
35 A Recompression Technique for ACA RACA
169

13 Admissible Partitions
21
131 Tensor vs Hierarchical Partitions
25
14 Cluster Trees
29
141 Construction of Cluster Trees
33
An Easily Analyzed Partition
41
15 Block Cluster Trees
43
Hierarchical Matrices
49
21 The Set of Hierarchical Matrices
50
22 MatrixVector Multiplication
52
23 Parallel MatrixVector Multiplication
53
231 Parallelization for Usual Matrices
54
232 NonUniform Block Distributions
55
233 Numerical Experiments
60
24 Blockwise and Global Norms
63
25 Adding HMatrices
65
251 Preserving Positivity
66
26 Coarsening HMatrices
69
27 Multiplying HMatrices
74
272 Preserving the Original Block Structure
77
273 Rounded Multiplication
79
274 Multiplication of Hierarchical and SemiSeparable Matrices
80
28 Hierarchical Inversion
83
29 Computing the HMatrix LU Decomposition
85
210 Hierarchical QR Decomposition
87
211 H˛Matrices and Fast Multipole Methods
90
212 Using Hierarchical Matrices for Preconditioning
92
2121 Hermitian Positive Definite Coefficient Matrices
94
2122 NonHermitian Coefficient Matrices
97
Approximation of Discrete Integral Operators
99
31 Boundary Integral Formulations
104
32 Asymptotic Smoothness of Kernel Functions
109
321 The Biharmonic Equation
114
33 Approximation by Degenerate Kernels
116
331 Degenerate Kernels through Taylor Expansion
121
332 Degenerate Kernels through Interpolation
123
333 Another Kind of Approximation
128
334 Matrix Approximation Error
134
357 Approximation Using Chebyshev Polynomials
172
352 Evaluation of the Approximation
173
353 Least Squares Approximation
175
354 Numerical Results
178
36 Preconditioning with LowAccuracy Approximations
180
362 Neumann Problem
184
363 Mixed Boundary Value Problems
187
Application to Finite Element Discretizations
193
41 Approximating FE Matrix Inverses
199
411 Inverses of Banded Matrices
200
412 Approximating the Inverse Mass Matrix
204
413 An Algebraic Approach to the Approximation of the Inverse
206
414 Degenerate Approximation of the Greens Function
209
415 Approximation of Discrete Operators
218
416 Numerical Experiments
222
42 Schur Complements
229
43 Hierarchical LU Decomposition
232
431 Approximating Schur Complements Hierarchically
234
432 Constructing the Factors LH and UH
236
44 Numerical Experiments with the HMatrix LU Factorization
238
441 TwoDimensional Diffusion
239
442 ConvectionDiffusion Problems
244
443 ThreeDimensional Diffusion
245
45 Nested Dissection LU Factorization
248
451 Matrix Partitioning
249
452 Approximation of the Factors of the LU Decomposition
250
453 Numerical Results
253
46 Solving Nonlinear Problems with Broyden Updates
257
461 Broyden Updates
260
462 An Update Method for the LU Decomposition
261
463 The Influence of Truncation Errors
264
464 Numerical Experiments
265
References
269
Appendix
281
Index
289
Copyright

Other editions - View all

Common terms and phrases

Popular passages

Page 272 - JE Dennis, Jr. and Robert B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations Richard E.

Bibliographic information