In this section, we will consider two methods for computing an eigenvector and in addition the associated eigenvalue of a matrix A.

This paper is the result of a study of the power method to find dominant eigenvalues of square matrices. It introduces ideas basic to the study and shows the development of the power method for the most well-behaved matrices possible, and it explores exactly which other types of matrices yield to the power method. The paper also discusses a type of matrix typically considered impossible for the power method, along with a modification of the power method which works for this type of matrix. It gives an overview of common extensions of the power method. The appendices contain BASIC versions of the power method and its modification.

Some of the theory of nonnegative matrices is first presented. The Perron-Frobenius theorem is highlighted. Some of the important linear algebraic methods of information retrieval are surveyed. Latent Semantic Indexing (LSI), which uses the singular value de-composition is discussed. The Hyper-Text Induced Topic Search (HITS) algorithm is next considered; here the power method for finding dominant eigenvectors is employed. Through the use of a theorem by Sinkohrn and Knopp, a modified HITS method is developed. Lastly, the PageRank algorithm is discussed. Numerical examples and MATLAB programs are also provided.

In this thesis, I study fluctuations and rare events of time-additive observables of discrete-time Markov chains on finite state spaces. The observable of interest is the mean node connectivity visited by a random walk running on instances of an Erdős-Rényi (ER) random graph. I implement and analyze the Adaptive Power Method (APM) which converges to the driven process, a biased random walk defined through a control parameter that simulates trajectories corresponding to rare events of the observable in the original dynamics. The APM demonstrates good convergence and accurately produces the desired quantities from a single trajectory. Due to the bulk-dangling-chain structure in the ER graph, the driven process seems to undergo a dynamical phase transition (DPT) for infinitely large graphs, meaning the behavior of the trajectories changes abruptly as the control parameter is varied. Observations show that the random walk visits two distinct phases, being de-localized in the bulk or localized in the chain. Through two simpler models capturing the bulk-dangling-chain property of the ER graph I study how the DPT occurs as the graph size increases. I observe that the trajectories of the driven process near the transition show intermittent behavior between the two phases. The diverging time scale of the DPT is found to be the average time that the random walk spends in a phase before it transitions to the other one. On the ER graph the trajectories are also intermittent but the form of the time scaling remains open due to computational limits on the graph size.

Made available in DSpace on 2014-12-17T15:26:38Z (GMT). No. of bitstreams: 1 ThiagoJA_DISSERT.pdf: 636679 bytes, checksum: 3497bfd29c2779ff70f7932b9a308a9c (MD5) Previous issue date: 2012-08-13 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / In this work we have elaborated a spline-based method of solution of inicial value problems involving ordinary differential equations, with emphasis on linear equations. The method can be seen as an alternative for the traditional solvers such as Runge-Kutta, and avoids root calculations in the linear time invariant case. The method is then applied on a central problem of control theory, namely, the step response problem for linear EDOs with possibly varying coefficients, where root calculations do not apply. We have implemented an efficient algorithm which uses exclusively matrix-vector operations. The working interval (till the settling time) was determined through a calculation of the least stable mode using a modified power method. Several variants of the method have been compared by simulation. For general linear problems with fine grid, the proposed method compares favorably with the Euler method. In the time invariant case, where the alternative is root calculation, we have indications that the proposed method is competitive for equations of sifficiently high order. / Neste trabalho desenlvolvemos um m?todo de resolu??o de problemas de valor inicial com equa??es diferenciais ordin?rias baseado em splines, com ?nfase em equa??es lineares. O m?todo serve como alternativa para os m?todos tradicionais como Runge-Kutta e no caso linear com coeficientes constantes, evita o c?lculo de ra?zes de polin?mios. O m?todo foi aplicado para um problema central da teoria de controle, o problema de resposta a degrau para uma EDO linear, incluindo o caso de coeficientes n?o-constantes, onde a alternativa pelo c?lculo de ra?zes n?o existe. Implementamos um algoritmo eficiente que usa apenas opera??es tipo matriz-vetor. O intervalo de trabalho (at? o tempo de acomoda??o) para as equa??es est?veis com coeficientes constantes ?e determinado pelo c?lculo da raiz menos est?vel do sistema, a partir de uma adapta??o do m?todo da pot?ncia. Atrav?s de simula??es, comparamos algumas variantes do m?todo. Em problemas lineares gerais com malha suficientemente fina, o novo m?todo mostra melhores resultados em compara??o com o m?todo de Euler. No caso de coeficientes constantes, onde existe a alternativa baseada em c?lculo das ra?zes, temos indica??es que o novo m?todo pode ficar competitivo para equa??es de grau bastante alto

