Search

We describe a subdivision algorithm for isolating the complex roots of a polynomial F ∈ C [ x ] . Given an oracle that provides approximations of each of the coefficients of F to any absolute error bound and given an arbitrary square B in the complex plane containing only simple roots of F , our algorithm returns disjoint isolating disks for the roots of F in B . Our complexity analysis bounds the absolute error to which the coefficients of F have to be provided, the total number of iterations, and the overall bit complexity. It further shows that the complexity of our algorithm is controlled by the geometry of the roots in a near neighborhood of the input square B , namely, the number of roots, their absolute values and pairwise distances. The number of subdivision steps is near-optimal. For the benchmark problem , namely, to isolate all the roots of a polynomial of degree n with integer coefficients of bit size less than τ , our algorithm needs O ˜ ( n 3 + n 2 τ ) bit operations, which is comparable to the record bound of Pan (2002) . It is the first time that such a bound has been achieved using subdivision methods, and independent of divide-and-conquer techniques such as Schönhage's splitting circle technique. Our algorithm uses the quadtree construction of Weyl (1924) with two key ingredients: using Pellet's Theorem (1881) combined with Graeffe iteration, we derive a “soft-test” to count the number of roots in a disk. Using Schröder's modified Newton operator combined with bisection, in a form inspired by the quadratic interval method from Abbot (2006), we achieve quadratic convergence towards root clusters. Relative to the divide-conquer algorithms, our algorithm is quite simple with the potential of being practical. This paper is self-contained: we provide pseudo-code for all subroutines used by our algorithm. [ABSTRACT FROM AUTHOR]

Abstract: This paper works on joint approximate diagonalization of simplified fourth order cumulant matrices for very fast and large scale blind separation of instantaneous mixing model sources. The JADE algorithm is widely accepted but only limited to small scale separation tasks. The SHIBBS algorithm calculates a fraction of the fourth order cumulant set and avoids eigenmatrix decomposition to reduce calculation cost. However, it was seen to be slower than JADE at the time of its first publication and is hence less known. On the other hand, the SJAD algorithm using the same approach is shown to be very fast. This paper studies the iteration convergence criterion and proposes to use a signal to noise ratio based iteration stopping threshold approach. The improved SHIBBS/SJAD algorithm is very fast, and capable of large scale separation. Experimental separation comparisons between the SHIBBS/SJAD and FastICA are presented. [Copyright &y& Elsevier]

The most common method to compute wedgelet transform is based on exhaustive search which requires assessment of all wedgelet atoms and hence is prohibitively slow. In this paper, the discontinuous edge model of the wedgelet is replaced by a continuous differentiable model to make gradient based estimation of the edge parameters possible. The proposed estimation based approach contributes to a surprisingly fast algorithm called Iterative Wedgelet Transform , which leads to a better tradeoff between quality and computation speed compared to the existing approaches. Performance of the proposed method is studied in the image approximation task and the results are compared with two other major algorithms, namely classical Wedgelet Transform and Moments-based Wedgelet Transform . The iterative algorithm is shown to be much faster than classical wedgelet transform, O ( N 2 log 2 N ) given an N × N image; and compared to the moments-based method exhibits higher precision. [ABSTRACT FROM AUTHOR]

Abstract: This paper presents a preconditioner for non-overlapping Schwarz methods applied to the Helmholtz problem. Starting from a simple analytic example, we show how such a preconditioner can be designed by approximating the inverse of the iteration operator for a layered partitioning of the domain. The preconditioner works by propagating information globally by concurrently sweeping in both directions over the subdomains, and can be interpreted as a coarse grid for the domain decomposition method. The resulting algorithm is shown to converge very fast, independently of the number of subdomains and frequency. The preconditioner has the advantage that, like the original Schwarz algorithm, it can be implemented as a matrix-free routine, with no additional preprocessing. [Copyright &y& Elsevier]

Abstract: In this paper, we investigate a non-iterative imaging algorithm based on the topological derivative in order to retrieve the shape of penetrable electromagnetic inclusions when their dielectric permittivity and/or magnetic permeability differ from those in the embedding (homogeneous) space. The main objective is the imaging of crack-like thin inclusions, but the algorithm can be applied to arbitrarily shaped inclusions. For this purpose, we apply multiple time-harmonic frequencies and normalize the topological derivative imaging function by its maximum value. In order to verify its validity, we apply it for the imaging of two-dimensional crack-like thin electromagnetic inhomogeneities completely hidden in a homogeneous material. Corresponding numerical simulations with noisy data are performed for showing the efficacy of the proposed algorithm. [Copyright &y& Elsevier]

Abstract: In this paper we propose a variation of the soft-thresholding algorithm for finding sparse approximate solutions of the equation , where as the sparsity of the iterate increases the penalty function changes. In this approach, sufficiently large entries in a sparse iterate are left untouched. The advantage of this approach is that a higher regularization constant can be used, leading to a significant reduction of the total number of iterations. Numerical experiments for sparse recovery problems, also with noisy data, are included. [Copyright &y& Elsevier]

Abstract: The solution of time-dependent PDE-constrained optimization problems subject to unsteady flow equations presents a challenge to both algorithms and computing power. In this paper we present an all-at-once approach where we solve for all time-steps of the discretized unsteady Stokes problem at once. The most desirable feature of this approach is that for all steps of an iterative scheme we only need approximate solutions of the discretized Stokes operator. This leads to an efficient scheme which exhibits mesh-independent behaviour. [Copyright &y& Elsevier]

Abstract: In this paper, we present iteration schemes to weakly and strongly approximate common fixed points of a finite family of a class of strict pseudocontractions. [Copyright &y& Elsevier]

Abstract: In this paper we describe a method that can be used for Minimum Bayes Risk (MBR) decoding for speech recognition. Our algorithm can take as input either a single lattice, or multiple lattices for system combination. It has similar functionality to the widely used Consensus method, but has a clearer theoretical basis and appears to give better results both for MBR decoding and system combination. Many different approximations have been described to solve the MBR decoding problem, which is very difficult from an optimization point of view. Our proposed method solves the problem through a novel forward–backward recursion on the lattice, not requiring time markings. We prove that our algorithm iteratively improves a bound on the Bayes risk. [Copyright &y& Elsevier]

Abstract: This paper presents an output-based adaptive algorithm for unsteady simulations of convection-dominated flows. A space–time discontinuous Galerkin discretization is used in which the spatial meshes remain static in both position and resolution, and in which all elements advance by the same time step. Error estimates are computed using an adjoint-weighted residual, where the discrete adjoint is computed on a finer space obtained by order enrichment of the primal space. An iterative method based on an approximate factorization is used to solve both the forward and adjoint problems. The output error estimate drives a fixed-growth adaptive strategy that employs hanging-node refinement in the spatial domain and slab bisection in the temporal domain. Detection of space–time anisotropy in the localization of the output error is found to be important for efficiency of the adaptive algorithm, and two anisotropy measures are presented: one based on inter-element solution jumps, and one based on projection of the adjoint. Adaptive results are shown for several two-dimensional convection-dominated flows, including the compressible Navier–Stokes equations. For sufficiently-low accuracy levels, output-based adaptation is shown to be advantageous in terms of degrees of freedom when compared to uniform refinement and to adaptive indicators based on approximation error and the unweighted residual. Time integral quantities are used for the outputs of interest, but entire time histories of the integrands are also compared and found to converge rapidly under the proposed scheme. In addition, the final output-adapted space–time meshes are shown to be relatively insensitive to the starting mesh. [Copyright &y& Elsevier]