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]

In this paper we establish an algorithmic framework between bin packing and strip packing, with which strip packing can be very well approximated by applying some bin packing algorithms. More precisely we obtain the following results: (1) Any off-line bin packing algorithm can be applied to strip packing maintaining almost the same asymptotic worst-case ratio. (2) A class of Harmonic-based algorithms for bin packing, such as Refined Harmonic, Modified Harmonic, Harmonic++, can be applied to online strip packing. In particular, we show that online strip packing admits an upper bound of 1.58889 + ϵ on the asymptotic competitive ratio, for any arbitrarily small ϵ > 0 . This significantly improves the previously best bound of 1.6910 and affirmatively answers an open question posed by Csirik and Woeginger (1997). Moreover, the time complexity mainly depends on a sorting procedure and the bin packing algorithms employed. [ABSTRACT FROM AUTHOR]

Abstract: In DeVore et al. (2011) we considered smooth functions on which depend on a much smaller number of variables or continuous functions which can be approximated by such functions. We were interested in approximating those functions when we can calculate point values at points of our choice. The number of points we needed for non-adaptive algorithms was higher than that in the adaptive case. In this paper we improve on DeVore et al. (2011) and show that in the non-adaptive case one can use the same number of points (up to a multiplicative constant depending on ) that we need in the adaptive case. [Copyright &y& Elsevier]

Abstract: Scheduling of large-scale, distributed topology-aware applications requires that not only the properties of the requested machines be considered, but also the properties of the machines’ interconnections. This requirement severely complicates the scheduling process, as even a matching between a single multi-processor task and available machines in a single time slot becomes an NP-complete problem with no polynomial approximation. In this paper we propose a complete scheduling framework for multi-cluster, heterogeneous environments that provides, in practice, an efficient solution for the scheduling of topology-aware applications. The proposed framework is very flexible as it is composed of pluggable components and can be easily configured to support a variety of scheduling policies. We also describe three novel scheduling and coallocation algorithms that were developed and plugged into the framework. The proposed scheduling framework was integrated into the QosCosGrid 1 [1] http://www.qoscosgrid.eu. system, where it is used as the main decision-making module. [ABSTRACT FROM AUTHOR]

The fast multipole method (FMM), which is originally an algorithm for fast evaluation of particle interactions, is also effective for accelerating several numerical computations. Yarvin and Rokhlin proposed “generalized” FMM using the singular value decomposition (SVD), which gives the optimum low-rank approximation. Their algorithm reduces the computational costs of the FMM evaluation and frees the FMM from analytical approximation formulae. However, the computational complexity of the preprocessing for an N×N matrix is O(N3) because of the SVD, and it requires orthogonal matrices of the low-rank approximations. In this paper we propose another preprocessing algorithm for the generalized FMM. Our algorithm runs in time O(N2) even with the SVD and releases the low-rank approximations from orthogonal matrices. The triangularization by the QR decomposition with sparsification, which reduces the costs of the FMM more than the diagonalization, is enabled. Although the algorithm by Yarvin and Rokhlin can be accelerated to O(N2) using the QR decomposition, our preprocessing algorithm outperforms it in fast spherical filter, fast polynomial interpolation and fast Legendre transform. [Copyright &y& Elsevier]