Open AccessComparison of two pivotal strategies in sparse plane rotations
Author(s) -
Zahari Zlatev
Publication year - 1980
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v9i122.6540
Subject(s) - diagonal , robustness (evolution) , computation , column (typography) , algorithm , matrix (chemical analysis) , sparse matrix , mathematics , plane (geometry) , diagonal matrix , triangular matrix , main diagonal , combinatorics , computer science , geometry , pure mathematics , physics , biochemistry , chemistry , materials science , connection (principal bundle) , quantum mechanics , invertible matrix , gaussian , composite material , gene
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.