Complexity and Numerical Stability in Matrix Computations and Nonconvex Optimization

In this dissertation, we study three problems in nonconvex optimization and matrix computation: rank-constrained hyperbolic programming, real and complex matrix multiplication, and complex matrix inversion. We study efficient algorithms that solve these problems. Here, we evaluate efficiency of algorithms in terms of both speed and accuracy. In terms of speed, we are looking for algorithms that use the least number of arithmetic operations. In terms of accuracy, we are looking for algorithms that induce the smallest rounding errors. Moreover, we will study the complexity of rank-constrained problems by understanding the NP-hardness of such problems.