The work consists of two parts. In the first part which is concerned with random walks, we construct the conditional versions of a multidimensional random walk given that it does not leave the Weyl chambers of type C and of type D, respectively, in terms of a Doob h-transform. Furthermore, we prove functional limit theorems for the rescaled random walks. This is an extension of recent work by Eichelsbacher and Koenig who studied the analogous conditioning for the Weyl chamber of type A. Our proof follows recent work by Denisov and Wachtel who used martingale properties and a strong approximation of random walks by Brownian motion. Therefore, we are able to keep minimal moment assumptions. Finally, we present an alternate function that is amenable to an h-transform in the Weyl chamber of type C. In the second part which is concerned with Brownian motion, we examine the non-exit probability of a multidimensional Brownian motion from a growing truncated Weyl chamber. Different regimes are identified according to the growth speed, ranging from polynomial decay over stretched-exponential to exponential decay. Furthermore we derive associated large deviation principles for the empirical measure of the properly rescaled and transformed Brownian motion as the dimension grows to infinity. Our main tool is an explicit eigenvalue expansion for the transition probabilities before exiting the truncated Weyl chamber.

For noiseless sampled data, we describe the close connections between Prony--like methods, namely the classical Prony method, the matrix pencil method and the ESPRIT method. Further we present a new efficient algorithm of matrix pencil factorization based on QR decomposition of a rectangular Hankel matrix. The algorithms of parameter estimation are also applied to sparse Fourier approximation and nonlinear approximation.

Ce travail s’intéresse à l’étude d’un système de pompage turbinage à vitesse variable avec une machine asynchrone doublement alimentée face aux perturbations de réseau électrique. L’objectif est d’assurer la continuité de service de cet élément stabilisateur de réseau électrique de sorte qu’il reste connecté au réseau même en cas de perturbations. Le contrôle du système dans les différentes phases de fonctionnement en mode sain a été tout d’abord développé ainsi qu'une étude de stabilité de système utilisant l’analyse modale. Les différents outils nécessaires pour cette analyse ont été tout d’abord mis en oeuvre. Ensuite, les limites de stabilité du système ont été étudiées tenant compte de la variation de longueur de ligne. Le comportement du système en présence des défauts a été par la suite étudié. Les défauts de réseau considérés sont les défauts symétriques et les défauts asymétriques. Une solution basée sur la modification de la stratégie de contrôle a été adoptée pour le cas des défauts symétriques et une solution basée sur l’ajout d’éléments au circuit de puissance a été adoptée pour les cas des défauts asymétriques. Un dispositif expérimental de 4kW a été mis en oeuvre pour la validation des développements menés dans le cadre de cette thèse. / This work focuses on the study of a variable speed pumped storage system based on a doubly fed induction machine in case of grid disturbances. Thus the main objective is to improve the fault ride through capabilities of this grid stabilizer and to guarantee its connection with the grid even under disturbances. The system control in the different operating phases in healthy conditions is developed and then a system stability study is conducted using the eigenvalue analysis. The system stability limits have been investigated taking into account the variation of grid line length so the grid impedance variation. Then the system behavior under disturbances is analyzed. Theconsidered grid faults are symmetric and asymmetric faults. The investigated fault ride through capabilities of the pumped storage system consist of two solutions, one based on the modification of the control strategy was adopted for the symmetric faults and one based on hardware modification has been adopted for the asymmetric ones. A 4kW laboratory set-up has been developed for experimental validation.

