A power sparse approximate inverse preconditioning procedure for large sparse linear systems

Motivated by the Cayley–Hamilton theorem, a novel adaptive procedure, called a Power Sparse Approximate Inverse (PSAI) procedure, is proposed that uses a different adaptive sparsity pattern selection approach to constructing a right preconditioner M for the large sparse linear system Ax=b. It determines the sparsity pattern of M dynamically and computes the n independent columns of M that is optimal in the Frobenius norm minimization, subject to the sparsity pattern of M. The PSAI procedure needs a matrix–vector product at each step and updates the solution of a small least squares problem cheaply. To control the sparsity of M and develop a practical PSAI algorithm, two dropping strategies are proposed. The PSAI algorithm can capture an effective approximate sparsity pattern of A^?1 and compute a good sparse approximate inverse M efficiently. Numerical experiments are reported to verify the effectiveness of the PSAI algorithm. Numerical comparisons are made for the PSAI algorithm and the adaptive SPAI algorithm proposed by Grote and Huckle as well as for the PSAI algorithm and three static Sparse Approximate Inverse (SAI) algorithms. The results indicate that the PSAI algorithm is at least comparable to and can be much more effective than the adaptive SPAI algorithm and it often outperforms the static SAI algorithms very considerably and is more robust and practical than the static ones for general problems. Copyright © 2008 John Wiley & Sons, Ltd.     

A Comparative Study on Dynamic and Static Sparsity Patterns in Parallel Sparse Approximate Inverse Preconditioning

Sparse approximate inverse (SAI) techniques have recently emerged as a new class of parallel preconditioning techniques for solving large sparse linear systems on high performance computers. The choice of the sparsity pattern of the SAI matrix is probably the most important step in constructing an SAI preconditioner. Both dynamic and static sparsity pattern selection approaches have been proposed by researchers. Through a few numerical experiments, we conduct a comparable study on the properties and performance of the SAI preconditioners using the different sparsity patterns for solving some sparse linear systems. This revised version was published online in July 2006 with corrections to the Cover Date.     

Diagonally compensated reduction and related preconditioning methods

When solving linear algebraic equations with large and sparse coefficient matrices, arising, for instance, from the discretization of partial differential equations, it is quite common to use preconditioning to accelerate the convergence of a basic iterative scheme. Incomplete factorizations and sparse approximate inverses can provide efficient preconditioning methods but their existence and convergence theory is based mostly on M-matrices (H-matrices). In some application areas, however, the arising coefficient matrices are not H-matrices. This is the case, for instance, when higher-order finite element approximations are used, which is typical for structural mechanics problems. We show that modification of a symmetric, positive definite matrix by reduction of positive offdiagonal entries and diagonal compensation of them leads to an M-matrix. This diagonally compensated reduction can take place in the whole matrix or only at the current pivot block in a recursive incomplete factorization method. Applications for constructing preconditioning matrices for finite element matrices are described.     

A residual based sparse approximate inverse preconditioning procedure for large sparse linear systems

We propose a residual based sparse approximate inverse (RSAI) preconditioning procedure, for the large sparse linear system A x =b . Different from the SParse Approximate Inverse (SPAI) algorithm proposed by Grote and Huckle (SIAM Journal on Scientific Computing, 18 (1997), pp. 838–853.), RSAI uses only the dominant other than all the information on the current residual and augments sparsity patterns adaptively during loops. In order to control the sparsity of M , we develop two practical algorithms RSAI(f i x ) and RSAI(t o l ). RSAI(f i x ) retains the prescribed number of large nonzero entries and adjusts their positions in each column of M among all available ones, in which the number of large entries is increased by a fixed number at each loop. In contrast, the existing indices of M by SPAI are untouched in subsequent loops and a few most profitable indices are added to each column of M from the new candidates in the next loop. RSAI(t o l ) is a tolerance based dropping algorithm and retains all large entries by dynamically dropping small ones below some tolerances, and it better suits for the problem where the numbers of large entries in the columns of A ^?1 differ greatly. When the two preconditioners M have almost the same or comparable numbers of nonzero entries, the numerical experiments on real‐world problems demonstrate that RSAI(f i x ) is highly competitive with SPAI and can outperform the latter for some problems. We also make comparisons of RSAI(f i x ), RSAI(t o l ), and power sparse approximate inverse(t o l ) proposed Jia and Zhu (Numerical Linear Algebra with Applications, 16 (2009), pp.259–299.) and incomplete LU factorization type methods and draw some general conclusions.     

