The main focus of this work lies in the simulation of the deformation of mechanical components which consist of nonlinear elastic, incompressible material and that are subject to large deformations. Starting from a nonlinear formulation one can derive a discrete problem by using linearisation techniques and an adaptive mixed finite element method. This turns out to be a saddle point problem that can be solved via a Bramble-Pasciak conjugate gradient method. With some modifications the simulation can be improved.

The computation of the Coulomb potentials and forces in charged particle systems under 3d-periodic boundary conditions is possible in an efficient way by utilizing the Ewald summation formulas and applying the fast Fourier transform (FFT). In this paper we consider the particle-particle NFFT (P2NFFT) approach, which is based on the fast Fourier transform for nonequispaced data (NFFT) and compare the error behaviors regarding different window functions, which are used in order to approximate the given continuous charge distribution by a mesh based charge density. While typically B-splines are applied in the scope of particle mesh methods, we consider for the first time also an approximation by Bessel functions. We show how the resulting root mean square errors in the forces can be predicted precisely and efficiently. The results show that if the parameters are tuned appropriately the Bessel window function can keep up with the B-spline window and is in many cases even the better choice with respect to computational costs.

By counting 1's in the "right half" of 2w consecutive rows, we locate the main diagonal of any doubly infinite permutation matrix with bandwidth w. Then the matrix can be correctly centered and factored into block-diagonal permutation matrices. Part II of the paper discusses the same questions for the much larger class of band-dominated matrices. The main diagonal is determined by the Fredholm index of a singly infinite submatrix. Thus the main diagonal is determined "at infinity" in general, but from only 2w rows for banded permutations.

This thesis investigates the numerical simulation of three-dimensional, mechanical deformation problems in the context of large deformations. The main focus lies on the prediction of non-linearly elastic, incompressible material. Based on the equilibrium of forces, we present the weak formulation of the large deformation problem. The discrete version can be derived by using linearisation techniques and an adaptive mixed finite element method. This problem turns out to be a saddle point problem that can, among other methods, be solved via the Bramble-Pasciak conjugate gradient method or the minimal residual algorithm. With some modifications the resulting simulation can be improved but we also address remaining limitations. Some numerical examples show the capability of the final FEM software. In addition, we briefly discuss the special case of linear elasticity with small deformations. Here we directly derive a linear weak formulation with a saddle point structure and apply the adaptive mixed finite element method. It is shown that the presented findings can also be used to treat the nearly incompressible case.

The Mindlin-Reissner plate model is widely used for the elastic deformation simulation of moderately thick plates. Shear locking occurs in the case of thin plates, which means slow convergence with respect to the mesh size. The Kirchhoff plate model does not show locking effects, but is valid only for thin plates. One would like to have a method suitable for both thick and thin plates. Several approaches are known to deal with the shear locking in the Mindlin-Reissner plate model. In addition to the well-known MITC elements and other approaches based on a mixed formulation, hierarchical methods have been developed in the recent years. These are based on the Kirchhoff model and add terms to account for shear deformations. We present some of these methods and develop a new hierarchic plate formulation. This new model can be discretised by a combination of C0 and C1 finite elements. Numerical tests show that the new formulation is locking-free and numerically efficient. We also give an extension of the model to a hierarchical Naghdi shell based on a Koiter shell formulation with unknowns in Cartesian coordinates.

Ill-posed inverse problems with quadratic structure are introduced, studied and solved. As an example an inverse problem appearing in laser optics is solved numerically based on a new regularized inversion algorithm. In addition, the theory of sparsity promoting regularization is extended to situations in which sparsity cannot be expected and also to equations with non-injective operators.