Comme la puissance de calcul des systèmes de calcul haute performance continue de croître, en utilisant un grand nombre de cœurs CPU ou d’unités de calcul spécialisées, les applications hautes performances destinées à la résolution des problèmes de très grande échelle sont de plus en plus sujettes à des pannes. En conséquence, la communauté de calcul haute performance a proposé de nombreuses contributions pour concevoir des applications tolérantes aux pannes. Cette étude porte sur une nouvelle classe d’algorithmes numériques de tolérance aux pannes au niveau de l’application qui ne nécessite pas de ressources supplémentaires, à savoir, des unités de calcul ou du temps de calcul additionnel, en l’absence de pannes. En supposant qu’un mécanisme distinct assure la détection des pannes, nous proposons des algorithmes numériques pour extraire des informations pertinentes à partir des données disponibles après une pannes. Après l’extraction de données, les données critiques manquantes sont régénérées grâce à des stratégies d’interpolation pour constituer des informations pertinentes pour redémarrer numériquement l’algorithme. Nous avons conçu ces méthodes appelées techniques d’Interpolation-restart pour des problèmes d’algèbre linéaire numérique tels que la résolution de systèmes linéaires ou des problèmes aux valeurs propres qui sont indispensables dans de nombreux noyaux scientifiques et applications d’ingénierie. La résolution de ces problèmes est souvent la partie dominante; en termes de temps de calcul, des applications scientifiques. Dans le cadre solveurs linéaires du sous-espace de Krylov, les entrées perdues de l’itération sont interpolées en utilisant les entrées disponibles sur les nœuds encore disponibles pour définir une nouvelle estimation de la solution initiale avant de redémarrer la méthode de Krylov. En particulier, nous considérons deux politiques d’interpolation qui préservent les propriétés numériques clés de solveurs linéaires bien connus, à savoir la décroissance monotone de la norme-A de l’erreur du gradient conjugué ou la décroissance monotone de la norme résiduelle de GMRES. Nous avons évalué l’impact du taux de pannes et l’impact de la quantité de données perdues sur la robustesse des stratégies de résilience conçues. Les expériences ont montré que nos stratégies numériques sont robustes même en présence de grandes fréquences de pannes, et de perte de grand volume de données. Dans le but de concevoir des solveurs résilients de résolution de problèmes aux valeurs propres, nous avons modifié les stratégies d’interpolation conçues pour les systèmes linéaires. Nous avons revisité les méthodes itératives de l’état de l’art pour la résolution des problèmes de valeurs propres creux à la lumière des stratégies d’Interpolation-restart. Pour chaque méthode considérée, nous avons adapté les stratégies d’Interpolation-restart pour régénérer autant d’informations spectrale que possible. Afin d’évaluer la performance de nos stratégies numériques, nous avons considéré un solveur parallèle hybride (direct/itérative) pleinement fonctionnel nommé MaPHyS pour la résolution des systèmes linéaires creux, et nous proposons des solutions numériques pour concevoir une version tolérante aux pannes du solveur. Le solveur étant hybride, nous nous concentrons dans cette étude sur l’étape de résolution itérative, qui est souvent l’étape dominante dans la pratique. Les solutions numériques proposées comportent deux volets. A chaque fois que cela est possible, nous exploitons la redondance de données entre les processus du solveur pour effectuer une régénération exacte des données en faisant des copies astucieuses dans les processus. D’autre part, les données perdues qui ne sont plus disponibles sur aucun processus sont régénérées grâce à un mécanisme d’interpolation. / As the computational power of high performance computing (HPC) systems continues to increase by using huge number of cores or specialized processing units, HPC applications are increasingly prone to faults. This study covers a new class of numerical fault tolerance algorithms at application level that does not require extra resources, i.e., computational unit or computing time, when no fault occurs. Assuming that a separate mechanism ensures fault detection, we propose numerical algorithms to extract relevant information from available data after a fault. After data extraction, well chosen part of missing data is regenerated through interpolation strategies to constitute meaningful inputs to numerically restart the algorithm. We have designed these methods called Interpolation-restart techniques for numerical linear algebra problems such as the solution of linear systems or eigen-problems that are the inner most numerical kernels in many scientific and engineering applications and also often ones of the most time consuming parts. In the framework of Krylov subspace linear solvers the lost entries of the iterate are interpolated using the available entries on the still alive nodes to define a new initial guess before restarting the Krylov method. In particular, we consider two interpolation policies that preserve key numerical properties of well-known linear solvers, namely the monotony decrease of the A-norm of the error of the conjugate gradient or the residual norm decrease of GMRES. We assess the impact of the fault rate and the amount of lost data on the robustness of the resulting linear solvers.For eigensolvers, we revisited state-of-the-art methods for solving large sparse eigenvalue problems namely the Arnoldi methods, subspace iteration methods and the Jacobi-Davidson method, in the light of Interpolation-restart strategies. For each considered eigensolver, we adapted the Interpolation-restart strategies to regenerate as much spectral information as possible. Through intensive experiments, we illustrate the qualitative numerical behavior of the resulting schemes when the number of faults and the amount of lost data are varied; and we demonstrate that they exhibit a numerical robustness close to that of fault-free calculations. In order to assess the efficiency of our numerical strategies, we have consideredan actual fully-featured parallel sparse hybrid (direct/iterative) linear solver, MaPHyS, and we proposed numerical remedies to design a resilient version of the solver. The solver being hybrid, we focus in this study on the iterative solution step, which is often the dominant step in practice. The numerical remedies we propose are twofold. Whenever possible, we exploit the natural data redundancy between processes from the solver toperform an exact recovery through clever copies over processes. Otherwise, data that has been lost and is not available anymore on any process is recovered through Interpolationrestart strategies. These numerical remedies have been implemented in the MaPHyS parallel solver so that we can assess their efficiency on a large number of processing units (up to 12; 288 CPU cores) for solving large-scale real-life problems.

