Row-Action Methods for Huge and Sparse Systems and Their Applications

This paper brings together and discusses theory and applications of methods, identified and labelled as row-action methods, for linear feasibility problems (find $x \in {{\bf R}^n $, such that $Ax \leqq b$), linearly constrained optimization problems (minimize $f(x)$, subject to $Ax \leqq b$) and some interval convex programming problems (minimize $f(x)$, subject to $c \leqq Ax \leqq b$). The main feature of row-action methods is that they are iterative procedures which, without making any changes to the original matrix A, use the rows of A, one row at a time. Such methods are important and have demonstrated effectiveness for problems with large or huge matrices which do not enjoy any detectable or usable structural pattern, apart from a high degree of sparaseness. Fields of application where row-action methods are used in various ways include image reconstruction from projection, operations research and game theory, learning theory, pattern recognition and transportation theory. A row-action method for the nonlinear convex feasibility problem is also presented.