检索结果-内蒙古大学图书馆

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

引用

ENGINEERING WITH COMPUTERS 2020年第4期36卷 1857-1873页

作者： de Oliveira, S. L. Gonzaga Silva, L. M. Univ Fed Lavras Dept Ciencia Computacao Lavras Brazil

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.

关键词： Bandwidth reduction Profile reduction Heuristics reordering algorithms Sparse matrices Renumbering Ordering Graph labeling Conjugate gradient method Graph algorithm Sparse symmetric positive definite linear systems Incomplete Cholesky factorization Ant colony optimization Hyperheuristic

来源：评论

学校读者我要写书评

暂无评论

An evaluation of reordering algorithms to reduce the computational cost of the incomplete Cholesky-conjugate gradient method

引用

COMPUTATIONAL & APPLIED MATHEMATICS 2018年第3期37卷 2965-3004页

作者： Gonzaga de Oliveira, Sanderson L. Bernardes, J. A. B. Chagas, G. O. Univ Fed Lavras Lavras Brazil

This paper is concerned with applying bandwidth and profile reduction reordering algorithms prior to computing an incomplete Cholesky factorization and using this as a preconditioner for the conjugate gradient method. Hundreds of reordering algorithms have been proposed to solve the problems of bandwidth and profile reductions since the mid-1960s. In previous publications, a large range of heuristics for bandwidth and/or profile reductions was reviewed. Based on this experience, 13 heuristics were selected as the most promising methods. These are evaluated in this paper along with a variant of the breadth-first search procedure that is proposed. Numerical results confirm the effectiveness of this modified reordering algorithm for linear systems derived from specific application areas. Moreover, the most promising heuristics for several application areas are identified when reducing the computational cost of the incomplete Cholesky-conjugate gradient method.

关键词： Bandwidth reduction Profile reduction Combinatorial optimization Heuristics Metaheuristics reordering algorithms Sparse matrices Renumbering Ordering Graph labeling Conjugate gradient method Graph algorithm Sparse symmetric positive-definite linear systems Incomplete Cholesky factorization

来源：评论

学校读者我要写书评

暂无评论

An Analysis of reordering algorithms to Reduce the Computational Cost of the Jacobi-Preconditioned CG Solver Using High-Precision Arithmetic 17th

An Analysis of Reordering Algorithms to Reduce the Computati...

引用

17th International Conference on Computational Science and its Applications (ICCSA)

作者： Gonzaga de Oliveira, Sanderson L. Chagas, Guilherme Oliveira Barreto Bernardes, Junior Assis Univ Fed Lavras Lavras MG Brazil Inst Nacl Pesquisas Espaciais Sao Paulo Brazil

ISBN: (纸本)9783319623924;9783319623917

Several heuristics for bandwidth and profile reductions have been proposed since the 1960s. In systematic reviews, 133 heuristics applied to these problems have been found. The results of these heuristics have been analyzed so that, among them, 13 were selected in a manner that no simulation or comparison showed that these algorithms could be outperformed by any other algorithm in the publications analyzed, in terms of bandwidth or profile reductions and also considering the computational costs of the heuristics. Therefore, these 13 heuristics were selected as the most promising low-cost methods to solve these problems. Based on this experience, this article reports that in certain cases no heuristic for bandwidth or profile reduction can reduce the computational cost of the Jacobi-preconditioned Conjugate Gradient Method when using high-precision numerical computations.

关键词： Bandwidth reduction Profile reduction Conjugate Gradient Method Graph labeling reordering algorithms Sparse matrices Graph algorithm High-precision arithmetic Ordering Sparse symmetric positive-definite linear systems Combinatorial optimization Heuristics

来源：评论

学校读者我要写书评

暂无评论

An Assessment of reordering algorithms to Speed Up the ICCG Method Applied to CFD Problems 18th

An Assessment of Reordering Algorithms to Speed Up the ICCG ...

引用

18th International Conference on Computational Science and Its Applications (ICCSA)

作者： Gonzaga de Oliveira, Sanderson L. Chagas, Guilherme Oliveira Bernardes, Junior Assis Barreto Robaina, Diogo T. Kischinhevsky, Mauricio Univ Fed Lavras Lavras MG Brazil Univ Fed Fluminense Niteroi RJ Brazil