This thesis considers the hydrodynamic instability and optimal forcing of a number of incompressible flow cases. In the first part, the instabilities of three problems that are of great interest in energy and aerospace applications are studied, namely a Blasius boundary layer subject to localized wall-suction, a Falkner–Skan–Cooke boundary layer with a localized surface roughness, and a pair of helical vortices. The two boundary layer flows are studied through spectral element simulations and eigenvalue computations, which enable their long-term behavior as well as the mechanisms causing transition to be determined. The emergence of transition in these cases is found to originate from a linear flow instability, but whereas the onset of this instability in the Blasius flow can be associated with a localized region in the vicinity of the suction orifice, the instability in the Falkner–Skan–Cooke flow involves the entire flow field. Due to this difference, the results of the eigenvalue analysis in the former case are found to be robust with respect to numerical parameters and domain size, whereas the results in the latter case exhibit an extreme sensitivity that prevents domain independent critical parameters from being determined. The instability of the two helices is primarily addressed through experiments and analytic theory. It is shown that the well known pairing instability of neighboring vortex filaments is responsible for transition, and careful measurements enable growth rates of the instabilities to be obtained that are in close agreement with theoretical predictions. Using the experimental baseflow data, a successful attempt is subsequently also made to reproduce this experiment numerically. In the second part of the thesis, a novel method for computing the optimal forcing of a dynamical system is developed. The method is based on an application of the inverse power method preconditioned by the Laplace preconditioner to the direct and adjoint resolvent operators. The method is analyzed for the Ginzburg–Landau equation and afterwards the Navier–Stokes equations, where it is implemented in the spectral element method and validated on the two-dimensional lid-driven cavity flow and the flow around a cylinder. / <p>QC 20171124</p>

