Explicit preconditioned iterative methods for solving large unsymmetric finite element systems

A class of Generalized Approximate Inverse Matrix (GAIM) techniques, based on the concept of LU-sparse factorization procedures, is introduced for computing explicitly approximate inverses of large sparse unsymmetric matrices of irregular structure, without inverting the decomposition factors. Explicit preconditioned iterative methods, in conjunction with modified forms of the GAIM techniques, are presented for solving numerically initial/boundary value problems on multiprocessor systems. Application of the new methods on linear boundary-value problems is discussed and numerical results are given.     

A class of explicit preconditioned conjugate gradient methods for solving large finite element systems

A class of Explicit Preconditioned Conjugate Gradient (EPCG) methods for solving large sparse linear systems of algebraic equations resulting from the Finite Element discretization of Elliptic and Parabolic PDE's is introduced. The EPCG methods are based on explicit Approximate Inverse Matrix techniques and are particularly suitable for solving numerically initial/boundary-value problems on multiprocessor systems. The application of the new methods on 2D-linear boundary-value problems is discussed and numerical results are given.     

Explicit semi-direct methods based on approximate inverse matrix techniques for solving boundary-value problems on parallel processors

Generalized approximate inverse matrix techniques and sparse Gauss-Jordan elimination procedures based on the concept of sparse product form of the inverse are introduced for calculating explicitly approximate inverses of large sparse unsymmetric (n × n) matrices. Explicit first and second order semi-direct methods in conjunction with the derived approximate inverse matrix techniques are presented for solving Parabolic and Elliptic difference equations on parallel processors. Application of the new methods on a 2D-model problem is discussed and numerical results are given.     

Isomorphic iterative methods in solving singularly perturbed elliptic difference equations

A new approach for the efficient numerical solution of Singular Perturbation (SP) second order boundary-value problems based on Gradient-type methods is introduced. Isomorphic implicit iterative schemes in conjuction with the Extended to the Limit sparse factorization procedures [9] are used for solving SP second order elliptic equations in two and three-space dimensions. Theoretical results on the convergence rate of these first-degree iterative methods for three-space variables are presented. The application of the new methods on characteristic SP boundary-value problems is discussed and numerical results are given.     

Computing the minimal relations in point-based qualitative temporal reasoning through metagraph closure

Computing the minimal representation of a given set of constraints (a CSP) over the Point Algebra (PA) is a fundamental temporal reasoning problem. The main property of a minimal CSP over PA is that the strongest entailed relation between any pair of variables in the CSP can be derived in constant time. We study some new methods for solving this problem which exploit and extend two prominent graph-based representations of a CSP over PA: the timegraph and the series-parallel (SP) metagraph. Essentially, these are graphs partitioned into sets of chains and series-parallel subgraphs, respectively, on which the search is supported by a metagraph data structure. The proposed approach is based on computing the metagraph closure for these representations, which can be accomplished by some methods studied in the paper.In comparison with the known techniques based on enforcing path consistency, under certain conditions about the structure of the input CSP and the size of the generated metagraph, the proposed metagraph closure approach has better worst-case time and space complexity. Moreover, for every sparse CSP over the convex PA, the time complexity is reduced to O(n²) from O(n³), where n is the number of variables involved in the CSP.An extensive experimental analysis presented in the paper compares the proposed techniques and other known algorithms. These experimental results identify the best performing methods and show that, in practice, for CSPs exhibiting chain or SP-graph structure and randomly generated (both sparse and dense) CSPs, the metagraph closure approach is significantly faster than the approach based on enforcing path consistency.     

The use of the generalized extended to the limit sparse factorization techniques for the solution of non-linear elliptic and parabolic difference equations

Generalized Extended to the Limit LU sparse factorization procedures for the solution of large sparse unsymmetric linear systems of irregular and unsymmetric structure are presented. Composite “inner-outer” iterative schemes incorporating these procedures are introduced for solving non-linear elliptic and parabolic difference equations. Applications of the methods on non-linear boundary-value problems are discussed and numerical results are given.     

