No description available.

As the dimension and the complexity of large interconnected systems grow, so does the necessity for decentralized control. One of the interesting challenges in the field of decentralized control is the arbitrary pole placement using output feedback. The feasibility of this problem depends solely on the identification of the decentralized fixed modes. As a matter of fact, if the system is free of fixed modes, then by increasing the controller’s order, any arbitrary closed loop poles can always be assigned. Due to this fact, reducing the controller’s order constitutes another interesting challenge when dealing with decentralization. This research describes the decentralized pole placement of linear systems. It is assumed that the internal structure of the system is unknown. The only access to the system is from a number of control stations. The decentralized controller consists of output feedback controllers each built at a control station. The research can be divided into two parts. In the first part, conditions for fixed modes existence as well as realization and stability of the overall system under decentralization are established using polynomial matrix algebra. The second part deals with the solution of decentralized pole placement problem, in particular, finding a decentralized controller which assigns some set of desired poles. The solution strategy is to reduce the controller’s order as much as possible using mathematical programming techniques. The idea behind this method is to start with a low order controller and then attempt to shift the poles of the closed loop system to the desired poles. / Ph. D. / incomplete_metadata

No description available.

Reducing the computing time of the matrix inversion has been a concern of many authors. The use of Systolic architectures containing orthogonally connected processing elements capable of few instructions multiple data have allowed for new algorithms to be implemented. Two algorithms are examined that rely on the triangularization methods for matrix inversion. One can be applied to the general non-singular matrix and the other to the symmetric matrix. The throughput in both implementation is revolutionized. The speed improvement over Liu and Young’s implementation of the symmetric matrix inversion is by a factor of three. The throughput in both implementation is revolutionized. The speed improvement over Liu and Young’s implementation of the symmetric matrix inversion is by a factor of three.

Cloud computing systems, like MapReduce and Pregel, provide a scalable and fault tolerant environment for running computations at massive scale. However, these systems are designed primarily for data intensive computational tasks, while a large class of problems in scientific computing and business analytics are computationally intensive (i.e., they require a lot of CPU in addition to I/O). In this thesis, we investigate the use of cloud computing systems, in particular MapReduce, for computationally intensive problems, focusing on two classic problems that arise in scienti c computing and also in analytics: maximum clique and matrix inversion. The key contribution that enables us to e ectively use MapReduce to solve the maximum clique problem on dense graphs is a recursive partitioning method that partitions the graph into several subgraphs of similar size and running time complexity. After partitioning, the maximum cliques of the di erent partitions can be computed independently, and the computation is sped up using a branch and bound method. Our experiments show that our approach leads to good scalability, which is unachievable by other partitioning methods since they result in partitions of di erent sizes and hence lead to load imbalance. Our method is more scalable than an MPI algorithm, and is simpler and more fault tolerant. For the matrix inversion problem, we show that a recursive block LU decomposition allows us to e ectively compute in parallel both the lower triangular (L) and upper triangular (U) matrices using MapReduce. After computing the L and U matrices, their inverses are computed using MapReduce. The inverse of the original matrix, which is the product of the inverses of the L and U matrices, is also obtained using MapReduce. Our technique is the rst matrix inversion technique that uses MapReduce. We show experimentally that our technique has good scalability, and it is simpler and more fault tolerant than MPI implementations such as ScaLAPACK.

The first part of the dissertation concerns the Ising problem proposed to Ernst Ising by his supervisor Wilhelm Lenz in the early 20s. The Ising model, or perhaps more correctly the Lenz-Ising model, tries to capture the behaviour of phase transitions, i.e. how local rules of engagement can produce large scale behaviour. Two decades later Lars Onsager solved the Ising problem for the quadratic lattice without an outer field. Using his ideas solutions for other lattices in two dimensions have been constructed. We describe a method for calculating the Ising partition function for immense square grids, up to linear order 320 (i.e. 102400 vertices). In three dimensions however only a few results are known. One of the most important unanswered questions is at which temperature the Ising model has its phase transition. In this dissertation it is shown that an upper bound for the critical coupling Kc, the inverse absolute temperature, is 0.29 for the tree dimensional cubic lattice. To be able to get more information one has to use different statistical methods. We describe one sampling method that can use simple state generation like the Metropolis algorithm for large lattices. We also discuss how to reconstruct the entropy from the model, in order to obtain parameters as the free energy. The Ising model gives a partition function associated with all finite graphs. In this dissertation we show that a number of interesting graph invariants can be calculated from the coefficients of the Ising partition function. We also give some interesting observations about the partition function in general and show that there are, for any N, N non-isomorphic graphs with the same Ising partition function. The second part of the dissertation is about matrix operations. We consider the problem of multiplying them when the entries are elements in a finite semiring or in an additively finitely generated semiring. We describe a method that uses O(n3 / log n) arithmetic operations. We also consider the problem of reducing n x n matrices over a finite field of size q using O(n2 / logq n) row operations in the worst case.