Dans tout ce qui suit, nous considérons une variété riemannienne compacte de dimension au moins égale à 2. A tout domaine (suffisamment régulier) , on peut associer la première valeur propre ?Ù de l’opérateur de Laplace-Beltrami avec condition de Dirichlet au bord. Nous dirons qu’un domaine est extrémal (sous entendu, pour la première valeur propre de l’opérateur de Laplace-Beltrami) si est un point critique de la fonctionnelle Ù? ?O sous une contrainte de volume V ol(Ù) = c0. Autrement dit, est extrémal si, pour toute famille régulière {Ot}te (-t0,t0) de domaines de volume constant, telle que Ù 0 = Ù, la dérivée de la fonction t ? ?Ot en 0 est nulle. Rappelons que les domaines extrémaux sont caractérisés par le fait que la fonction propre, associée à la première valeur propre sur le domaine avec condition de Dirichlet au bord, a une donnée de Neumann constante au bord. Ce résultat a été démontré par A. El Soufi et S. Ilias en 2007. Les domaines extrémaux sont donc des domaines sur lesquels peut être résolu un problème elliptique surdéterminé. L’objectif principal de cette thèse est la construction de domaines extrémaux pour la première valeur propre de l’opérateur de Laplace-Beltrami avec condition de Dirichlet au bord. Nous donnons des résultats d’existence de domaines extrémaux dans le cas de petits volumes ou bien dans le cas de volumes proches du volume de la variété. Nos résultats permettent ainsi de donner de nouveaux exemples non triviaux de domaines extrémaux. Le premier résultat que nous avons obtenu affirme que si une variété admet un point critique non dégénéré de la courbure scalaire, alors pour tout volume petit il existe un domaine extrémal qui peut être construit en perturbant une boule géodésique centrée en ce point critique non dégénéré de la courbure scalaire. La méthode que nous utilisons pour construire ces domaines extrémaux revient à étudier l’opérateur (non linéaire) qui à un domaine associe la donnée de Neumann de la première fonction propre de l’opérateur de Laplace-Beltrami sur le domaine. Il s’agit d’un opérateur (hautement non linéaire), nonlocal, elliptique d’ordre 1. Dans Rn × R/Z, le domaine cylindrique Br × R/Z, o`u Br est la boule de rayon r > 0 dans Rn, est un domaine extrémal. En étudiant le linéarisé de l’opérateur elliptique du premier ordre défini par le problème précédent et en utilisant un résultat de bifurcation, nous avons démontré l’existence de domaines extrémaux nontriviaux dans Rn × R/Z. Ces nouveaux domaines extrémaux sont proches de domaines cylindriques Br × R/Z. S’ils sont invariants par rotation autour de l’axe vertical, ces domaines ne sont plus invariants par translations verticales. Ce deuxi`eme r´esultat donne un contre-exemple à une conjecture de Berestycki, Caffarelli et Nirenberg énoncée en 1997. Pour de grands volumes la construction de domaines extrémaux est techniquement plus difficile et fait apparaître des phénomènes nouveaux. Dans ce cadre, nous avons dû distinguer deux cas selon que la première fonction propre Ø0 de l’opérateur de Laplace-Beltrami sur la variété est constante ou non. Les résultats que nous avons obtenus sont les suivants : 1. Si Ø0 a des points critiques non dégénérés (donc en particulier n’est pas constante), alors pour tout volume assez proche du volume de la variété, il existe un domaine extrémal obtenu en perturbant le complément d’une boule géodésique centrée en un des points critiques non dégénérés de Ø0. 2. Si Ø0 est constante et la variété admet des points critiques non dégénérés de la courbure scalaire, alors pour tout volume assez proche du volume de la variété il existe un domaine extrémal obtenu en perturbant le complément d’une boule géodésique centrée en un des points critiques non dégénérés de la courbure scalaire / In what follows, we will consider a compact Riemannian manifold whose dimension is at least 2. Let Ù be a (smooth enough) domain and ?O the first eigenvalue of the Laplace-Beltrami operator on Ù with 0 Dirichlet boundary condition. We say that Ù is extremal (for the first eigenvalue of the Laplace-Beltrami operator) if is a critical point for the functional Ù? ?O with respect to variations of the domain which preserve its volume. In other words, Ù is extremal if, for all smooth family of domains { Ù t}te(-t0,t0) whose volume is equal to a constant c0, and Ù 0 = Ù, the derivative of the function t ? ?Ot computed at t = 0 is equal to 0. We recall that an extremal domain is characterized by the fact that the eigenfunction associated to the first eigenvalue of the Laplace-Beltrami operator over the domain with 0 Dirichlet boundary condition, has constant Neumann data at the boundary. This result has been proved by A. El Soufi and S. Ilias in 2007. Extremal domains are then domains over which can be solved an elliptic overdeterminated problem. The main aim of this thesis is the construction of extremal domains for the first eigenvalue of the Laplace-Beltrami operator with 0 Dirichlet boundary condition. We give some existence results of extremal domains in the cases of small volume or volume closed to the volume of the manifold. Our results allow also to construct some new nontrivial exemples of extremal domains. The first result we obtained states that if the manifold has a nondegenerate critical point of the scalar curvature, then, given a fixed volume small enough, there exists an extremal domain that can be constructed by perturbation of a geodesic ball centered in that nondegenerated critical point of the scalar curvature. The methode used is based on the study of the operator that to a given domain associes the Neumann data of the first eigenfunction of the Laplace-Beltrami operator over the domain. It is a highly nonlinear, non local, elliptic first order operator. In Rn × R/Z, the circular-cylinder-type domain Br × R/Z, where Br is the ball of radius r > 0 in Rn, is an extremal domain. By studying the linearized of the elliptic first order operator defined in the previous problem, and using some bifurcation results, we prove the existence of nontrivial extremal domains in Rn × R/Z. Such extremal domains are closed to the circular-cylinder-type domains Br × R/Z. If they are invariant by rotation with respect to the vertical axe, they are not invariant by vertical translations. This second result gives a counterexemple to a conjecture of Berestycki, Caffarelli and Nirenberg stated in 1997. For big volumes the construction of extremal domains is technically more difficult and shows some new phenomena. In this context, we had to distinguish two cases, according to the fact that the first eigenfunction Ø0 of the Laplace-Beltrami operator over the manifold is constant or not. The results obtained are the following : 1. If Ø0 has a nondegenerated critical point (in particular it is not constant), then, given a fixed volume closed to the volume of the manifold, there exists an extremal domain obtained by perturbation of the complement of a geodesic ball centered in a nondegenerated critical point of Ø0. 2. If Ø0 is constant and the manifold has some nondegenerate critical points of the scalar curvature, then, for a given fixed volume closed to the volume of the manifold, there exists an extremal domain obtained by perturbation of the complement of a geodesic ball centered in a nondegenerate critical point of the scalar curvature