A Compressed Diagonals Remapping Technique for Dynamic Data Redistribution on Banded Sparse Matrix

In many scientific applications, dynamic data redistribution is used to enhance algorithm performance and achieve data locality in parallel programs on distributed memory multi-computers. In this paper, we present a new method, Compressed Diagonals Remapping (CDR) technique aims to the efficiency of runtime data redistribution on banded sparse matrices. The main idea of the proposed technique is first to compress the source matrix into a Compressed Diagonal Matrix (CDM) form. Based on the compressed diagonal matrix, a one-dimensional local and global index transformation method can be applied to carry out data redistribution on the compressed diagonal matrix. This process is identical to redistribute data in the two-dimensional banded sparse matrix. The CDR technique uses an efficient one-dimensional indexing scheme to perform data redistribution on banded sparse matrix. A significant improvement of this approach is that a processor does not need to determine the complicated sending or receiving data sets for dynamic data redistribution. The indexing cost is reduced significantly. The second advantage of the present techniques is the achievement of optimal packing/unpacking stages consequent upon the consecutive attribute of column elements in a compressed diagonal matrix. Another contribution of our methods is the ability to handle sparse matrix redistribution under two disjoint processor grids in the source and destination phases. A theoretical model to analyze the performance of the proposed technique is also presented in this paper. To evaluate the performance of our methods, we have implemented the present techniques on an IBM SP2 parallel machine along with the v2m algorithm and a dense redistribution strategy. The experimental results show that our technique provides significant improvement for runtime data redistribution of banded sparse matrices in most test samples.     

Spline approximate solution of eighth-order boundary-value problems

We use non-polynomial spline functions to develop numerical methods for the solution of the eighth-order linear boundary-value problems. End conditions of the spline are derived. We compare our results with the results produced by decomposition method and polynomial spline method. However, it is observed that our approach produce better numerical solutions in the sense that max |e _i | is minimum.     

Data Mining with Sparse Grids

O (h _n ⁻¹ n ^{d −1}) instead of O(h _n ^−d ) grid points and unknowns are involved. Here d denotes the dimension of the feature space and h _n = 2 ⁻ⁿ gives the mesh size. To be precise, we suggest to use the sparse grid combination technique [42] where the classification problem is discretized and solved on a certain sequence of conventional grids with uniform mesh sizes in each coordinate direction. The sparse grid solution is then obtained from the solutions on these different grids by linear combination. In contrast to other sparse grid techniques, the combination method is simpler to use and can be parallelized in a natural and straightforward way. We describe the sparse grid combination technique for the classification problem in terms of the regularization network approach. We then give implementational details and discuss the complexity of the algorithm. It turns out that the method scales only linearly with the number of instances, i.e. the amount of data to be classified. Finally we report on the quality of the classifier built by our new method. Here we consider standard test problems from the UCI repository and problems with huge synthetical data sets in up to 9 dimensions. It turns out that our new method achieves correctness rates which are competitive to that of the best existing methods. Received April 25, 2001     

Multiscale Annealing for Grouping and Unsupervised Texture Segmentation

We derive real-time global optimization methods for several clustering optimization problems commonly used in unsupervised texture segmentation. Speed is achieved by exploiting the image neighborhood relation of features to design a multiscale optimization technique, while accuracy and global optimization properties are gained using annealing techniques. Coarse grained cost functions are derived for central and histogram-based clustering as well as several sparse proximity-based clustering methods. For optimization deterministic annealing algorithms are applied. Annealing schedule, coarse-to-fine optimization and the estimated number of segments are tightly coupled by a statistical convergence criterion derived from computational learning theory. The notion of optimization scale parametrized by a computational temperature is thus unified with the scales defined by the image resolution and the model or segment complexity. The algorithms are benchmarked on Brodatz-like microtexture mixtures. Results are presented for an autonomous robotics application. Extensions are discussed in the context of prestructuring large image databases valuable for fast and reliable image retrieval.     

Generalized extended to the limit sparse factorization techniques for solving unsymmetric finite element systems

