Block-Partitioned Algorithms for Solving the Linear Least Squares Problem

. The linear least squares problem arises in many areas of sciences and engineerings. When the coefficient matrix has full rank, the solution can be obtained in a fast way by using QR factorization with BLAS-3. In contrast, when the matrix is rank-deficient, or the rank is unknown, other slower methods should be applied: the SVD or the complete orthogonal decompositions. The SVD gives more reliable determination of rank but is computationally more expensive. On the other hand, the complete orthogonal decomposition is faster and in practice works well. We present several new implementations for solving the linear least squares problem by means of the complete orthogonal decomposition that are faster than the algorithms currently included in LAPACK. Experimental comparison of our methods with the LAPACK implementations on a wide range of platforms (such as IBM RS/6000-370, SUN HyperSPARC, SGI R8000, DEC Alpha/AXP, HP 9000/715, etc.) show considerable performance improvements. Some of th..