El análisis y el control de las vibraciones cobra especial importancia en muchas ramas de la ingeniería, en especial la ingeniería mecánica, civil, aeronáutica y automovilística. Tal es así que prácticamente se identi¿ca como un área independiente dentro del análisis dinámico de estructuras. Desde los comienzos de esta teoría, las fuerzas disipativas o de amortiguamiento han sido uno de los fenómenos más difíciles de modelizar. El modelo viscoso, por su sencillez y versatilidad ha sido y sigue siendo el gran paradigma de los modelos de amortiguamiento. Sin embargo, como consecuencia de la aparición de materiales con memoria se introdujo el fenómeno de la viscoelasticidad; Esta, si bien está también 'íntimamente ligada ' a la velocidad de la respuesta, necesito de la introducción de las denominadas funciones hereditarias, que permiten poner a las fuerzas disipativas como función no solo de la velocidad instantánea sino de la historia de velocidades desde el comienzo del movimiento, de ahí el termino memoria. De forma natural, el avance teórico introducido en el modelo supone también una complicación computacional, pues donde antes teníamos un sistema lineal de ecuaciones diferenciales ahora tenemos un sistema de ecuaciones integro-diferenciales. El análisis de las vibraciones libres de los sistemas con amortiguamiento viscoelástico conduce a un problema nolineal de autovalores donde la característica principal es una matriz de amortiguamiento que depende de la frecuencia de excitación. El estudio de la solución de autovalores y autovectores de este problema es importante si se desean conocer los modos de vibración de la estructura o si se pretende obtener la respuesta en el dominio de la frecuencia del sistema. El objetivo fundamental de esta Tesis Doctoral es doble: Por un lado, profundizar en el conocimiento del problema de autovalores de sistemas viscoelásticos proponiendo para ello nuevos métodos numéricos de resolución. Por otro, desarrollar un nuevo modelo viscoso que, bajo ciertas condiciones, reproduzca la respuesta del modelo viscoelástico con su¿ciente aproximación. La Tesis se divide en ocho capítulos, de ellos el cuerpo principal se encuentra en los seis centrales (Capítulos 2 a 7. Todos ellos son artículos de investigación que, o bien han sido publicados, o bien están en proceso de revisión en revistas contenidas en el Journal Citation Reports (JCR). Por esta razón, todos los capítulos conservan la estructura intrínseca de un artículo, incluidas una introducción y una bibliografía en cada uno. Los cuatro primeros capítulos (Capítulos 2 a 5) se centran en el estudio del problema no lineal de autovalores. Se proponen dos metodologías de resolución: la primera es un procedimiento iterativo basado en el esquema del punto-¿jo y desarrollado para sistemas proporcionales o ligeramente no-proporcionales (aquellos en los que los modos se presentan desacoplados o casi desacoplados). La segunda metodología (presentada en dos capítulos diferentes), denominada paramétrica, permite obtener soluciones casi-analíticas de los autovalores, tanto para sistemas de un grado de libertad como para sistemas de múltiples grados de libertad y dentro de 'estos, para sistemas proporcionales y no proporcionales. El estudio del problema de autovalores se completa con un capítulo dedicado a los autovalores reales, también denominados autovalores no viscosos. En 'él se demuestra una nueva caracterización maten ática que deben cumplir dichos autovalores y que permite proponer un nuevo concepto: el conjunto no-viscoso. Los dos 'últimos capítulos (Capítulos 6 y 7) analizan el Modelo Viscoso Equivalente como propuesta para la modelización de la respuesta de sistemas viscoelásticos. El análisis se realiza desde el dominio de la frecuencia estudiando la función de transferencia. En una primera etapa (pen último capítulo), de naturaleza más maten ática, se demuestra que la función de transferencia exacta de un modelo viscoelástico se puede expresar como suma de una función de transferencia propia de un modelo viscoso más un término denominado residual, directamente dependiente del nivel de amortiguamiento inducido y del acoplamiento modal (noproporcionalidad de la matriz de amortiguamiento). En una segunda etapa ('ultimo capítulo), se desarrolla una aplicación para estructuras reales formadas por entramados planos de elementos 1D amortiguados con capas de material visco elástico. Este tipo de estructuras ha permitido usar una variante mejorada del método paramétrico para la obtención de los autovalores, de forma que en este 'ultimo capítulo ha servido como nexo de unión de las metodologías más importantes desarrolladas en la Tesis. / Lázaro Navarro, M. (2013). The Eigenvalue Problem in Linear Viscoelastic Structures: New Numerical Approaches and the Equivalent Viscous Model [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/30062 / TESIS