ISBN: (纸本)9783319951621;9783319951614

Previous publications analyzed a large number of heuristics for bandwidth and profile reductions, and 14 heuristics were selected as promising low-cost heuristics for these problems. Based on extensive numerical experiments, this paper evaluates these heuristics when applied to matrices contained in systems of linear equations arising from computational fluid dynamics problems and the most promising heuristics are identified when reducing the zero-fill incomplete Cholesky-preconditioned conjugate gradient method.

关键词： Bandwidth reduction Profile reduction Sparse matrices Graph labeling Conjugate gradient method reordering algorithms

来源：评论

学校读者我要写书评

暂无评论

The Influence of reordering algorithms on the Convergence of a Preconditioned Restarted GMRES Method 20th

The Influence of Reordering Algorithms on the Convergence of...

引用

20th International Conference on Computational Science and Its Applications (ICCSA)

作者： de Oliveira, S. L. Gonzaga Carvalho, C. Osthoff, C. Univ Fed Lavras Lavras MG Brazil Lab Nacl Comp Cient Petropolis RJ Brazil

ISBN: (纸本)9783030587994;9783030587987

This paper concentrates on applying reordering algorithms as a preprocessing step of a restarted Generalized Minimal Residual (GMRES for short) solver preconditioned by three ILU-type preconditioners. This paper investigates the effect of 13 orderings on the convergence of the preconditioned GMRES solver restarted every 50 steps when applied to nine real large-scale nonsymmetric and not positive definite matrices. Specifically, this paper shows the most promising combination of preconditioners and reordering for each linear system used.

关键词： Bandwidth reduction Profile reduction reordering algorithms Graph labeling GMRES method

来源：评论

学校读者我要写书评

暂无评论

A Survey of Heuristics for Profile and Wavefront Reductions

引用

ACM COMPUTING SURVEYS 2025年第5期57卷 1-16页

作者： de Oliveira, Sanderson L. Gonzaga Univ Fed Sao Paulo Inst Ciencia & Tecnol Sao Jose Dos Campos SP Brazil

This article surveys heuristic methods for profile and wavefront reductions. These graph layout problems represent a challenge for optimization methods and heuristics especially. The article presents the graph layout problems with their formal definition. It provides an ample perspective of techniques for designing heuristic methods for these graph layout problems but concentrates on the approaches and methodologies that yield high-quality solutions. Thus, this work references the most relevant studies in the associated literature and discusses the current state-of-the-art heuristics for these graph layout problems.

关键词： Matrix ordering profile optimization profile reduction graph profile sparse matrices matrix profile reordering algorithms heuristic methods metaheuristics graph theory wave-front ordering wavefront reduction search methods combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

Metaheuristic algorithms for the bandwidth reduction of large-scale matrices

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第4期43卷 727-784页

作者： Gonzaga de Oliveira, S. L. Carvalho, C. Univ Fed Lavras Dept Ciencia Comp Lavras Brazil

This paper considers the bandwidth reduction problem for large-scale sparse matrices in serial computations. A heuristic for bandwidth reduction reorders the rows and columns of a given sparse matrix. Thus, the method places entries with a nonzero value as close to the main diagonal as possible. Bandwidth optimization is a critical issue for many scientific and engineering applications. This manuscript proposes two heuristics for the bandwidth reduction of large-scale matrices. The first is a variant of the Fast Node Centroid Hill-Climbing algorithm, and the second is an algorithm based on the iterated local search metaheuristic. This paper then experimentally compares the solutions yielded by the new reordering algorithms with the bandwidth solutions delivered by state-of-the-art heuristics for the problem, including tests on large-scale problem matrices. A considerable number of results for a range of realistic test problems showed that the performance of the two new algorithms compared favorably with state-of-the-art heuristics for bandwidth reduction. Specifically, the variant of the Fast Node Centroid Hill-Climbing algorithm yielded the overall best bandwidth results.

关键词： Bandwidth reduction Heuristics Sparse matrices reordering algorithms Renumbering Ordering Metaheuristics Graph algorithm Iterated local search

来源：评论

学校读者我要写书评

暂无评论

Low-cost heuristics for matrix bandwidth reduction combined with a Hill-Climbing strategy

引用

