國立虎尾科技大學 |

Matrix Balancing in Lp Norms.

紀錄類型:	書目-語言資料,手稿 : Monograph/item
正題名/作者:	Matrix Balancing in Lp Norms./
作者:	Yousefi, Arman.
面頁冊數:	1 online resource (61 pages)
附註:	Source: Dissertation Abstracts International, Volume: 79-04(E), Section: B.
Contained By:	Dissertation Abstracts International79-04B(E).
標題:	Computer science. -
電子資源:	click for full text (PQDT)
ISBN:	9780355396478

Matrix Balancing in Lp Norms.
Yousefi, Arman.

Matrix Balancing in Lp Norms. - 1 online resource (61 pages)

Source: Dissertation Abstracts International, Volume: 79-04(E), Section: B.

Thesis (Ph.D.)

Includes bibliographical references

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 L 2 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 Linfinity norm and a different order of choosing row-column pairs. In this thesis we study matrix balancing in the L1 norm and other L p norms. We consider two notions of approximately balancing matrices and refer to them as epsilon-balancing and strict epsilon-balancing . As the names suggest strict epsilon-balancing implies epsilon-balancing. These notions will be defined in the body of the thesis.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2018

Mode of access: World Wide Web

ISBN: 9780355396478Subjects--Topical Terms:

573171
Computer science.
Index Terms--Genre/Form:

554714
Electronic books.

Matrix Balancing in Lp Norms.
LDR:05167ntm a2200361Ki 4500 001 909930
005 20180426091050.5
006 m o u
007 cr mn||||a|a||
008 190606s2017 xx obm 000 0 eng d
020 $a 9780355396478
035 $a (MiAaPQ)AAI10638333
035 $a (MiAaPQ)ucla:16275
035 $a AAI10638333
040 $a MiAaPQ $b eng $c MiAaPQ
099 $a TUL $f hyy $c available through World Wide Web
100 1 $a Yousefi, Arman. $3 1180946
245 1 0 $a Matrix Balancing in Lp Norms.
264 0 $c 2017
300 $a 1 online resource (61 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertation Abstracts International, Volume: 79-04(E), Section: B.
500 $a Adviser: Rafail Ostrovsky.
502 $a Thesis (Ph.D.) $c University of California, Los Angeles $d 2017.
504 $a Includes bibliographical references
520 $a 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 L 2 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 Linfinity norm and a different order of choosing row-column pairs. In this thesis we study matrix balancing in the L1 norm and other L p norms. We consider two notions of approximately balancing matrices and refer to them as epsilon-balancing and strict epsilon-balancing . As the names suggest strict epsilon-balancing implies epsilon-balancing. These notions will be defined in the body of the thesis.
520 $a 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 epsilon-balanced matrix, and propose a variant that converges to a strictly epsilon-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 = (aij)ni,j = 1: 1. We propose a simple greedy variant of Osborne's algorithm and show that it converges to an epsilon-balanced matrix in K = O(min{epsilon--2 log w, epsilon --1n3/2 log(w/epsilon)}) iterations that cost a total of O(m + Kn log n) arithmetic operations over O( n log(w/epsilon))-bit numbers. Here m is the number of non-zero entries of A, and w = sum i,j |aij |/amin with amin = min{|aij | : aij ≠ 0}. 2. We show that the original round-robin implementation of Osborne's algorithm converges to an epsilon-balanced matrix in O(epsilon--2n 2 log w) iterations totaling O(epsilon --2mn log w) arithmetic operations over O(n log(w/epsilon))-bit numbers. 3. We devise a random implementation of the iteration and show that it converges to an epsilon-balanced matrix in O(epsilon --2 log w) iterations using O(m + epsilon--2n log w) arithmetic operations over O(log(wn/epsilon))-bit numbers. 4. We propose a variant of Osborne's algorithm and prove that it converges to a strictly epsilon-balanced matrix in O(epsilon --2n9 log(wn/epsilon) log w/ log n) iterations that require O(epsilon--2n10 log(wn/epsilon) log w/ log n) arithmetic operations over O(n log w/epsilon)-bit numbers. 5. We demonstrate a lower bound of O(1/√epsilon) on the convergence rate of any implementation of the iteration. Thus, the dependence of our upper bounds on 1/epsilon 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 p 2 in some cases).
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2018
538 $a Mode of access: World Wide Web
650 4 $a Computer science. $3 573171
650 4 $a Mathematics. $3 527692
655 7 $a Electronic books. $2 local $3 554714
690 $a 0984
690 $a 0405
710 2 $a ProQuest Information and Learning Co. $3 1178819
710 2 $a University of California, Los Angeles. $b Computer Science. $3 1180947
773 0 $t Dissertation Abstracts International $g 79-04B(E).
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10638333 $z click for full text (PQDT)