In large-scale civil structures, a limited number of sensors are placed to monitor the health of civil structures to reduce maintenance, communication and energy costs. In this thesis, the problem of optimal sensor location placement to infer the health of civil structures is explored. First, a comparative study of approaches from the fields of control engineering and civil engineering is conducted . The widely used civil engineering approaches such as effective independence (EI) and modal assurance criterion (MAC) have limitations because of the negligence of modes and damping parameters. On the other hand, control engineering approaches consider the entire system dynamics using impulse response-type sensor measurement data. Such inference can be formulated as an estimation problem, with the dynamics formulated as a second-order differential equation. The comparative study suggests that damping dynamics play significant impact to the selection of best sensor location---the civil engineering approaches that neglect the damping dynamics lead to very different sensor locations from those of the control engineering approaches. In the second part of the thesis, an initial attempt to directly connect the topological graph of the structure (that defines the damping and stiffness matrices) and the second-order dynamics is conducted.

Rozpoznávanie tvárí je komplexný proces, ktorého hlavným ciežom je rozpoznanie žudskej tváre v obrázku alebo vo video sekvencii. Najčastejšími aplikáciami sú sledovacie a identifikačné systémy. Taktiež je rozpoznávanie tvárí dôležité vo výskume počítačového videnia a umelej inteligencií. Systémy rozpoznávania tvárí sú často založené na analýze obrazu alebo na neurónových sieťach. Táto práca sa zaoberá implementáciou algoritmu založeného na takzvaných „Eigenfaces“ tvárach. „Eigenfaces“ tváre sú výsledkom Analýzy hlavných komponent (Principal Component Analysis - PCA), ktorá extrahuje najdôležitejšie tvárové črty z originálneho obrázku. Táto metóda je založená na riešení lineárnej maticovej rovnice, kde zo známej kovariančnej matice sa počítajú takzvané „eigenvalues“ a „eigenvectors“, v preklade vlastné hodnoty a vlastné vektory. Tvár, ktorá má byť rozpoznaná, sa premietne do takzvaného „eigenspace“ (priestor vlastných hodnôt). Vlastné rozpoznanie je na základe porovnania takýchto tvárí s existujúcou databázou tvárí, ktorá je premietnutá do rovnakého „eigenspace“. Pred procesom rozpoznávania tvárí, musí byť tvár lokalizovaná v obrázku a upravená (normalizácia, kompenzácia svetelných podmienok a odstránenie šumu). Existuje mnoho algoritmov na lokalizáciu tváre, ale v tejto práci je použitý algoritmus lokalizácie tváre na základe farby žudskej pokožky, ktorý je rýchly a postačujúci pre túto aplikáciu. Algoritmy rozpoznávania tváre a lokalizácie tváre sú implementované do DSP procesoru Blackfin ADSP-BF561 od Analog Devices.

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