Search

The selective delayless subband structure stands out as a promising algorithmic choice for the multi-channel active control of vehicle interior noise, particularly in the context of road noise. This type of algorithm reduces the eigenvalue spread of the autocorrelation matrix of the signal by decomposing the signal into subbands, and the desired subbands are activated selectively, thus achieving a significant performance improvement while consuming less computational resources compared with the traditional fullband algorithms. Nevertheless, the effectiveness of the subband algorithm appears to be closely tied to the configuration of the primary disturbance signal. In cases where the primary disturbance signal encompasses both broadband and tonal components, the performance advantage of the subband algorithm becomes constrained. In this paper, we conduct a thorough comparative analysis of two extensively employed subband algorithms, namely the Morgan and the Milani methods, through simulations employing data obtained from a multi-channel active noise control (ANC) headrest system. The results indicate that the Morgan method outperforms the Milani method when configured optimally. Subsequently, we propose an enhanced version of the subband algorithm based on the Morgan method. The enhanced algorithm incorporates an additional sinusoidal noise canceller (SNC) subsystem and a narrowband active noise control (NANC) subsystem based on local secondary path modeling to address tonal components, while the selective subband structure is employed for controlling broadband components. In addition, the computational complexity of the algorithm is analyzed. The effectiveness of the proposed algorithm is validated through numerous simulations and the ANC tests conducted on an actual vehicle utilizing the multi-channel ANC headrest system. The performance of the proposed algorithm surpasses that of traditional selective subband and fullband algorithms, and balanced binaural noise reduction is achieved. [ABSTRACT FROM AUTHOR]

Satisfiability of word equations problem is: Given two sequences consisting of letters and variables decide whether there is a substitution for the variables that turns this equation into true equality. The exact computational complexity of this problem remains unknown, with the best lower and upper bounds being, respectively, NP and PSPACE. Recently, the novel technique of recompression was applied to this problem, simplifying the known proofs and lowering the space complexity to (non-deterministic) O (n log ⁡ n). In this paper we show that satisfiability of word equations is in non-deterministic linear space, thus the language of satisfiable word equations is context-sensitive. We use the known recompression-based algorithm and additionally employ Huffman coding for letters. The proof, however, uses analysis of how the fragments of the equation depend on each other as well as a new strategy for non-deterministic choices of the algorithm. [ABSTRACT FROM AUTHOR]

Abstract Extracting impulsive information under strong background noise and harmonic interference is a challenging problem for bearing fault diagnosis. Multi-scale transforms have achieved great success in extracting impulsive feature information, however, how to choose a suitable transform is a difficult problem, especially in the case of strong noise interference. Therefore, dictionary learning methods have attracted more and more attention in recent years. A weighted multi-scale dictionary learning model (WMSDL) is proposed in this paper which integrates the multi-scale transform and fault information into a unified dictionary learning model and it successfully overcomes four disadvantages of traditional dictionary learning algorithms including lacking the multi-scale property; restricting training samples to local patches; being sensitive to strong harmonic interference; suffering from high computational complexity. Moreover, algorithmic derivation, computational complexity and parameter selection are discussed. Finally, The effectiveness of the proposed method is verified by both the numerical simulations and experiments. Comparisons with other state-of-the-art methods further demonstrate the superiority of the proposed method. [ABSTRACT FROM AUTHOR]

Highlights • We model the RD cost comparison as a MDP for low complexity video coding. • We learn a CU early termination classifier with end-to-end actor-critic RL algorithm. • A CU early termination algorithm independent of depths is derived for whole CTU. Abstract In this paper, we propose a Reinforcement Learning (RL) based Coding Unit (CU) early termination algorithm for High Efficiency Video Coding (HEVC). RL is utilized to learn a CU early termination classifier independent of depths for low complexity video coding. Firstly, we model the process of CU decision as a Markov Decision Process (MDP) according to the Markov property of CU decision. Secondly, based on the MDP, a CU early termination classifier independent of depths is learned from trajectories of CU decision across different depths with the end-to-end actor-critic RL algorithm. Finally, a CU decision early termination algorithm is introduced with the learned classifier, so as to reduce computational complexity of CU decision. We implement the proposed scheme with different neural network structures. Two different neural network structures are utilized in the implementation of RL based video encoder, which are evaluated to reduce video coding complexity by 34.34 % and 43.33 %. With regard to Bj ø ntegaard delta peak signal-to-noise ratio and Bj ø ntegaard delta bit rate, the results are −0.033 dB and 0.85 % , −0.099 dB and 2.56 % respectively on average under low delay B main configuration, when compared with the HEVC test model version 16.5. [ABSTRACT FROM AUTHOR]

Visualization and interaction of multidimensional data are challenges in visual data analytics, which requires optimized solutions to integrate the display, exploration and analytical reasoning of data into one visual pipeline for human-centered data analysis and interpretation. Even though it is considered to be one of the most popular techniques for visualization and analysis of multidimensional data, parallel coordinate visualization is also suffered from the visual clutter problem as well as the computational complexity problem, same as other visualization methods in which visual clutter occurs where the volume of data needs to be visualized to be increasing. One straightforward way to address these problems is to change the ordering of axis to reach the minimal number of visual clutters. However, the optimization of the ordering of axes is actually a NP-complete problem. In this paper, two axes re-ordering methods are proposed in parallel coordinates visualization: (1) a contribution-based method and (2) a similarity-based method. The contribution-based re-ordering method is mainly based on the singular value decomposition (SVD) algorithm. It can not only provide users with the mathmetical theory for the selection of the first remarkable axis, but also help with visualizing detailed structure of the data according to the contribution of each data dimension. This approach reduces the computational complexity greatly in comparison with other re-ordering methods. A similarity-based re-ordering method is based on the combination of nonlinear correlation coefficient (NCC) and SVD algorithms. By using this approach, axes are re-ordered in line with the degree of similarities among them. It is much more rational, exact and systemic than other re-ordering methods, including those based on Pearson’s correlation coefficient (PCC). Meanwhile, the paper also proposes a measurement of contribution rate of each dimension to reveal the property hidden in the dataset. At last, the rationale and effectiveness of these approaches are demonstrated through case studies. For example, the patterns of Smurf and Neptune attacks hidden in KDD 1999 dataset are visualized in parallel coordinates using contribution-based re-ordering method; NCC re-ordering method can enlarge the mean crossing angles and reduce the amount of polylines between the neighboring axes. [ABSTRACT FROM AUTHOR]