RAIRO-OPERATIONS RESEARCH 2021年第4期55卷 2247-2264页

作者： Gonzaga de Oliveira, Sanderson L. Silva, Liberio M. Univ Fed Lavras Lavras Brazil

This paper studies heuristics for the bandwidth reduction of large-scale matrices in serial computations. Bandwidth optimization is a demanding subject for a large number of scientific and engineering applications. A heuristic for bandwidth reduction labels the rows and columns of a given sparse matrix. The algorithm arranges entries with a nonzero coefficient as close to the main diagonal as possible. This paper modifies an ant colony hyper-heuristic approach to generate expert-level heuristics for bandwidth reduction combined with a Hill-Climbing strategy when applied to matrices arising from specific application areas. Specifically, this paper uses low-cost state-of-the-art heuristics for bandwidth reduction in tandem with a Hill-Climbing procedure. The results yielded on a wide-ranging set of standard benchmark matrices showed that the proposed strategy outperformed low-cost state-of-the-art heuristics for bandwidth reduction when applied to matrices with symmetric sparsity patterns.

关键词： Bandwidth reduction sparse matrix ant colony optimization hyper-heuristic reordering algorithms renumbering ordering graph labeling graph algorithm local search procedure Hill-Climbing procedure

来源：评论

学校读者我要写书评

暂无评论

An ant colony hyperheuristic approach for matrix bandwidth reduction

引用

APPLIED SOFT COMPUTING 2020年 94卷 106434-106434页

作者： de Oliveira, S. L. Gonzaga Silva, L. M. Univ Fed Lavras Lavras Brazil

This paper considers the bandwidth reduction problem for large-scale matrices in serial computations. A heuristic for bandwidth reduction reorders the rows and columns of a given sparse matrix so that the method places entries with a nonzero value as close to the main diagonal as possible. Bandwidth optimization is a critical issue for many scientific and engineering applications. In this regard, this paper proposes an ant colony hyperheuristic approach for the bandwidth reduction of symmetric and nonsymmetric matrices. The ant colony hyperheuristic approach evolves and selects graph theory bandwidth reduction algorithms for application areas. This paper evaluates the resulting heuristics for bandwidth reduction in each application area against the most promising low-cost heuristics for bandwidth reduction. This paper also includes a numerical examination of the current state-of-the-art metaheuristic algorithms for matrix bandwidth reduction. The results yielded on a wide-ranging set of standard benchmark matrices showed that the proposed approach outperformed state-of-the-art low-cost heuristics for bandwidth reduction when applied to problem cases arising from several application areas, clearly indicating the promise of the proposal. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Bandwidth reduction Sparse matrix Ant colony optimization Hyperheuristic reordering algorithms Renumbering Ordering Graph labeling Graph algorithm

来源：评论

学校读者我要写书评

暂无评论

An analysis of spectral envelope reduction via quadratic assignment problems

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 1997年第3期18卷 706-732页

作者： George, A Pothen, A OLD DOMINION UNIV DEPT COMP SCINORFOLKVA 23529

A new spectral algorithm for reordering a sparse symmetric matrix to reduce its em elope size was described in [Barnard, Pothen, and Simon, Numer. Linear Algebra Appl., 2 (1995), PP 317-334]. The ordering is computed by associating a Laplacian matrix with the given matrix and then sorting the components of a specified eigenvector of the Laplacian. In this paper we provide an analysis of the spectral envelope reduction algorithm. We describe related 1- and 2-sum problems;the farmer is related to the envelope size, while the latter is related to an upper bound on the work in an envelope Cholesky factorization. We formulate these two problems as quadratic assignment problems and then study the 2-sum problem in more detail. We obtain lower bounds on the 2-sum by considering a relaxation of the problem and then show that the spectral ordering finds a permutation matrix closest tcr an orthogonal matrix attaining the lower bound. This provides a stronger justification of the spectral envelope reduction algorithm than previously known. The lower bound on the 2-sum is seen to be tight fur reasonably ''uniform'' finite element meshes. We show that problems with bounded separator sizes also have bounded envelope parameters.

关键词： 1-sum problem 2-sum problem envelope reduction eigenvalues of graphs Laplacian matrices quadratic assignment problems reordering algorithms sparse matrices

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：