A comparison of three algorithms for reducing the profile of a sparse matrix

Alain Billionnet; Jean-François Brêteau

RAIRO - Operations Research - Recherche Opérationnelle (1989)

  • Volume: 23, Issue: 3, page 289-302
  • ISSN: 0399-0559

How to cite

top

Billionnet, Alain, and Brêteau, Jean-François. "A comparison of three algorithms for reducing the profile of a sparse matrix." RAIRO - Operations Research - Recherche Opérationnelle 23.3 (1989): 289-302. <http://eudml.org/doc/104965>.

@article{Billionnet1989,
author = {Billionnet, Alain, Brêteau, Jean-François},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {profile reduction; numerical examples; heuristic algorithms; sparse matrix; interval graph},
language = {eng},
number = {3},
pages = {289-302},
publisher = {EDP-Sciences},
title = {A comparison of three algorithms for reducing the profile of a sparse matrix},
url = {http://eudml.org/doc/104965},
volume = {23},
year = {1989},
}

TY - JOUR
AU - Billionnet, Alain
AU - Brêteau, Jean-François
TI - A comparison of three algorithms for reducing the profile of a sparse matrix
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 1989
PB - EDP-Sciences
VL - 23
IS - 3
SP - 289
EP - 302
LA - eng
KW - profile reduction; numerical examples; heuristic algorithms; sparse matrix; interval graph
UR - http://eudml.org/doc/104965
ER -

References

top
  1. [BER, 70] C. BERGE, Graphes et Hypergraphes, Dunod, Paris. Zbl0213.25702MR357173
  2. [BIL, 86] A. BILLIONNET, On Interval Graphs and Matrice Profiles, R.A.I.R.O. Operations Research, Vol. 20, No. 3, août, pp. 245-256. Zbl0606.05063MR872642
  3. [CUT-MCK, 69] E. CUTHILL and J. McKEE, Reducing the Bandwidth of Sparse Symmetric Matrices, Proc. 24th Nat. Conf. Assoc. Comput. Mach., ACM Publ., pp. 157-172. 
  4. [EVE, 79] G. C. EVERSTINE, A Comparison of Three Resequencing Algorithms for Reduction of Matrix Profile and Wavefront, Int. J. for Num. Meth. in engineering, Vol. 14, pp. 837-853. Zbl0401.73082
  5. [GEO, 71] A. GEORGE, Computer Implementation of the Finite Element Method, STAN-CS-71-208, Computer Science Dept., Stanford Univ., Calif. 
  6. [GEO-LIU, 81] A. GEORGE and J. W. H. LIU, Computer Solutions of Large Sparse Positive Definite Systems, Prentice Hall, Englewood Cliffs, New Jersey, 324 p. Zbl0516.65010MR646786
  7. [GIB-POO-STO, 76] N. E. GIBBS, W. G. POOLE and P. K. STOCKMEYER, An Algorithm for Reducing the Bandwidth and Profile of a Sparse Matrix, S.I.A.M. J. Numer. Anal., Vol. 13, No. 2, April, pp. 236-250. Zbl0329.65024MR501810
  8. [GIB-POO-STO, 76] N. E. GIBBS, W. G. POOLE and P. K. STOCKMEYER, A Comparison of Several Bandwidth and Profile Reduction Algorithms, A.C.M. Transactions on Math. Software, Vol. 2, No. 4, December, pp. 322-330. Zbl0345.65014
  9. [GOL, 80] M. C. GOLUMBIC, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 284 p. Zbl0541.05054MR562306
  10. [KIN, 70] I. P. KING, An Automatic Reordering Scheme for Simultaneous Equations Derived from Network Systems. Int. J. Numer. Meth. Engrg., Vol. 2, pp. 523-533. 
  11. [LEV, 71] R. LEVY, Resequencing of the Structural Stiffness Matrix to Improve Computational Efficiency, J.P.L. Quart Tech. Rev., Vol. 1, pp. 61-70. 
  12. [LEW, 82] J. G. LEWIS, Implementation of the Gibbs-Poole-Stockmeyer and Gibbs-King Algorithms, A.C.M. Transactions on Mathematical Software, Vol. 8, No. 2, June, pp. 180-189. Zbl0478.65026
  13. [SHI, 84] D. R. SHIER, Some Aspects of Perfect Elimination Orderings in Chordal Graphs, Discrete Applied Mathematics, Vol. 7, pp. 325-331. Zbl0537.05069MR736895
  14. [TAR, 76] R. E. TARJAN, Graph Theory and Gaussian Elimination in Sparse Matrix Computations, J. R. BUNCH and D. J. ROSE Eds., Academic Press, New York, pp. 3-22. Zbl0347.65017

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.