Website Search
Find information on spaces, staff, and services.
Catalog Search
Books
Hierarchical matrices : algorithms and analysis
- Author / Creator
- Available as
- Physical
Details
Checking for availability...
- Creator
- Wolfgang Hackbusch
- Format
- Books
- Language
- English
- Publication
-
- Berlin : Springer, [2015]
- ©2015
- Physical Details
-
- xxv, 511 pages : illustrations ; 25 cm
- ISBNs
- 9783662473238, 3662473232, 9783662473245, 3662473240
- OCLC
- ocn934599847
- Includes bibliographical references (pages 493-502) and index.
- Introductory and preparatory topics -- Introduction -- Numerical linear algebra and its difficulties -- Basic tasks -- large-scale problems -- Exact or approximate computations -- Complexity of algorithms -- Complexity -- Why large-scale problems require (almost) linear complexity -- Basic structures and implementational representations -- Notation of vectors and matrices -- Implementational representations -- Representations and operations -- When is linear complexity attainable? -- Family of diagonal matrices -- Application of the fast fourier transform -- Difficulties in the other cases -- Where do large-scale problems occur? -- Discretisation of elliptic differential equations -- Integral equations and their discretisation -- Ordered and non-ordered index sets -- Index sets -- Vectors ... -- Matrices ... -- About ordering and non-ordering of hierarchical matrices -- Overview of further chapters -- Local rank-r matrices -- Block hierarchy and matrix operations -- Rank-r matrices -- Matrix rank -- Representation and cost -- Operations and their cost -- Best approximation by rank-r matrices -- Best approximation of rank-s matrices by rank-r matrices -- Rank-r matrix addition followed by truncation -- Formatted addition -- Formatted agglomeration -- More than two terms -- Level-wise agglomeration -- Modifications of the rank-r matrix representation -- Akb representation -- Svd representation -- Introductory example -- The model format ... -- Number of blocks -- Storage cost -- Matrix-vector multiplication -- Matrix addition -- Matrix-matrix multiplication -- Matrix inversion -- LU decomposition -- Forward substitution -- Backward substitution -- Cost of the LU decomposition -- Further properties of the model matrices and semiseparability -- Separable expansions and low-rank matrices -- Relation between low-rank submatrices and separable expressions -- Basic terms -- Separable expansions -- Exponential convergence -- Admissibility conditions for x, y -- Polynomial expansions -- Taylor expansion -- Interpolation -- Exponential error estimate -- Asymptotically smooth kernels -- Estimate of the taylor error -- Interpolation error for d = 1 -- Sharpened error estimate -- Interpolation error for d > 1 -- Further separable expansions -- Other interpolation methods -- Transformations -- Piecewise separable expansion -- Kernels depending on x-y -- L-harmonic functions -- Separable expansions via cross approximation -- Optimal separable expansion -- Discretisation of integral operators involving separable kernels -- General setting -- Functionals related to discretisations of integral operators -- Approximation error -- Operator norms -- Matrix norms -- Appropriate norms -- Matrix partition -- Aims -- One-dimensional model example -- Admissible blocks -- Metric of the clusters -- Admissibility -- Generalised admissibility -- Illustration using the example from ʹ5.1.2 -- Cluster tree T(I) -- Definitions -- Example -- Block partition of a vector -- Storage cost for T(I) -- Construction of the cluster tree T(I) -- Necessary data -- Geometry-based construction of T(I) via bounding boxes -- Cardinality-based construction -- Global metric versus geodesic metric -- Implementation and cost -- Evaluation of the admissibility condition -- Block cluster tree T(I x J) -- Level-conserving block cluster tree -- Generalisation of the definition -- Alternative construction of T(I x J) from T(I) and T(J) -- Definition and construction -- Examples -- Alternative block cluster tree constructions -- H-matrices and their arithmetic -- Definition and properties of hierarchical matrices -- The set H(r, P) of hierarchical matrices -- Elementary properties -- Sparsity and storage cost -- Definition -- Storage cost of a hierarchical matrix -- Estimate of csp -- Illustrative example -- First approach -- Estimate in the case of construction (5.23) -- A remark concerning construction (5.27) -- Error estimates -- Frobenius norm -- Preparatory lemmata -- Spectral norm -- Norm ... -- Adaptive determination of the rank -- Recompression techniques -- Compression by ... -- Coarsening of the blocks -- Modifications of the h-matrix approximation -- H-matrices with equations as side conditions -- Positive definiteness -- Positivity of matrices -- Orthogonality of matrices -- Formatted matrix operations for hierarchical matrices -- Truncations and conversions -- Truncations ... -- Agglomeration -- Conversion ... -- Conversion ... between different block cluster trees -- Addition -- Complications of matrix multiplication -- Algorithm in the consistent case -- Algorithm in the level-conserving case -- Recursive algorithm -- Alternative algorithm via domain decomposition -- Newton's method -- Nested iteration -- LU, cholesky, and LDL decomposition -- Format of triangular matrices -- Solution of LU x = b -- Matrix-valued solutions of LX = Z and XU = Z -- Generation of the LU or cholesky decomposition -- UL decomposition of the inverse matrix -- Hadamard product -- Computational cost of the algorithms -- Lu and cholesky decompositions -- H2-matrices -- Notation -- First step : ... -- Second step : ... -- Definition of H2-matrices -- Transfer matrices -- Orthonormalisation -- Projection onto the H2-format -- SVD bases -- Truncation -- Various applications -- Sufficient conditions for nested bases -- General case -- approximation of integral operators by interpolation -- Linear complexity of H2-matrices -- Matrix-vector multiplication by H2-matrices -- Forward transformation -- Multiplication phase -- Back transformation -- Complete algorithm -- Addition and truncation -- Exact addition -- Truncated addition --