Ce manuscrit regroupe différents travaux explorant les interactions entre les tenseurs et l'apprentissage automatique. Le premier chapitre est consacré à l'extension des modèles de séries reconnaissables de chaînes et d'arbres aux graphes. Nous y montrons que les modèles d'automates pondérés de chaînes et d'arbres peuvent être interprétés d'une manière simple et unifiée à l'aide de réseaux de tenseurs, et que cette interprétation s'étend naturellement aux graphes ; nous étudions certaines propriétés de ce modèle et présentons des résultats préliminaires sur leur apprentissage. Le second chapitre porte sur la minimisation approximée d'automates pondérés d'arbres et propose une approche théoriquement fondée à la problématique suivante : étant donné un automate pondéré d'arbres à n états, comment trouver un automate à m<n états calculant une fonction proche de l'originale. Le troisième chapitre traite de la régression de faible rang pour sorties à structure tensorielle. Nous y proposons un algorithme d'apprentissage rapide et efficace pour traiter un problème de régression dans lequel les sorties des tenseurs. Nous montrons que l'algorithme proposé est un algorithme d'approximation pour ce problème NP-difficile et nous donnons une analyse théorique de ses propriétés statistiques et de généralisation. Enfin, le quatrième chapitre introduit le modèle de mélanges algébriques de distributions. Ce modèle considère des combinaisons affines de distributions (où les coefficients somment à un mais ne sont pas nécessairement positifs). Nous proposons une approche pour l'apprentissage de mélanges algébriques qui étend la méthode tensorielle des moments introduite récemment. . / This thesis tackles several problems exploring connections between tensors and machine learning. In the first chapter, we propose an extension of the classical notion of recognizable function on strings and trees to graphs. We first show that the computations of weighted automata on strings and trees can be interpreted in a natural and unifying way using tensor networks, which naturally leads us to define a computational model on graphs: graph weighted models; we then study fundamental properties of this model and present preliminary learning results. The second chapter tackles a model reduction problem for weighted tree automata. We propose a principled approach to the following problem: given a weighted tree automaton with n states, how can we find an automaton with m<n states that is a good approximation of the original one? In the third chapter, we consider a problem of low rank regression for tensor structured outputs. We design a fast and efficient algorithm to address a regression task where the outputs are tensors. We show that this algorithm generalizes the reduced rank regression method and that it offers good approximation, statistical and generalization guarantees. Lastly in the fourth chapter, we introduce the algebraic mixture model. This model considers affine combinations of probability distributions (where the weights sum to one but may be negative). We extend the recently proposed tensor method of moments to algebraic mixtures, which allows us in particular to design a learning algorithm for algebraic mixtures of spherical Gaussian distributions.

