Finding a block upper trapezoidal form of a rectangular matrix

where the A_ii have dimensions m _i x n _i, m _i ≥ n _i for each 1 ≤ i ≤ k . This algorithm extends the work of I. S. Duff and J. K. Reid who have provided algorithms and codes in the Harwell sparse matrix package MA28 , for block triangularizing square matrices.

A special case of the block upper trapezoidal form, called the dual angular form, is discussed and an algorithm presented to find a permutation matrix which may be incorporated into the equation above to yield a pexrmutation of A to dual angular form as shown next (Chart on document)

where the A_ii have dimensions m_i x n_i , m _i ≥ n _i , for each 1 ≤ i ≤ k . Each of these two forms facilitate the block orthogonal decomposition of sparse matrices involved in least squares computations.

The first two appendices contain examples showing permutations of sparse rectangular matrices to block upper trapezoidal form. FORTRAN codes of the main program and of subroutines used to implement these algorithms are given in the remaining appendices.