Comparison of two pivotal strategies in sparse plane rotations

Resumé

Let the rectangular matrix A be large and sparse. Assume that plane rotations are used to decompose A into RDS where R^T R = I, D is a diagonal and S is upper triangular. Both column and row interchanges have to be used in order to preserve the sparsity of matrix A during the decomposition. It is proved that H the column interchanges are fixed, then the number of non-zero elements in S does not depend on the row interchanges used. However, this does not mean that the computational work is also independent of the row interchanges. Two pivotal strategies, where the same rule is used in the choice of pivotal columns, are described and compared. It is verified (by many numerical examples) that if matrix A is not very sparse, then one of these strategies will often perform better than the other both with regard to the storage and the computing time. The accuracy and the robustness of the computations are also discussed.