New algorithms for matrix envelope compression in real world environment

• Autorzy: Stabrowski M.M.

Warianty tytułu

PL

Nowe algorytmy kompresji profilu macierzy w realnych zastosowaniach

• Języki publikacji: EN

Abstrakty

EN

The first of new methods defines the row weights and performs quick sorting of the rows and columns using weights criterion. The second method relies on "bubble" swapping with constant or variable distance in order to find true global optimum. Both methods are compared with classic algorithms. Matrices used in the tests are derived from Harwell-Boeing collection.

PL

Pierwsza z nowych metod definiuje wagi wierszy macierzy i sortuje wiersze i kolumny macierzy używając kryterium wag. Druga metoda korzysta z bąbelkowych zamian wierszy i kolumn dla stałej lub zmiennej odległości by znaleźć prawdziwe globalne optimum. Obie metody porównano z klasycznymi algorytmami kompresji. Do testów użyto macierzy ze znanej kolekcji Harwell-Boeing.

Słowa kluczowe

PL

algorytmy; kompresja; macierze

• Wydawca: Polish Academy of Sciences, Committee on Electrical Engineering
• Czasopismo: Archives of Electrical Engineering
• Rocznik: 2001
• Tom: Vol. 50, nr 4
• Strony: 379--394
• Opis fizyczny: Bibliogr. 19 poz., tab., rys.

Twórcy

autor

Stabrowski M.M.

• Lublin University of Technology, Katedra Informatyki, Lublin

Bibliografia

• 1. Akyuz F. A., Utku S.: An Automatic Relabelling Scheme for Bandwidth Minimisation of Stiffness Matrices. AIAA J., 6, 1968, pp. 728-730.
• 2. Armstrong B.A.: A hybrid algorithm for reducing matrix bandwidth. Int. J. Num. Meth. Engng., 20, 1984, pp. 1929-1940.
• 3. Bekakos M.P., Bartzi A.A.: Systolic Bandwidth and Profile Reduction of Sparse matrices on pipenets. Nonlinear Analysis Theory, Methods and Applications, Vol. 30, 5, 1997, pp. 2883-89.
• 4. Billionet A., Breteau J.F.: A comparison of three algorithms for reducing the profile of a sparse matrix. Recherche Operationnele, 23, 1989, pp. 289-302.
• 5. Cormen T.H., Leiserson C.E.,Rivest R.L.: Introduction to Algorithms. MIT Press, Cambridge Mass., 1994.
• 6. Cuthill E., McKee J.: Reducing the Bandwidth of Sparse Symmetric Matrices. Proc. 24th Nat. Conf. ACM Publ. P-69, Brandon Systems Press, Princeton, New Jersey 1968, pp. 157-172.
• 7. Engeln-Muellges G., Uhlig F.: Numerical Algorithms with C. Springer Verlag, Berlin 1996.
• 8. Everstine G.C.: A comparison of three resequencing algorithms for the reduction of matrix profile and wavefront. Int. J. Num. Meth. Engng., 14, 1979, pp. 837-853.
• 9. George A., Liu W.H.: Computer Solution of Large Sparse Positive Definite Systems. Prentice Hall, Englewood Cliffs 1981.
• 10. Gibbs N.E., Poole W.G., Stockmeyer P.K.: An Algorithm for Reducing the Bandwidth and profile of a Sparse Matrix. SIAM J. Numer. Anal., 13, 1976, pp. 236-250.
• 11. Kumfert G., Pothen A.: Two improved algorithms for envelope and wavefront reduction. BIT, Vol. 37, No. 3, September 1997, pp. 559-590.
• 12. Lewis J.G.: Implementation of the Gibbs Poole-Stockmeyer and Gibbs-King algorithms. ACM Trans Math. Software, 8, 1982, pp. 180-189.
• 13. Lewis R.R.: Simulated Annealing for Profile and Fill Reduction of Sparse Matrices. Int. J. Num. Meth. Engng., 1993.
• 14. Lim I.L., Johnston I.W., Choi S.K.: A comparison of algorithms for profile reduction of sparse matrices. Computers & Structures, Vol. 57, No. 2, 1995, pp. 297-302.
• 15. Medeiros S.R.P., Pimenta P.M., Goldenberg P.: An algorithm for profile and wavefront reduction of sparse matrices with a symmetric structure. Engineering Computation, Vol. 10, No. 3, 1993, pp. 257-266.
• 16. Rosen R.: Matrix Bandwidth Minimisation. Proc. 23rd Nat. Conf. ACM Publ. P-68, Brandon Systems Press, Princeton, New Jersey 1968, pp. 585-595.
• 17. Sloan S.W.: An algorithm for profile and wavefront reduction of sparse matrices. Int. J. Num. Meth. Engng., 23, 1986, pp. 239-251.
• 18. Tewarson R.P.: Sorting and Ordering Sparse Linear Systems in Large Sparse Sets of Linear Equations (J.K. Reid ed.), Academic Press, New York 1971, pp. 151-168.
• 19. Tewarson R.P., Sparse Matrices. Academic Press, New York 1973.