This thesis demonstrates an efficient parallel method of solving the generalized eigenvalue problem, KΦ = M ΦΛ, where K is symmetric and M is symmetric positive-definite, by first converting it to a standard eigenvalue problem, solving the standard eigenvalue problem, and back-transforming the results. An abstraction for parallel dense linear algebra is introduced along with a new algorithm for forming A := U⁻ᵀ K U⁻¹ , where U is the Cholesky factor of M , that is up to twice as fast as the ScaLAPACK implementation. Additionally, large improvements over the PBLAS implementations of general matrix-matrix multiplication and triangular solves with many right-hand sides are shown. Significant performance gains are also demonstrated for Cholesky factorizations, and a case is made for using 2D-cyclic distributions with a distribution blocksize of one. / text

Yes / Beamforming in multi-user MIMO (MU-MIMO) systems is a vital part of modern wireless communication systems. Researchers looking for best operational performance normally optimize the problem and then solve for best weight solutions. The weight optimization problem contains variables in numerator and dominator: this leads to so-called variable coupling, making the problem hard to solve. Formulating the optimization in terms of the signal to leakage and noise ratio (SLNR) helps in decoupling the problem variables. In this paper we study the performance of the SLNR with variable numbers of users and handset antennas. The results show that there is an optimum and the capacity curve is a concave over these two parameters. The performances of two further variations of this method are also considered.

Symmetric generalized eigenvalue problems arise in many physical applications and frequently only a few of the eigenpairs are of interest. Typically, the problems are large and sparse, and therefore traditional methods such as the QZ algorithm may not be considered. Moreover, it may be impractical to apply shift-and-invert Lanczos, a favored method for problems of this type, due to difficulties in applying the inverse of the shifted matrix. With these difficulties in mind, Golub and Ye developed an inverse free Krylov subspace algorithm for the symmetric generalized eigenvalue problem. This method does not rely on shift-and-invert transformations for convergence acceleration, but rather a preconditioner is used. The algorithm suffers, however, in the presence of multiple or clustered eigenvalues. Also, it is only applicable to the location of extreme eigenvalues. In this work, we extend the method of Golub and Ye by developing a block generalization of their algorithm which enjoys considerably faster convergence than the usual method in the presence of multiplicities and clusters. Preconditioning techniques for the problems are discussed at length, and some insight is given into how these preconditioners accelerate the method. Finally we discuss a transformation which can be applied so that the algorithm extracts interior eigenvalues. A preconditioner based on a QR factorization with respect to the B-1 inner product is developed and applied in locating interior eigenvalues.

