5352108
Efficient parallelization of the iterative solution of a coupled fluid-structure interaction problem
In this paper we consider the parallelization of the generation and iterative solution of coupled linear systems modelling the interaction of an acoustic field in a fluid medium with an elastic structure immersed in the fluid. The particular case studied is that of a hollow steel sphere in water. The aim of the work is to speed up the generation and solution of the systems. We describe the methods used, which involve special sparse storage arrangements and a novel application of a sparse approximate inverse preconditioning technique, and present results showing that the methods are very effective in terms of speeding up the generation and iterative solution of the systems. Copyright © 2007 John Wiley & Sons, Ltd.
3879090
On A Recursive Schur Preconditioner For Iterative Solution Of A Class Of Dense Matrix Problems
There are currently several distinct preconditioning methods for dense matrices based on applying a wavelet transform to obtain a matrix with a large number of small entries. A sparse preconditioner for this transformed matrix can be formed by setting to zero entries that are assumed to be unimportant. The effectiveness of the preconditioner depends on retaining the most important entries and on ensuring that they are positioned conveniently within the transformed matrix. In this paper we present a new, recursive preconditioning strategy that takes into account more of the significant entries without greatly increasing cost and outperforms existing methods in certain cases.
15785287
A Nonlinear Multigrid Method for Total Variation Minimization from Image Restoration
Abstract
Image restoration has been an active research topic and variational formulations are particularly effective in high quality recovery. Although there exist many modelling and theoretical results, available iterative solvers are not yet robust in solving such modeling equations. Recent attempts on developing optimisation multigrid methods have been based on first order conditions. Different from this idea, this paper proposes to use piecewise linear function spanned subspace correction to design a multilevel method for directly solving the total variation minimisation. Our method appears to be more robust than the primal-dual method (Chan et al., SIAM J. Sci. Comput. 20(6), 1964–1977, 1999) previously found reliable. Supporting numerical results are presented.

