nach oben

Engineering with Computers

Erschienen in:

21.06.2019 | Original Article

Evolving reordering algorithms using an ant colony hyperheuristic approach for accelerating the convergence of the ICCG method

verfasst von: S. L. Gonzaga de Oliveira, L. M. Silva

Erschienen in: Engineering with Computers | Ausgabe 4/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This paper proposes a novel ant colony hyperheuristic approach for reordering the rows and columns of symmetric positive definite matrices. This ant colony hyperheuristic approach evolves heuristics for bandwidth reduction applied to instances arising from specific application areas with the objective of generating low-cost reordering algorithms. This paper evaluates the resulting reordering algorithm in each application area against state-of-the-art reordering algorithms with the purpose of reducing the running times of the zero-fill incomplete Cholesky-preconditioned conjugate gradient method. The results obtained on a wide-ranging set of standard benchmark matrices show that the proposed approach compares favorably with state-of-the-art reordering algorithms when applied to instances arising from computational fluid dynamics, structural, and thermal problems.

Vorheriger Artikel Micro-seismic source location determined by a modified objective function

Nächster Artikel Prediction of frictional characteristics of bituminous mixes using group method of data handling and multigene symbolic genetic programming

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Ajiz MA, Jennings A (1984) A robust incomplete Choleski-conjugate gradient algorithm. Int J Numer Methods Eng 20:949–966MathSciNetCrossRef

Bathe K (1996) Finite element procedures. Prentice Hall, New JerseyMATH

Benzi M (2002) Preconditioning techniques for large linear systems: a survey. J Comput Phys 182:418–477MathSciNetCrossRef

Benzi M, Tuma M (2003) A robust incomplete factorization preconditioner for positive definite matrices. Numer Linear Algebra Appl 10:385–400MathSciNetCrossRef

Bernardes JAB, Gonzaga de Oliveira SL (2015) A systematic review of heuristics for profile reduction of symmetric matrices. Procedia Comput Sci 51:221–230. https://doi.org/10.1016/j.procs.2015.05.231CrossRef

Camata JJ, Rossa AL, Valli AMP, Catabriga L, Carey GF, Coutinho ALGA (2012) Reordering and incomplete preconditioning in serial and parallel adaptive mesh refinement and coarsening flow solutions. Int J Numer Methods Fluids 69(4):802–823MathSciNetCrossRef

Chagas GO, Gonzaga de Oliveira SL (2015) Metaheuristic-based heuristics for symmetric-matrix bandwidth reduction: a systematic review. Procedia Comput Sci 51:211–220. https://doi.org/10.1016/j.procs.2015.05.229CrossRef

Davis TA, Hu Y (2011) The University of Florida sparse matrix collection. ACM Trans Math Softw 38(1):1–25MathSciNetMATH

Dorigo M, Stützle T (2003) The ant colony optimization metaheuristic: algorithms, applications, and advances. In: Glover FW, Kochenberger GA (eds) Handbook of metaheuristics. International series in operations research and management science, vol 57. Springer, Boston, pp 250–285

10.

Gao J, Liang R, Wang J (2014) Research on the conjugate gradient algorithm with a modified incomplete Cholesky preconditioner on GPU. J Parallel Distrib Comput 74:2088–2098CrossRef

11.

George A (1971) Computer implementation of the finite element method. Ph.D. thesis, Stanford University, Stanford

12.

George A, Liu JW (1981) Computer solution of large sparse positive definite systems. Prentice-Hall, Englewood CliffsMATH

13.

George A, Liu JWH (1979) An implementation of a pseudoperipheral node finder. ACM Trans Math Softw 5(3):284–295CrossRef

14.

Gkountouvas T, Karakasis V, Kourtis K, Goumas G, , Koziris N (2013) Improving the performance of the symmetric sparse matrix-vector multiplication in multicore. In: 27th international symposium on parallel and distributed processing (IPDPS). IEEE Computer Society, Boston, pp 273–283

15.

Golub GH, van Loan CF (1996) Matrix computations, 3rd edn. The Johns Hopkins University Press, BaltimoreMATH

16.

Gonzaga de Oliveira SL, Abreu AAAM (2018) An evaluation of pseudoperipheral vertex finders for the reverse Cuthill–McKee method for bandwidth and profile reductions of symmetric matrices. In: 37th international conference of the Chilean Computer Science Society (SCCC). Chilean Computer Science Society, Santiago, Chile. https://ieeexplore.ieee.org/document/8705263

17.

Gonzaga de Oliveira SL, Bernardes JAB, Chagas GO (2018) An evaluation of low-cost heuristics for matrix bandwidth and profile reductions. Comput Appl Math 37(2):1412–1471MathSciNetCrossRef

18.

Gonzaga de Oliveira SL, Bernardes JAB, Chagas GO (2018) An evaluation of reordering algorithms to reduce the computational cost of the incomplete Cholesky-conjugate gradient method. Comput Appl Math 37(3):2965–3004MathSciNetCrossRef

19.

Gonzaga de Oliveira SL, Chagas GO (2015) A systematic review of heuristics for symmetric-matrix bandwidth reduction: methods not based on metaheuristics. In: Proceedings of the Brazilian symposium on operations research (SBPO 2015), Sobrapo, Pernambuco, Brazil

20.

Hestenes MR, Stiefel E (1952) Methods of conjugate gradients for solving linear systems. J Res Natl Bur Stand 49(36):409–436MathSciNetCrossRef

