No description available.

Sequences of matrices arise in many applications in science and engineering. In this thesis we consider matrices that are closely related (or closely related in groups), and we take advantage of the small differences between them to efficiently solve sequences of linear systems and eigenproblems. Recycling techniques, such as recycling preconditioners or subspaces, are popular approaches for reducing computational cost. In this thesis, we introduce two novel approaches for recycling previously computed information for a subsequent system or eigenproblem, and demonstrate good results for sequences arising in several applications. Preconditioners are often essential for fast convergence of iterative methods. However, computing a good preconditioner can be very expensive, and when solving a sequence of linear systems, we want to avoid computing a new preconditioner too often. Instead, we can recycle a previously computed preconditioner, for which we have good convergence behavior of the preconditioned system. We propose an update technique we call the sparse approximate map, or SAM update, that approximately maps one matrix to another matrix in our sequence. SAM updates are very cheap to compute and apply, preserve good convergence properties of a previously computed preconditioner, and help to amortize the cost of that preconditioner over many linear solves. When solving a sequence of eigenproblems, we can reduce the computational cost of constructing the Krylov space starting with a single vector by warm-starting the eigensolver with a subspace instead. We propose an algorithm to warm-start the Krylov-Schur method using a previously computed approximate invariant subspace. We first compute the approximate Krylov decomposition for a matrix with minimal residual, and use this space to warm-start the eigensolver. We account for the residual matrix when expanding, truncating, and deflating the decomposition and show that the norm of the residual monotonically decreases. This method is effective in reducing the total number of matrix-vector products, and computes an approximate invariant subspace that is as accurate as the one computed with standard Krylov-Schur. In applications where the matrix-vector products require an implicit linear solve, we incorporate Krylov subspace recycling. Finally, in many applications, sequences of matrices take the special form of the sum of the identity matrix, a very low-rank matrix, and a small-in-norm matrix. We consider convergence rates for GMRES applied to these matrices by identifying the sources of sensitivity. / Doctor of Philosophy / Problems in science and engineering often require the solution to many linear systems, or a sequence of systems, that model the behavior of physical phenomena. In order to construct highly accurate mathematical models to describe this behavior, the resulting matrices can be very large, and therefore the linear system can be very expensive to solve. To efficiently solve a sequence of large linear systems, we often use iterative methods, which can require preconditioning techniques to achieve fast convergence. The preconditioners themselves can be very expensive to compute. So, we propose a cheap update technique that approximately maps one matrix to another in the sequence for which we already have a good preconditioner. We then combine the preconditioner and the map and use the updated preconditioner for the current system. Sequences of eigenvalue problems also arise in many scientific applications, such as those modeling disk brake squeal in a motor vehicle. To accurately represent this physical system, large eigenvalue problems must be solved. The behavior of certain eigenvalues can reveal instability in the physical system but to identify these eigenvalues, we must solve a sequence of very large eigenproblems. The eigensolvers used to solve eigenproblems generally begin with a single vector, and instead, we propose starting the method with several vectors, or a subspace. This allows us to reduce the total number of iterations required by the eigensolver while still producing an accurate solution. We demonstrate good results for both of these approaches using sequences of linear systems and eigenvalue problems arising in several real-world applications. Finally, in many applications, sequences of matrices take the special form of the sum of the identity matrix, a very low-rank matrix, and a small-in-norm matrix. We examine the convergence behavior of the iterative method GMRES when solving such a sequence of matrices.

