The solution of large and sparse eigenvalue problems arising from the discretization of the diffusion equation is considered. The multigroup<p>diffusion equation is discretized by means of the Nodal expansion Method (NEM) [9, 10]. A new formulation of the higher order NEM variants revealing the true nature of the problem, that is, a generalized eigenvalue problem, is proposed. These generalized eigenvalue problems are solved using the Jacobi-Davidson (JD) method<p>[26]. The most expensive part of the method consists of solving a linear system referred to as correction equation. It is solved using Krylov subspace methods in combination with aggregation-based Algebraic Multigrid (AMG) techniques. In that context, a particular<p>aggregation technique used in combination with classical smoothers, referred to as oblique geometric coarsening, has been derived. Its particularity is that it aggregates unknowns that<p>are not coupled, which has never been done to our<p>knowledge. A modular code, combining JD with an AMG preconditioner, has been developed. The code comes with many options, that have been tested. In particular, the instability of the Rayleigh-Ritz [33] acceleration procedure in the non-symmetric case has been underlined. Our code has also been compared to an industrial code extracted from ARTEMIS. / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

Après une présentation des notations usuelles de la théorie des graphes, on étudie l'ensemble des fonctions harmoniques sur les graphes, c'est à dire des fonctions dont le laplacien est nul. Ces fonctions forment un espace vectoriel et sur un graphe uniformément localement fini, on montre que cet espace vectoriel est soit de dimension un, soit de dimension infinie. Lorsque le graphe comporte une infinité de cycles, ce résultat tombe en défaut et on exhibe des exemples qui montrent qu'il existe un graphe sur lequel les harmoniques forment un espace vectoriel de dimension n, pour tout n. Un exemple de graphe périodique est également traité. Ensuite, toujours pour le laplacien, on étudie plus précisément sur les arbres uniformément localement finis les valeurs propres dont l'espace propre est de dimension infini. Dans ce cas, il est montré que l'espace propre contient un sous-espace isomorphe à l'ensemble des suites réelles bornées. Une inégalité concernant le spectre est donnée dans le cas spécial où les arêtes sont de longueur un. Des exemples montrent que ces inclusions sont optimales. Dans le chapitre suivant, on étudie le comportement asymptotique des valeurs propres pour des opérateurs elliptiques d'ordre 2 quelconques sous des conditions de Kirchhoff dynamiques. Après réécriture du problème sous la forme d'un opérateur de Sturm-Liouville, on écrit le problème de façon matricielle. Puis on trouve une équation caractéristique dont les zéros correspondent aux valeurs propres. On en déduit une formule pour l'asymptotique des valeurs propres. Dans le dernier chapitre, on étudie la stabilité de solutions stationnaires pour certains problèmes de réaction-diffusion où le terme de non linéarité est polynomial. / After a quick presentation of usual notations for the graph theory, we study the set of harmonic functions on graphs, that is, the functions whose laplacian is zero. These functions form a vectorial space. On a uniformly locally finite tree, we shaw that this space has dimension one or infinity. When the graph has an infinite number of cycles, this result change and we describe some examples showing that there exists a graph on which the harmonic functions form a vectorial space of dimension n, for all n. We also treat the case of a particular periodic graph. Then, we study more precisely the eigenvalues of infinite dimension. In this case, the eigenspace contains a subspace isomorphic to the set of bounded sequences. An inequality concerning the spectral is given when edges length is equal to one. Examples show that these inclusions are optimal. We also study the asymptotic behavior of eigenvalues for elliptic operators under dynamical Kirchhoff node conditions. We write the problem as a Sturm-Liouville operator and we transform it in a matrix problem. Then we find a characteristic equation whose zeroes correspond to eigenvalues. We deduce a formula for the asymptotic behavior. In the last chapter, we study the stability of stationary solutions for some reaction-diffusion problem whose the non-linear term is polynomial.

