UC Berkeley

In this dissertation, we explore two problems involving large matrix computations. In the first half, we study the fast factorization of a large, sparse symmetric positive definite matrix and explain the underlying structures of the intermediate steps in the computation. Using these underlying structures, we present a new algorithm which takes advantage of these structures to reduce computational and memory costs. Our new algorithm is an improvement upon the well known and commonly used multifrontal method. We incorporate the use of fast structured computations to improve the algorithm as in [95, 92, 99].

In the second part of the dissertation, we explore a new algorithm for solving minimization problems of the form

min |Ax - b| s.t. |x| ₁ ≤ τ,

where A is a wide matrix. This problem is often referred to in some fields as the Lasso problem. We improve upon an existing method by making a simple modification. Then we prove that this method is locally linearly convergent under certain reasonable conditions.