In this dissertation, we present several new graph-based techniques for solving numerical problems involving sparse matrices. Using support theory, we construct preconditioners for stiffness matrices of 2-dimensional trusses. The construction is based on the fretsaw extension technique of Shklarski and Toledo. These pre-conditioners yield an algorithm for solving linear systems of force equations on an n-element truss to within relative error epsilon in time O&d5; (n5/4 log(1/epsilon)). For an M-matrix M of size n x n with m nonzero entries, along with a width-2 factorization of M, we show how to find a diagonal matrix D such that DMD is diagonally dominant, by solving O&d5; (log n) diagonally-dominant linear systems. Using the nearly linear time algorithm of Spielman and Teng to solve the diagonally-dominant linear systems, we obtain an algorithm for solving a linear system in an M-matrix to within relative error epsilon in time O&d5; (m log(1/epsilon)). We establish that approximate solvers may be used in interior point methods to efficiently solve linear programs, and that this technique yields the fastest known algorithms for certain network flow problems. Using the Spielman-Teng solver inside an interior-point algorithm, we can solve the standard maximum flow and minimum-cost flow problems exactly on a graph with m edges, in time O&d5; (m3/2). For generalized flow problems, in which flow may be lost along the graph edges, each interior-point iteration requires the solution of a linear system in an M-matrix. Using our M-matrix algorithm for the interior-point iterations, we may solve the generalized versions of maximum flow and minimum-cost flow problems to within additive error epsilon in time O&d5; (m3/2 log2(1/epsilon)). Finally, we look at applying graph-based algorithms to numerical vector data with no inherent graph structure. We describe novel techniques for constructing sparse graphs that capture relationships among the data. We show that these graphs may be efficiently computed, and that the graphs yield competitive results when used in machine learning algorithms to solve classification, regression, and clustering problems.
