Partial Orthogonalization in Linear Algebra and Linear Programming
Knarik Tunyan, 7.4.2006
A significant part of practical problems employs a variety of numerical
methods of linear algebra and linear programming, such as inverting
matrices, solving systems of linear equations, least squares problems, and
optimization problems.
Based on the concept of partial orthogonality, some fundamental methods in
linear algebra and linear programming are modified, which can provide
computational savings and/or allow to obtain an improved solution, compared
to the existing algorithms. Namely, our approach to the linear least squares
problem allows decomposing it into simpler sub-problems, yielding
computational efficiency in comparison with the algorithms using the
Gram-Schmidt and the Householder transformations. For the problem of
finding both accurate and sparse solution we obtain better results, compared
to the existing methods. We also investigate the simplex method of interior
points which combines the desirable theoretical properties of interior point
methods and practical advantages of the simplex method.