An evaluation of reordering algorithms to reduce the computational cost of the incomplete Cholesky-conjugate gradient me
- PDF / 2,210,732 Bytes
- 40 Pages / 439.37 x 666.142 pts Page_size
- 99 Downloads / 149 Views
An evaluation of reordering algorithms to reduce the computational cost of the incomplete Cholesky-conjugate gradient method Sanderson L. Gonzaga de Oliveira1 · J. A. B. Bernardes1 · G. O. Chagas1
Received: 8 December 2016 / Revised: 19 April 2017 / Accepted: 15 July 2017 © SBMAC - Sociedade Brasileira de Matemática Aplicada e Computacional 2017
Abstract 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. Keywords 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
1 Introduction The solution of large sparse linear systems Ax = b, where A is a sparse n × n matrix, x is the unknown solution, and b is a known vector, is a crucial step in several science and Communicated by Michele Benzi.
B
Sanderson L. Gonzaga de Oliveira [email protected] J. A. B. Bernardes [email protected] G. O. Chagas [email protected]
1
Universidade Federal de Lavras, Lavras, Brazil
123
S. L. Gonzaga de Oliveira et al.
engineering applications. It is commonly the step of the simulation that requires the highest computational cost. The principal source of the problems with large-scale matrices arises from the discretization of elliptic or parabolic partial differential equations (PDEs) (Benzi 2002). The methods of finite elements, finite differences, and finite volumes are some of the most common numerical problem-solving methods related to physical phenomena that are governed by PDEs (Gonzaga de Oliveira et al. 2016b). These methods produce large sparse linear systems. These systems also originate from problems that are not modeled by PDEs, such as chemical engineering processes, design and analysis of integrated circuits, and power system networks (Benzi 2002). A significant amount of memory and a high processing cost are required to store and solve these large-scale linear systems (Gonzaga de Oliveira et al. 2016b); the highest computational c
Data Loading...