On the GPGPU parallelization issues of finite element approximate inverse preconditioning

During the past decades, explicit finite element approximate inverse preconditioning methods have been extensively used for efficiently solving sparse linear systems on multiprocessor systems. The effectiveness of explicit approximate inverse preconditioning schemes relies on the use of efficient preconditioners that are close approximants to the coefficient matrix and are fast to compute in parallel. New parallel computational techniques are proposed for the parallelization of the Optimized Banded Generalized Approximate Inverse Finite Element Matrix (OBGAIFEM) algorithm, based on the concept of the “fish bone” computational approach, and for the Explicit Preconditioned Conjugate Gradient type methods on a General Purpose Graphics Processing Unit (GPGPU). The proposed parallel methods have been implemented using Compute Unified Device Architecture (CUDA) developed by NVIDIA. Finally, numerical results for the performance of the finite element explicit approximate inverse preconditioning for solving characteristic two dimensional boundary value problems on a massive multiprocessor interface on a GPU are presented. The CUDA implementation issues of the proposed methods are also discussed.     

On the GPGPU parallelization issues of finite element approximate inverse preconditioning

During the past decades, explicit finite element approximate inverse preconditioning methods have been extensively used for efficiently solving sparse linear systems on multiprocessor systems. The effectiveness of explicit approximate inverse preconditioning schemes relies on the use of efficient preconditioners that are close approximants to the coefficient matrix and are fast to compute in parallel. New parallel computational techniques are proposed for the parallelization of the Optimized Banded Generalized Approximate Inverse Finite Element Matrix (OBGAIFEM) algorithm, based on the concept of the “fish bone” computational approach, and for the Explicit Preconditioned Conjugate Gradient type methods on a General Purpose Graphics Processing Unit (GPGPU). The proposed parallel methods have been implemented using Compute Unified Device Architecture (CUDA) developed by NVIDIA. Finally, numerical results for the performance of the finite element explicit approximate inverse preconditioning for solving characteristic two dimensional boundary value problems on a massive multiprocessor interface on a GPU are presented. The CUDA implementation issues of the proposed methods are also discussed.     

A parallel iterative solver for positive-definite systems with hybrid MPI–OpenMP parallelization for multi-core clusters

This article is devoted to the development and study of an algorithm for solving large systems of linear algebraic equations with sparse stiffness matrix on supercomputer by using the preconditioned conjugate gradient method (PCG). An efficient preconditioner is constructed on the basis of the domain decomposition method (the additive Schwarz method) which makes it possible to implement the algorithm on several computing nodes. We describe the parallel algorithm of the action of the stiffness matrix and the preconditioner on a vector. In addition, to increase the computational efficiency we make use of the routines from Intel^®MKL: the direct solver (PARDISO) and the matrix–vector multiplication for sparse matrices (Sparse BLAS). We also study efficiency of using OpenMP directives on each computational node and compare it with pure MPI parallelization. The corresponding performance and scalability charts are presented.     

Option pricing with a direct adaptive sparse grid approach

We present an adaptive sparse grid algorithm for the solution of the Black–Scholes equation for option pricing, using the finite element method. Sparse grids enable us to deal with higher-dimensional problems better than full grids. In contrast to common approaches that are based on the combination technique, which combines different solutions on anisotropic coarse full grids, the direct sparse grid approach allows for local adaptive refinement. When dealing with non-smooth payoff functions, this reduces the computational effort significantly. In this paper, we introduce the spatially adaptive discretization of the Black–Scholes equation with sparse grids and describe the algorithmic structure of the numerical solver. We present several strategies for adaptive refinement, evaluate them for different dimensionalities, and demonstrate their performance showing numerical results.     

A High-Quality Preconditioning Technique for Multi-Length-Scale Symmetric Positive Definite Linear Systems

We study preconditioning techniques used in conjunction with the conjugate gradient method for solving multi-length-scale symmetric positive definite linear systems originating from the quantum Monte Carlo simulation of electron interaction of correlated materials. Existing preconditioning techniques are not designed to be adaptive to varying numerical properties of the multi-length-scale systems. In this paper, we propose a hybrid incomplete Cholesky (HIC) preconditioner and demonstrate its adaptivity to the multi-length-scale systems. In addition, we propose an extension of the compressed sparse column with row access (CSCR) sparse matrix storage format to efficiently accommodate the data access pattern to compute the HIC preconditioner. We show that for moderately correlated materials, the HIC preconditioner achieves the optimal linear scaling of the simulation. The development of a linear-scaling preconditioner for strongly correlated materials remains an open topic.     

