O(n 3 ) g-inversion-free noniterative near-consistent linear system solver for minimum-norm least-squares and nonnegative solutions

Abstract

Presented here is an O(mn²) physically concise algorithm (solver) to obtain noniteratively a minimum-norm (m-) solution of the consistent under-/over-determined linear system Ax=b without computing any generalized inverse (g-inverse), where the matrix A is m × n. This m-solution is also the minimum-norm least-squares (mt-) solution of the consistent system. When the system is near-consistent/inconsistent, the algorithm can be used to obtain (i) the g-inversion-free mt-solution of the inconsistent system just by replacing A by A^tA and b by A^tb or (ii) the g-inversion-free mt-solution of a consistent system closest (in some sense) to the inconsistent system without modifying/premultiplying both sides of the system by A^t. It provides an in-built consistency check and an inconsistency index – a measure of degree of inconsistency, and the rank (that provides the information content of the system) of the matrix A. Further, if required, it can identify and prune/weed out redundant (linearly dependent) rows of (A, b), i.e., throw away redundant equations and convert A into a full row-rank matrix, thus potentially reducing the storage requirement, amount of computation and hence errors and computing time, while preserving the complete information of the contradiction-free system. In addition, the solver produces the unique projection operator P that projects the real n-dimensional space orthogonally onto the null space of A and that readily provides a means of computing any number of solutions desired. The solver also produces a relative error bound without computing any kind of g-inverse of A subject to a certain condition. It is also readily amenable to both error-free computation and parallel/vector implementation. In addition, it detects whether the system is unacceptable (excessively inconsistent) and prompts us to check the physical and the mathematical models for a possible reason and consequent correction before we continue further the solution process. A heuristic algorithm is presented, in which two of the outputs of the solver, viz., the solution vector and the projection operator are used as inputs for a nonnegative solution of the system noniteratively in O(mn²) operations.