Cloud computing systems, like MapReduce and Pregel, provide a scalable and fault tolerant environment for running computations at massive scale. However, these systems are designed primarily for data intensive computational tasks, while a large class of problems in scientific computing and business analytics are computationally intensive (i.e., they require a lot of CPU in addition to I/O). In this thesis, we investigate the use of cloud computing systems, in particular MapReduce, for computationally intensive problems, focusing on two classic problems that arise in scienti c computing and also in analytics: maximum clique and matrix inversion. The key contribution that enables us to e ectively use MapReduce to solve the maximum clique problem on dense graphs is a recursive partitioning method that partitions the graph into several subgraphs of similar size and running time complexity. After partitioning, the maximum cliques of the di erent partitions can be computed independently, and the computation is sped up using a branch and bound method. Our experiments show that our approach leads to good scalability, which is unachievable by other partitioning methods since they result in partitions of di erent sizes and hence lead to load imbalance. Our method is more scalable than an MPI algorithm, and is simpler and more fault tolerant. For the matrix inversion problem, we show that a recursive block LU decomposition allows us to e ectively compute in parallel both the lower triangular (L) and upper triangular (U) matrices using MapReduce. After computing the L and U matrices, their inverses are computed using MapReduce. The inverse of the original matrix, which is the product of the inverses of the L and U matrices, is also obtained using MapReduce. Our technique is the rst matrix inversion technique that uses MapReduce. We show experimentally that our technique has good scalability, and it is simpler and more fault tolerant than MPI implementations such as ScaLAPACK.

The Gaussian geostatistical model has been widely used in Bayesian modeling of spatial data. A core difficulty for this model is at inverting the n x n covariance matrix, where n is a sample size. The computational complexity of matrix inversion increases as O(n3). This difficulty is involved in almost all statistical inferences approaches of the model, such as Kriging and Bayesian modeling. In Bayesian inference, the inverse of covariance matrix needs to be evaluated at each iteration in posterior simulations, so Bayesian approach is infeasible for large sample size n due to the current computational power limit. In this dissertation, we propose two approaches to address this computational issue, namely, the auxiliary lattice model (ALM) approach and the Bayesian site selection (BSS) approach. The key feature of ALM is to introduce a latent regular lattice which links Gaussian Markov Random Field (GMRF) with Gaussian Field (GF) of the observations. The GMRF on the auxiliary lattice represents an approximation to the Gaussian process. The distinctive feature of ALM from other approximations lies in that ALM avoids completely the problem of the matrix inversion by using analytical likelihood of GMRF. The computational complexity of ALM is rather attractive, which increase linearly with sample size. The second approach, Bayesian site selection (BSS), attempts to reduce the dimension of data through a smart selection of a representative subset of the observations. The BSS method first split the observations into two parts, the observations near the target prediction sites (part I) and their remaining (part II). Then, by treating the observations in part I as response variable and those in part II as explanatory variables, BSS forms a regression model which relates all observations through a conditional likelihood derived from the original model. The dimension of the data can then be reduced by applying a stochastic variable selection procedure to the regression model, which selects only a subset of the part II data as explanatory data. BSS can provide us more understanding to the underlying true Gaussian process, as it directly works on the original process without any approximations involved. The practical performance of ALM and BSS will be illustrated with simulated data and real data sets.

Weakness analysis based on grid strength assessment is useful for identifying potential weak grid issues. However, when taking into account the impact of the interactions among Renewable Energy Sources (RESs), the weakness analysis becomes computationally challenging. Different combinations of PointsofInterconnections (POIs) of RESs may have different impacts on grid strength at each POI. Due to the combination nature, such weakness analysis may be time-consuming when identifying the weakest combination of POIs from a large number of potential candidate locations in realistic power grids. This dissertation addresses the topic of determination of the weakest RESs combinations. Based on impedance ratios as a criterion, the dissertation shows that the impacts of impedance ratios magnitudes and angles are ‘quasi-mutually exclusive’. Such a concept is then used to reduce the computational burden with a fast screening algorithm. To further understand the impact of network components on grid strength, vector-based interaction analysis is developed based on the concepts of operational transfer impedances and operational interaction operators. In particular, this dissertation shows how mathematical models of interaction of multiple RESs can be simplified by replacing them with equivalent impedances, allowing us to simplify the mathematical expressions that quantify interactions among RESs. The conclusions and concepts established based on simplified models are statistically tested for their applicability to the generalized interaction model. The result would be a more simplified mathematical representation of interaction among RESs. Finally, a new technique is presented to efficiently update the Bus Impedance Matrix (Zbus) following changes in the series impedance of a branch. Conventionally, such update requires redundant recalculations, which involve matrix inversion operations (i.e., inverting the Bus Admittance Matrix, Ybus) and thus cause high computational burden because of potential matrix ill-conditioning, especially for largescale power grids. This dissertation overcomes these shortcomings by deriving an analytical expression for changes in Zbus in terms of its old elements and the variation of the impedance of a given branch. Hence, the computation overhead is comparatively small, and no issues arise due to the new Ybus being ill-conditioned. Such contribution helps facilitate real-time applications of methods that rely on Zbus.

No description available.