A New Algorithm for Solution of System of Linear Equations

Abstract

Systemsoflinearequationsareusedinavarietyoffields. Thecanonicalproblemofsolving a system of linear equations arises in numerous contexts in information theory, communication theory, and related fields. This thesis is aimed at analyzing the available methods for solving a system of linear equations of the form n x n. Using a couple of iterative and/or direct methods, implement a program for these methods that could be run for different dimension size n of system of linear equation . At the end, a graph can be plotted with time taken for execution of a method considered V/s dimension size n. In this contribution, we develop a solution that does not involve direct matrix inversion. The iterative nature of our approachallowsforadistributedmessage-passingimplementationofthesolutionalgorithm. We present test results which show that our solver achieves good results, both in terms of numerical accuracy as well as computing time. Furthermore, even very large systems (n≤ 1000) can be solved given a cluster with sufficient resources. We also address some properties of the algorithm, including convergence, exactness, its complexity order and relation to classical solution methods.