In Markov chain models in finance and healthcare a transition matrix over a certain time interval is needed but only a transition matrix over a longer time interval may be available. The problem arises of determining a stochastic $p$th root of astochastic matrix (the given transition matrix). By exploiting the theory of functions of matrices, we develop results on the existence and characterization of stochastic $p$th roots. Our contributions include characterization of when a real matrix hasa real $p$th root, a classification of $p$th roots of a possibly singular matrix,a sufficient condition for a $p$th root of a stochastic matrix to have unit row sums,and the identification of two classes of stochastic matrices that have stochastic $p$th roots for all $p$. We also delineate a wide variety of possible configurationsas regards existence, nature (primary or nonprimary), and number of stochastic roots,and develop a necessary condition for existence of a stochastic root in terms of the spectrum of the given matrix. On the computational side, we emphasize finding an approximate stochastic root: perturb the principal root $A^{1/p}$ or the principal logarithm $\log(A)$ to the nearest stochastic matrix or the nearest intensity matrix, respectively, if they are not valid ones;minimize the residual $\normF{X^p-A}$ over all stochastic matrices $X$ and also over stochastic matrices that are primary functions of $A$. For the first two nearness problems, the global minimizers are found in the Frobenius norm. For the last two nonlinear programming problems, we derive explicit formulae for the gradient and Hessian of the objective function $\normF{X^p-A}^2$ and investigate Newton's method, a spectral projected gradient method (SPGM) and the sequential quadratic programming method to solve the problem as well as various matrices to start the iteration. Numerical experiments show that SPGM starting with the perturbed $A^{1/p}$to minimize $\normF{X^p-A}$ over all stochastic matrices is method of choice.Finally, a new algorithm is developed for computing arbitrary real powers $A^\a$ of a matrix $A\in\mathbb{C}^{n\times n}$. The algorithm starts with a Schur decomposition,takes $k$ square roots of the triangular factor $T$, evaluates an $[m/m]$ Pad\'e approximant of $(1-x)^\a$ at $I - T^$, and squares the result $k$ times. The parameters $k$ and $m$ are chosen to minimize the cost subject to achieving double precision accuracy in the evaluation of the Pad\'e approximant, making use of a result that bounds the error in the matrix Pad\'e approximant by the error in the scalar Pad\'e approximant with argument the norm of the matrix. The Pad\'e approximant is evaluated from the continued fraction representation in bottom-up fashion, which is shown to be numerically stable. In the squaring phase the diagonal and first superdiagonal are computed from explicit formulae for $T^$, yielding increased accuracy. Since the basic algorithm is designed for $\a\in(-1,1)$, a criterion for reducing an arbitrary real $\a$ to this range is developed, making use of bounds for the condition number of the $A^\a$ problem. How best to compute $A^k$ for a negative integer $k$ is also investigated. In numerical experiments the new algorithm is found to be superior in accuracy and stability to several alternatives,including the use of an eigendecomposition, a method based on the Schur--Parlett\alg\ with our new algorithm applied to the diagonal blocks and approaches based on the formula $A^\a = \exp(\a\log(A))$.

Cette thèse est consacrée à l'étude du spectre de l'opérateur de Laplace avec conditions de Dirichlet dans différents domaines du plan ou de l'espace. Dans un premier temps on s'intéresse à des triangles asymptotiquement plats et des cônes de petite ouverture. Ces problèmes admettent une reformulation semi-classique et nous donnons des développements asymptotiques à tout ordre des premières valeurs et fonctions propres. Ce type de résultat est déjà connu pour des domaines minces à profil régulier. Pour les triangles et les cônes, on prouve que le problème admet maintenant deux échelles. Dans un second temps, on étudie une famille de couches coniques indexées par leur ouverture. Là encore, on s'intéresse à la limite semi-classique quand l'ouverture tend vers zéro: on donne un développement asymptotique à deux termes des premières valeurs propres et on démontre un résultat de localisation des fonctions propres associées. Nous donnons également, à ouverture fixée, un équivalent du nombre de valeurs propres sous le seuil du spectre essentiel. / This thesis deals with the spectrum of the Dirichlet Laplacian in various two or three dimensional domains. First, we consider asymptotically flat triangles and cones with small aperture. These problems admit a semi-classical formulation and we provide asymptotic expansions at any order for the first eigenvalues and the associated eigenfunctions. These type of results is already known for thin domains with smooth profiles. For triangles and cones, we show that the problem admits now two different scales. Second, we study a family of conical layers parametrized by their aperture. Again, we consider the semi-classical limit when the aperture tends to zero: We provide a two-term asymptotics of the first eigenvalues and we prove a localization result about the associated eigenfunctions. We also estimate, for each chosen aperture, the number of eigenvalues below the threshold of the essential spectrum.