Spatially adaptive sparse grids for high-dimensional data-driven problems

Sparse grids allow one to employ grid-based discretization methods in data-driven problems. We present an extension of the classical sparse grid approach that allows us to tackle high-dimensional problems by spatially adaptive refinement, modified ansatz functions, and efficient regularization techniques. The competitiveness of this method is shown for typical benchmark problems with up to 166 dimensions for classification in data mining, pointing out properties of sparse grids in this context. To gain insight into the adaptive refinement and to examine the scope for further improvements, the approximation of non-smooth indicator functions with adaptive sparse grids has been studied as a model problem. As an example for an improved adaptive grid refinement, we present results for an edge-detection strategy.     

Matrix analysis for associated consistency in cooperative game theory

Hamiache axiomatized the Shapley value as the unique solution verifying the inessential game property, continuity and associated consistency. Driessen extended Hamiache’s axiomatization to the enlarged class of efficient, symmetric, and linear values. In this paper, we introduce the notion of row (resp. column)-coalitional matrix in the framework of cooperative game theory. The Shapley value as well as the associated game are represented algebraically by their coalitional matrices called the Shapley standard matrix M^Sh and the associated transformation matrix M_λ, respectively. We develop a matrix approach for Hamiache’s axiomatization of the Shapley value. The associated consistency for the Shapley value is formulated as the matrix equality M^Sh = M^Sh · M_λ. The diagonalization procedure of M_λ and the inessential property for coalitional matrices are fundamental tools to prove the convergence of the sequence of repeated associated games as well as its limit game to be inessential. In addition, a similar matrix approach is applicable to study Driessen’s axiomatization of a certain class of linear values. In summary, it is illustrated that matrix analysis is a new and powerful technique for research in the field of cooperative game theory.     

Approximate factoring of the inverse

Computation of approximate factors for the inverse constitutes an algebraic approach to preconditioning large and sparse linear systems. In this paper, the aim is to combine standard preconditioning ideas with sparse approximate inverse approximation, to have dense approximate inverse approximations (implicitly). For optimality, the approximate factoring problem is associated with a minimization problem involving two matrix subspaces. This task can be converted into an eigenvalue problem for a Hermitian positive semidefinite operator whose smallest eigenpairs are of interest. Because of storage and complexity constraints, the power method appears to be the only admissible algorithm for devising sparse–sparse iterations. The subtle issue of choosing the matrix subspaces is addressed. Numerical experiments are presented.     

On a finite rational criterion for the irreducibility of a matrix

A matrix A ∈ M _n (C) is said to be irreducible if the only orthoprojectors that commute with A are the zero and unit matrices. A finite rational criterion for irreducibility is proposed. The criteria for verification of this property that can be found in the literature are neither finite nor rational.     

A class of preconditioners based on matrix splitting for nonsymmetric linear systems

Given a general matrix splitting A=M-N where M is nonsingular, a new factorization scheme in terms of factorized and splitting matrices is given using the Sherman-Morrison formula. Theoretical analysis shows that the factorization can give an LDU decomposition of A under some special choices. We propose and implement a class of preconditioners based on this factorization combining with dropping rules. A number of numerical experiments from discrete convection diffusion equation and some practical problems show that the new preconditioner is efficient, and is comparable to existing preconditioners in term of storage requirement and computational cost.     

Two class of synchronous matrix multisplitting schemes for solving linear complementarity problems

Many problems in the areas of scientific computing and engineering applications can lead to the solution of the linear complementarity problem LCP (M,q). It is well known that the matrix multisplitting methods have been found very useful for solving LCP (M,q). In this article, by applying the generalized accelerated overrelaxation (GAOR) and the symmetric successive overrelaxation (SSOR) techniques, we introduce two class of synchronous matrix multisplitting methods to solve LCP (M,q). Convergence results for these two methods are presented when M is an H-matrix (and also an M-matrix). Also the monotone convergence of the new methods is established. Finally, the numerical results show that the introduced methods are effective for solving the large and sparse linear complementary problems.     