Αντικείμενο αυτής της μεταπτυχιακής εργασίας είναι ο εντοπισμός της ύπαρξης μιας κυρίαρχης ευρείας ζώνης ισοτροπικής πηγής κι η εκτίμηση των συντεταγμένων θέσης αυτής, όταν αυτή βρίσκεται σ’ έναν τρισδιάστατο ή δισδιάστατο χώρο, ο οποίος εποπτεύεται και παρακολουθείται από ένα δίκτυο τυχαία διασκορπισμένων αισθητήρων. Οι κόμβοι του δικτύου μπορούν να περιέχουν ακουστικά, παλμικά κι άλλου είδους μικροηλεκτρομηχανολογικά στοιχεία αίσθησης του περιβάλλοντος. Κατά την αίσθηση ενός γεγονότος ενδιαφέροντος μπορούν να αυτοοργανωθούν σ’ ένα συγχρονισμένο ασύρματο ραδιοδίκτυο χρησιμοποιώντας χαμηλής κατανάλωσης πομποδέκτες spread spectrum, ώστε να επικοινωνούν μεταξύ τους και με τους κεντρικούς επεξεργαστές. Ο εντοπισμός της ύπαρξης μιας κυρίαρχης πηγής σ’ ένα δίκτυο αισθητήρων, με τα παραπάνω χαρακτηριστικά, επιτεύχθηκε με τη χρήση μιας τυφλής μεθόδου μορφοποίησης λοβού, γνωστή ως μέθοδος συλλογής της μέγιστης ισχύος. Η μέθοδος αυτή, η οποία υλοποιήθηκε στα πλαίσια αυτής της εργασίας, παρέχει τις εκτιμήσεις των σχετικών χρόνων καθυστέρησης άφιξης του σήματος της κυρίαρχης πηγής στους αισθητήρες του δικτύου ως προς έναν αισθητήρα αναφοράς. Κύριο αντικείμενο μελέτης αυτής της εργασίας είναι ο υπολογισμός του κυρίαρχου ιδιοδιανύσματος του δειγματοληπτημένου πίνακα αυτοσυσχέτισης. Αυτό επιτυγχάνεται στη βιβλιογραφία που μελετήθηκε είτε με χρήση της δυναμικής μεθόδου είτε με χρήση της μεθόδου ιδιοανάλυσης. Ανά στιγμιότυπο δειγμάτων απαιτείται η ανανέωση του πίνακα αυτοσυσχέτισης κι ο υπολογισμός του κυρίαρχου ιδιοδιανύσματος. Όμως, οι δύο παραπάνω μέθοδοι για τον υπολογισμό αυτό χρειάζονται αυξημένη πολυπλοκότητα μιας κι η διάσταση του πίνακα είναι αρκετά μεγάλη. Η συνεισφορά της εργασίας αυτής έγκειται στη μείωση αυτής της πολυπλοκότητας με τη χρήση μιας προσαρμοστικής μεθόδου υπολογισμού του κυρίαρχου ιδιοδιανύσματος. Τέλος, αντικείμενο της εργασίας αυτής είναι και το πρόβλημα εντοπισμού και παρακολούθησης των συντεταγμένων θέσης της κυρίαρχης πηγής από τις εκτιμήσεις των σχετικών χρόνων καθυστέρησης άφιξης. / Object of this postgraduate work are the detection of presence of an isotropic wideband dominant source and the estimate of its coordinates of placement (localization), when the source is found in a three or two dimensional space, which is supervised and watched by a randomly distributed sensor network. The nodes of the network may contain acoustical, vibrational and other MEM-sensing (Micro-Electro-Mechanical) elements. Upon sensing an event of interest, they can self-organize into a synchronized wireless radio network using low-power spread-spectrum transceivers to communicate among themselves and central processors. The detection of presence of a dominant source in a sensor network, with the above characteristics, was achieved with the use of a blind beamforming method, known as the maximum power collection method. This method, which was implemented in the context of this work, provides estimates of the relative time delays of arrival (relative TDEs - Time Delay Estimations) of the dominant source’s signal to the sensors of the network referenced to a reference sensor. The main object of study of the work is the calculation of the dominant eigenvector of the sampled correlation matrix. This is achieved, in the bibliography that was studied, either by using the power method or with use of the SVD method (Singular Value Decomposition). Per snapshot of samples it is required to update the autocorrelation matrix and to calculate the dominant eigenvector. However, the above two methods for this calculation have an increased complexity because the dimension of the matrix is high enough. The contribution of this work lies in the reduction of that complexity by using an adaptive method for the dominant eigenvector calculation. Finally, this work also focuses on the problem of localization and tracking of the coordinates of placement of the dominant source from the estimates of the relative time delays of arrival.

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>

In this thesis I hope to provide a clear and concise introduction to Feigenbaum scaling accessible to undergraduate students. This is accompanied by a description of how to obtain numerical results by various means. A more intricate approach drawing from renormalization theory as well as a short consideration of some of the topological properties will also be presented. I was furthermore trying to put great emphasis on diagrams throughout the text to make the contents more comprehensible and intuitive.