Generalized extended to the limit sparse factorization procedures in algorithmic form are derived yielding direct and iterative methods for the solution of unsymmetric finite element or finite difference systems of irregular structure. The proposed approximate factorization procedures are chosen as the basis to yield systems on which Chebyshev methods are implicitly applied. Application of the methods on a two dimensional linear boundary-value problem is discussed and numerical results are given.     

Piecewise-linearized and linearized θ-methods for ordinary and partial differential equations

Initial- and boundary-value problems appear frequently in many branches of physics. In this paper, several numerical methods, based on linearization techniques, for solving these problems are reviewed. First, piecewise-linearized methods and linearized θ-methods are considered for the solution of initial-value problems in ordinary differential equations. Second, piecewise-linearized techniques for two-point boundary-value problems in ordinary differential equations are developed and used in conjunction with a shooting method. In order to overcome the lack of convergence associated with shooting, piecewise-linearized methods which provide piecewise analytical solutions and yield nonstandard finite difference schemes are presented. Third, methods of lines in either space or time for the solution of one-dimensional convection-reaction-diffusion problems that transform the original problem into an initial- or boundary-value one are reviewed. Methods of lines in time that result in boundary-value problems at each time step can be solved by means of the techniques described here, whereas methods of lines in space that yield initial-value problems and employ either piecewise-linearized techniques or linearized θ-methods in time are also developed. Finally, for multidimensional problems, approximate factorization methods are first used to transform the multidimensional problem into a sequence of one-dimensional ones which are then solved by means of the linearized and piecewise-linearized methods presented here.     

Sparse Matrix Block-Cyclic Realignment on Distributed Memory Machines

Modifying the data distribution over the course of a program to adapt to variations in the data access patterns may leads to significant computational benefits in many scientific applications. Therefore, dynamic realignment of data is used to enhance algorithm performance in parallel programs on distributed memory machines. This paper presents a new method aims to the efficiency of block-cyclic data realignment of sparse matrix. The main idea of the proposed technique is first todevelop closed forms for generating the Vector Index Set (VIS) of each source/destination processor. Based on the vector index set and the nonzero structure of sparse matrix, two efficient algorithms,vector2message (v2m) and message2vector (m2v) can be derived. The proposed technique uses v2m to extract nonzero elements from source compressed structures and packs them into messages in the source stage; and uses m2v to unpack each received messages and construct the destination matrix in the destination stage. A significant improvement of this approach is that a processor does not need to determine the complicated sending or receiving data sets for dynamic data redistribution. The indexing cost is reduced obviously. The second advantage of the present techniques is the achievement of optimal packing/unpacking stages consequent upon the informative VIS tables. Another contribution of our methods is the ability to handle sparse matrix redistribution under two disjoint processor grids in the source and destination phases. A theoretical model to analyze the performance of the proposed technique is also presented in this work. To evaluate the performance of our methods, we have implemented the present algorithms on an IBM SP2 parallel machine along with the Histogram method and a dense redistribution strategy. The experimental results show that our technique provides significant improvement for runtime data redistribution of sparse matrices in most test samples.     

基于深度稀疏自动编码器的社区发现算法

社区结构是复杂网络的一个重要特征,社区发现对研究网络结构有重要的应用价值.k-均值等经典聚类算法是解决社区发现问题的一类基本方法.然而,在处理网络的高维矩阵时,使用这些经典聚类方法得到的社区往往不够准确.提出一种基于深度稀疏自动编码器的社区发现算法CoDDA,尝试提高使用这些经典方法处理高维邻接矩阵进行社区发现的准确性.首先,提出基于跳数的处理方法,对稀疏的邻接矩阵进行优化处理.得到的相似度矩阵不仅能反映网络拓扑结构中相连节点间的相似关系,同时能反映不相连节点间的相似关系.接着,基于无监督深度学习方法,构建深度稀疏自动编码器,对相似度矩阵进行特征提取,得到低维的特征矩阵.与邻接矩阵相比,特征矩阵对网络拓扑结构有更强的特征表达能力.最后,使用k-均值算法对低维特征矩阵聚类得到社区结构.实验结果显示,与6种典型的社区发现算法相比,CoDDA算法能够发现更准确的社区结构.同时,参数实验结果显示,CoDDA算法发现的社区结构比直接使用高维邻接矩阵的基本k-均值算法发现的社区结构更为准确.     

