Solving Linear System of Equations Via A Convex Hull Algorithm

arXiv1210.7858MaRDI QIDQ6236763FDOQ6236763

Bahman Kalantari

Publication date: 29 October 2012

Abstract: We present new iterative algorithms for solving a square linear system $Ax=b$ in dimension $n$ by employing the {it Triangle Algorithm} cite{kal12}, 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 {it sensitivity theorem}, we compute in $O(n^{2}epsilo{n}^{-2})$ arithmetic operations an approximate solution satisfying $VertA{x}_{e}psilon-bVertleqepsilonho$, where $ho=maxVert{a}_{1}Vert,\mathrm{...},Vert{a}_{n}Vert,VertbVert$, and $a_i$ is the $i$-th column of $A$. In another approach we apply the Triangle Algorithm incrementally, solving a sequence of convex hull problems while repeatedly employing a {it distance duality}. 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 linear systems. The assessment of computational performance however is the subject of future experimentations.

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Linear programming (90C05) Iterative numerical methods for linear systems (65F10) Computational aspects related to convexity (52B55) Linear ordinary differential equations and systems (34A30) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20)

This page was built for publication: Solving Linear System of Equations Via A Convex Hull Algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6236763)