La théorie des matrices s'est développée rapidement au cours des dernières décennies en raison de son large éventail d'applications et de ses nombreux liens avec différents domaines des mathématiques, de l'économie, de l'apprentissage automatique et du traitement du signal. Cette thèse concerne trois axes principaux liés à deux objets d'étude fondamentaux de la théorie des matrices et apparaissant naturellement dans de nombreuses applications, à savoir les matrices semi-définies positives et les matrices doublement stochastiques.Un concept qui découle naturellement du domaine de l'apprentissage automatique et qui est lié à la propriété semi-définie positive est celui des matrices de similarité. En fait, les matrices de similarité qui sont semi-définies positives revêtent une importance particulière en raison de leur capacité à définir des distances métriques. Cette thèse explorera la propriété semi-définie positive pour une liste de matrices de similarité trouvées dans la littérature. De plus, nous présentons de nouveaux résultats concernant les propriétés définie positive et semi-définie trois-positive de certains matrices de similarité. Une discussion détaillée des nombreuses applications de tous ces propriétés dans divers domaines est également établie.D'autre part, un problème récent de l'analyse matricielle implique l'étude des racines des matrices stochastiques, ce qui s'avère important dans les modèles de chaîne de Markov en finance. Nous étendons l'analyse de ce problème aux matrices doublement stochastiques semi-définies positives. Nous montrons d'abord certaines propriétés géométriques de l'ensemble de toutes les matrices semi-définies positives doublement stochastiques d'ordre n ayant la p-ième racine doublement stochastique pour un entier donné p . En utilisant la théorie des M-matrices et le problème inverse des valeurs propres des matrices symétriques doublement stochastiques (SDIEP), nous présentons également quelques méthodes pour trouver des classes de matrices semi-définies positives doublement stochastiques ayant des p-ièmes racines doublement stochastiques pour tout entier p.Dans le contexte du SDIEP, qui est le problème de caractériser ces listes de nombres réels qui puissent constituer le spectre d’une matrice symétrique doublement stochastique, nous présentons quelques nouveaux résultats le long de cette ligne. En particulier, nous proposons d’utiliser une méthode récursive de construction de matrices doublement stochastiques afin d'obtenir de nouvelles conditions suffisantes indépendantes pour SDIEP. Enfin, nous concentrons notre attention sur les spectres normalisés de Suleimanova, qui constituent un cas particulier des spectres introduits par Suleimanova. En particulier, nous prouvons que de tels spectres ne sont pas toujours réalisables et nous construisons trois familles de conditions suffisantes qui affinent les conditions suffisantes précédemment connues pour SDIEP dans le cas particulier des spectres normalisés de Suleimanova. / Matrix theory has shown its importance by its wide range of applications in different fields such as statistics, machine learning, economics and signal processing. This thesis concerns three main axis related to two fundamental objects of study in matrix theory and that arise naturally in many applications, that are positive semi-definite matrices and doubly stochastic matrices.One concept which stems naturally from machine learning area and is related to the positive semi-definite property, is the one of similarity matrices. In fact, similarity matrices that are positive semi-definite are of particular importance because of their ability to define metric distances. This thesis will explore the latter desirable structure for a list of similarity matrices found in the literature. Moreover, we present new results concerning the strictly positive definite and the three positive semi-definite properties of particular similarity matrices. A detailed discussion of the many applications of all these properties in various fields is also established.On the other hand, an interesting research field in matrix analysis involves the study of roots of stochastic matrices which is important in Markov chain models in finance and healthcare. We extend the analysis of this problem to positive semi-definite doubly stochastic matrices.Our contributions include some geometrical properties of the set of all positive semi-definite doubly stochastic matrices of order n with nonnegative pth roots for a given integer p. We also present methods for finding classes of positive semi-definite doubly stochastic matrices that have doubly stochastic pth roots for all p, by making use of the theory of M-Matrices and the symmetric doubly stochastic inverse eigenvalue problem (SDIEP), which is also of independent interest.In the context of the SDIEP, which is the problem of characterising those lists of real numbers which are realisable as the spectrum of some symmetric doubly stochastic matrix, we present some new results along this line. In particular, we propose to use a recursive method on constructing doubly stochastic matrices from smaller size matrices with known spectra to obtain new independent sufficient conditions for SDIEP. Finally, we focus our attention on the realizability by a symmetric doubly stochastic matrix of normalised Suleimanova spectra which is a normalized variant of the spectra introduced by Suleimanova. In particular, we prove that such spectra is not always realizable for odd orders and we construct three families of sufficient conditions that make a refinement for previously known sufficient conditions for SDIEP in the particular case of normalized Suleimanova spectra.