Longitudinal data analysis is common in biomedical research area. Generalized estimating equations (GEE) approach is widely used for longitudinal marginal models. The GEE method is known to provide consistent regression parameter estimates regardless of the choice of working correlation structure, provided the square root of n consistent nuisance parameters are used. However, it is important to use the appropriate working correlation structure in small samples, since it improves the statistical efficiency of β estimate. Several working correlation selection criteria have been proposed (Rotnitzky and Jewell, 1990; Pan, 2001; Hin and Wang, 2009; Shults et. al, 2009). However, these selection criteria have the same limitation in that they perform poorly when over-parameterized structures are considered as candidates. In this dissertation, new working correlation selection criteria are developed based on generalized eigenvalues. A set of generalized eigenvalues is used to measure the disparity between the bias-corrected sandwich variance estimator under the hypothesized working correlation matrix and the model-based variance estimator under a working independence assumption. A summary measure based on the set of the generalized eigenvalues provides an indication of the disparity between the true correlation structure and the misspecified working correlation structure. Motivated by the test statistics in MANOVA, three working correlation selection criteria are proposed: PT (Pillai's trace type criterion),WR (Wilks' ratio type criterion) and RMR (Roy's Maximum Root type criterion). The relationship between these generalized eigenvalues and the CIC measure is revealed. In addition, this dissertation proposes a method to penalize for the over-parameterized working correlation structures. The over-parameterized structure converges to the true correlation structure, using extra parameters. Thus, the true correlation structure and the over-parameterized structure tend to provide similar variance estimate of the estimated β and similar working correlation selection criterion values. However, the over-parameterized structure is more likely to be chosen as the best working correlation structure by "the smaller the better" rule for criterion values. This is because the over-parameterization leads to the negatively biased sandwich variance estimator, hence smaller selection criterion value. In this dissertation, the over-parameterized structure is penalized through cluster detection and an optimization function. In order to find the group ("cluster") of the working correlation structures that are similar to each other, a cluster detection method is developed, based on spacings of the order statistics of the selection criterion measures. Once a cluster is found, the optimization function considering the trade-off between bias and variability provides the choice of the "best" approximating working correlation structure. The performance of our proposed criterion measures relative to other relevant criteria (QIC, RJ and CIC) is examined in a series of simulation studies.

Directional wave-field decomposition for heterogeneousanisotropic media with in-stantaneous response is establishedfor both the acoustic and the electromagnetic equations. We derive a sufficient condition for ellipticity of thesystem's matrix in the Laplace domain and show that theconstruction of the splitting matrix via a Dunford-Taylorintegral over the resolvent of the non-compact, non-normalsystem's matrix is well de ned. The splitting matrix also hasproperties that make it possible to construct the decompositionwith a generalized eigenvector procedure. The classical way ofobtaining the decomposition is equivalent to solving analgebraic Riccati operator equation. Hence the proceduredescribed above also provides a solution to the algebraicRiccati operator equation. The solution to the wave-field decomposition for theisotropic wave equation is expressed in terms of theDirichlet-to-Neumann map for a plane. The equivalence of thisDirichlet-to-Neumann map is the acoustic admittance, i.e. themapping between the pressure and the particle velocity. Theacoustic admittance, as well as the related impedance aresolutions to algebraic Riccati operator equations and are keyelements in the decomposition. In the electromagnetic case thecorresponding impedance and admittance mappings solve therespective algebraic Riccati operator equations and henceprovide solutions to the decomposition problem. The present research shows that it is advantageous toutilize the freedom implied by the generalized eigenvectorprocedure to obtain the solution to the decomposition problemin more general terms than the admittance/impedancemappings. The time-reversal approach to steer an acoustic wave eld inthe cavity and half space geometries are analyzed from aboundary control perspective. For the cavity it is shown thatwe can steer the field to a desired final configuration, withthe assumption of local energy decay. It is also shown that thetime-reversal algorithm minimizes a least square error forfinite times when the data are obtained by measurements. Forthe half space geometry, the boundary condition is expressedwith help of the wave-field decomposition. In the homogeneousmaterial case, the response of the time-reversal algorithm iscalculated analytically. This procedure uses the one-wayequations together with the decomposition operator.

<p>Directional wave-field decomposition for heterogeneousanisotropic media with in-stantaneous response is establishedfor both the acoustic and the electromagnetic equations.</p><p>We derive a sufficient condition for ellipticity of thesystem's matrix in the Laplace domain and show that theconstruction of the splitting matrix via a Dunford-Taylorintegral over the resolvent of the non-compact, non-normalsystem's matrix is well de ned. The splitting matrix also hasproperties that make it possible to construct the decompositionwith a generalized eigenvector procedure. The classical way ofobtaining the decomposition is equivalent to solving analgebraic Riccati operator equation. Hence the proceduredescribed above also provides a solution to the algebraicRiccati operator equation.</p><p>The solution to the wave-field decomposition for theisotropic wave equation is expressed in terms of theDirichlet-to-Neumann map for a plane. The equivalence of thisDirichlet-to-Neumann map is the acoustic admittance, i.e. themapping between the pressure and the particle velocity. Theacoustic admittance, as well as the related impedance aresolutions to algebraic Riccati operator equations and are keyelements in the decomposition. In the electromagnetic case thecorresponding impedance and admittance mappings solve therespective algebraic Riccati operator equations and henceprovide solutions to the decomposition problem.</p><p>The present research shows that it is advantageous toutilize the freedom implied by the generalized eigenvectorprocedure to obtain the solution to the decomposition problemin more general terms than the admittance/impedancemappings.</p><p>The time-reversal approach to steer an acoustic wave eld inthe cavity and half space geometries are analyzed from aboundary control perspective. For the cavity it is shown thatwe can steer the field to a desired final configuration, withthe assumption of local energy decay. It is also shown that thetime-reversal algorithm minimizes a least square error forfinite times when the data are obtained by measurements. Forthe half space geometry, the boundary condition is expressedwith help of the wave-field decomposition. In the homogeneousmaterial case, the response of the time-reversal algorithm iscalculated analytically. This procedure uses the one-wayequations together with the decomposition operator.</p>

京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第18400号 / 情博第515号 / 新制||情||91(附属図書館) / 31258 / 京都大学大学院情報学研究科数理工学専攻 / (主査)准教授 辻本 諭, 教授 中村 佳正, 教授 梅野 健 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

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.

In this thesis, we study the relationship between the generalized eigenvalue problem (GEP) $Ax=\lambda Bx$, and systems of differential equations. We examine both the Jordan canonical form and Kronecker's canonical form (KCF). The first part of this work provides an introduction to the fundamentals of generalized eigenvalue problems and methods for solving this problem. We discuss the QZ algorithm, which can be used to determine the generalized eigenvalues and also how it can be implemented on MATLAB with the built in function 'eig'.  One essential facet of this work is the exploration of symmetric matrix pencils, which arise when A and B are both symmetric matrices. Furthermore we discuss discrete velocity models (DVMs) focusing specifically on a 12-velocity model on the plane. The results obtained are then applied to half-space problems for discrete velocity models, with a focus on planar stationary systems.

L'optimisation topologique vise à concevoir une structure en recherchant la disposition optimale du matériau dans un espace de conception donné, permettant ainsi de proposer des designs optimaux innovants. Cette thèse est centrée sur l'optimisation topologique pour des problèmes de conception de structures prenant en compte des contraintes de flambage. Dans une large variété de domaines de l'ingénierie, la conception innovante de structures est cruciale. L'allègement des structures lors la phase de conception tient une place prépondérante afin de réduire les coûts de fabrication. Ainsi l'objectif est souvent la minimisation de la masse de la structure à concevoir. En ce qui concerne les contraintes, en plus des contraintes mécaniques classiques (compression, tension), il est nécessaire de prendre en compte des phénomènes dits de flambage, qui se caractérisent par une amplification des déformations de la structure et une potentielle annihilation des capacités de la structure à supporter les efforts appliqués. Dans le but d'adresser un large panel de problèmes d'optimisation topologique, nous considérons les deux types de représentation d'une structure : les structures treillis et les structures continues. Dans le cadre de structures treillis, l'objectif est de minimiser la masse en optimisant le nombre d'éléments de la structure et les dimensions des sections transversales associées à ces éléments. Nous considérons les structures constituées d'éléments poutres et nous introduisons une formulation du problème comme un problème d'optimisation non-linéaire en variables mixtes. Afin de prendre en compte des contraintes de manufacturabilité, nous proposons une fonction coût combinant la masse et la somme des seconds moments d'inertie de chaque poutre. Nous avons développé un algorithme adapté au problème d'optimisation considéré. Les résultats numériques montrent que l'approche proposée mène à des gains de masses significatifs par rapport à des approches existantes. Dans le cas des structures continues, l'optimisation topologique vise à discrétiser le domaine de conception et à déterminer les éléments de ce domaine discrétisé qui doivent être composés de matière, définissant ainsi un problème d'optimisation discret. [...] / Topology optimization aims to design a structure by seeking the optimal material layout within a given design space, thus making it possible to propose innovative optimal designs. This thesis focuses on topology optimization for structural problems taking into account buckling constraints. In a wide variety of engineering fields, innovative structural design is crucial. The lightening of structures during the design phase holds a prominent place in order to reduce manufacturing costs. Thus the goal is often the minimization of the mass of the structure to be designed. Regarding the constraints, in addition to the conventional mechanical constraints (compression, tension), it is necessary to take into account buckling phenomena which are characterized by an amplification of the deformations of the structure and a potential annihilation of the capabilities of the structure to support the applied efforts. In order to adress a wide range of topology optimization problems, we consider the two types of representation of a structure: lattice structures and continuous structures. In the framework of lattice structures, the objective is to minimize the mass by optimizing the number of elements of the structure and the dimensions of the cross sections associated to these elements. We consider structures constituted by a set of frame elements and we introduce a formulation of the problem as a mixed-integer nonlinear problem. In order to obtain a manufacturable structure, we propose a cost function combining the mass and the sum of the second moments of inertia of each frame. We developed an algorithm adapted to the considered optimization problem. The numerical results show that the proposed approach leads to significant mass gains over existing approaches. In the case of continuous structures, topology optimization aims to discretize the design domain and to determine the elements of this discretized domain that must be composed of material, thus defining a discrete optimization problem. [...]