رکورد قبلیرکورد بعدی

" Matrix Balancing in Lp Norms "


Document Type : Latin Dissertation
Language of Document : English
Record Number : 905594
Doc. No : TL3847b5dr
Main Entry : Yousefi, Arman
Title & Author : Matrix Balancing in Lp Norms\ Yousefi, ArmanOstrovsky, Rafail
College : UCLA
Date : 2017
student score : 2017
Abstract : Matrix balancing is a preprocessing step in linear algebra computations such as the computation of eigenvalues of a matrix. Such computations are known to be numerically unstable if the matrix is unbalanced, that is the L2 norm of some rows and their corresponding columns are different by orders of magnitude. Given an unbalanced matrix A, the goal of matrix balancing is to find an invertible diagonal matrix D such that DAD^{−1} is balanced or approximately balanced in the sense that every row and its corresponding column have the same norm. In thesis, we study a classic iterative algorithm for matrix balancing due to Osborne (1960). The original algorithm was proposed for balancing rows and columns in the L2 norm, and it works by iterating over balancing a row-column pair in fixed round-robin order. Variants of the algorithm for other norms have been heavily studied and are implemented as standard preconditioners in many numerical linear algebra packages. Despite the popularity of Osborne’s algorithm in practice and extensive research on it there were no polynomial-time upper bound on the running time of this algorithm to explain the excellent performance of this algorithm in practice. Recently (in 2015), Schulman and Sinclair, in a first result of its kind for any norm, analyzed the rate of convergence of a variant of Osborne’s algorithm that uses the L∞ norm and a different order of choosing row-column pairs. In this thesis we study matrix balancing in the L1 norm and other Lp norms. We consider two notions of approximately balancing matrices and refer to them as ε-balancing and strict ε-balancing. As the names suggest strict ε-balancing implies ε-balancing. These notions will be defined in the body of the thesis.We prove upper bounds on the convergence rate of Osborne’s algorithm and some of its vari- ants. We prove fast convergence of different variants of the algorithm to an ε-balanced matrix, and propose a variant that converges to a strictly ε-balanced matrix in polynomial time. These results resolve a problem that has been open since Osborne proposed his algorithm in 1960. The following is a summary of our results for any real matrix A = (a_{ij})_{i,j}:1. We propose a simple greedy variant of Osborne’s algorithm and show that it converges to an ε-balanced matrix in K = O(min{ε^{−2} log w, ε^{−1}n^{3/2} log(w/ε)}) iterations that cost a total of O(m + Kn log n) arithmetic operations over O(n log(w/ε))-bit numbers. Here m is the number of non-zero entries of A, and w = \sum_{i,j} |a_{ij} |/a_{min} with a_{min}= min{|a_{ij} | : a_{ij} ̸= 0}.2. We show that the original round-robin implementation of Osborne’s algorithm converges to an ε-balanced matrix in O(ε^{−2}n^2 log w) iterations totaling O(ε^{−2}mn log w) arithmetic operations over O(n log(w/ε))-bit numbers.3. We devise a random implementation of the iteration and show that it converges to an ε-balanced matrix in O(ε^{−2} log w) iterations using O(m + ε^{−2}n log w) arithmetic operations over O(log(wn/ε))-bit numbers.4. We propose a variant of Osborne’s algorithm and prove that it converges to a strictly ε-balanced matrix in O (ε^{−2}n^9 log(wn/ε) log w/ log n) iterations that requireO (ε^{−2}n^10 log(wn/ε) log w/ log n) arithmetic operations over O(n log w/ε)-bit numbers.5. We demonstrate a lower bound of Ω(1/\sqrt{ε}) on the convergence rate of any implementation of the iteration. Thus, the dependence of our upper bounds on 1/ε is in the right ballpark.All our results are proved for balancing in L1 norm, but we observe, through a known trivial reduction, that our results for L1 balancing apply to any Lp norm for all finite p, at the cost of increasing the number of iterations by only a factor of p (or p2 in some cases).
Added Entry : Ostrovsky, Rafail
Added Entry : UCLA
کپی لینک

پیشنهاد خرید
پیوستها
عنوان :
نام فایل :
نوع عام محتوا :
نوع ماده :
فرمت :
سایز :
عرض :
طول :
3847b5dr_14063.pdf
3847b5dr.pdf
پایان نامه لاتین
متن
application/pdf
471.51 KB
85
85
نظرسنجی
نظرسنجی منابع دیجیتال

1 - آیا از کیفیت منابع دیجیتال راضی هستید؟