本論文は,様々なネットワーク最適化問題の数学的構造について様々な観点から調べたものである.主たる結果はネットワーク最適化問題の代表例である最大流問題に,関するいくつかの結果と,Min-Plus代数に値をもつ行列の固有値と固有ベクトルに関する特徴づけに関する結果からなっている. / 博士(理学) / Doctor of Philosophy in Science / 同志社大学 / Doshisha University

[pt] Neste trabalho apresentam-se três tipos de técnicas de análise do colapso estrutural através do método dos elementos finitos: análise linearizada da carga crítica, análise incremental da carga crítica e análise não linear completa. Na análise linearizada da carga crítica formulou-se um problema de autovalor empregando matrizes de rigidez baseadas na configuração indeformada da estrutura e materiais com comportamento linear elástico. No caso da análise incremental da carga crítica, o problema de autovalor foi formulado empregando matrizes de rigidez incrementais para levar em consideração os grandes deslocamentos e propriedades não lineares do material. Finalmente, na análise não linear completa a configuração deformada da estrutura e propriedades não lineares do material são atualizadas durante todo o processo incremental-iterativo até atingir a carga crítica. Desenvolveu-se uma implementação computacional para estudar as três técnicas de análise em estruturas planas como vigas, colunas, pórticos e arcos, empregando elementos isoparamétricos bidimensionais para estado plano de tensões. A configuração deformada da estrutura, devido aos grandes deslocamentos e rotações dos elementos, foi considerada através de uma formulação Lagrangeana Total, enquanto o comportamento inelástico do material foi modelado empregando um modelo elastoplástico de Von Mises (J2) com encruamento isotrópico. Nos exemplos apresentados mostrou-se a influência da não linearidade geométrica e física na estimativa de cargas críticas e no comportamento pós-crítico, podendo ocorrer bifurcações ao longo da trajetória de equilíbrio fundamental definida no espaço carga-deslocamentos. / [en] This work presents three kinds of techniques for collapse analysis using the finite element method: linear buckling analysis, nonlinear buckling analysis and full nonlinear analysis. The linear buckling analysis requires the definition of an eigenvalue problem using a stiffness matrix formulation based on the initial configuration of the structure and under the assumption of a linear elastic material behavior. In the case of nonlinear buckling analysis, the eigenvalue problem was formulated employing an incremental stiffness matrix in order to consider the effects of large displacements and nonlinear material properties in the critical load estimation. Finally, the full nonlinear analysis takes into account the deformed configuration and the nonlinear material properties of the structure, updating both of them through all the incremental-iterative process up to reaching the critical load. A Finite Element computational program, using plane stress isoperimetric bidimensional elements, was developed to study the three analysis techniques applied to plane structures such as beams, columns, frames and arches. The deformed configuration of the structure, due to large displacements and rotations, was considered through the Total Lagrangian formulation, whereas the inelastic material behavior was modeled using the Von Mises plasticity model with isotropic hardening. The examples presented in this article show the influence of geometric and material nonlinearity in the critical load estimation and the postcritical behavior, being this the reason for the potential occurrence of bifurcation points over the fundamental equilibrium path defined in the load-displacement space.

