Diagonally dominant matrices arise in many applications. In this work, we exploit the structure of diagonally dominant matrices to provide sharp entrywise relative perturbation bounds. We first generalize the results of Dopico and Koev to provide relative perturbation bounds for the LDU factorization with a well conditioned L factor. We then establish relative perturbation bounds for the inverse that are entrywise and independent of the condition number. This allows us to also present relative perturbation bounds for the linear system Ax=b that are independent of the condition number. Lastly, we continue the work of Ye to provide relative perturbation bounds for the eigenvalues of symmetric indefinite matrices and non-symmetric matrices.

No description available.

Matrix calculations underlie countless problems in science, mathematics, and engineering. When the involved matrices are highly structured, displacement operators can be used to accelerate fundamental operations such as matrix-vector multiplication. In this thesis, we provide an introduction to the theory of displacement operators and study the interplay between displacement and natural matrix constructions involving direct sums, Kronecker products, and blocking. We also investigate the algebraic behavior of displacement operators, developing results about invertibility and kernels.

The process of factorizing a symmetric matrix using the Cholesky (LLT ) or indefinite (LDLT ) factorization of A allows the efficient solution of systems Ax = b when A is symmetric. This thesis describes the development of new serial and parallel techniques for this problem and demonstrates them in the setting of interior point methods. In serial, the effects of various scalings are reported, and a fast and robust mixed precision sparse solver is developed. In parallel, DAG-driven dense and sparse factorizations are developed for the positive definite case. These achieve performance comparable with other world-leading implementations using a novel algorithm in the same family as those given by Buttari et al. for the dense problem. Performance of these techniques in the context of an interior point method is assessed.

La méthode de factorisation est appliquée sur les données initiales d'un problème de mécanique quantique déja résolu. Les solutions (états propres et fonctions propres) sont presque tous retrouvés. / The factorization methode is applied to the initial data of an already solved quantum mechanics problem. The solutions (eigenfunctions and eigenvalues) are almost all rederived.

Since some of the location of where the users posted their tweets collected by social media company have varied accuracy, and some are missing. We want to use those tweets with highest accuracy to help fill in the data of those tweets with incomplete information. To test our algorithm, we used the sets of social media data from a city, we separated them into training sets, where we know all the information, and the testing sets, where we intentionally pretend to not know the location. One prediction method that was used in (Dukler, Han and Wang, 2016) requires appending one-hot encoding of the location to the bag of words matrix to do Location Oriented Nonnegative Matrix Factorization (LONMF). We improve further on this algorithm by introducing iterative LONMF. We found that when the threshold and number of iterations are chosen correctly, we can predict tweets location with higher accuracy than using LONMF.

Intellectual property has gained more attention in recent decades because innovations have become one of the most important resources. This paper implements a probabilistic topic model using nonnegative matrix factorization (NMF) to discover some of the key elements in computer patent, as the industry grew from 1990 to 2009. This paper proposes a new “shrinking model” based on NMF and also performs a close examination of some variations of the base model. Note that rather than studying the strategy to pick the optimized number of topics (“rank”), this paper is particularly interested in which factorization (including different kinds of initiation) methods are able to construct “topics” with the best quality given the predetermined rank. Performing NMF to the description text of patent features, we observe key topics emerge such as “platform” and “display” with strong presence across all years but we also see other short-lived significant topics such as “power” and “heat” which signify the saturation of the industry.

While it has been known for some time that connected non-bipartite graphs have unique prime factorizations over the direct product, the same cannot be said of bipartite graphs. This is somewhat vexing, as bipartite graphs do have unique prime factorizations over other graph products (the Cartesian product, for example). However, it is fairly easy to show that a connected bipartite graph has only one prime bipartite factor, which begs the question: is such a prime bipartite factor unique? In other words, although a connected bipartite graph may have multiple prime factorizations over the direct product, do such factorizations contain the same prime bipartite factor? It has previously been shown by Hammack that when the prime bipartite factor is K_2, this is in fact true. The goal of this paper is to prove that this is in fact true for any prime bipartite factor, provided the graph being factored is R-thin. The proof of the main result takes the same initial approach as the proof by Hammack, before moving into new territory in order to prove the final result.

The aim of the thesis is to desribe and implement the elliptic curve factorization method using curves in Edwards form. The thesis can be notionally divided into two parts. The first part deals with the theory of Edwards curves especially with properties of elliptic function fields. The second part deals with the factorization algorithm using Edwards form both formally and practically in the way the algorithm is really implemented. The contribution of this thesis is the enclosed implementation of the elliptic curve factorisation algorithm which can be run on a graphic card and which is faster than the state-of-the-art implementation GMP-ECM. Powered by TCPDF (www.tcpdf.org)

Master of Science / Department of Computing and Information Sciences / Daniel A. Anderson / Most of the e-commerce websites like Amazon, EBay, hotels, trip advisor etc. use recommender systems to recommend products to their users. Some of them use the knowledge of history/ of all users to recommend what kind of products the current user may like (Collaborative filtering) and some use the knowledge of the products which the user is interested in and make recommendations (Content based filtering). An example is Amazon which uses both kinds of techniques.. These recommendation systems can be represented in the form of a graph where the nodes are users and products and edges are between users and products. The aim of this project is to build a recommender system for recipes by using the data from allrecipes.com. Allrecipes.com is a popular website used all throughout the world to post recipes, review them and rate them. To understand the data set one needs to know how the recipes are posted and rated in allrecipes.com, whose details are given in the paper. The network of allrecipes.com consists of users, recipes and ingredients. The aim of this research project is to extensively study about two algorithms adsorption and matrix factorization, which are evaluated on homogeneous networks and try them on the heterogeneous networks and analyze their results. This project also studies another algorithm that is used to propagate influence from one network to another network. To learn from one network and propagate the same information to another network we compute flow (influence of one network on another) as described in [7]. The paper introduces a variant of adsorption that takes the flow values into account and tries to make recommendations in the user-recipe and the user-ingredient networks. The results of this variant are analyzed in depth in this paper.