21.

Hu Y, Scott JA (2001) A multilevel algorithm for wavefront reduction. SIAM J Sci Comput 23(4):1352–1375MathSciNetCrossRef

22.

Iwashita T, Mifune T, Shimasaki M (2007) Evaluation index of acceleration factor and ordering in shifted ICCG method for electromagnetic field analyses. IEEE Trans Magn 43(4):1493–1496CrossRef

23.

Jansen KE, Rasquin M, Farnsworth JA, Rathay N, Monastero MC, Amitay M (2018) Interaction of a synthetic jet with separated flow over a vertical tail. AIAA J 56(7):2653–2668CrossRef

24.

King IP (1970) An automatic reordering scheme for simultaneous equations derived from network systems. Int J Numer Methods Eng 2(4):523–533CrossRef

25.

Konshin I (2016) Parallel computational models to estimate an actual speedup of analyzed algorithm. In: Voevodin V, Sobolev S (eds) Supercomputing, second Russian supercomputing day, RuSCDays 2016. Communications in computer and information science. Springer, Moscow, pp 304–317

26.

Koohestani B, Poli R (2011) A hyper-heuristic approach to evolving algorithms for bandwidth reduction based on genetic programming. In: Research and development in intelligent systems XXVIII. Springer, London, pp 93–106

27.

Kumfert G, Pothen A (1997) Two improved algorithms for envelope and wavefront reduction. BIT Numer Math 37(3):559–590MathSciNetCrossRef

28.

Lanczos C (1952) Solutions of systems of linear equations by minimized iterations. J Res Natl Bur Stand 49(1):33–53MathSciNetCrossRef

29.

Li L, Huang TZ, Jing YF, Zhang Y (2010) Application of the incomplete Cholesky factorization preconditioned Krylov subspace method to the vector finite element method for 3-D electromagnetic scattering problems. Comput Phys Commun 181:271–276MathSciNetCrossRef

30.

Lin YX, Yuan JJ (1994) Profile minimization problem for matrices and graphs. Acta Math Appl Sin 10(1):107–122MathSciNetCrossRef

31.

Medeiros SRP, Pimenta PM, Goldenberg P (1993) Algorithm for profile and wavefront reduction of sparse matrices with a symmetric structure. Eng Comput 10(3):257–266CrossRef

32.

Papadimitriou CH (1976) The NP-completeness of bandwidth minimization problem. Comput J 16:177–192MathSciNetMATH

33.

Rasquin M, Smith C, Chitale K, Seol ES, Matthews BA, Martin JL, Sahni O, Loy RM, Shephard MS, Jansen KE (2014) Scalable implicit flow solver for realistic wing simulations with flow control. Comput Sci Eng 16(6):13–21CrossRef

34.

Reid JK, Scott JA (1999) Ordering symmetric sparse matrices for small profile and wavefront. Int J Numer Methods Eng 45(12):1737–1755CrossRef

35.

Reid JK, Scott JA (2002) Implementing Hager’s exchange methods for matrix profile reduction. ACM Trans Math Softw 28(4):377–391MathSciNetCrossRef

36.

Semba K, Tani K, Yamada T, Iwashita T, Takahashi Y, Nakashima H (2013) Parallel performance of multithreaded ICCG solver based on algebraic block multicolor ordering in finite element electromagnetic field analyses. IEEE Trans Magn 49(5):1581–1584CrossRef

37.

Sloan SW (1989) A Fortran program for profile and wavefront reduction. Int J Numer Methods Eng 28(11):2651–2679CrossRef

38.

STFC: The Science and Technology Facilities Council (2018) HSL. A collection of Fortran codes for large scale scientific computation. http://www.hsl.rl.ac.uk. Accessed Dec 2018

39.

Toivanen J, Avery P, Farhat C (2018) A multilevel FETI-DP method and its performance for problems with billions of degrees of freedom. Int J Numer Methods Eng 116(10–11):661–682MathSciNetCrossRef

40.

Williams S, Waterman A, Patterson D (2009) Roofline: an insightful visual performance model for multicore architectures. Commun ACM 52(4):65–76CrossRef

41.

Wout E, van Gijzen MB, Ditzel A, van der Ploeg A, Vuik C (2012) The deflated relaxed incomplete Cholesky CG method for use in a real-time ship simulator. Procedia Comput Sci 1:249–257CrossRef

Titel: Evolving reordering algorithms using an ant colony hyperheuristic approach for accelerating the convergence of the ICCG method
verfasst von: S. L. Gonzaga de Oliveira
L. M. Silva
Publikationsdatum: 21.06.2019
Verlag: Springer London
Erschienen in: Engineering with Computers / Ausgabe 4/2020
Print ISSN: 0177-0667
Elektronische ISSN: 1435-5663
DOI: https://doi.org/10.1007/s00366-019-00801-5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 4/2020

A heuristic moment-based framework for optimization design under uncertainty

A meshless multiple-scale polynomial method for numerical solution of 3D convection–diffusion problems with variable coefficients

Nonlocal strain gradient forced vibrations of FG-GPLRC nanocomposite microbeams

Non-gradient probabilistic Gaussian global-best harmony search optimization for first-order reliability method

Development of a novel hybrid intelligent model for solving engineering problems using GS-GMDH algorithm

Wave dispersion characteristics of fluid-conveying magneto-electro-elastic nanotubes