Aufgrund der fundamentalen Bedeutung partieller Differentialgleichungen zur Beschreibung von Phänomenen in angewandten Wissenschaften ist deren Analyse ein Kerngebiet der Mathematik. Durch Computer lassen sich die Lösungen für eine Vielzahl dieser Gleichungen näherungsweise bestimmen. Die dabei verwendeten numerischen Verfahren sollen auf möglichst exakte Approximationen führen und deren Genauigkeit verifizieren. Die Least-Squares Finite-Elemente-Methode (LSFEM) und die unstetige Petrov-Galerkin (DPG) Methode sind solche Verfahren. Sie werden in dieser Dissertation untersucht. Der erste Teil der Arbeit untersucht die Genauigkeit der mittels LSFEM berechneten Näherungen. Dazu werden Eigenschaften der zugrundeliegenden Differentialgleichungen mit den Eigenschaften der LSFEM kombiniert. Dies zeigt, dass die Abweichung der berechneten Näherung von der exakten Lösung einem berechenbaren Residuum asymptotisch entspricht. Ferner wird ein Verfahren zu Berechnung einer garantierten oberen Fehlerschranke eingeführt. Während etablierte Fehlerschätzer den Fehler signifikant überschätzt, zeigen numerische Experimente eine äußerst geringe Überschätzung des Fehlers mittels der neuen Fehlerschranke. Die Analyse der Fehlerschranken für das Stokes-Problem offenbart ein Beziehung der LSFEM und der LBB Konstanten. Diese Konstante ist entscheidend für die Existenz und Stabilität von Lösungen in der Strömungslehre. Der zweite Teil der Arbeit nutzt diese Beziehung und entwickelt ein auf der LSFEM basierendes Verfahren zur numerischen Berechnung der LBB Konstanten. Der dritte Teil der Arbeit untersucht die DPG Methode. Dabei werden existierende Anwendungen der DPG Methode zusammengefasst und analysiert. Diese Analyse zeigt, dass sich die DPG Methode als eine leicht gestörte LSFEM interpretieren lässt. Diese Interpretation erlaubt die Anwendung der Resultate aus dem ersten Teil der Arbeit und ermöglicht dadurch eine genauere Untersuchung existierender und die Entwicklung neuer DPG Methoden. / The analysis of partial differential equations is a core area in mathematics due to the fundamental role of partial differential equations in the description of phenomena in applied sciences. Computers can approximate the solutions to these equations for many problems. They use numerical schemes which should provide good approximations and verify the accuracy. The least-squares finite element method (LSFEM) and the discontinuous Petrov-Galerkin (DPG) method satisfy these requirements. This thesis investigates these two schemes. The first part of this thesis explores the accuracy of solutions to the LSFEM. It combines properties of the underlying partial differential equation with properties of the LSFEM and so proves the asymptotic equality of the error and a computable residual. Moreover, this thesis introduces an novel scheme for the computation of guaranteed upper error bounds. While the established error estimator leads to a significant overestimation of the error, numerical experiments indicate a tiny overestimation with the novel bound. The investigation of error bounds for the Stokes problem visualizes a relation of the LSFEM and the Ladyzhenskaya-Babuška-Brezzi (LBB) constant. This constant is a key in the existence and stability of solution to problems in fluid dynamics. The second part of this thesis utilizes this relation to design a competitive numerical scheme for the computation of the LBB constant. The third part of this thesis investigates the DPG method. It analyses an abstract framework which compiles existing applications of the DPG method. The analysis relates the DPG method with a slightly perturbed LSFEM. Hence, the results from the first part of this thesis extend to the DPG method. This enables a precise investigation of existing and the design of novel DPG schemes.