21847139
An Analysis of Sparse Approximate Inverse Preconditioners for Boundary Integral Equations
Preconditioning techniques for dense linear systems arising from singular boundary integral equations are described and analyzed. A particular class of approximate inverse based preconditioners related to the mesh neighbor methods is known to be efficient. This paper shows that it is an operator splitting preconditioner and clusters eigenvalues for the normal equation matrix thus ensuring a fast convergence of the conjugate gradient normal method. Clustering of the eigenvalues of the preconditioned matrix and fast convergence of the generalized minimal residual method are also observed. For the type of problems considered, we demonstrate a crucial connection between two essential features of eigenvalue clustering for a sparse preconditioner---approximate inversion for a small cluster radius and operator splitting for a small cluster size. Experimental results from several boundary integral equations are presented.
25215706
On Two Variants of an Algebraic Wavelet Preconditioner
A recursive method of constructing preconditioning matrices for the nonsymmetric stiffness matrix in a wavelet basis is proposed for solving a class of integral and differential equations. It is based on a level-by-level application of the wavelet scales decoupling the different wavelet levels in a matrix form just as in the well-known nonstandard form. The result is a powerful iterative method with built-in preconditioning leading to two specific algebraic multilevel iteration algorithms: one with an exact Schur preconditioning and the other with an approximate Schur preconditioning. Numerical examples are presented to illustrate the efficiency of the new algorithms.
12726286
Fast Multilevel Algorithm for a Minimization Problem in Impulse Noise Removal
An effective 2-phase method for removing impulse noise was recently proposed. Its phase 1 identifies noisy pixel candidates by using median-type filters. Then in phase $2$, it restores only the noisy pixel candidates by some variational methods. The resulting method can handle salt-and-pepper noise and random-valued impulse noise at a level as high as 90% and 60%, respectively. The aim of this paper is to generalize a fast multilevel method for Gaussian denoising to solving the minimization problem arising in phase $2$ of the 2-phase method. The multilevel algorithm gives better images than standard optimization methods such as the Newton method or the conjugate gradient method. Also it can handle more general regularization functionals than the smooth ones previously considered. Supporting numerical experiments on two-dimensional gray-scale images are presented.
24158595
A Fractal Watermark Solution for Product Data
Copyright and integrity protection over product data is becoming an urgent requirement, because in a Distributed Networked Manufacturing environment, enterprises have to interact with each other to share product data. In this paper, we introduce a novel watermarking solution for product data based on the idea of fractal, which classifies product data watermarks into three tiers: fractal watermark, tree-structure watermark, and tree-node watermark. It embeds watermarks not only in value-carrying nodes but also in product structures that "glue" all the nodes together by embedding multiple structure watermarks in product data. Simulation results show that the proposed technique is robust against various forms of malicious attacks of product data, and naturally immune from structure transformation attacks and subtractive (sub-tree) attacks. Moreover, the solution can protect tree-structure data whose knowledge is mainly embodied in the tree structure efficiently. It is very easy to implement and popularize.
11647155
Methods of Combining Multiple Classifiers with Different Features and Their Applications to Text-Independent Speaker Identification
In practical applications of pattern recognition, there are often different features extracted from raw data which needs recognizing. Methods of combining multiple classifiers with different features are viewed as a general problem in various application areas of pattern recognition. In this paper, a systematic investigation has been made and possible solutions are classified into three frameworks, i.e. linear opinion pools, winner-take-all and evidential reasoning. For combining multiple classifiers with different features, a novel method is presented in the framework of linear opinion pools and a modified training algorithm for associative switch is also proposed in the framework of winner-take-all. In the framework of evidential reasoning, several typical methods are briefly reviewed for use. All aforementioned methods have already been applied to text-independent speaker identification. The simulations show that results yielded by the methods described in this paper are better than not only the individual classifiers' but also ones obtained by combining multiple classifiers with the same feature. It indicates that the use of combining multiple classifiers with different features is an effective way to attack the problem of text-independent speaker identification.
32262987
Speaker Modeling with Various Speech Representations
Although numerous speech representations have been reported to be useful in speaker recognition, there is much less agreement on which speech representation provides a perfect representation of speaker-specific information. In this paper, we charaterize a speaker’s identity through the simultaneous use of various speech representations of his/her voice. We present a parametric statistical model, generalized Gaussian mixture model, and develop an EM algorithm for parameter estimation. Our approach has been applied to speaker recognition and comparative results on KING corpus demonstrate its effectiveness.
16722943
The Euclidean Orienteering Problem Revisited
We consider the rooted orienteering problem: Given a set $P$ of $n$ points in the plane, a starting point $r \in P$, and a length constraint $B$, one needs to find a path starting from $r$ that visits as many points of $P$ as possible and of length not exceeding $B$. We present a $(1-\varepsilon)$-approximation algorithm for this problem that runs in $n^{O(1/\varepsilon)}$ time; the computed path visits at least $ (1-\varepsilon)k_{\mathrm{opt}}$ points of $P$, where $k_{\mathrm{opt}}$ is the number of points visited by an optimal solution. This is the first polynomial time approximation scheme for this problem. The algorithm also works in higher dimensions.
640529
Heuristic Discovery of Role-Based Trust Chains in Peer-to-Peer Networks
Credential chains are needed in trusted peer-to-peer (P2P) applications, where trust delegation must be established between each pair of peers at specific role level. Role-based trust is refined from the coarse-grained trust model used in most P2P reputation systems. This paper offers a novel heuristic-weighting approach to selecting the most likely path to construct a role-based trust chain. We apply history-sensitive heuristics to measure the path complexity and assess the chaining efficiency. We discover successive edges of a trust chain, adaptively, to match with the demands from various P2P applications. New heuristic chaining algorithms are developed for backward, forward, and bi-directional discovery of trust chains. Our heuristic chain discovery scheme shortens the search time, reduces the memory requirement, and enhances the chaining accuracy in scalable P2P networks. Consider a trust graph over N credentials and M distinct role nodes. Our heuristic trust-chain discovery algorithms require O(N2 logN) search time and O(M) memory space, if the secondary heuristics are generated off-line in advance. These are improved from O(N3) search time and O(NM) space required in non-heuristic discovery algorithms by Li, Winsborough, and Mitchell (2003). Our analytical results are verified by extensive simulation experiments over typical classes of role-based trust graphs.