Affiliations: [a] Department of Mathematical Sciences, Florida Institute of Technology, 150 West University Boulevard, Melbourne, Florida 32901-6975, USA | [b] Modeling, Simulation and Design Laboratory, School of Computer Science, McGill University, 3480 University Street, Montreal, Quebec, Canada H3A 2A7
Correspondence:
[*]
Corresponding author. S.K. Sen, E-mail: [email protected].
Abstract: Presented here is an O(mn2) 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 AtA and b by Atb 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 At. 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(mn2) operations.
