G.A. Gravvanis, P.I. Matskanidis, K.M. Giannoutakis and E.A. Lipitakis
The purpose of this paper is to propose novel parallel computational techniques for the parallelization of explicit finite element generalized approximate inverse methods, based…
Abstract
Purpose
The purpose of this paper is to propose novel parallel computational techniques for the parallelization of explicit finite element generalized approximate inverse methods, based on Portable Operating System Interface for UniX (POSIX) threads, for multicore systems.
Design/methodology/approach
The authors' main motive for the derivation of the new Parallel Generalized Approximate Inverse Finite Element Matrix algorithmic techniques is that they can be efficiently used in conjunction with explicit preconditioned conjugate gradient‐type schemes on multicore systems. The proposed parallelization technique of the Optimized Banded Generalized Approximate Inverse Finite Element Matrix (OBGAIFEM) algorithm is achieved based on the concept of the “fish bone” approach with the use of a thread pool pattern. Theoretical estimates on the computational complexity of the parallel generalized approximate inverse finite element matrix algorithmic techniques are also derived.
Findings
Application of the proposed method on a two‐dimensional boundary value problem is discussed and numerical results are given on a multicore system using POSIX threads. These results tend to become optimum and are favorably compared to corresponding results from multiprocessor systems, as presented in recent work by Gravvanis et al.
Originality/value
The proposed parallel explicit finite element generalized approximate inverse preconditioning, using approximate factorization and approximate inverse algorithms, is an efficient computational method that is valuable for computer scientists and for scientists and engineers in engineering computations.
Details
Keywords
Christos K. Filelis-Papadopoulos and George A. Gravvanis
– The purpose of this paper is to propose novel factored approximate sparse inverse schemes and multi-level methods for the solution of large sparse linear systems.
Abstract
Purpose
The purpose of this paper is to propose novel factored approximate sparse inverse schemes and multi-level methods for the solution of large sparse linear systems.
Design/methodology/approach
The main motive for the derivation of the various generic preconditioning schemes lies to the efficiency and effectiveness of factored preconditioning schemes in conjunction with Krylov subspace iterative methods as well as multi-level techniques for solving various model problems. Factored approximate inverses, namely, Generic Factored Approximate Sparse Inverse, require less fill-in and are computed faster due to the reduced number of nonzero elements. A modified column wise approach, namely, Modified Generic Factored Approximate Sparse Inverse, is also proposed to further enhance performance. The multi-level approximate inverse scheme, namely, Multi-level Algebraic Recursive Generic Approximate Inverse Solver, utilizes a multi-level hierarchy formed using Block Independent Set reordering scheme and an approximation of the Schur complement that results in the solution of reduced order linear systems thus enhancing performance and convergence behavior. Moreover, a theoretical estimate for the quality of the multi-level approximate inverse is also provided.
Findings
Application of the proposed schemes to various model problems is discussed and numerical results are given concerning the convergence behavior and the convergence factors. The results are comparatively better than results by other researchers for some of the model problems.
Research limitations/implications
Further enhancements are investigated for the proposed factored approximate inverse schemes as well as the multi-level techniques to improve quality of the schemes. Furthermore, the proposed schemes rely on the definition of multiple parameters that for some problems require thorough testing, thus adaptive techniques to define the values of the various parameters are currently under research. Moreover, parallel schemes will be investigated.
Originality/value
The proposed approximate inverse preconditioning schemes as well as multi-level schemes are efficient computational methods that are valuable for computer scientists and for scientists and engineers in engineering computations.
Details
Keywords
A new class of explicit preconditioning methods based on the concept of sparse approximate factorization procedures and inverse matrix techniques is introduced for solving…
Abstract
A new class of explicit preconditioning methods based on the concept of sparse approximate factorization procedures and inverse matrix techniques is introduced for solving biharmonic equations. Isomorphic methods in conunction with explicit preconditioned schemes based on approximate inverse matrix techniques are presented for the efficient solution of biharmonic equations. Application of the proposed method on linear systems is discussed and numerical results are given.
Details
Keywords
Konstantinos M. Giannoutakis and George A. Gravvanis
To propose novel parallel/distributed normalized explicit finite element (FE) approximate inverse preconditioning for solving sparse FE linear systems.
Abstract
Purpose
To propose novel parallel/distributed normalized explicit finite element (FE) approximate inverse preconditioning for solving sparse FE linear systems.
Design/methodology/approach
The design of suitable methods was the main objective for which several families of the normalized approximate inverse, based on sparse normalized approximate factorization, are produced. The main motive for the derivation of the new normalized approximate inverse FE matrix algorithmic techniques is that they can be efficiently used in conjunction with normalized explicit preconditioned conjugate gradient (NEPCG) – type schemes on parallel and distributed systems. Theoretical estimates on the rate of convergence and computational complexity of the NEPCG method are also derived.
Findings
Application of the proposed method on a three‐dimensional boundary value problem is discussed and numerical results for uniprocessor systems along with speed‐ups and efficiency for multicomputer systems are given. These results tend to become optimum, which are in qualitative agreement with the theoretical results presented for uniprocessor and distributed memory systems, using message passing interface (MPI) communication library.
Research limitations/implications
Further parallel algorithmic techniques will be investigated in order to improve the speed‐ups and the computational complexity of the parallel normalized explicit approximate inverse preconditioning.
Originality/value
The proposed parallel/distributed normalized explicit approximate inverse preconditioning, using approximate factorization and approximate inverse algorithms, is an efficient computational method that is valuable for computer scientists and for scientists and engineers in engineering computations.
Details
Keywords
George A. Gravvanis and Christos K. Filelis-Papadopoulos
The purpose of this paper is to propose multigrid methods in conjunction with explicit approximate inverses with various cycles strategies and comparison with the other smoothers…
Abstract
Purpose
The purpose of this paper is to propose multigrid methods in conjunction with explicit approximate inverses with various cycles strategies and comparison with the other smoothers.
Design/methodology/approach
The main motive for the derivation of the various multigrid schemes lies in the efficiency of the multigrid methods as well as the explicit approximate inverses. The combination of the various multigrid cycles with the explicit approximate inverses as smoothers in conjunction with the dynamic over/under relaxation (DOUR) algorithm results in efficient schemes for solving large sparse linear systems derived from the discretization of partial differential equations (PDE).
Findings
Application of the proposed multigrid methods on two-dimensional boundary value problems is discussed and numerical results are given concerning the convergence behavior and the convergence factors. The results are comparatively better than the V-cycle multigrid schemes presented in a recent report (Filelis-Papadopoulos and Gravvanis).
Research limitations/implications
The limitations of the proposed scheme lie in the fact that the explicit finite difference approximate inverse matrix used as smoother in the multigrid method is a preconditioner for specific sparsity pattern. Further research is carried out in order to derive a generic explicit approximate inverse for any type of sparsity pattern.
Originality/value
A novel smoother for the geometric multigrid method is proposed, based on optimized banded approximate inverse matrix preconditioner, the Richardson method in conjunction with the DOUR scheme, for solving large sparse linear systems derived from finite difference discretization of PDEs. Moreover, the applicability and convergence behavior of the proposed scheme is examined based on various cycles and comparative results are given against the damped Jacobi smoother.
Details
Keywords
A new class of approximate inverse banded matrix techniques based on the concept of LU‐type factorization procedures is introduced for computing explicitly approximate inverses…
Abstract
A new class of approximate inverse banded matrix techniques based on the concept of LU‐type factorization procedures is introduced for computing explicitly approximate inverses without inverting the decomposition factors. Explicit preconditioned iterative schemes in conjunction with approximate inverse matrix techniques are presented for the efficient solution of banded linear systems. Applications of the method on a linear system are discussed and numerical results are given.
Details
Keywords
Presents a review on implementing finite element methods on supercomputers, workstations and PCs and gives main trends in hardware and software developments. An appendix included…
Abstract
Presents a review on implementing finite element methods on supercomputers, workstations and PCs and gives main trends in hardware and software developments. An appendix included at the end of the paper presents a bibliography on the subjects retrospectively to 1985 and approximately 1,100 references are listed.
Details
Keywords
The paper analyses the preconditioning of non‐linear nonsymmetric equations with approximations of the discrete Laplace operator. The test problems are non‐linear 2‐D elliptic…
Abstract
The paper analyses the preconditioning of non‐linear nonsymmetric equations with approximations of the discrete Laplace operator. The test problems are non‐linear 2‐D elliptic equations that describe natural convection, Darcy flow, in a porous medium. The standard second order accurate finite difference scheme is used to discretize the models’ equations. The discrete approximations are solved with a double iterative process using the Newton method as outer iteration and the preconditioned generalised conjugate gradient (PGCG) methods as inner iteration. Three PGCG algorithms, CGN, CGS and GMRES, are tested. The preconditioning with discrete Laplace operator approximations consists of replacing the solving of the equation with the preconditioner by a few iterations of an appropriate iterative scheme. Two iterative algorithms are tested: incomplete Cholesky (IC) and multigrid (MG). The numerical results show that MG preconditioning leads to mesh independence. CGS is the most robust algorithm but its efficiency is lower than that of GMRES.
Details
Keywords
Zhenhan Yao, Xiaoping Zheng, Han Yuan and Jinlong Feng
Based on the error analysis, the authors proposed a new kind of high accuracy boundary element method (BEM) (HABEM), and for the large-scale problems, the fast algorithm, such as…
Abstract
Purpose
Based on the error analysis, the authors proposed a new kind of high accuracy boundary element method (BEM) (HABEM), and for the large-scale problems, the fast algorithm, such as adaptive cross approximation (ACA) with generalized minimal residual (GMRES) is introduced to develop the high performance BEM (HPBEM). It is found that for slender beams, the stress analysis using iterative solver GMRES will difficult to converge. For the analysis of slender beams and thin structures, to enhance the efficiency of GMRES solver becomes a key problem in the development of the HPBEM. The purpose of this paper is study on the preconditioning method to solve this convergence problem, and it is started from the 2D BE analysis of slender beams.
Design/methodology/approach
The conventional sparse approximate inverse (SAI) based on adjacent nodes is modified to that based on adjacent nodes along the boundary line. In addition, the authors proposed a dual node variable merging (DNVM) preprocessing for slender thin-plate beams. As benchmark problems, the pure bending of thin-plate beam and the local stress analysis (LSA) of real thin-plate cantilever beam are applied to verify the effect of these two preconditioning method.
Findings
For the LSA of real thin-plate cantilever beams, as GMRES (m) without preconditioning applied, it is difficult to converge provided the length to height ratio greater than 50. Even with the preconditioner SAI or DNVM, it is also difficult to obtain the converged results. For the slender real beams, the iteration of GMRES (m) with SAI or DNVM stopped at wrong deformation state, and the computation failed. By changing zero initial solution to the analytical displacement solution of conventional beam theory, GMRES (m) with SAI or DNVM will not be stopped at wrong deformation state, but the stress error is still difficult to converge. However, by GMRES (m) combined with both SAI and DNVM preconditioning, the computation efficiency enhanced significantly.
Originality/value
This paper presents two preconditioners: DNVM and a modified SAI based on adjacent nodes along the boundary line of slender thin-plate beam. In the LSA, by using GMRES (m) combined with both DNVM and SAI, the computation efficiency enhanced significantly. It provides a reference for the further development of the 3D HPBEM in the LSA of real beam, plate and shell structures.
Details
Keywords
Christos K. Filelis-Papadopoulos and George A. Gravvanis
Large sparse least-squares problems arise in different scientific disciplines such as optimization, data analysis, machine learning and simulation. This paper aims to propose a…
Abstract
Purpose
Large sparse least-squares problems arise in different scientific disciplines such as optimization, data analysis, machine learning and simulation. This paper aims to propose a two-level hybrid direct-iterative scheme, based on novel block independent column reordering, for efficiently solving large sparse least-squares linear systems.
Design/methodology/approach
Herewith, a novel block column independent set reordering scheme is used to separate the columns in two groups: columns that are block independent and columns that are coupled. The permutation scheme leads to a two-level hierarchy. Using this two-level hierarchy, the solution of the least-squares linear system results in the solution of a reduced size Schur complement-type square linear system, using the preconditioned conjugate gradient (PCG) method as well as backward substitution using the upper triangular factor, computed through sparse Q-less QR factorization of the columns that are block independent. To improve the convergence behavior of the PCG method, the upper triangular factor, computed through sparse Q-less QR factorization of the coupled columns, is used as a preconditioner. Moreover, to further reduce the fill-in, then the column approximate minimum degree (COLAMD) algorithm is used to permute the block consisting of the coupled columns.
Findings
The memory requirements for solving large sparse least-squares linear systems are significantly reduced compared to Q-less QR decomposition of the original as well as the permuted problem with COLAMD. The memory requirements are reduced further by choosing to form larger blocks of independent columns. The convergence behavior of the iterative scheme is improved due to the chosen preconditioning scheme. The proposed scheme is inherently parallel due to the introduction of block independent column reordering.
Originality/value
The proposed scheme is a hybrid direct-iterative approach for solving sparse least squares linear systems based on the implicit computation of a two-level approximate pseudo-inverse matrix. Numerical results indicating the applicability and effectiveness of the proposed scheme are given.