This work addresses two primary topics related to vibrations in structures. The first topic is the use of a spatially distributed sensor network for localization of vibration events. I use a received signal strength (RSS) framework that presumes exponential energy decay with distance to the source. I derive the Cramér-Rao bound (CRB) for this parameter estimation problem, with the unknown parameters being source location, source intensity, and the energy dissipation rate. In this framework, I show that the CRB matches the variance of maximum likelihood estimators (MLEs) in more computationally expensive Monte Carlo trials. I also compare the CRB to the results of physical experiments to test the power of the CRB to predict spatial areas where MLEs show practical evidence of being ill-conditioned. Supported by this evidence, I recommend the CRB as a simple measure of localization accuracy, which may be used to optimize sensor layouts before installation. I demonstrate how this numerical optimization may be performed for some regions of interest with simple geometries. The second topic investigates modal vibrations of multi-body structures built from simple one-dimensional elements, with networks of elastic strings as the primary example. I introduce a method of using a nonlinear eigenvalue problem (NLEVP) to express boundary conditions of the vibrating elements so that the (infinitely many) eigenvalues of the full structure are the eigenvalues of the finite-dimensional NLEVP. The mode shapes of the structure can then be recovered in analytic form (not as a discretization) from the corresponding eigenvectors of the NLEVP. I show some advantages of this method over dynamic stiffness matrices, which is another NLEVP framework for modal analysis. In numerical experiments, I test several contour integration solvers for NLEVPs on sample problems generated from string networks. / Doctor of Philosophy / This work deals with two primary topics related to vibrations in structures. The first topic is the use of vibration sensors to detect movement or impact and to estimate the location of the detected event. Sensors that are close to the event will record a larger amount of energy than the sensors that are farther away, so comparing the signals of several sensors can approximately establish the event location. In this way, vibration sensors might be used to monitor activity in a building without the use of intrusive cameras. The accuracy of location estimates can be greatly affected by the relative positions of the sensors and the event. Generally, location estimates tend to be most accurate if the sensors closely surround the event, and less accurate if the event is outside of the sensor zone. These principles are useful, but not precise. Given a framework for how event energy and noise are picked up by the sensors, the Cramér-Rao bound (CRB) is a formula for the achievable accuracy of location estimates. I demonstrate that the CRB is usefully similar to the location estimate accuracy from experimental data collected from a volunteer walking through a sensor-rigged hallway. I then show how CRB computations may be used to find an optimal arrangement of sensors. The match between the CRB and the accuracy of the experiments suggests that the sensor layout that optimizes the CRB will also provide accurate location estimates in a real building. The other main topic is how the vibrations of a structure can be understood through the structure's natural vibration frequencies and corresponding vibration shapes, called the "modes" of the structure. I connect vibration modes to the abstract framework of "nonlinear eigenvalue problems" (NLEVPs). An NLEVP is a square matrix-valued function for which one wants to find the inputs that make the matrix singular. But these singular matrices are usually isolated---% distributed among the infinitely many matrices of the NLEVP in places that are difficult to predict. After discussing NLEVPs in general and some methods for solving them, I show how the vibration modes of certain structures can be represented by the solutions of NLEVPs. The structures I analyze are multi-body structures that are made of simple interconnected pieces, such as elastic strings strung together into a spider web. Once a multi-body structure has been cast into the NLEVP form, an NLEVP solver can be used to find the vibration modes. Finally, I demonstrate that this method can be computationally faster than many traditional modal analysis techniques.

京都大学 / 新制・課程博士 / 博士(人間・環境学) / 甲第25365号 / 人博第1107号 / 京都大学大学院人間・環境学研究科共生人間学専攻 / (主査)教授 足立 匡義, 教授 上木 直昌, 教授 角 大輝, 教授 峯 拓矢 / 学位規則第4条第1項該当 / Doctor of Human and Environmental Studies / Kyoto University / DFAM

Dynamical systems are a commonly used and studied tool for simulation, optimization and design. In many applications such as inverse problem, optimal control, shape optimization and uncertainty quantification, those systems typically depend on a parameter. The need for high fidelity in the modeling stage leads to large-scale parametric dynamical systems. Since these models need to be simulated for a variety of parameter values, the computational burden they incur becomes increasingly difficult. To address these issues, parametric reduced models have encountered increased popularity in recent years. We are interested in constructing parametric reduced models that represent the full-order system accurately over a range of parameters. First, we define a global joint error mea- sure in the frequency and parameter domain to assess the accuracy of the reduced model. Then, by assuming a rational form for the reduced model with poles both in the frequency and parameter domain, we derive necessary conditions for an optimal parametric reduced model in this joint error measure. Similar to the nonparametric case, Hermite interpolation conditions at the reflected images of the poles characterize the optimal parametric approxi- mant. This result extends the well-known interpolatory H2 optimality conditions by Meier and Luenberger to the parametric case. We also develop a numerical algorithm to construct locally optimal reduced models. The theory and algorithm are data-driven, in the sense that only function evaluations of the parametric transfer function are required, not access to the internal dynamics of the full model. While this first framework operates on the continuous function level, assuming repeated transfer function evaluations are available, in some cases merely frequency samples might be given without an option to re-evaluate the transfer function at desired points; in other words, the function samples in parameter and frequency are fixed. In this case, we construct a parametric reduced model that minimizes a discretized least-squares error in the finite set of measurements. Towards this goal, we extend Vector Fitting (VF) to the parametric case, solving a global least-squares problem in both frequency and parameter. The output of this approach might lead to a moderate size reduced model. In this case, we perform a post- processing step to reduce the output of the parametric VF approach using H2 optimal model reduction for a special parametrization. The final model inherits the parametric dependence of the intermediate model, but is of smaller order. A special case of a parameter in a dynamical system is a delay in the model equation, e.g., arising from a feedback loop, reaction time, delayed response and various other physical phenomena. Modeling such a delay comes with several challenges for the mathematical formulation, analysis, and solution. We address the issue of transient behavior for scalar delay equations. Besides the choice of an appropriate measure, we analyze the impact of the coefficients of the delay equation on the finite time growth, which can be arbitrary large purely by the influence of the delay. / Ph. D. / Mathematical models play an increasingly important role in the sciences for experimental design, optimization and control. These high fidelity models are often computationally expensive and may require large resources, especially for repeated evaluation. Parametric model reduction offers a remedy by constructing models that are accurate over a range of parameters, and yet are much cheaper to evaluate. An appropriate choice of quality measure and form of the reduced model enable us to characterize these high quality reduced models. Our first contribution is a characterization of optimal parametric reduced models and an efficient implementation to construct them. While this first framework assumes we have access to repeated evaluations of the full model, in some cases merely measurement data might be available. In this case, we construct a parametric model that fits the measurements in a least squares sense. The output of this approach might lead to a moderate size reduced model, which we address with a post-processing step that reduces the model size while maintaining important properties. A special case of a parameter is a delay in the model equation, e.g., arising from a feedback loop, reaction time, delayed response and various other physical phenomena. While asymptotically stable solutions eventually vanish, they might grow large before asymptotic behavior takes over; this leads to the notion of transient behavior, which is our main focus for a simple class of delay equations. Besides the choice of an appropriate measure, we analyze the impact of the structure of the delay equation on the transient growth, which can be arbitrary large purely by the influence of the delay.

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.

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.

