×

Ordering algorithms for irreducible sparse linear systems. (English) Zbl 0786.90036

Summary: Ordinary algorithms aim to pre-order a matrix in order to achieve a favourable structure for factorization. Two prototype structures are described which are commonly aimed at by current algorithms. A different structure, based on a lower Hessenberg form, is introduced. We show that the common structures may be obtained from the Hessenberg form in a simple way. A fundamental and very simple algorithm is presented for deriving the lower Hessenberg form. This algorithm is inherently a part of other common algorithms, but is usually obscured by other detailed heuristics. Some of these heuristics are seen to correspond to different tie-break rules in the fundamental algorithm. We describe a particularly simple tie-break rule used in SPK1 [see M. A. Stadtherr and S. E. Wood, Comp. Chem. Eng. 8, 9-18 (1984)], which is effective and not at all well-known. Ordinary algorithms need to be modified to enable pivoting for numerical stability to be carried out. We describe how the idea of threshold pivoting can be used in the context of these algorithms. Most ordering algorithms in common use employ some sort of look-ahead to promote a favourable struture. It is argued that look-ahead is generally ineffective in practice, and that numerical evidence supports the use of very simple strategies. A new ordering algorithm is presented which aims to obtain a narrower bandwidth in the lower Hessenberg form. Some limited numerical experience is presented which enables us to draw tentative conclusions about various ordering strategies, and how they compare with those in common use.

MSC:

90C05 Linear programming

Software:

Algorithm 529
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] M. Arioli, I.S. Duff, N.I.M. Gould and J.K. Reid, The practical use of the Hellerman-Rarick P4 algorithm and the P5 algorithm of Erisman et al., A.E.R.E. Harwell Report CSS 213 (1987).
[2] M. Arioli and I.S. Duff, Experiments in tearing large sparse systems, A.E.R.E. Report CSS 217 (1988). · Zbl 0723.65025
[3] I.S. Duff, On algorithms for obtaining a maximum transversal, A.E.R.E. Report CSS 49 (1978).
[4] I.S. Duff and J.K. Reid, A comparison of sparsity orderings for obtaining pivotal sequences in Gaussian elimination, J. Inst. Math. Appl. 14(1974)281–291. · Zbl 0308.65021 · doi:10.1093/imamat/14.3.281
[5] I.S. Duff and J.K. Reid, Algorithm 529: Permutations to block triangular form, ACM Trans. Math. Software 4(1978)189–192. · doi:10.1145/355780.355790
[6] I.S. Duff, A.M. Erisman and J.K. Reid,Direct Methods for Sparse Matrices (Oxford Science Publ., Oxford, 1986). · Zbl 0604.65011
[7] A.M. Erisman, R.G. Grimes, J.G. Lewis and W.G. Poole, A structurally stable modification of Hellerman-Rarick’s P4 algorithm for reordering unsymmetric sparse matrices, SIAM J. Numer. Anal. 22(1985)369–385. · Zbl 0586.65035 · doi:10.1137/0722022
[8] R. Fletcher and J.A.J. Hall, Towards reliable linear programming, in:Numerical Analysis 1989, ed. D.F. Griffiths and G.A. Watson, Pitman Research Notes in Mathematics 228 (Longman, Harlow, 1990).
[9] E. Hellerman and D.C. Rarick, The partitioned preassigned pivot procedure (P4), in:Sparse Matrices and their Applications, ed. D.J. Rose and R.A. Willoughby (Plenum Press, New York, 1972). · Zbl 0246.65022
[10] H.M. Markowitz, The elimination form of the inverse and its application to linear programming, Manag. Sci. 3(1957)255–269. · Zbl 0995.90592 · doi:10.1287/mnsc.3.3.255
[11] M.A. Stadtherr and S.E. Wood, Sparse matrix methods for equation based chemical process flowsheeting. I. Reordering phase, Comp. Chem. Eng. 8(1984)9–18. · doi:10.1016/0098-1354(84)80011-3
[12] M.A. Stadtherr and S.E. Wood, Sparse matrix methods for equation based chemical process flowsheeting. II. Numerical phase, Comp. Chem. Eng. 8(1984)19–33. · doi:10.1016/0098-1354(84)80012-5
[13] R.E. Tarjan, Depth first search and linear graph algorithms, SIAM J. Comput. 1(1972)146–160. · Zbl 0251.05107 · doi:10.1137/0201010
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.