This thesis is on the numerical computation of eigenvalues of symmetric hierarchical matrices. The numerical algorithms used for this computation are derivations of the LR Cholesky algorithm, the preconditioned inverse iteration, and a bisection method based on LDLT factorizations. The investigation of QR decompositions for H-matrices leads to a new QR decomposition. It has some properties that are superior to the existing ones, which is shown by experiments using the HQR decompositions to build a QR (eigenvalue) algorithm for H-matrices does not progress to a more efficient algorithm than the LR Cholesky algorithm. The implementation of the LR Cholesky algorithm for hierarchical matrices together with deflation and shift strategies yields an algorithm that require O(n) iterations to find all eigenvalues. Unfortunately, the local ranks of the iterates show a strong growth in the first steps. These H-fill-ins makes the computation expensive, so that O(n³) flops and O(n²) storage are required. Theorem 4.3.1 explains this behavior and shows that the LR Cholesky algorithm is efficient for the simple structured Hl-matrices. There is an exact LDLT factorization for Hl-matrices and an approximate LDLT factorization for H-matrices in linear-polylogarithmic complexity. This factorizations can be used to compute the inertia of an H-matrix. With the knowledge of the inertia for arbitrary shifts, one can compute an eigenvalue by bisectioning. The slicing the spectrum algorithm can compute all eigenvalues of an Hl-matrix in linear-polylogarithmic complexity. A single eigenvalue can be computed in O(k²n log^4 n). Since the LDLT factorization for general H-matrices is only approximative, the accuracy of the LDLT slicing algorithm is limited. The local ranks of the LDLT factorization for indefinite matrices are generally unknown, so that there is no statement on the complexity of the algorithm besides the numerical results in Table 5.7. The preconditioned inverse iteration computes the smallest eigenvalue and the corresponding eigenvector. This method is efficient, since the number of iterations is independent of the matrix dimension. If other eigenvalues than the smallest are searched, then preconditioned inverse iteration can not be simply applied to the shifted matrix, since positive definiteness is necessary. The squared and shifted matrix (M-mu I)² is positive definite. Inner eigenvalues can be computed by the combination of folded spectrum method and PINVIT. Numerical experiments show that the approximate inversion of (M-mu I)² is more expensive than the approximate inversion of M, so that the computation of the inner eigenvalues is more expensive. We compare the different eigenvalue algorithms. The preconditioned inverse iteration for hierarchical matrices is better than the LDLT slicing algorithm for the computation of the smallest eigenvalues, especially if the inverse is already available. The computation of inner eigenvalues with the folded spectrum method and preconditioned inverse iteration is more expensive. The LDLT slicing algorithm is competitive to H-PINVIT for the computation of inner eigenvalues. In the case of large, sparse matrices, specially tailored algorithms for sparse matrices, like the MATLAB function eigs, are more efficient. If one wants to compute all eigenvalues, then the LDLT slicing algorithm seems to be better than the LR Cholesky algorithm. If the matrix is small enough to be handled in dense arithmetic (and is not an Hl(1)-matrix), then dense eigensolvers, like the LAPACK function dsyev, are superior. The H-PINVIT and the LDLT slicing algorithm require only an almost linear amount of storage. They can handle larger matrices than eigenvalue algorithms for dense matrices. For Hl-matrices of local rank 1, the LDLT slicing algorithm and the LR Cholesky algorithm need almost the same time for the computation of all eigenvalues. For large matrices, both algorithms are faster than the dense LAPACK function dsyev.:List of Figures xi List of Tables xiii List of Algorithms xv List of Acronyms xvii List of Symbols xix Publications xxi 1 Introduction 1 1.1 Notation 2 1.2 Structure of this Thesis 3 2 Basics 5 2.1 Linear Algebra and Eigenvalues 6 2.1.1 The Eigenvalue Problem 7 2.1.2 Dense Matrix Algorithms 9 2.2 Integral Operators and Integral Equations 14 2.2.1 Definitions 14 2.2.2 Example - BEM 16 2.3 Introduction to Hierarchical Arithmetic 17 2.3.1 Main Idea 17 2.3.2 Definitions 19 2.3.3 Hierarchical Arithmetic 24 2.3.4 Simple Hierarchical Matrices (Hl-Matrices) 30 2.4 Examples 33 2.4.1 FEM Example 33 2.4.2 BEM Example 36 2.4.3 Randomly Generated Examples 37 2.4.4 Application Based Examples 38 2.4.5 One-Dimensional Integral Equation 38 2.5 Related Matrix Formats 39 2.5.1 H2-Matrices 40 2.5.2 Diagonal plus Semiseparable Matrices 40 2.5.3 Hierarchically Semiseparable Matrices 42 2.6 Review of Existing Eigenvalue Algorithms 44 2.6.1 Projection Method 44 2.6.2 Divide-and-Conquer for Hl(1)-Matrices 45 2.6.3 Transforming Hierarchical into Semiseparable Matrices 46 2.7 Compute Cluster Otto 47 3 QR Decomposition of Hierarchical Matrices 49 3.1 Introduction 49 3.2 Review of Known QR Decompositions for H-Matrices 50 3.2.1 Lintner’s H-QR Decomposition 50 3.2.2 Bebendorf’s H-QR Decomposition 52 3.3 A new Method for Computing the H-QR Decomposition 54 3.3.1 Leaf Block-Column 54 3.3.2 Non-Leaf Block Column 56 3.3.3 Complexity 57 3.3.4 Orthogonality 60 3.3.5 Comparison to QR Decompositions for Sparse Matrices 61 3.4 Numerical Results 62 3.4.1 Lintner’s H-QR decomposition 62 3.4.2 Bebendorf’s H-QR decomposition 66 3.4.3 The new H-QR decomposition 66 3.5 Conclusions 67 4 QR-like Algorithms for Hierarchical Matrices 69 4.1 Introduction 70 4.1.1 LR Cholesky Algorithm 70 4.1.2 QR Algorithm 70 4.1.3 Complexity 71 4.2 LR Cholesky Algorithm for Hierarchical Matrices 72 4.2.1 Algorithm 72 4.2.2 Shift Strategy 72 4.2.3 Deflation 73 4.2.4 Numerical Results 73 4.3 LR Cholesky Algorithm for Diagonal plus Semiseparable Matrices 75 4.3.1 Theorem 75 4.3.2 Application to Tridiagonal and Band Matrices 79 4.3.3 Application to Matrices with Rank Structure 79 4.3.4 Application to H-Matrices 80 4.3.5 Application to Hl-Matrices 82 4.3.6 Application to H2-Matrices 83 4.4 Numerical Examples 84 4.5 The Unsymmetric Case 84 4.6 Conclusions 88 5 Slicing the Spectrum of Hierarchical Matrices 89 5.1 Introduction 89 5.2 Slicing the Spectrum by LDLT Factorization 91 5.2.1 The Function nu(M − µI) 91 5.2.2 LDLT Factorization of Hl-Matrices 92 5.2.3 Start-Interval [a, b] 96 5.2.4 Complexity 96 5.3 Numerical Results 97 5.4 Possible Extensions 100 5.4.1 LDLT Slicing Algorithm for HSS Matrices 103 5.4.2 LDLT Slicing Algorithm for H-Matrices 103 5.4.3 Parallelization 105 5.4.4 Eigenvectors 107 5.5 Conclusions 107 6 Computing Eigenvalues by Vector Iterations 109 6.1 Power Iteration 109 6.1.1 Power Iteration for Hierarchical Matrices 110 6.1.2 Inverse Iteration 111 6.2 Preconditioned Inverse Iteration for Hierarchical Matrices 111 6.2.1 Preconditioned Inverse Iteration 113 6.2.2 The Approximate Inverse of an H-Matrix 115 6.2.3 The Approximate Cholesky Decomposition of an H-Matrix 116 6.2.4 PINVIT for H-Matrices 117 6.2.5 The Interior of the Spectrum 120 6.2.6 Numerical Results 123 6.2.7 Conclusions 130 7 Comparison of the Algorithms and Numerical Results 133 7.1 Theoretical Comparison 133 7.2 Numerical Comparison 135 8 Conclusions 141 Theses 143 Bibliography 145 Index 153

We describe an implementation of a multi-threaded NFFT (nonequispaced fast Fourier transform) software library and present the used parallelization approaches. Besides the NFFT kernel, the NFFT on the two-sphere and the fast summation based on NFFT are also parallelized. Thereby, the parallelization is based on OpenMP and the multi-threaded FFTW library. Furthermore, benchmarks for various cases are performed. The results show that an efficiency higher than 0.50 and up to 0.79 can still be achieved at 12 threads.

In this paper we describe a parallel algorithm for calculating nonequispaced fast Fourier transforms on massively parallel distributed memory architectures. These algorithms are implemented in an open source software library called PNFFT. Furthermore, we derive a parallel fast algorithm for the computation of the Coulomb potentials and forces in a charged particle system, which is based on the parallel nonequispaced fast Fourier transform. To prove the high scalability of our algorithms we provide performance results on a BlueGene/P system using up to 65536 cores.