Active sound profiling (ASP) is gaining ever-increasing attention owing to its powerful ability to balance the sound pressure levels of certain frequency points or frequency bands of target noise for sound quality enhancement. Most of the current ASP algorithms, however, only focus on narrowband or broadband noise alone and the computational efficiency is very low. To alleviate this problem, a feedforward time–frequency-domain hybrid active sound profiling (TFD-HASP) algorithm is proposed in this paper. The algorithm consists of three subsystems, in which the narrowband ASP (NASP) subsystem utilizes the time-domain internal model FXLMS algorithm along with the local secondary path estimation approach, the broadband ASP (BASP) subsystem is based on the delayless frequency-domain internal model FXLMS algorithm, and the sinusoidal noise canceller (SNC) subsystem is designed to eliminate narrowband interference to the BASP subsystem. In this way, the presented TFD-HASP algorithm not only has good spectral reshaping capability for both narrowband and broadband noise components, but also requires notably low computational effort. A series of simulations are performed to evaluate the performance of the TFD-HASP algorithm. In addition, the comfortable sound quality of a real vehicle interior noise at high speed is designed and realized. Experimental results demonstrate that the proposed algorithm achieves satisfactory active sound profiling for noise with both narrowband and broadband characteristics. [ABSTRACT FROM AUTHOR]

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]

Model checking allows one to automatically verify a specification of the expected properties of a system against a formal model of its behavior (generally, a Kripke structure). Point-based temporal logics, such as LTL, CTL, and CTL ⁎ , that describe how the system evolves state-by-state, are commonly used as specification languages. They proved themselves quite successful in a variety of application domains. However, properties constraining the temporal ordering of temporally extended events as well as properties involving temporal aggregations, which are inherently interval-based, can not be properly dealt with by them. Interval temporal logics (ITLs), that take intervals as their primitive temporal entities, turn out to be well-suited for the specification and verification of interval properties of computations (we interpret all the tracks of a Kripke structure as computation intervals). In this paper, we study the model checking problem for some fragments of Halpern and Shoham's modal logic of time intervals (HS). HS features one modality for each possible ordering relation between pairs of intervals (the so-called Allen's relations). First, we describe an EXPSPACE model checking algorithm for the HS fragment of Allen's relations meets , met-by , starts , started-by , and finishes , which exploits the possibility of finding, for each track (of unbounded length), an equivalent bounded-length track representative. While checking a property, it only needs to consider tracks whose length does not exceed the given bound. Then, we prove the model checking problem for such a fragment to be PSPACE-hard. Finally, we identify other well-behaved HS fragments which are expressive enough to capture meaningful interval properties of systems, such as mutual exclusion, state reachability, and non-starvation, and whose computational complexity is less than or equal to that of LTL. [ABSTRACT FROM AUTHOR]

In this paper, we study the backward–forward algorithm as a splitting method to solve structured monotone inclusions, and convex minimization problems in Hilbert spaces. It has a natural link with the forward–backward algorithm and has the same computational complexity, since it involves the same basic blocks, but organized differently. Surprisingly enough, this kind of iteration arises when studying the time discretization of the regularized Newton method for maximally monotone operators. First, we show that these two methods enjoy remarkable involutive relations, which go far beyond the evident inversion of the order in which the forward and backward steps are applied. Next, we establish several convergence properties for both methods, some of which were unknown even for the forward–backward algorithm. This brings further insight into this well-known scheme. Finally, we specialize our results to structured convex minimization problems, the gradient-projection algorithms, and give a numerical illustration of theoretical interest. [ABSTRACT FROM AUTHOR]

The topic of this paper is the distributed and incremental generation of long executions of concurrent systems, uniformly or more generally with weights associated to elementary actions. Synchronizing sequences of letters on alphabets sharing letters are known to produce a trace in the concurrency theoretic sense, i.e. , a labeled partially ordered set. We study the probabilistic aspects by considering the synchronization of Bernoulli sequences of letters, under the light of Bernoulli and uniform measures recently introduced for trace monoids. We introduce two algorithms that produce random traces, using only local random primitives. We thoroughly study some specific examples, the path model and the ring model, both of arbitrary size. For these models, we show how to generate any Bernoulli distributed random traces, which includes the case of uniform generation. [ABSTRACT FROM AUTHOR]

Abstract: As demonstrated by Slepian et al. in a sequence of classical papers (see Slepian (1983) [33], Slepian and Pollak (1961) [34], Landau and Pollak (1961) [18], Slepian and Pollak (1964) [35], Slepian (1965) [36]), prolate spheroidal wave functions (PSWFs) provide a natural and efficient tool for computing with bandlimited functions defined on an interval. Recently, PSWFs have been becoming increasingly popular in various areas in which such functions occur – this includes physics (e.g. wave phenomena, fluid dynamics), engineering (signal processing, filter design), etc. To use PSWFs as a computational tool, one needs fast and accurate numerical algorithms for the evaluation of PSWFs and related quantities, as well as for the construction of corresponding quadrature rules, interpolation formulas, etc. During the last 15 years, substantial progress has been made in the design of such algorithms – see, for example, Xiao et al. (2001) [40] (see also Bowkamp (1947) [6], Slepian and Pollak (1961) [34], Landau and Pollak (1961) [18], Slepian and Pollak (1964) [35] for some classical results). The complexity of many of the existing algorithms, however, is at least quadratic in the band limit c. For example, the evaluation of the nth eigenvalue of the prolate integral operator requires operations (see e.g. Xiao et al. (2001) [40]); the construction of accurate quadrature rules for the integration (and associated interpolation) of bandlimited functions with band limit c requires operations (see e.g. Cheng et al. (1999) [8]). Therefore, while the existing algorithms are satisfactory for moderate values of c (e.g. ), they tend to be relatively slow when c is large (e.g. ). In this paper, we describe several numerical algorithms for the evaluation of PSWFs and related quantities, and design a class of PSWF-based quadratures for the integration of bandlimited functions. While the analysis is somewhat involved and will be published separately (currently, it can be found in Osipov and Rokhlin (2012) [27]), the resulting numerical algorithms are quite simple and efficient in practice. For example, the evaluation of the nth eigenvalue of the prolate integral operator requires operations; the construction of accurate quadrature rules for the integration (and associated interpolation) of bandlimited functions with band limit c requires operations. All algorithms described in this paper produce results essentially to machine precision. Our results are illustrated via several numerical experiments. [Copyright &y& Elsevier]