The interest in sustainable investing has increased significantly during recent years. Asset managers and institutional investors are urged to invest more sustainable from their stakeholders, reducing their investment universe. This thesis has found that sustainable investments have a different linear dependence structure compared to the regional markets in Europe and North America, but not in Asia-Pacific. However, the largest drawdowns of an sustainable compliant portfolio has historically been lower compared to the a random market portfolio, especially in Europe and North America. / Intresset för hållbara investeringar har ökat avsevärt de senaste åren. Fondförvaltare och institutionella investerare är, från deras intressenter, manade att investera mer hållbart vilket minskar förvaltarnas investeringsuniversum. Denna uppsats har funnit att hållbara investeringar har en beroendestruktur som är skild från de regionala marknaderna i Europa och Nordamerika, men inte för Asien-Stillahavsregionen. De största värdeminskningarna i en hållbar portfölj har historiskt varit mindre än värdeminskningarna från en slumpmässig marknadsportfölj, framförallt i Europa och Nordamerika.

In this digital age, it is more important than ever to have good methods for processing images. We focus on the removal of blur from a captured image, which is called the image deblurring problem. In particular, we make no assumptions about the blur itself, which is called a blind deconvolution. We approach the problem by miniming an energy functional that utilizes total variation norm and a fidelity constraint. In particular, we extend the work of Chan and Wong to use a reference image in the computation. Using the shock filter as a reference image, we produce a superior result compared to existing methods. We are able to produce good results on non-black background images and images where the blurring function is not centro-symmetric. We consider using a general Lp norm for the fidelity term and compare different values for p. Using an analysis similar to Strong and Chan, we derive an adaptive scale method for the recovery of the blurring function. We also consider two numerical methods in this disseration. The first method is an extension of Picards method for PDEs in the discrete case. We compare the results to the analytical Picard method, showing the only difference is the use of the approximation versus exact derivatives. We relate the method to existing finite difference schemes, including the Lax-Wendroff method. We derive the stability constraints for several linear problems and illustrate the stability region is increasing. We conclude by showing several examples of the method and how the computational savings is substantial. The second method we consider is a black-box implementation of a method for solving the generalized eigenvalue problem. By utilizing the work of Golub and Ye, we implement a routine which is robust against existing methods. We compare this routine against JDQZ and LOBPCG and show this method performs well in numerical testing.

在研究工作的範疇□，探討一件事物的因果關係時，考慮的變數太多，常是導致研究 效率無法提高的主因。而主成份分析與因子分析便是解決此種問題的主要方法；它們 最重要的功能，便是能將為數眾多的相關觀察變數，精簡成少數幾個互不相關的變數 ，而此少數的變數對原來的問題仍具有相當高的解釋能力。 然而，布進行精簡變數的過程中，取樣的多寡成了如何有效進行分析的經濟效益問題 。因此，本文最主要是研究，在某些控制條件之下，對所而樣本數之決定提出參考的 依據。在此，因其變異矩陣（Σ）為因子分析模型中主要關鍵所在，而其固有值（E- igenvalue ）為主要成份的判足依據，所以在控制型Ｉ誤差（α），對所有固有值均 相等進行檢足時，若達到預定檢定力，則可控制樣本數的大小；也就是當重要因素出 現時，能夠很可靠的挑選出來。 本文預計分五章討論，如下： 第一章緒論：將詳述研究動機、目的、限制及結構。 第二章因子分析模型之原理：將介紹因子分析的主要理論與特質，並導出對主要成份 選取之有關檢定。 第三章樣本數之決定：利用上述檢定之檢定力函數，進而控制檢定力強弱以決定樣本 數與變數個數之關係。 第四章模擬分析。 第五章結論。