Date of Degree

6-2017

Document Type

Dissertation

Degree Name

Ph.D.

Program

Mathematics

Advisor

Victor Pan

Committee Members

Christina Sormani

Christina Zamfirescu

Subject Categories

Numerical Analysis and Computation

Keywords

Low-rank Approximation, Gaussian Elimination, Neural Network

Abstract

Randomization of matrix computations has become a hot research area in the big data era. Sampling with randomly generated matrices has enabled fast algorithms to perform well for some most fundamental problems of numerical algebra with probability close to 1. The dissertation develops a set of algorithms with random and structured matrices for the following applications: 1) We prove that using random sparse and structured sampling enables rank-r approximation of the average input matrix having numerical rank r. 2) We prove that Gaussian elimination with no pivoting (GENP) is numerically safe for the average nonsingular and well-conditioned matrix preprocessed with a nonsingular and well-conditioned f-Circulant or another structured multiplier. This can be an attractive alternative to the customary Gaussian elimination with partial pivoting (GEPP). 3) By using structured matrices of a large family we compress large-scale neural networks while retaining high accuracy. The results of our extensive are in good accordance with those of our theoretical study.

Comments

A revised version was uploaded on July 2, 2018 with the approval of the dissertation committee chair and the Graduate Center.

Share

COinS