Abstract: This is part II of our paper in which we propose and develop a dynamically bi-orthogonal method (DyBO) to study a class of time-dependent stochastic partial differential equations (SPDEs) whose solutions enjoy a low-dimensional structure. In part I of our paper [9], we derived the DyBO formulation and proposed numerical algorithms based on this formulation. Some important theoretical results regarding consistency and bi-orthogonality preservation were also established in the first part along with a range of numerical examples to illustrate the effectiveness of the DyBO method. In this paper, we focus on the computational complexity analysis and develop an effective adaptivity strategy to add or remove modes dynamically. Our complexity analysis shows that the ratio of computational complexities between the DyBO method and a generalized polynomial chaos method (gPC) is roughly of order for a quadratic nonlinear SPDE, where m is the number of mode pairs used in the DyBO method and is the number of elements in the polynomial basis in gPC. The effective dimensions of the stochastic solutions have been found to be small in many applications, so we can expect m is much smaller than and computational savings of our DyBO method against gPC are dramatic. The adaptive strategy plays an essential role for the DyBO method to be effective in solving some challenging problems. Another important contribution of this paper is the generalization of the DyBO formulation for a system of time-dependent SPDEs. Several numerical examples are provided to demonstrate the effectiveness of our method, including the Navier–Stokes equations and the Boussinesq approximation with Brownian forcing. [Copyright &y& Elsevier]

In this paper, we study the abelian complexity of the Rudin–Shapiro sequence and a related sequence. We show that these two sequences share the same complexity function ρ ( n ) , which satisfies certain recurrence relations. As a consequence, the abelian complexity function is 2-regular. Further, we prove that the box dimension of the graph of the asymptotic function λ ( x ) is 3/2, where λ ( x ) = lim k → ∞ ⁡ ρ ( 4 k x ) / 4 k x and ρ ( x ) = ρ ( ⌊ x ⌋ ) for every x > 0 . [ABSTRACT FROM AUTHOR]

Two-player games on graphs provide the theoretical framework for many important problems such as reactive synthesis. While the traditional study of two-player zero-sum games has been extended to multi-player games with several notions of equilibria, they are decidable only for perfect-information games, whereas several applications require imperfect-information. In this paper we propose a new notion of equilibria, called doomsday equilibria, which is a strategy profile where all players satisfy their own objective, and if any coalition of players deviates and violates even one of the players' objective, then the objective of every player is violated. We present algorithms and complexity results for deciding the existence of doomsday equilibria for various classes of ω -regular objectives, both for imperfect-information games, and for perfect-information games. We provide optimal complexity bounds for imperfect-information games, and in most cases for perfect-information games. [ABSTRACT FROM AUTHOR]

In High Efficiency Video Coding (HEVC), intra coding plays an important role, but also involves huge computational complexity due to a flexible coding unit (CU) structure and a large number of prediction modes. This paper presents a fast algorithm based on the sole- and multi-depth texture measurements to reduce the complexity from CU size and prediction mode decisions. For the CU size decision, evaluation results in the CU coding with one and multiple depths are utilized to classify CUs into heterogeneous, homogeneous, depth-prominent and other ones. Fast CU size decisions are made for different kinds of CUs. For the prediction mode decision, the tendencies for different CU sizes are detected based on multiple depths. The number of searching modes is decreased adaptively for the CU size with fewer tendencies. Experimental results show the proposed algorithm by off-line training reduces 53.32% computational complexity, with 1.47% bit-rate increasing. [ABSTRACT FROM AUTHOR]