Gegenstand dieser Arbeit ist die numerische Approximation von Eigenwerten elliptischer Differentialoperatoren vermittels der adaptiven finite-Elemente-Methode (AFEM). Durch lokale Netzverfeinerung können derartige Verfahren den Rechenaufwand im Vergleich zu uniformer Verfeinerung deutlich reduzieren und sind daher von großer praktischer Bedeutung. Diese Arbeit behandelt adaptive Algorithmen für Finite-Elemente-Methoden (FEMs) für drei selbstadjungierte Modellprobleme: den Laplaceoperator, das Stokes-System und den biharmonischen Operator. In praktischen Anwendungen führen Störungen der Koeffizienten oder der Geometrie auf Eigenwert-Haufen (Cluster). Dies macht simultanes Markieren im adaptiven Algorithmus notwendig. In dieser Arbeit werden optimale Konvergenzraten für einen praktischen adaptiven Algorithmus für Eigenwert-Cluster des Laplaceoperators (konforme und nichtkonforme P1-FEM), des Stokes-Systems (nichtkonforme P1-FEM) und des biharmonischen Operators (Morley-FEM) bewiesen. Fehlerabschätzungen in der L2-Norm und Bestapproximations-Resultate für diese Nichtstandard-Methoden erfordern neue Techniken, die in dieser Arbeit entwickelt werden. Dadurch wird der Beweis optimaler Konvergenzraten ermöglicht. Die Optimalität bezüglich einer nichtlinearen Approximationsklasse betrachtet die Approximation des invarianten Unterraums, der von den Eigenfunktionen im Cluster aufgespannt wird. Der Fehler der Eigenwerte kann dazu in Bezug gesetzt werden: Die hierfür notwendigen Eigenwert-Fehlerabschätzungen für nichtkonforme Finite-Elemente-Methoden werden in dieser Arbeit gezeigt. Die numerischen Tests für die betrachteten Modellprobleme legen nahe, dass der vorgeschlagene Algorithmus, der bezüglich aller Eigenfunktionen im Cluster markiert, einem Markieren, das auf den Vielfachheiten der Eigenwerte beruht, überlegen ist. So kann der neue Algorithmus selbst im Fall, dass alle Eigenwerte im Cluster einfach sind, den vorasymptotischen Bereich signifikant verringern. / The numerical approximation of the eigenvalues of elliptic differential operators with the adaptive finite element method (AFEM) is of high practical interest because the local mesh-refinement leads to reduced computational costs compared to uniform refinement. This thesis studies adaptive algorithms for finite element methods (FEMs) for three model problems, namely the eigenvalues of the Laplacian, the Stokes system and the biharmonic operator. In practice, little perturbations in coefficients or in the geometry immediately lead to eigenvalue clusters which requires the simultaneous marking in adaptive finite element methods. This thesis proves optimality of a practical adaptive algorithm for eigenvalue clusters for the conforming and nonconforming P1 FEM for the eigenvalues of the Laplacian, the nonconforming P1 FEM for the eigenvalues of the Stokes system and the Morley FEM for the eigenvalues of the biharmonic operator. New techniques from the medius analysis enable the proof of L2 error estimates and best-approximation properties for these nonstandard finite element methods and thereby lead to the proof of optimality. The optimality in terms of the concept of nonlinear approximation classes is concerned with the approximation of invariant subspaces spanned by eigenfunctions of an eigenvalue cluster. In order to obtain eigenvalue error estimates, this thesis presents new estimates for nonconforming finite elements which relate the error of the eigenvalue approximation to the error of the approximation of the invariant subspace. Numerical experiments for the aforementioned model problems suggest that the proposed practical algorithm that uses marking with respect to all eigenfunctions within the cluster is superior to marking that is based on the multiplicity of the eigenvalues: Even if all exact eigenvalues in the cluster are simple, the simultaneous approximation can reduce the pre-asymptotic range significantly.

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.

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.