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 redu...
详细信息
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.
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....
详细信息
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.
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 an...
详细信息
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.
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 exper...
详细信息
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.
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 inves...
详细信息
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.
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 ...
详细信息
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.
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...
详细信息
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.
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 ...
详细信息
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.
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 place...
详细信息
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.
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 ...
详细信息
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.
暂无评论