Search results

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.

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.

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.

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.

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.

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.

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.

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.

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.

This paper gives a bibliographical review of the finite element and boundary element parallel processing techniques from the theoretical and application points of view. Topics include: theory – domain decomposition/partitioning, load balancing, parallel solvers/algorithms, parallel mesh generation, adaptive methods, and visualization/graphics; applications – structural mechanics problems, dynamic problems, material/geometrical non‐linear problems, contact problems, fracture mechanics, field problems, coupled problems, sensitivity and optimization, and other problems; hardware and software environments – hardware environments, programming techniques, and software development and presentations. The bibliography at the end of this paper contains 850 references to papers, conference proceedings and theses/dissertations dealing with presented subjects that were published between 1996 and 2002.

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.

The purpose of this paper is to introduce a novel approach to solving linear systems arising from applying a Boundary Element Method (BEM) to elasticity problems.

The key idea is based on using wavelet transforms as a tool to change dense and fully populated matrices of BEM systems into sparse matrices. Wavelets are then used again to produce an algorithm to solve the resultant sparse linear systems. The wavelet transformation part of the method can be added as a black box to existing BEM codes.

Numerical results focusing on the sensitivity of the solution for various physical variables to the thresholding parameters, and savings in computer time and memory are presented. The results show that the proposed method is efficient for large problems.

Application of the proposed method is restricted to problems with number of DOF equal to an integer power of 2.

The novel algorithm to solve transformed algebraic linear equations uses NS‐form of the modified matrix, taking the advantage of the hierarchical nature of Multi‐Resolution Analysis (MRA) to decompose a parent system into descendant systems with reduced size. These smaller systems are then solved iteratively using generalized minimal residual method.

This paper aims to propose a novel direct method for indefinite algebraic linear systems. It is well adapted for sparse linear systems, such as those of two-dimensional (2-D) finite elements problems, especially for coupled systems.

The proposed method is developed on an example of an indefinite symmetric matrix. The algorithm of the method is given next, and a comparison between the numbers of operations required by the method and the Cholesky method is also given. Finally, an application on a magnetostatic problem for classical methods (Gauss and Cholesky) shows the relative efficiency of the proposed method.

The proposed method can be used advantageously for 2-D finite elements in stepping methods without using a block decomposition of matrices.

This method is advantageous for direct linear solving for 2-D problems, but it is not recommended at this time for three-dimensional problems.

The proposed method is the first direct solver for algebraic linear systems proposed since more than a half century. It is not limited for symmetric positive systems such as many of direct and iterative methods.

To propose novel parallel/distributed normalized explicit finite element (FE) approximate inverse preconditioning for solving sparse FE linear systems.

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.

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.

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.

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.

The purpose of this paper is to discuss the linear solution of equality constrained problems by using the Frontal solution method without explicit assembling.

Re-written frontal solution method with a priori pivot and front sequence. OpenMP parallelization, nearly linear (in elimination and substitution) up to 40 threads. Constraints enforced at the local assembling stage.

When compared with both standard sparse solvers and classical frontal implementations, memory requirements and code size are significantly reduced.

Large, non-linear problems with constraints typically make use of the Newton method with Lagrange multipliers. In the context of the solution of problems with large number of constraints, the matrix transformation methods (MTM) are often more cost-effective. The paper presents a complete solution, with topological ordering, for this problem.

A complete software package in Fortran 2003 is described. Examples of clique-based problems are shown with large systems solved in core.

More realistic non-linear problems can be solved with this Frontal code at the core of the Newton method.

Use of topological ordering of constraints. A-priori pivot and front sequences. No need for symbolic assembling. Constraints treated at the core of the Frontal solver. Use of OpenMP in the main Frontal loop, now quantified. Availability of Software.

Finite element discretizations of low‐frequency, time‐harmonic magnetic problems lead to sparse, complex symmetric systems of linear equations. The question arises which Krylov subspace methods are appropriate to solve such systems. The quasi minimal residual method combines a constant amount of work and storage per iteration step with a smooth convergence history. These advantages are obtained by building a quasi minimal residual approach on top of a Lanczos process to construct the search space. Solving the complex systems by transforming them to equivalent real ones of double dimension has to be avoided as such real systems have spectra that are less favourable for the convergence of Krylov‐based methods. Numerical experiments are performed on electromagnetic engineering problems to compare the quasi minimal residual method to the bi‐conjugate gradient method and the generalized minimal residual method.

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.

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).

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).

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.

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.