Recurrence relation for biorthogonal polynomials

We use a geometric approach to obtain a recurrence relation for two families of biorthogonal polynomials associated to a nonsingular, strongly regular matrix M. We propose a “look-ahead procedure” for computing the biorthogonal polynomials when M has singular or ill-conditioned leading principal submatrices. These polynomials lead to two recursive triangular factorizations for the inverse of a nonsingular matrix M which is not necessarily strongly regular.     

自适应稀疏伪谱逼近新方法

自适应稀疏伪谱逼近法是广义混沌多项式类方法的最新进展,相对于其它方法具有计算精度高、速度快的优点.但它仍存在如下缺点：1）终止判据对逼近误差的估计精度偏低;2）只适用于单输出问题.本文提出了适用于多输出问题且具有更高逼近精度的自适应稀疏伪谱逼近新方法.本文首先提出了新型终止判据及基于此新型终止判据的自适应稀疏伪谱逼近新方法,并以命题的形式证明了新型终止判据相比于现有终止判据具有更高的估计精度,从而使基于此的逼近函数精度更接近于预期精度;进而,本文基于指标集的统一策略和新型终止判据,提出了适用于多输出问题的自适应稀疏伪谱逼近新方法,该方法因能充分利用各输出变量的抽样结果,具有比将单输出方法直接推广到多输出问题更高的计算效率.多个算例验证了本文所提出新方法的有效性和正确性.     

Full Spark Frames

Finite frame theory has a number of real-world applications. In applications like sparse signal processing, data transmission with robustness to erasures, and reconstruction without phase, there is a pressing need for deterministic constructions of frames with the following property: every size-M subcollection of the M-dimensional frame elements is a spanning set. Such frames are called full spark frames, and this paper provides new constructions using the discrete Fourier transform. Later, we prove that full spark Parseval frames are dense in the entire set of Parseval frames, meaning full spark frames are abundant, even if one imposes an additional tightness constraint. Finally, we prove that testing whether a given matrix is full spark is hard for NP under randomized polynomial-time reductions, indicating that deterministic full spark constructions are particularly significant because they guarantee a property which is otherwise difficult to check.     

Wavelet-like bases for thin-wire integral equations in electromagnetics

In this paper, wavelets are used in solving, by the method of moments, a modified version of the thin-wire electric field integral equation, in frequency domain. The time domain electromagnetic quantities, are obtained by using the inverse discrete fast Fourier transform. The retarded scalar electric and vector magnetic potentials are employed in order to obtain the integral formulation. The discretized model generated by applying the direct method of moments via point-matching procedure, results in a linear system with a dense matrix which have to be solved for each frequency of the Fourier spectrum of the time domain impressed source. Therefore, orthogonal wavelet-like basis transform is used to sparsify the moment matrix. In particular, dyadic and M-band wavelet transforms have been adopted, so generating different sparse matrix structures. This leads to an efficient solution in solving the resulting sparse matrix equation. Moreover, a wavelet preconditioner is used to accelerate the convergence rate of the iterative solver employed. These numerical features are used in analyzing the transient behavior of a lightning protection system. In particular, the transient performance of the earth termination system of a lightning protection system or of the earth electrode of an electric power substation, during its operation is focused. The numerical results, obtained by running a complex structure, are discussed and the features of the used method are underlined.     

A hierarchical interactive method for ranking alternatives with multiple qualitative criteria

In this study we deal with the problem of finding the most preferred composite ranking of a set of alternatives evaluated using a large number of criteria having a hierarchical structure. The criteria may be qualitative or quantitative. The decision maker evaluates alternatives using each criterion at the lowest (basic) level. That information is then used to construct the generalized correlation matrix to describe interdependencies between the criteria. The correlation matrix and the criterion hierarchy are the basic information used in the approach. Our interactive approach is designed to help the decision maker find the most preferred aggregation of the kth level criteria, which produces the criteria at the (k + 1)st level. As the final result of the aggregation we obtain the strength of the preference matrix for the criterion at the highest level. By means of that matrix, we produce the final ranking of the alternatives using the Bowman and Colantoni (1973) model. The approach is easy to implement and convenient to use. We have implemented an experimental version of it on an Apple III microcomputer. The graphical colour display is used as an aid in finding the most preferred aggregation. An illustrative example is provided.