For random sample consensus (RANSAC) method, high levels of contamination may slow down its convergence and impede the acquisition of the optimal model. In this paper, an improved RANSAC algorithm based on SIFT matches is proposed, which could provide robust performance in high levels of contamination and with low computational complexity. The improved RANSAC algorithm is particularly tailored to planar homography, by appropriately exploring feature scales. Firstly, a new feature scale constraint, i.e., the scale variation homogeneity (SVH), is proposed by exploiting the fact that the feature scale ratio of a correct match is approximate to the actual scale variation of two matched images. As a result, the potential correct and false matches can be effectively determined by SVH. Secondly, each model is scored by the number of partial identified false matches instead of all correct matches, which will speed up the evaluation process. Finally, fast converge can be obtained by adaptive selection of the test set for determining termination criterion according to the levels of contamination. Experimental results have demonstrated that the proposed SVH-RANSAC algorithm can perform very well even in the scenario of 90% contamination level. The number of iterations could be decreased by at least 35% and computational complexity for the evaluation procedure could be decreased by at least 2.5% compared with the LO + -RANSAC. [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 this paper, we study the problem of feature extraction for pattern classification applications. RELIEF is considered as one of the best-performed algorithms for assessing the quality of features for pattern classification. Its extension, local feature extraction (LFE), was proposed recently and was shown to outperform RELIEF. In this paper, we extend LFE to the nonlinear case, and develop a new algorithm called kernel LFE (KLFE). Compared with other feature extraction algorithms, KLFE enjoys nice properties such as low computational complexity, and high probability of identifying relevant features; this is because KLFE is a nonlinear wrapper feature extraction method and consists of solving a simple convex optimization problem. The experimental results have shown the superiority of KLFE over the existing algorithms. [Copyright &y& Elsevier]

Abstract: “Clarithmetic” is a generic name for formal number theories similar to Peano arithmetic, but based on computability logic instead of the more traditional classical or intuitionistic logics. Formulas of clarithmetical theories represent interactive computational problems, and their “truth” is understood as existence of an algorithmic solution. Imposing various complexity constraints on such solutions yields various versions of clarithmetic. The present paper introduces a system of clarithmetic for polynomial time computability, which is shown to be sound and complete. Sound in the sense that every theorem T of the system represents an interactive number-theoretic computational problem with a polynomial time solution and, furthermore, such a solution can be efficiently extracted from a proof of T. And complete in the sense that every interactive number-theoretic problem with a polynomial time solution is represented by some theorem T of the system. The paper is written in a semitutorial style and targets readers with no prior familiarity with computability logic. [Copyright &y& Elsevier]

Abstract: We introduce and discuss a new computational model for the Hermite–Lagrange interpolation with nonlinear classes of polynomial interpolants. We distinguish between an interpolation problem and an algorithm that solves it. Our model includes also coalescence phenomena and captures a large variety of known Hermite–Lagrange interpolation problems and algorithms. Like in traditional Hermite–Lagrange interpolation, our model is based on the execution of arithmetic operations (including divisions) in the field where the data (nodes and values) are interpreted and arithmetic operations are counted at unit cost. This leads us to a new view of rational functions and maps defined on arbitrary constructible subsets of complex affine spaces. For this purpose we have to develop new tools in algebraic geometry which themselves are mainly based on Zariski’s Main Theorem and the theory of places (or equivalently: valuations). We finish this paper by exhibiting two examples of Lagrange interpolation problems with nonlinear classes of interpolants, which do not admit efficient interpolation algorithms (one of these interpolation problems requires even an exponential quantity of arithmetic operations in terms of the number of the given nodes in order to represent some of the interpolants). In other words, classic Lagrange interpolation algorithms are asymptotically optimal for the solution of these selected interpolation problems and nothing is gained by allowing interpolation algorithms and classes of interpolants to be nonlinear. We show also that classic Lagrange interpolation algorithms are almost optimal for generic nodes and values. This generic data cannot be substantially compressed by using nonlinear techniques. We finish this paper highlighting the close connection of our complexity results in Hermite–Lagrange interpolation with a modern trend in software engineering: architecture tradeoff analysis methods (ATAM). [Copyright &y& Elsevier]

Abstract: In this paper we analyze the equilibrium limit of the constitutive model for two-phase granular mixtures introduced in Papalexandris (2004) , and develop an algorithm for its numerical approximation. At, equilibrium, the constitutive model reduces to a strongly coupled, overdetermined system of quasilinear elliptic partial differential equations with respect to the pressure and the volume fraction of the solid granular phase. First we carry a perturbation analysis based on standard hydrostatic-type scaling arguments which reduces the complexity of the coupling of the equations. The perturbed system is then supplemented by an appropriate compatibility condition which arises from the properties of the gradient operator. Further, based on the Helmholtz decomposition and Ladyzhenskaya’s decomposition theorem, we develop a projection-type, Successive-Over-Relaxation numerical method. This method is general enough and can be applied to a variety of continuum models of complex mixtures and mixtures with micro-structure. We also prove that this method is both stable and consistent hence, under standard assumptions, convergent. The paper concludes with the presentation of representative numerical results. [Copyright &y& Elsevier]

Abstract: Compressed sensing is a technique to sample compressible signals below the Nyquist rate, whilst still allowing near optimal reconstruction of the signal. In this paper we present a theoretical analysis of the iterative hard thresholding algorithm when applied to the compressed sensing recovery problem. We show that the algorithm has the following properties (made more precise in the main text of the paper) [•] It gives near-optimal error guarantees. [•] It is robust to observation noise. [•] It succeeds with a minimum number of observations. [•] It can be used with any sampling operator for which the operator and its adjoint can be computed. [•] The memory requirement is linear in the problem size. [•] Its computational complexity per iteration is of the same order as the application of the measurement operator or its adjoint. [•] It requires a fixed number of iterations depending only on the logarithm of a form of signal to noise ratio of the signal. [•] Its performance guarantees are uniform in that they only depend on properties of the sampling operator and signal sparsity. [Copyright &y& Elsevier]

Abstract: This paper investigates a graph enumeration problem, called the maximal -subgraphs problem, where is a hereditary or connected-hereditary graph property. Formally, given a graph G, the maximal -subgraphs problem is to generate all maximal induced subgraphs of G that satisfy . This problem differs from the well-known node-deletion problem, studied by Yannakakis and Lewis [J. Lewis, On the complexity of the maximum subgraph problem, in: Proc. 10th Annual ACM Symposium on Theory of Computing, ACM Press, New York, USA, 1978, pp. 265–274; M. Yannakakis, Node- and edge-deletion NP-complete problems, in: Proc. 10th Annual ACM Symposium on Theory of Computing, ACM Press, New York, USA, 1978, pp. 253–264; J. Lewis, M. Yannakakis, The node-deletion problem for hereditary properties is NP-complete, J. Comput. System Sci. 20 (2) (1980) 219–230]. In the maximal -subgraphs problem, the goal is to produce all (locally) maximal subgraphs of a graph that have property , whereas in the node-deletion problem, the goal is to find a single (globally) maximum size subgraph with property . Algorithms are presented that reduce the maximal -subgraphs problem to an input-restricted version of this problem. These algorithms imply that when attempting to efficiently solve the maximal -subgraphs problem for a specific , it is sufficient to solve the restricted case. The main contributions of this paper are characterizations of when the maximal -subgraphs problem is in a complexity class C (e.g., polynomial delay, total polynomial time). [Copyright &y& Elsevier]

Abstract: To attack block cipher systems, it is inevitable to handle the bit-substitutions, such as S-box, cycle left shift, and expansion substitutions. In this paper, a DNA sticker algorithm for bit-substitution such as cycle left shift is proposed. The proposed algorithm requires two equal long memory strands. The first memory strand stores the original binary string, while the second memory strand stores the resulting binary string. With the proposed algorithm, cycle left shift is performed on a mass of equal long binary strings, and the computation complexity of the cycle left shift is for all -bit binary strings. Furthermore, this work indicates that block cipher systems with a 64-bit key are perhaps insecure. This paper presents clear evidence of the ability of DNA computing to perform intractable computation problems. [Copyright &y& Elsevier]

Abstract: The subclass of directed series–parallel graphs plays an important role in computer science. Whether a given graph is series–parallel is a well studied problem in algorithmic graph theory, for which fast sequential and parallel algorithms have been developed in a sequence of papers. Also methods are known to solve the reachability and the decomposition problem for series–parallel graphs time efficiently. However, no dedicated results have been obtained for the space complexity of these problems when restricted to series–parallel graphs – the topic of this paper. Deterministic algorithms are presented for the recognition, reachability, decomposition and the path counting problem for series–parallel graphs that use only logarithmic space. Since for arbitrary directed graphs reachability and path counting are believed not to be solvable in Logspace, the main contribution of this work are novel deterministic path finding routines that work correctly in series–parallel graphs, and a characterization of series–parallel graphs by forbidden subgraphs that can be tested space-efficiently. The space bounds are best possible, i.e. the decision problem is shown to be -complete with respect to -reductions. They have also implications for the parallel time complexity of these problems when restricted to series–parallel graphs. Finally, we sketch how these results can be generalized to extension of the series–parallel graph family: to graphs with multiple sources or multiple sinks and to the class of minimal vertex series–parallel graphs. [Copyright &y& Elsevier]

In this paper, we solve a long-standing problem that has been of interest since about 1988. The problem in general is to decide whether or not it is possible to partition the vertices of a graph into k distinct non-empty sets A0,A1,…,Ak−1, such that the vertices in Ai are independent and there is at least one edge between the pair of sets Ai and A(i+1) mod k, for all i=0,1,2,…,k−1, k>2, and there is no edge between any other pair of sets. Determining the computational complexity of this problem, for any value of even k⩾6, has been of interest since about 1988 to various people, including Pavol Hell and Jaroslav Nesetril. We show in this paper that the problem is NP-complete, for all even k⩾6. We study the problem as the compaction problem for an irreflexive k-cycle. [Copyright &y& Elsevier]

Motivated by the research in reconfigurable memory array structures, this paper studies the complexity and algorithms for the constrained minimum vertex cover problem on bipartite graphs (min-cvcb) defined as follows: given a bipartite graph G=(V,E) with vertex bipartition V=U∪L and two integers ku and kl, decide whether there is a minimum vertex cover in G with at most ku vertices in U and at most kl vertices in L. It is proved in this paper that the min-cvcb problem is NP-complete. This answers a question posed by Hasan and Liu. A parameterized algorithm is developed for the problem, in which classical results in matching theory and recently developed techniques in parameterized computation theory are nicely combined and extended. The algorithm runs in time O(1.26ku+kl+(ku+kl)|G|) and significantly improves previous algorithms for the problem. [Copyright &y& Elsevier]

This paper describes the fastest quantum algorithm at this moment for the quantum Fourier transform (QFT) over symmetric groups. We provide a new FFT (classical) algorithm over symmetric groups and then transform it to a quantum algorithm. The complexity of our QFT algorithm is O ( n 3 log ⁡ n ) , faster than the existing O ( n 4 log ⁡ n ) QFT algorithm. In addition, we show that the algorithm can be performed in O ( n 3 ) if the use of threshold gates is allowed. [ABSTRACT FROM AUTHOR]

In this paper, we propose algorithms for computing differential Chow forms for ordinary prime differential ideals which are given by characteristic sets. The algorithms are based on an optimal bound for the order of a prime differential ideal in terms of a characteristic set under an arbitrary ranking, which shows the Jacobi bound conjecture holds in this case. Apart from the order bound, we also give a degree bound for the differential Chow form. In addition, for a prime differential ideal given by a characteristic set under an orderly ranking, a much simpler algorithm is given to compute its differential Chow form. The computational complexity of the algorithms is single exponential in terms of the Jacobi number, the maximal degree of the differential polynomials in a characteristic set, and the number of variables. [ABSTRACT FROM AUTHOR]

This paper introduces stochastic weighted particle algorithms for the solution of multi-compartment population balance equations. In particular, it presents a class of fragmentation weight transfer functions which are constructed such that the number of computational particles stays constant during fragmentation events. The weight transfer functions are constructed based on systems of weighted computational particles and each of it leads to a stochastic particle algorithm for the numerical treatment of population balance equations. Besides fragmentation, the algorithms also consider physical processes such as coagulation and the exchange of mass with the surroundings. The numerical properties of the algorithms are compared to the direct simulation algorithm and an existing method for the fragmentation of weighted particles. It is found that the new algorithms show better numerical performance over the two existing methods especially for systems with significant amount of large particles and high fragmentation rates. [ABSTRACT FROM AUTHOR]

The linear complementarity problem (LCP) provides a unified approach to many problems such as linear programs, convex quadratic programs, and bimatrix games. The general LCP is known to be NP-hard, but there are some promising results that suggest the possibility that the LCP with a P-matrix (PLCP) may be polynomial-time solvable. However, no polynomial-time algorithm for the PLCP has been found yet and the computational complexity of the PLCP remains open. Simple principal pivoting (SPP) algorithms, also known as Bard-type algorithms, are candidates for polynomial-time algorithms for the PLCP. In 1978, Stickney and Watson interpreted SPP algorithms as a family of algorithms that seek the sink of unique-sink orientations of n -cubes. They performed the enumeration of the arising orientations of the 3-cube, hereafter called PLCP-orientations. In this paper, we present the enumeration of PLCP-orientations of the 4-cube. The enumeration is done via construction of oriented matroids generalizing P-matrices and realizability classification of oriented matroids. Some insights obtained in the computational experiments are presented as well. [ABSTRACT FROM AUTHOR]

This paper presents a computationally fast algorithm for estimating, both, the system and observation noise covariances of nonlinear dynamics, that can be used in an ensemble Kalman filtering framework. The new method is a modification of Belanger's recursive method, to avoid an expensive computational cost in inverting error covariance matrices of product of innovation processes of different lags when the number of observations becomes large. When we use only product of innovation processes up to one-lag, the computational cost is indeed comparable to a recently proposed method by Berry–Sauer's. However, our method is more flexible since it allows for using information from product of innovation processes of more than one-lag. Extensive numerical comparisons between the proposed method and both the original Belanger's and Berry–Sauer's schemes are shown in various examples, ranging from low-dimensional linear and nonlinear systems of SDEs and 40-dimensional stochastically forced Lorenz-96 model. Our numerical results suggest that the proposed scheme is as accurate as the original Belanger's scheme on low-dimensional problems and has a wider range of more accurate estimates compared to Berry–Sauer's method on L-96 example. [ABSTRACT FROM AUTHOR]

Counting objects is a fundamental but challenging problem. In this paper, we propose diffusion-based, geometry-free, and learning-free methodologies to count the number of objects in images. The main idea is to represent each object by a unique index value regardless of its intensity or size, and to simply count the number of index values. First, we place different vectors, refer to as seed vectors, uniformly throughout the mask image. The mask image has boundary information of the objects to be counted. Secondly, the seeds are diffused using an edge-weighted harmonic variational optimization model within each object. We propose an efficient algorithm based on an operator splitting approach and alternating direction minimization method, and theoretical analysis of this algorithm is given. An optimal solution of the model is obtained when the distributed seeds are completely diffused such that there is a unique intensity within each object, which we refer to as an index. For computational efficiency, we stop the diffusion process before a full convergence, and propose to cluster these diffused index values. We refer to this approach as Counting Objects by Diffused Index (CODI). We explore scalar and multi-dimensional seed vectors. For Scalar seeds, we use Gaussian fitting in histogram to count, while for vector seeds, we exploit a high-dimensional clustering method for the final step of counting via clustering. The proposed method is flexible even if the boundary of the object is not clear nor fully enclosed. We present counting results in various applications such as biological cells, agriculture, concert crowd, and transportation. Some comparisons with existing methods are presented. [ABSTRACT FROM AUTHOR]

The more advanced multi-view extension, MV-HEVC, effectively exploits visual similarities between multi-view videos and enables high compression efficiency. Each view in the multi-view sequence depends on the captured scene, the distance between cameras and recording angles. Increasing the distance between dependent viewpoints generates an inter-view disparity. This impacts the inter-view similarities, affects the disparity estimation and further increases the computational complexity of the MV-HEVC encoder. In this paper, an efficient earlier disparity estimation is proposed for low complexity MV-HEVC. This algorithm is based on reducing the complexity of disparity estimation by eliminating the inter-view offset. Moreover, the inter-view similarities are controlled by considering the reliability of each coding unit size in the search range. This reliability is estimated by reducing the number of searching points within a new limited window. For reliable motion estimation, we further proposed an earlier decision of coding units splitting in the dependent views according to those in the reference views. Experimental results show that the proposed algorithm can achieve an average encoding time saving of 20.37%–40,61% with marginal performance degradation. • Visual adjustment between views can be improved by eliminating inter-view offsets. • Eliminating inter-view offsets reduces search time in the disparity estimation. • The visual adjustment allows a trade-off between encoding time and video quality. • An earlier decision of coding units splitting for reliable motion estimation. [ABSTRACT FROM AUTHOR]

The main problem in information storage has previously been how large amounts of data can be stored. However, the technological development over the years has been able to give rather satisfactory answers to this problem. Recently, the focus has shifted towards determining how stored information can be efficiently retrieved. This problem is addressed in an article by E. Yaakobi and J. Bruck (2012), where information retrieval in associative memories is studied. In this paper, we focus on the case where the retrieved information unit is unambiguous. In particular, we present characterizations and study various extremal properties of such associative memories. Moreover, the algorithmic complexity of certain naturally rising problems is considered. [ABSTRACT FROM AUTHOR]

GPUs can provide powerful computing ability especially for data parallel applications, such as video/image processing applications. However, the complexity of GPU system makes the optimization of even a simple algorithm difficult. Different optimization methods on a GPU often lead to different performances. The matrix–vector multiplication routine for general dense matrices (GEMV) is an important kernel in video/image processing applications. We find that the implementations of GEMV in CUBLAS or MAGMA are not efficient, especially for small or fat matrix. In this paper, we propose a novel register blocking method to optimize GEMV on GPU architecture. This new method has three advantages. First, instead of using only one thread, we use a warp to compute an element of vector y so that the method can exploit the highly parallel GPU architecture. Second, the register blocking method is used to reduce the requirement of off-chip memory bandwidth. At last, the memory access order is elaborately arranged for the threads in one warp so that coalesced memory access is ensured. The proposed optimization methods for GEMV are comprehensively evaluated on different matrix sizes. The performance of the register blocking method with different block sizes is also evaluated in the experiment. Experiment results show that the new method can achieve very high speedup for small square matrices and fat matrices compared to CUBLAS or MAGMA, and can also achieve higher performance for large square matrices. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we present a simple and efficient computational algorithm for solving eigenvalue problems of high fractional-order differential equations with variable coefficients. The method of solution is based on utilizing the series solution to convert the governing fractional differential equation into a linear system of algebraic equations. Then, the eigenvalues can be calculated by finding the roots of the corresponding characteristic polynomial. Notice that this class of eigenvalue problems is very promising to the solution of linear fractional partial differential equations (FPDE). The numerical results demonstrate reliability and efficiency of the proposed algorithm. Based on our simulations some theoretical conjectures are reported. [Copyright &y& Elsevier]

• A cost-efficient LFE-ASQC algorithm with similar or even better control accuracy than the ANE and ASP algorithms is proposed. • The proposed algorithm reduces the computational complexity more than one order of magnitude compared to the ANE or ASP algorithms. • The proposed LSP modeling methods A and B have significantly higher modeling accuracy. • Simulated and experimental studies confirm the equalization capability of the proposed algorithm in both stationary and non-stationary cases. Current active noise equalization or active sound profiling algorithms with a parallel structure are typically used for sound quality improvement of multi-harmonic noise. The computational efficiency and system performance may, however, be severely degraded due to an increase in the length of estimated secondary path or the number of controlled frequencies. To alleviate this problem, a local secondary path estimation and filtered-error structure based active sound quality control (LFE-ASQC) algorithm is proposed in this paper. The algorithm utilizes a set of low-order local secondary path (LSP) models to perform filtering operations and uses the filtered pseudo-error signals instead of usual filtered reference signals to update control filter weights, thus it not only has good spectral reshaping capability but also requires notably low computational effort. Two new LSP modeling methods are also proposed. Moreover, a computational complexity analysis of the proposed LFE-ASQC algorithm is provided. Numerical simulations are conducted to evaluate the accuracy of the LSP modeling methods and the performance of the LFE-ASQC algorithm. In addition, the powerful sound quality of a real vehicle interior noise during acceleration is designed and realized. Experimental results demonstrate that the proposed algorithm achieves satisfactory active sound quality control for stationary and non-stationary multi-tonal noises. [ABSTRACT FROM AUTHOR]

• A novel NANC system based on FEWT and recursive third-order Chebyshev expansion is proposed. • The FEWT with order-statistic filtering is applied to stabilize non-stationary noise. • A RTOCN filter is presented for compensating the higher-order nonlinear distortions. • The channel-reduced diagonal structure is designed to optimize the RTOCN filter. • Experiment results indicate that proposed method outperforms conventional methods. Active noise control (ANC) has been widely studied to eliminate low-frequency noise. However, efficiently controlling higher-order distortions of nonlinear primary and secondary path is still a major challenge. To address this, this paper proposes a novel nonlinear ANC algorithm based on the fast empirical wavelet transform and recursive Chebyshev nonlinear filter. In this method, the fast empirical wavelet transform based on order-statistic filtering is first applied to decompose non-stationary noise into empirical mode functions (EMFs) which are more stationary and easy to control. Furthermore, a novel third-order Chebyshev nonlinear filter including the non-recursive subsection and recursive one is proposed to individually expand EMFs for compensating higher-order nonlinear distortions from primary path and secondary path. Moreover, the strategy of channel-reduced diagonal structure is designed to optimise the number of expanded channels, and the computational complexity of proposed algorithm is also investigated. Experimental results demonstrate that proposed method performs the highest noise reduction over the conventional algorithms but also has a fast convergence rate. [ABSTRACT FROM AUTHOR]

Abstract: In the present paper we study convergence of subgradient projection algorithms for solving convex feasibility problems in a Hilbert space. Our goal is to obtain an approximate solution of the problem in the presence of computational errors. We show that our subgradient projection algorithm generates a good approximate solution, if the sequence of computational errors is bounded from above by a constant. [Copyright &y& Elsevier]

Abstract: Constructing the bag-of-features model from Space–time interest points (STIPs) has been successfully utilized for human action recognition. However, how to eliminate a large number of irrelevant STIPs for representing a specific action in realistic scenarios as well as how to select discriminative codewords for effective bag-of-features model still need to be further investigated. In this paper, we propose to select more representative codewords based on our pruned interest points algorithm so as to reduce computational cost as well as improve recognition performance. By taking human perception into account, attention based saliency map is employed to choose salient interest points which fall into salient regions, since visual saliency can provide strong evidence for the location of acting subjects. After salient interest points are identified, each human action is represented with the bag-of-features model. In order to obtain more discriminative codewords, an unsupervised codeword selection algorithm is utilized. Finally, the Support Vector Machine (SVM) method is employed to perform human action recognition. Comprehensive experimental results on the widely used and challenging Hollywood-2 Human Action (HOHA-2) dataset and YouTube dataset demonstrate that our proposed method is computationally efficient while achieving improved performance in recognizing realistic human actions. [Copyright &y& Elsevier]

Abstract: Recent advances in technology have increased the availability of video data, creating a strong requirement for efficient systems to manage those materials. Making efficient use of video information requires that data to be accessed in a user-friendly way. Ideally, one would like to understand a video content, without having to watch it entirely. This has been the goal of a quickly evolving research area known as video summarization. In this paper, we present a novel approach for video summarization that works in the compressed domain and allows the progressive generation of a video summary. The proposed method relies on exploiting visual features extracted from the video stream and on using a simple and fast algorithm to summarize the video content. Experiments on a TRECVID 2007 dataset show that our approach presents high quality relative to the state-of-the-art solutions and in a computational time that makes it suitable for online usage. [Copyright &y& Elsevier]

Abstract: Reduction of high computational complexity of multi-view video coding (MVC) is necessary for realization in consumer electronics. Since mode decision is one of the key computational bottlenecks of multi-view video encoders, this paper proposes a coding statistics based fast mode decision algorithm. First of all, a rate–distortion cost based fast DIRECT mode decision algorithm early terminates the mode decision process if possible. Next, the candidates for Inter modes are reduced by taking the advantage of the correlation between an optimal mode and motion cost. The proper thresholds to reduce the candidates for the above two fast algorithms can be easily derived from exponential functions at run time. Finally, motion vector difference based motion characteristics is referred to further speed up the mode decision process of Inter modes. The experimental results show that the proposed scheme reduces up to 70.82% of encoding time with negligible degradation of RD performance. [Copyright &y& Elsevier]

A real number x is absolutely normal if, for every base b ≥ 2 , every two equally long strings of digits appear with equal asymptotic frequency in the base- b expansion of x. This paper presents an explicit algorithm that generates the binary expansion of an absolutely normal number x , with the n th bit of x appearing after n polylog (n) computation steps. This speed is achieved by simultaneously computing and diagonalizing against a martingale that incorporates Lempel-Ziv parsing algorithms in all bases. [ABSTRACT FROM AUTHOR]

Abstract: The computational complexity of the virtual FXLMS algorithm is higher than that of the conventional FXLMS algorithm. The additional complexity comes from computation of three secondary path transfer functions (as opposed to one) and a transfer function between the physical and the virtual microphones. The order of these transfer functions may be very high in practical situations where the acoustic damping is low. The high computational complexity of the virtual FXLMS algorithm imposes issues like high power consumption, making it difficult to implement the algorithm in battery operated ANC devices such as active headsets. In addition, the operating sampling frequency of the algorithm is limited and this in turn restricts its operation to relatively low frequency applications. In this paper, a new virtual FXLMS algorithm is derived by implementing all of the secondary path transfer functions in the frequency domain. The algorithm is simulated using measured transfer functions in a duct with low acoustic damping. Implementation schemes are proposed for the new frequency-domain virtual FXLMS algorithm, citing its advantages for use as an efficient real-time active noise control algorithm. [Copyright &y& Elsevier]

Abstract: In this paper we prove that the problem of deciding whether a given -uniform hypergraph , with minimum -wise vertex degree at least , contains a matching missing exactly vertices, that is, a set of disjoint edges of size , is NP-complete for , while for and we provide a polynomial time algorithm for the corresponding search problem. For the perfect case, , we show that the problem is NP-complete for and give a polynomial time algorithm for leaving a hardness gap in . Our reduction carries over to the more general case when, for , the minimum -wise codegree of a -uniform hypergraph is considered. In particular, for and we deduce that the problem of deciding the existence of a perfect matching in a given -uniform hypergraph , with minimum degree at least , is NP-complete for , complementing a fact proved recently in Han et al. (2009) [8] that the problem is trivial for . In addition, we use our reduction to show that a problem of deciding the existence of a perfect packing of the cycle into a 3-uniform hypergraph with minimum -wise vertex degree at least is NP-complete only for , which combined with a result from Kühn and Osthus (2006) [16] is, again, asymptotically tight. [Copyright &y& Elsevier]

Abstract: The multivariate resultant is a fundamental tool of computational algebraic geometry. It can in particular be used to decide whether a system of homogeneous equations in variables is satisfiable (the resultant is a polynomial in the system’s coefficients which vanishes if and only if the system is satisfiable). In this paper, we investigate the complexity of computing the multivariate resultant. First, we study the complexity of testing the multivariate resultant for zero. Our main result is that this problem is -hard under deterministic reductions in any characteristic, for systems of low-degree polynomials with coefficients in the ground field (rather than in an extension). In null characteristic, we observe that this problem is in the Arthur–Merlin class if the generalized Riemann hypothesis holds true, while the best known upper bound in positive characteristic remains . Second, we study the classical algorithms to compute the resultant. They usually rely on the computation of the determinant of an exponential-size matrix, known as Macaulay matrix. We show that this matrix belongs to a class of succinctly representable matrices, for which testing the determinant for zero is proved -complete. This means that improving Canny’s upper bound requires either to look at the fine structure of the Macaulay matrix to find an ad hoc algorithm for computing its determinant, or to use altogether different techniques. [Copyright &y& Elsevier]

Abstract: Many methods to compute the winding number of plane curves have been proposed, often with the aim of counting the number of roots of polynomials (or, more generally, zeros of analytic functions) inside some region by using the principle of argument. In this paper we propose another method, which are not based on numerical integration, but on discrete geometry. We give conditions that ensure its correct behavior, and a complexity bound based on the distance of the curve to singular cases. Besides, we provide a modification of the algorithm that detects the proximity to a singular case of the curve. If this proximity is such that the number of operations required grows over certain threshold, set by the user, the modified algorithm returns without winding number computation, but with information about the distance to singular case. When the method is applied to polynomials, this information refers to the localization of the roots placed near the curve. [Copyright &y& Elsevier]

Abstract: The Hilbert curve is a one-to-one mapping between multidimensional space and one-dimensional (1-D) space. Due to the advantage of preserving high correlation of multidimensional points, it receives much attention in many areas. Especially in image processing, Hilbert curve is studied actively as a scan technique (Hilbert scan). Currently there have been several Hilbert scan algorithms, but they usually have strict implementation conditions. For example, they use recursive functions to generate scans, which makes the algorithms complex and difficult to implement in real-time systems. Moreover the length of each side in a scanned region should be same and equal to the power of two, which limits the application of Hilbert scan greatly. In this paper, to remove the constraints and improve the Hilbert scan for a general application, an effective generalized three-dimensional (3-D) Hilbert scan algorithm is proposed. The proposed algorithm uses two simple look-up tables instead of recursive functions to generate a scan, which greatly reduces the computational complexity and saves storage memory. Furthermore, the experimental results show that the proposed generalized Hilbert scan can also take advantage of the high correlation between neighboring lattice points in an arbitrarily-sized cuboid region, and give competitive performance in comparison with some common scan techniques. [Copyright &y& Elsevier]

Abstract: This paper examines worst-case evaluation bounds for finding weak minimizers in unconstrained optimization. For the cubic regularization algorithm, Nesterov and Polyak (2006) and Cartis et al. (2010) show that at most iterations may have to be performed for finding an iterate which is within of satisfying second-order optimality conditions. We first show that this bound can be derived for a version of the algorithm, which only uses one-dimensional global optimization of the cubic model and that it is sharp. We next consider the standard trust-region method and show that a bound of the same type may also be derived for this method, and that it is also sharp in some cases. We conclude by showing that a comparison of the bounds on the worst-case behaviour of the cubic regularization and trust-region algorithms favours the first of these methods. [Copyright &y& Elsevier]