This paper discussed QR factorization algorithms for a special type of matrix arising from the application of the Tikhnov's regularization method to an ill-conditioned least squares problem. The matrix involved is half dense and half sparse. Householder transformation and the hybrid algorithm were implemented on iPSC/2 and iPSC/860 hypercubes. For a highly over-determined system, the row-oriented hybrid algorithm is faster than the column-oriented Householder transformation. The efficiency of the algorithms has been improved by overlapping communications with computations. BLAS routines are also used on iPSC/860 to enhance the performance of the algorithms.