An Approximate Solution for a Class of Second-Order Elliptic Variational Inequalities in Arbitrary-Form Domains

Penalty and dummy-domain methods are used to approximate second-order elliptic variational inequalities with a restriction inside a domain by nonlinear boundary-value problems in a rectangle. Difference schemes, with the order of accuracy O(h ^1/2) in the grid norm W ₂ ¹(), are constructed for these problems.     

Solving linear finite element systems by normalized approximate matrix factorization semi-direct methods

New normalized Extended to the Limit sparse factorization procedures in algorithmic form are derived yielding direct and iterative methods for the solution of finite element or finite difference systems of irregular structure. The proposed factorization procedures are chosen as the basis to yield normalized systems on which the Conjugate Gradient and Chebychev methods are implicitly applied. The application of the derived normalized implicit semi-direct methods on a two-dimensional elliptic boundary-value problem is discussed and numerical results are given.     

A new steganography algorithm based on video sparse representation

Steganography has been a great interest since long time ago. There are a lot of methods that have been widely used since long past. Recently, there has been a growing interest in the use of sparse representation in signal processing. Sparse representation can efficiently model signals in different applications to facilitate processing. Much of the previous work was focused on image and audio sparse representation for steganography. In this paper, a new steganography scheme based on video sparse representation (VSR) is proposed. To exploit proper dictionary, KSVD algorithm is applied to DCT coefficients of Y component related to video (cover) frames. Both I and Q components of video frames are used for secure message insertion. The aim is to hide secret messages into non-zero coefficients of sparse representation of DCT called, I and Q video frames. Several experiments are performed to evaluate the performance of the proposed algorithm, in case of some metrics such as pick signal to noise ratio (PSNR), the hiding ratio (HR), bit error rate (BER) and similarity (Sim) of secret message, and also runtime. The simulation results show that the proposed method exhibits appropriate invisibility and robustness.

     

Numerical solution of non-linear elliptic boundary-value problems by isomorphic iterative methods

New implicit iterative methods are presented for the efficient numerical solution of non-linear elliptic boundary-value problems. Isomorphic iterative schemes in conjunction with preconditioning techniques are used for solving non-linear elliptic equations in two and three-space dimensions. The application of the derived methods on characteristic 2D and 3D non-linear boundary-value problems is discussed and numerical results are given.     

Factorized Sparse Approximate Inverses for Preconditioning

In recent papers the use of sparse approximate inverses for the preconditioning of linear equations Ax=b is examined. The minimization of ||AM–I|| in the Frobenius norm generates good preconditioners without any a priori knowledge on the pattern of M. For symmetric positive definite A and a given a priori pattern there exist methods for computing factorized sparse approximate inverses L with LL ^T A ^–1. Here, we want to modify these algorithms that they are able to capture automatically a promising pattern for L.We use these approximate inverses for solving linear equations with the cg-method. Furthermore we introduce and test modifications of this method for computing factorized sparse approximate inverses.     

Fast Fluid Simulations with Sparse Volumes on the GPU

We introduce efficient, large scale fluid simulation on GPU hardware using the fluid‐implicit particle (FLIP) method over a sparse hierarchy of grids represented in NVIDIA^® GVDB Voxels. Our approach handles tens of millions of particles within a virtually unbounded simulation domain. We describe novel techniques for parallel sparse grid hierarchy construction and fast incremental updates on the GPU for moving particles. In addition, our FLIP technique introduces sparse, work efficient parallel data gathering from particle to voxel, and a matrix‐free GPU‐based conjugate gradient solver optimized for sparse grids. Our results show that our method can achieve up to an order of magnitude faster simulations on the GPU as compared to FLIP simulations running on the CPU.