No description available.

This thesis concerns the analysis and sensitivity of nonlinear eigenvalue problems for matrices and linear operators. The first part illustrates that lack of normality may result in catastrophic ill-conditioned eigenvalue problem. Linearization of rational eigenvalue problems for both operators over finite and infinite dimensional spaces are considered. The standard approach is to multiply by the least common denominator in the rational term and apply a well known linearization technique to the polynomial eigenvalue problem. However, the symmetry of the original problem is lost, which may result in a more ill-conditioned problem. In this thesis, an alternative linearization method is used and the sensitivity of the two different linearizations are studied. Moreover, this work contains numerically solved rational eigenvalue problems with applications in photonic crystals. For these examples the pseudospectra is used to show how well-conditioned the problems are which indicates whether the solutions are reliable or not.

No description available.

El problema de valores propios (tambien llamado de autovalores, o eigenvalues) esta presente en diversas tareas cienficas a traves de la resolucion de ecuaciones diferenciales, analisis de modelos y calculos de funciones matriciales, entre otras muchas aplicaciones. Si los problemas son de dimension moderada (menor a 106), pueden ser abordados mediante los llamados metodos directos, como el algoritmo iterativo QR o el metodo de divide y vencerlas. Sin embargo, si el problema es de gran dimension y solo se requieren unas pocas soluciones (comparado con el tama~no del problema) y con un cierto grado de aproximacion, los metodos iterativos pueden resultar mas eficientes. Ademas los metodos iterativos pueden ofrecer mejores prestaciones en arquitecturas de altas prestaciones, como las de memoria distribuida, en las que existen un cierto numero de nodos computacionales con espacio de memoria propios y solo pueden compartir informacion y sincronizarse mediante el paso de mensajes. Esta tesis aborda la implementacion de metodos de tipo Davidson, destacando Generalized Davidson y Jacobi-Davidson, una clase de metodos iterativos que puede ser competitiva en casos especialmente dificiles como calcular valores propios en el interior del espectro o cuando la factorizacion de matrices es prohibitiva o ineficiente, y solo es posible una factorizacion aproximada. La implementacion se desarrolla en SLEPc (Scalable Library for Eigenvalue Problem Computations), libreria libre destacada en la resolucion de problemas de gran tama~no de valores propios, problemas cuadraticos de valores propios y problemas de valores singulares, entre otros. A su vez, SLEPc se desarrolla bajo el marco de PETSc (Portable, Extensible Toolkit for Scientic Computation), que ofrece implementaciones eficientes de operaciones basicas del algebra lineal, como operaciones con matrices y vectores, resolucion aproximada de sistemas lineales, factorizaciones exactas y aproximadas de matrices, etc. / Romero Alcalde, E. (2012). Parallel implementation of Davidson-type methods for large-scale eigenvalue problems [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/15188 / Palancia

This thesis investigates the numerical treatment of nonlinear eigenvalue problems. These problems are defined by the condition $T(lambda) v = boldsymbol{0}$, with $T: C to C^{n times n}$, where we seek to compute the scalar-vector pairs, $lambda in C$ and nonzero $ v in C^{n}$. The first contribution of this work connects recent contour integration methods to the theory and practice of system identification. This observation leads us to explore rational interpolation for system realization, producing a Loewner matrix contour integration technique. The second development of this work studies the application of rational interpolation to the function $T(z)^{-1}$, where we use the poles of this interpolant to approximate the eigenvalues of $T$. We then expand this idea to several iterative methods, where at each step the approximate eigenvalues are taken as new interpolation points. We show that the case where one interpolation point is used is theoretically equivalent to Newton's method for a particular scalar function. / Master of Science / This thesis investigates the numerical treatment of nonlinear eigenvalue problems. The solutions to these problems often reveal characteristics of an underlying physical system. One popular methodology for handling these problems uses contour integrals to compute a set of the solutions. The first contribution of this work connects these contour integration methods to the theory and practice of system identification. This leads us to explore other techniques for system identification, resulting in a new method. Another common methodology approximates the nonlinear problem directly. The second development of this work studies the application of rational interpolation for this purpose. We then use this idea to form several iterative methods, where at each step the approximate solutions are taken to be new interpolation points. We show that the case where one interpolation point is used is theoretically equivalent to Newton’s method for a particular scalar function.

This Thesis contains contributions in two different but closely related subfields of Scientific and Parallel Computing which arise in the context of various eigenvalue problems: periodic and parallel eigenvalue reordering and parallel algorithms for Sylvestertype matrix equations with applications in condition estimation. Many real world phenomena behave periodically, e.g., helicopter rotors, revolving satellites and dynamic systems corresponding to natural processes, like the water flow in a system of connected lakes, and can be described in terms of periodic eigenvalue problems. Typically, eigenvalues and invariant subspaces (or, specifically, eigenvectors) to certain periodic matrix products are of interest and have direct physical interpretations. The eigenvalues of a matrix product can be computed without forming the product explicitly via variants of the periodic Schur decomposition. In the first part of the Thesis, we propose direct methods for eigenvalue reordering in the periodic standard and generalized real Schur forms which extend earlier work on the standard and generalized eigenvalue problems. The core step of the methods consists of solving periodic Sylvester-type equations to high accuracy. Periodic eigenvalue reordering is vital in the computation of periodic eigenspaces corresponding to specified spectra. The proposed direct reordering methods rely on orthogonal transformations and can be generalized to more general periodic matrix products where the factors have varying dimensions and ±1 exponents of arbitrary order. In the second part, we consider Sylvester-type matrix equations, like the continuoustime Sylvester equation AX −XB =C, where A of size m×m, B of size n×n, and C of size m×n are general matrices with real entries, which have applications in many areas. Examples include eigenvalue problems and condition estimation, and several problems in control system design and analysis. The parallel algorithms presented are based on the well-known Bartels–Stewart’s method and extend earlier work on triangular Sylvester-type matrix equations resulting in a novel software library SCASY. The parallel library provides robust and scalable software for solving 44 sign and transpose variants of eight common Sylvester-type matrix equations. SCASY also includes a parallel condition estimator associated with each matrix equation. In the last part of the Thesis, we propose parallel variants of the direct eigenvalue reordering method for the standard and generalized real Schur forms. Together with the existing and future parallel implementations of the non-symmetric QR/QZ algorithms and the parallel Sylvester solvers presented in the Thesis, the developed software can be used for parallel computation of invariant and deflating subspaces corresponding to specified spectra and associated reciprocal condition number estimates.

Objects such as documents, people, words or utilities, that are related in some way, for instance by citations, friendship, appearance in definitions or physical connections, may be conveniently represented using graphs or networks. An increasing number of such relational databases, as for instance the World Wide Web, digital libraries, social networking web sites or phone calls logs, are available. Relevant information may be hidden in these networks. A user may for instance need to get authority web pages on a particular topic or a list of similar documents from a digital library, or to determine communities of friends from a social networking site or a phone calls log. Unfortunately, extracting this information may not be easy. This thesis is devoted to the study of problems related to information extraction in large graphs with the help of dominant vectors of nonnegative matrices. The graph structure is indeed very useful to retrieve information from a relational database. The correspondence between nonnegative matrices and graphs makes Perron--Frobenius methods a powerful tool for the analysis of networks. In a first part, we analyze the fixed points of a normalized affine iteration used by a database matching algorithm. Then, we consider questions related to PageRank, a ranking method of the web pages based on a random surfer model and used by the well known web search engine Google. In a second part, we study optimal linkage strategies for a web master who wants to maximize the average PageRank score of a web site. Finally, the third part is devoted to the study of a nonlinear variant of PageRank. The simple model that we propose takes into account the mutual influence between web ranking and web surfing.

For Laplace's eigenvalue problems, this thesis presents new algorithms of the Trefftz method (i.e. the boundary approximation method), which solve the Helmholtz equation and then use a iteration process to yield approximate eigenvalues and eigenfunctions. The new iteration method has superlinear convergence rates and gives a better performance in numerical testing, compared with the other popular methods of rootfinding. Moreover, piecewise particular solutions are used for a basic model of eigenvalue problems on the unit square with the Dirichlet condition. Numerical experiments are also conducted for the eigenvalue problems with singularities. Our new algorithms using piecewise particular solutions are well suited to seek very accurate solutions of eigenvalue problems, in particular those with multiple singularities, interfaces and those on unbounded domains. Using piecewise particular solutions has also the advantage to solve complicated problems because uniform particular solutions may not always exist for the entire solution domain.

Consider (1) -yn1+ q1y1 = (λr11 + µr12)y1 on [0, 1] y’1(0) = cot α1 and = y’1(1) = a1λ + b1 y1(0) y1(1) c1λ+d1 (2) - yn2 + q2y2 = (λr21 + µr22)y2 on [0, 1] y’2(0) = cot α2 and = y’2(1) = a2µ + b2 y2(0) y2(1) c2µ + d2 subject to certain definiteness conditions; where qi and rij are continuous real valued functions on [0, 1], the angle αi is in [0, π) and ai, bi, ci, di are real numbers with δi = aidi − bici > 0 and ci = 0 for I, j = 1,2. Under the Uniform Left Definite condition we have proved an asymptotic theorem and an oscillation theorem. Analysis of (1) and (2) subject to the Uniform Ellipticity condition focus on the location of eigenvalues, perturbation theory and the local analysis of eigenvalues. We also gave a bound for the number of nonreal eigenvalues. We also have studied the system T1(x1) = (λA11 + µA12)(x1) and T2(x2) = (λA21 + µA22)(x2) where Aij (j =1, 2) and Ti are linear operators acting on finite dimensional Hilbert spaces Hi (i = 1, 2). For a pair of commutative operators Γ = (Γ0, Γ1) constructed from Aij and Ti on the Hilbert space tensor product H1 ⊗ H2, we can associate a natural Koszul complex namely Dºr-(λ,μ) D1 r-(λ,μ) 0 H H ø H H 0 We have constructed a basis for the Koszul quotient space N(D1Г−(λ,µ))/R(D0Г−( λ,µ)) in terms of the root basis of (Г0, Г1). (For equations pl refer the PDF file)

This thesis describes improvements of the periodic QZ algorithm and several variants of the Schur algorithm for block Toeplitz matrices. Documentation of the available software is included.