Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)
Title: Solving Linear Systems Via A Convex Hull Algorithm
Speaker: Bahman Kalantari, Rutgers University (Computer Science)
Date: Thursday, November 15, 2012 5:00pm
Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We present new iterative algorithms for solving a square linear system Ax=b in dimension n by employing the Triangle Algorithm [BK2012], a fully polynomial-time approximation scheme for testing if the convex hull of a finite set of points in a Euclidean space contains a given point. By converting Ax=b into a convex hull problem and solving via the Triangle Algorithm, together with a sensitivity theorem, we compute in O(n^2 epsilon^{-2}) arithmetic operations an approximate solution where the Euclidean norm of the residual is bounded above by epsilon times the maximum of the Euclidean norm of b and those of the columns of A. In another approach we apply the Triangle Algorithm incrementally, solving a sequence of convex hull problems while repeatedly employing a distance duality. We compare the two methods. The simplicity and theoretical complexity bounds of the proposed algorithms, requiring no structural restrictions on the matrix A, suggest their potential practicality, offering alternatives to the existing exact and iterative methods, especially for large scale systems. The assessment of computational performance however is the subject of future experimentations.